1

Fast Polarization for Processes with Memory

arXiv:1710.02849v2 [] 15 Oct 2017

Boaz Shuval, Ido Tal
Department of Electrical Engineering,
Technion, Haifa 32000, Israel.
Email: {bshuval@campus, idotal@ee}.technion.ac.il

sets: a ‘low entropy’ set and a ‘high entropy’ set. These sets
can be determined beforehand, and prescribe which portion of
UN
1 to reveal to the decoder or decompressor.
The rate of polarization is particularly important for the
analysis of polar codes. Their error-free performance at any
achievable rate is due to polarization happening sufficiently
fast. Fast polarization to the low entropy set for the memoryless setting was established in [1, Theorem 2], [2].
Remarkably, polar codes were extended to a plethora of
other memoryless scenarios, including non-binary channels [3],
Index Terms—Polar codes, rate of polarization, fast polariza- [4], source coding [5], [6], wiretap channels [7], [8], asymtion, channels with memory, Markov processes
metric channels and sources [9], and more. See the survey
paper [10, Section IV] for a large list of extensions and appliI. I NTRODUCTION
cations. Many of these applications are contingent upon fast
EMORY is prevalent in many communication scenar- polarization to the high-entropy set; for memoryless settings,
ios. Examples include finite state channels (FSCs) such this was established in [5].
The main tools used for polar code analysis in the memas intersymbol interference channels and correlated fading
channels, and coding for input-constrained systems. In this oryless case are the focus of Section III. In particular, we
research we show that polar codes can be used directly present Arıkan’s probabilistic approach, which is at the heart
for a large class of scenarios with memory. This enables of many polarization results. It is this approach that we extend
leveraging the attractive properties of polar codes — such as to settings with memory.
The study of polar codes for scenarios with memory began
low complexity encoding and decoding, explicit construction,
and sound theoretical basis — to scenarios with memory.
with [4, Chapter 5]. Şaşoğlu was able to show that polarization
A fundamental problem of information theory is estimating indeed occurs for a certain class of processes with memory.
N
= In the subsequent work [11], the authors were able to prove
a block XN
1 = X1 , X2 , . . . , XN from observations Y1
N
Y1 , Y2 , . . . , YN . In a channel-coding scenario, X1 may be polarization for a more general class of processes with memory.
the input to a channel and Y1N its output. In a source-coding One advancement made in that paper was regarding the
scenario, XN
rate of polarization under memory. The authors showed that
1 may be an information source to be compressed
and Y1N observations available to the decompressor. In either polarization to the low entropy set is fast even for processes
case, there is redundancy in XN
with memory. Fast polarization to the high entropy set was not
1 : added redundancy in channel
coding, or removed redundancy in source coding. A good addressed.
A practical decoding algorithm for polar codes for FSCs
channel code needs to add the least amount of redundancy
while still allowing for correct decoding, whereas a good was suggested in [12]. This algorithm is an extension of SC
source code eliminates as much redundancy as possible while decoding, taking into account the underlying state structure.
Its increase in complexity relative to the complexity of SC
still allowing reconstruction subject to a distortion criterion.
Polar codes [1] were first developed for binary-input, sym- decoding is polynomial with the number of states. Thus, it
metric, memoryless, channels. They provide a systematic is practical for a moderate number of states. The authors also
framework to handle this fundamental problem. They are showed [12, Theorem 3] that their elegant scheme from [9] can
block codes, whose encoding operation consists of an explicit be applied to models with memory. To this end, they required
N
the additional assumption of fast polarization both to the low
invertible transformation between XN
1 and U1 . A portion of
N
U1 is revealed to the decoder or decompressor. The decoder and high entropy sets.
This paper completes the picture. We show that for a large
employs successive cancellation (SC) decoding, recovering
class
of processes with memory, polarization is fast both to
UN
incrementally:
first
U
,
then
U
,
and
so
on.
Each
suc1
2
1
cessive decoding operation uses the observations Y1N and the the low entropy and high entropy sets. Fast polarization to the
outcome of the previous decoding operations as well as the low entropy set will follow from a specialization of [11]. Fast
polarization to the high entropy set, Theorem 13, is the main
revealed portion of UN
1 . The polarization phenomenon is that
for large enough N , the decoding operations polarize to two result of this paper. Consequently, polar codes can be used in

Abstract—Fast polarization is crucial for the performance
guarantees of polar codes. In the memoryless setting, the rate
of polarization is known to be exponential in the square root
of the block length. A complete characterization of the rate
of polarization for models with memory has been missing.
We consider polar codes for processes with memory that are
characterized by an underlying ergodic finite state Markov chain.
We show that the rate of polarization for these processes is the
same as in the memoryless setting, both to the high and to the
low entropy sets. Thus, polar codes achieve the Markov capacity
in many infromation-theoretic applications.

M

2

settings with memory with vanishing error probability.
Specifically, we consider stationary processes whose memory can be encompassed by an underlying finite-state ergodic1
Markov chain. This Markov chain governs the joint distribuN
tion of XN
1 and Y1 , and is assumed to be hidden. The model
is described in detail in Section IV. This family of processes
includes, as special cases, finite state Markov channels [13,
Chapter 4.6] with an ergodic state sequence, discrete ergodic
sources with finite memory, and many input-constrained systems (e.g., (d, k)-runlength limited (RLL) constraint [14], with
and without noise). In particular, polar codes may be used to
achieve the Markov capacity [15], [16] in such settings (see
also [17]).
The tools we develop for this family of processes with
memory are the subject of Section V. Our tools mirror those
used in the memoryless construction. Thus, we expect that this
addition to the ‘polar toolbox’ will enable natural adaptation
of many polar coding results to settings with memory.

Consider a pair of random variables (U, Q) with joint distribution PU,Q (u, q) = PQ (q)PU|Q (u|q). The random variable
U is binary2 and Q is some observation dependent on U that
takes values in a finite alphabet Q.
Definition 1 (Probability of error). The probability of error
Pe (U|Q) of optimally estimating U from the observation Q, in
the sense of minimizing the probability of error, is given by
X
Pe (U|Q) =
min{PU,Q (0, q), PU,Q (1, q)}
q

=

X

Definition 2 (Bhattacharyya parameter). The Bhattacharyya
parameter of U given Q, Z(U|Q), is defined as
Xq
Z(U|Q) = 2
PU,Q (0, q)PU,Q (1, q)
q

=2
II. N OTATION

PQ (q) min{PU|Q (0|q), PU|Q (1|q)}.

q

X
q

q
PQ (q) PU|Q (0|q)PU|Q (1|q).

(1)

A set of elements is denoted as a list in braces, e.g., Definition 3 (Total Variation Distance). The total variation
{1, 2, . . . , L}. The number of elements in a set A is denoted distance of U given Q, K(U|Q), is defined as
X
by |A|. The disjoint union of two sets A0 , A1 is denoted by
K(U|Q) =
|PU,Q (0, q) − PU,Q (1, q)|
A0 ∪· A1 . To use this notation, A0 and A1 must indeed be
q
X
(2)
disjoint. Open and closed intervals are denoted by (a, b) and
=
PQ (q) PU|Q (0|q) − PU|Q (1|q) .
[a, b], respectively. 

q
We denote yjk = yj yj+1 · · · yk for j < k. For an
The parameters defined above all required that U be binary.
arbitrary set of indices F we denote yF = {yj , j ∈ F }.
A
final
parameter we will use is the conditional entropy. Unlike
In a summation involving multiple variables, if only one
the
other
parameters, the conditional entropy is also defined
variable is being summed, we P
will make this explicit by
when
U
takes
values in an arbitrary finite alphabet U, not
underlining it. For example, in
a6=b f (a, b) we sum over
necessarily
binary.
the values P
of a that are different
P P than b, and b is fixed. In
particular, a6=b f (a, b) = b a6=b f (a, b).
Definition 4 (Conditional Entropy). The conditional entropy
For a sequence of binary
B1 , B2 , . . . , Bn we of U given Q, H(U|Q), is defined as
Pn numbers
denote (B1 B2 · · · Bn )2 = j=1 Bj 2n−j . I.e., the rightmost
XX
PU,Q (u, q)
digit Bn is the least significant bit. Addition of binary numbers
H(U|Q) = −
PU,Q (u, q) log2 P
in assumed to be an XOR operation (i.e., modulo-2 addition).
u PU,Q (u, q)
q
u
(3)
X
X
The probability of an event A is denoted by P(A). Ran=−
PQ (q)
PU|Q (u|q) log2 PU|Q (u|q).
dom variables are denoted using a sans-serif font, e.g., X
q
u
and their realizations using lower-case letters, e.g., x. The
It is easily seen that all four parameters take values in [0, 1]
distribution of random variable X is denoted by PX = PX (x).
when
U is binary. They are all related, as established in the
When marginalizing
distributions,
we will sometimes use the
P
P
following
lemma.
shorthand x PX,Y ≡ x PX,Y (x, y); the summation variable
will denote which random variable is being marginalized. The Lemma 1. The total variation distance, probability of error,
expectation of X is denoted by E [X].
conditional entropy, and Bhattacharyya parameter are related
by
III. T HE P OLAR T OOLBOX
K(U|Q) = 1 − 2Pe (U|Q),
(4a)
p
p
A. Various Parameters of Distributions
(4b)
K(U|Q) ≥ 1 − H(U|Q) ≥ 1 − Z(U|Q),
In this section we introduce several parameters that may be
p
p
2
2
K(U|Q) ≤ 1 − Z(U|Q) ≤ 1 − H(U|Q) .
(4c)
computed from the joint distribution of two random variables:
probability of error, Bhattacharyya parameter, conditional enThe proof of Lemma 1 is relegated to Appendix A. We
tropy, and total variation distance. These parameters are useful note that the left-most inequality of (4c) was also shown in [1,
for the analysis of polar codes. These parameters are not Appendix A]; our proof is more general. Due to (4a), we shall
random variables; they are deterministic quantities computed concentrate in the sequel on K(U|Q) rather than Pe (U|Q).
from the joint distribution.
1 I.e.,

aperiodic and irreducible.

2 This assumption is for the sake of simplicity. See Remark 2 at the end of
this subsection for a discussion of the implications of non-binary U.

3

In [6], Arıkan used the inequality

B. Polarization
We review some basics of polarization in this section. The
Z(U|Q)2 ≤ H(U|Q) ≤ log2 (1 + Z(U|Q))
(5)
concepts introduced here will be useful in the sequel.
1) General Definitions: Consider a strictly stationary proto show that if the Bhattacharyya parameter approaches 0 or
cess
(Xj , Yj ), j = 1, 2, . . . with a known joint distribution.
1 then the conditional entropy approaches 0 or 1 as well
We
assume
that Xj are binary and Yj ∈ Y, where Y is a
and vice versa. An alternative proof of this can be had by
finite
alphabet.
The random variables Xj are to be estimated
combining (4b) and (4c). This yields
from the observations Yj . In a channel coding setting, Xj is
p
Z(U|Q)2 ≤ H(U|Q) ≤ Z(U|Q) ≤ H(U|Q),
the input to a channel and Yj its output. In a source coding
setting, Xj is a data sequence to be compressed and Yj is side
which indeed implies that the Bhattacharyya parameter and
information available to the decompressor.
conditional entropy approach 0 and 1 in tandem. This inequalWe denote Arıkan’s polarization matrix by GN = BN G⊗n
2 ,
ity is tighter than (5); however, as discussed in Appendix B,
where N
= 2n , BN is the N × N bit-reversal matrix, and

an advantage of inequality (5) is that it has a natural extension
1 0
G2 =
. Recall that G−1
to the case where U is non-binary.
N = GN . Following [11], we
1 1
An additional consequence of Lemma 1 is that (a) if define
Z(U|Q) → 0 or H(U|Q) → 0 then K(U|Q) → 1 and (b)
N
UN
(7a)
1 = X1 GN ,
if Z(U|Q) → 1 or H(U|Q) → 1 then K(U|Q) → 0.
N
2N
V1 = XN +1 GN ,
(7b)
Remark 1. A weaker version of (4b) is
N
Qi = (Ui−1
(7c)
1 , Y1 ),
K(U|Q) ≥ 1 − H(U|Q) ≥ 1 − Z(U|Q).
i−1
2N
Ri = (V1 , YN +1 ),
(7d)
√
We obtain it from (4b) by noting that 1 − x ≥ 1 − x for where i = 1, 2, . . . , N .
x ∈ [0, 1] and using the inequality Z(U|Q) ≥ H(U|Q) (see
The operation (7a) is called “encoding.” A certain subset
Lemma 15 in Appendix A). By combining this weaker inequal- of indices F ⊂ {1, 2, . . . , N } is preselected according to
ity with (4a) we obtain the well-known bound, Pe (U|Q) ≤ some rule; the set F dictates the performance of the code.
Z(U|Q)/2.
After encoding, UF is revealed to the decoder. The decoding
The definitions above naturally extend to the case where operation is iterative. For i = 1, 2, . . ., the decoder estimates
instead of Q there are multiple random variables related to U. Ui from Qi ; it uses its previous estimates of Ui−1
to form Qi .
1
For example, consider a triplet of random variables (U, Q, S) Whenever it encounters an index in F , it returns as its estimate
with joint distribution PU,Q,S (u, q, s) such that U is binary and the relevant value from UF . After estimating UN
1 , the decoder
Q, S take values in finite alphabets Q, S. We call S the ‘state’. recovers XN
via
(7a).
1
Then,
The polarization phenomenon is that for large enough n,
X
the fraction of indices with moderate conditional entropy,
K(U|Q, S) =
|PU,Q,S (0, q, s) − PU,Q,S (1, q, s)|;
|{i : H(Ui |Qi ) ∈ (ǫ, 1 − ǫ)}|/N , becomes negligibly small
q,s
for any ǫ > 0. One approach [1], [6] to derive such results
the remaining parameters are similarly extended. We say that is probabilistic. Rather than counting the number of indices
K(U|Q, S) is a state-informed (SI) version of K(U|Q).
with moderate conditional entropy, a sequence of random
How do the SI parameters compare to their non-SI counter- variables Hn , n = 1, 2, . . . is defined. The random variable
parts? For the entropy, the answer lies in [18, Theorem 2.6.5], Hn assumes the value H(Ui |Qi ), with i selected uniformly
the well known property that conditioning reduces entropy. In from {1, 2, . . . , N }. Thus, the probability that Hn lies in a
the following lemma, proved in Appendix A, we consider the certain range equals the fraction of indices whose conditional
other parameters as well.
entropies lie in this range.
The recursive nature of the polarization transform is at the
Lemma 2. Let (U, Q, S) be a triplet of random variables with
heart of the probabilistic approach. Concretely, let B1 , B2 , . . .
joint distribution PU,Q,S (u, q, s). Then
be a sequence of independent and identically distributed
(i.i.d.)
Bernoulli-1/2 random variables. We set i − 1 =
K(U|Q) ≤ K(U|Q, S),
(6a)
(B1 B2 · · · Bn )2 ; indeed, i assumes any value in {1, 2, . . . , N }
Z(U|Q) ≥ Z(U|Q, S),
(6b)
with equal probability. Define the random variables
H(U|Q) ≥ H(U|Q, S).
(6c)
N
Kn = K(Ui |Ui−1
1 , Y1 ) = K(Ui |Qi ),
N
Remark 2. In this paper, we assume for simplicity that U is
Zn = Z(Ui |Ui−1
(8)
1 , Y1 ) = Z(Ui |Qi ),
binary. It is possible to extend our results to the non-binary
i−1
N
Hn = H(Ui |U1 , Y1 ) = H(Ui |Qi )
case. To this end, a suitable extension of the distribution
parameters is required. The key properties that need to be whenever (i − 1) = (B1 B2 · · · Bn )2 . That is, they denote
preserved are (a) that they be bounded between 0 and 1; (b) the relevant distribution parameters for a uniformly chosen
that they approach their extreme values in tandem; and (c) that index after n polarization steps. We call Kn , Zn , and Hn , n =
they satisfy Lemma 2. In Appendix B we suggest a suitable 1, 2, . . . the total variation distance process, the Bhattacharyya
extension that satisfies these requirements.
process, and the conditional entropy process, respectively.

4

By the properties of GN [1, Section VII],
(
K(Ui + Vi |Qi , Ri )
if Bn+1 = 0
Kn+1 =
K(Vi |Ui + Vi , Qi , Ri ) if Bn+1 = 1.

Ti

+

Ui · · ·

Qi

···

Ri

(9)
Vi

Vi

Similar relationships hold for Hn+1 and Zn+1 . We shall use
+
the mnemonics K−
Fig. 1. Illustration of a polarization transform. Random variables (Ui , Qi )
n and Kn to denote K(Ui + Vi |Qi , Ri ) and
K(Vi |Ui + Vi , Qi , Ri ), respectively. I.e., Kn+1 assumes the have joint distribution PUi ,Qi and random variables (Vi , Ri ) have joint
distribution PVi ,Ri .
+
value K−
n when Bn+1 = 0 and the value Kn when Bn+1 = 1.
We shall use similar mnemonics for Hn and Zn .
The probability law of (Ui , Vi , Qi , Ri ) can be obtained from
Remark 3. It was shown in [19] that Lemma 3 can be
2N
the probability law of (X2N
1 , Y1 ) using (7). Moreover, for
strengthened. Namely, equation (12) can be replaced with the
nβ
fixed i, there exists a function f , which depends solely on i,
stronger assertion limn0 →∞ P(An ≤ 2−2 for all n ≥ n0 ) =
such that
P(A∞ = 0). Hence, any result based on Lemma 3, such as
N
(Ui , Qi ) = f (XN
Theorems 7 and 13, can be strengthened similarly.
1 , Y1 ),
(10)
2N
(Vi , Ri ) = f (X2N
2) The Memoryless Case: TheQmemoryless case is charN +1 , YN +1 ).
N
N
N
acterized
by PXN
N (x
1 , y1 ) =
j=1 PX,Y (xj , yj ). Arıkan
This can be seen by comparing (7a) and (7c) with (7b) and
1 ,Y1
showed
in
[1]
that
in
the
memoryless
case the process Hn
(7d). Due to stationarity, PUi ,Qi = PVi ,Ri .
polarizes.
Consequently,
when
n
is
large
enough, for all but a
Denote Ti = Ui + Vi , as in Figure 1. The mapping
i−1
N
negligible
fraction
of
indices
i,
H(U
|U
i 1 , Y1 ) is either very
(Ui , Vi ) 7→ (Ti , Vi ) is one-to-one and onto. Hence,
close to 0 or very close to 1.
PTi ,Vi ,Qi ,Ri (t, v, q, r) = PUi ,Vi ,Qi ,Ri (t + v, v, q, r). (11)
To achieve this, Arıkan had shown that the sequence Hn ,
n = 1, 2, . . . is a bounded martingale sequence and thus
We now formally define polarization and fast polarization.
converges almost surely to some random variable H∞ . By
Definition 5. Let An , n = 1, 2, . . . be a sequence of random showing that H∞ can only assume the values 0 and 1,
variables that take values in [0, 1].
polarization is obtained.
The Bhattacharyya process, in the memoryless case, is a
1) The sequence An polarizes if it converges almost surely
bounded
supermartingale that converges almost surely to a
to a {0, 1}-random variable A∞ as n → ∞. We will
{0,
1}-random
variable Z∞ . The process Zn satisfies Lemma 3
sometimes abbreviate this by saying that “An polarizes
with
E
=
1/2
by
virtue of [1, Proposition 5], by which
to A∞ .”
(
2) The sequence An polarizes fast to 0 with β > 0 if it
≤ 2Zn if Bn+1 = 0
polarizes and
Zn+1 =


Z2n
if Bn+1 = 1.
nβ
= P (A∞ = 0) .
lim P An < 2−2
n→∞
Thus, the Bhattacharyya process polarizes fast to 0 with any
3) The sequence An polarizes fast to 1 with β > 0 if it β < 1/2.
polarizes and
Fast polarization of the Bhattacharyya parameter is impor

tant for the performance analysis of polar codes. In particular,
−2nβ
lim P An > 1 − 2
= P (A∞ = 1) .
n→∞
this was instrumental in Arıkan’s proof that polar codes are
When the precise value of β is either obvious from the context capacity-achieving for binary-input, memoryless, symmetric,
or not needed, we will write that An polarizes fast to, say, 0, channels [1]. Arıkan had upper-bounded the probability of error of polar codes by the union-Bhattacharyya bound. Thanks
without mentioning the value of β.
to fast polarization of the Bhattacharyya process to 0, the
The following lemma, first obtained by Arıkan and Telatar bound converges to 0.
in [2] and later adapted to the general case by Şaşoğlu in [4],
The additional requirement of fast polarization of Zn to 1 is
is an important tool for establishing fast polarization for a important for many applications of polar codes. For example,
sequence of random variables.
it is integral to source coding applications [5] and to channel
Lemma 3. [2],[4, Lemma 4.2] Let Bn , n = 1, 2, . . . be an coding without symmetry assumptions [9]. In [5, Theorem
i.i.d. Bernoulli-1/2 process and An , n = 1, 2, . . . be a [0, 1]- 16], this fast polarization was established by showing that the
2
valued process that polarizes to a {0, 1}-random variable A∞ . process Z̃n = 1−Zn polarizes fast to 0 with β < 1/2. Another
Assume that there exist k ≥ 1 and d0 , d1 > 0 such that for way to see this, which we pursue in the sequel, is via the total
variation process Kn .
i = 0, 1,
A consequence of (4b) is that if Kn polarizes fast to 0 then
An+1 ≤ kAdni if Bn+1 = i.
Zn must polarize fast to 1. The total variation process Kn can
Then, for any 0 < β < E = (log2 d0 + log2 d1 )/2, we have
be shown to polarize (we show this in Corollary 11 for a more


general setting). Fast polarization of Kn to 0 is obtained from
−2nβ
= P (A∞ = 0) .
(12)
lim P An < 2
Lemma 3 and the following proposition.
n→∞

5

Proposition 4. Assume that (Xj , Yj ), j ∈ Z is a memoryless
process, where Xj is binary and Yj ∈ Y. Then,
Kn+1 =

(

Thus,
Kn+1 =

X

t,q,r

K2n
≤ 2Kn

if Bn+1 = 0
if Bn+1 = 1.

(13)

=

X

t,q,r

In the sequel, we shall generalize this proposition to a nonmemoryless case. The proof for the memoryless case serves
as preparation for the more general case, which uses similar
techniques. For an extension of Proposition 4 to the case where
Xj is non-binary, see Appendix B.
Proof: Fix B1 , . . . , Bn and let i − 1 = (B1 B2 · · · Bn )2 .
This also fixes the value of Kn . Using (10) and the memoryless
assumption, we denote P ≡ PUi ,Qi = PVi ,Ri , by which

|PTi ,Vi ,Qi ,Ri (t, 0, q, r) − PTi ,Vi ,Qi ,Ri (t, 1, q, r)|
|P (t, q)P (0, r) − P (t + 1, q)P (1, r)|

1X
P (q) |P (0, r) − P (1, r)|
2 t,q,r
1X
P (r) |P (t, q) − P (t + 1, q)|
+
2 t,q,r
1X
=
|P (0, r) − P (1, r)|
2 t,r
1X
+
|P (t, q) − P (t + 1, q)|
2 t,q

≤

= 2Kn ,

PUi ,Vi ,Qi ,Ri (u, v, q, r) = P (u, q)P (v, r).

where the inequality is due to a combination of (15) with the
triangle inequality.
Note that Kn = K(Ui |Qi ) = K(Vi |Ri ).
We have shown that Kn+1 = K2n if Bn+1 = 0 and Kn+1 ≤
Set Ti = Ui + Vi ; by (11),
2Kn if Bn+1 = 1, completing the proof.
Remark 4. Several other authors have independently looked
PTi ,Vi ,Qi ,Ri (t, v, q, r) = P (t + v, q)P (v, r),
at the polarization of the total variation distance. For example, [20, Proposition 5.1] derives relations similar to (13);
P
and PTi ,Qi ,Ri (t, q, r) = 1v=0 PTi ,Vi ,Qi ,Ri (t, v, q, r). A single- the top equality of (13) is also shown in [21, Equation 12].
Those results were derived for binary-input, memoryless, and
step polarization from Kn to Kn+1 , (9), becomes
symmetric channels. Our Proposition 4, on the other hand,
(
does not require symmetry. We note in passing that it is
K(Ti |Q, Ri )
if Bn+1 = 0
Kn+1 =
(14) also easily extended to a non-stationary case (similar to [22,
K(Vi |Ti , Qi , Ri ) if Bn+1 = 1.
Appendix 2.A] for the Bhattacharyya process), but that is
outside the scope of this paper.
Assume first that Bn+1 = 0. Then
IV. F INITE -S TATE A PERIODIC I RREDUCIBLE M ARKOV
X
P ROCESSES
Kn+1 =
|PTi ,Qi ,Ri (0, q, r) − PTi ,Qi ,Ri (1, q, r)|
In
this
section
we
introduce
a class of processes with memq,r
ory
that
we
call
Finite-state
Apreiodic
Irrecducible Markov
1
X X
processes
(FAIM
processes).
This
is
the
class
of processes for
=
P (v, r)(P (v, q) − P (v + 1, q))
which
we
establish
polarization
and
fast
polarization.
q,r v=0
These processes are described using an underlying state


X 
=
P (0, q) − P (1, q) P (0, r) − P (1, r)
sequence. Often, however, the state sequence is hidden. The
q,r
polarization results we obtain apply to processes with a hidden
(a) X
state sequence.
=
|P (0, q) − P (1, q)| · |P (0, r) − P (1, r)|
q,r

=

=

X

q
K2n ,

|P (0, q) − P (1, q)| ·

X
r

|P (0, r) − P (1, r)|

where (a) is because |ab| = |a| · |b| for any two numbers
a, b. Next, assume that Bn+1 = 1. Observe that for any four
numbers a, b, c, d,
(ab − cd) =

(a + c)(b − d) + (b + d)(a − c)
.
2

(15)

With a slight abuse of notation, we denote P (q) = PQi (q) =
P (0, q) + P (1, q). Then, P (r) = PRi (r) = P (0, r) + P (1, r).

A. Definition
Let (Xj , Yj , Sj ), j ∈ Z be a strictly stationary process,
where Xj is binary, Yj ∈ Y, and Sj ∈ S. The alphabets Y
and S are finite; in particular, S = {1, 2, . . . , |S|}. We call
Sj , j ∈ Z the state sequence; it governs the distribution of
sequences Xj and Yj , j ∈ Z.
We may think of Xj as a state-dependent input to a statedependent channel with output Yj . Alternatively, Xj may be
some state-dependent source to be compressed, and Yj an
observation that the decoder may use as a decompression aid.
The state sequence encompasses the memory of the process.
The process is described by the conditional probability
PXj ,Yj ,Sj |Sj−1 , which, by the stationarity assumption, is independent of j. We assume a Markov property: conditioned

6

on Sj−1 , the random variables Xk , Yk , Sk are independent of
Xl , Yl , Sl−1 for any l < j ≤ k. Thus, for any N > M > 0,
N
PXN
1 ,Y1 ,SN |S0
X
=
PXM
M
N
N
1 ,Y1 ,SM ,XM +1 ,YM +1 ,SN |S0

=

X

b
X
b

Typically, the state sequence is not observed. The joint
N
distribution of (XN
1 , Y1 ) is given by
X
N
N
N
PXN
N (x
,
y
)
=
(xN
PXN
N
,Y
1
1
1 , y1 , b|a)π0 (a),
1
1
1 ,Y1 ,SN |S0
b,a

b

=

B. Blocks of a FAIM Process

(16)
N
M
M
M
PXN
· PXM
1 ,Y1 ,SM |S0
M +1 ,YM +1 ,SN |SM ,X1 ,Y1 ,S0
,
· PXM
M
PXN
N
1 ,Y1 ,SM |S0
M +1 ,YM +1 ,SN |SM

where b in the sum represents the value of the middle state
SM .
The state sequence is a finite-state homogeneous Markov
chain. We denote its marginal distribution by π, and use the
shorthand

where π0 is the stationary distribution of the initial state.
Definition 6 (Block). Let (Xj , Yj , Sj ), j ∈ Z be a FAIM
M
process and assume M > L. We call (XM
L+1 , YL+1 ) a block
of the FAIM process. Its length is M − L.
State SL is called the initial state of the block. State SM is
called the final state of the block.
We emphasize that the initial state of the block
M
(XM
L+1 , YL+1 ) is SL and not SL+1 .
The following lemma holds for any two non-overlapping
blocks of a FAIM process. It establishes that FAIM processes
are a special case of the family of processes considered in [11].

πN (a) = PSN (a)
πN |M (b|a) = PSN |SM (b|a)
πN,M (b, a) = PSN ,SM (b, a),

(17)

Lemma 5. Assume that (Xj , Yj , Sj ), j ∈ Z is a FAIM process.
Then, there exists a non-increasing sequence ψ(N ), ψ(N ) → 1
as N → ∞, such that for any N > M ≥ L ≥ 1,

where N > M . Note that πN (a) = π0 (a) and πN |M (b|a) =
PXL1 ,Y1L ,XN
N
≤ ψ(M − L)·PXL1 ,Y1L ·PXN
N
, (18)
M +1 ,YM +1
M +1 ,YM +1
πN −M|0 (b|a).
A finite-state homogeneous Markov chain is aperiodic and and ψ(0) < ∞.
irreducible (ergodic) if and only if there is some N0 > 0 such
We relegate the proof to Appedix C. We remark, however,
that for any N ≥ N0 , πN |0 (b|a) > 0 for any a, b ∈ S. It
that

can be shown that it has a unique stationary distribution π0
πN |0 (b|a)


if N > 0
and π0 (a) > 0 for any a ∈ S. Moreover, πN |0 (b|a) → π0 (b)
max
a,b
π0 (b)
(19)
ψ(N ) =
exponentially fast as N → ∞ for any a, b ∈ S. See, e.g., [23,


Section 8]
max 1
if N = 0.
a π0 (a)
The process (Xj , Yj , Sj ), j ∈ Z is called a finite-state aperiodic irreducible Markov process if the underlying Markov I.e., ψ(·) is completely determined by the distribution of the
process Sj , j ∈ Z is homogenous, finite-state, strictly station- underlying state sequence. Indeed, ψ(N ) → 1 as N → ∞.
ary, aperiodic, and irreducible.3 In the sequel, we assume that
A process satisfying (18) with ψ(N ) → 1 as N → ∞
(Xj , Yj , Sj ), j ∈ Z is a FAIM process.
is called ψ-mixing.4 The function ψ(·) is called the mixing
At this point, the reader may wonder why we have imposed coefficient. The operational meaning of (18) is that as L and
L
L
aperiodicity and irreducibility. In [11, Theorem 3], it was M becomes more separated in time, the blocks (X1 , Y1 ) and
5
N
N
demonstrated that periodic processes may not polarize. We (XM+1 , YM+1 ) become almost independent.
Two adjacent blocks of the process share a state. The final
assume aperiodicity to ensure that polarization indeed happens.
As for irreducibility, note that since the number of states is state of the first block is the initial state of the second block.
finite, the state sequence Sj , j ∈ Z must reach an irreducible Given the shared state, the two blocks are independent. We
sink after sufficient time. Hence, the irreducibility assumption capture this in the following lemma.
is equivalent to assuming that the state sequence begins in Lemma 6. For any N > M ≥ 1,
some irreducible sink.
M
N
N
M
N
PXM
= PXM
PXN
,
Our model applies to many problems in information theory
1 ,Y1 ,XM +1 ,YM +1 |SM
1 ,Y1 |SM
M +1 ,YM +1 |SM
that can be described using states. For example, compression
of finite memory sources and coding for input constrained
(20a)
channels. Additionally, our model may be applied to finite- P M M N
.
PXN
N
= PXM
M
N
X1 ,Y1 ,XM +1 ,YM
1 ,Y1 |S0 ,SM
M +1 ,YM +1 |SM ,SN
+1 |S0 ,SM ,SN
state channels; in this case, the FAIM state sequence describes
(20b)
both the channel state and input state. That is, FAIM processes
4 In some literature, e.g. [24], the term used is ψ ∗ -mixing.
enable us to model non-i.i.d. input sequences. In particular,
5 Let A and B be two σ-algebras. If for any two events A ∈ A and B ∈ B
they can be used to achieve the Markov capacity [15], [16] of we have P(A∩B) ≤ P(A)P(B) then P(A∩B) = P(A)P(B). Assume to the
finite-state channels.
contrary that for some events A0 , B0 , P(A0 ∩ B0 ) < P(A0 )P(B0 ). Denote
3 We

remark that the process (Xj , Yj ), j ∈ Z is not necessarily Markov.

the complement of A0 by Ā0 . Since Ā0 ∈ A, we obtain a contradiction:
P(B0 ) = P(Ā0 ∩ B0 ) + P(A0 ∩ B0 ) < P(A0 )P(B0 ) + P(Ā0 )P(B0 ) =
P(B0 ).

7

SN

S0

2N
(Vi , Ri ) = f (X2N
N +1 , YN +1 )

N
(Ui , Qi ) = f (XN
1 , Y1 )

b

a

S2N

c

Fig. 2. Two adjacent length-N blocks of a FAIM process. When i − 1 =
N
(B1 B2 · · · Bn )2 , there is a function f such that (Ui , Qi ) = f (XN
1 , Y1 ) and
2N ). The initial state of the first block, S , assumes
,
Y
(Vi , Ri ) = f (X2N
0
N+1
N+1
value a ∈ S. The final state of the first block, SN , which is also the initial
state of the second block, assumes value b ∈ S. The final state of the second
block, S2N , assumes value c ∈ S.

N
Definition 7. Let (U, Q) = f (XN
1 , Y1 ) with U binary. The
boundary state-informed (BSI) total variation distance, Bhattacharyya parameter, and conditional entropy are respectively
defined as
X
K(U|Q, SN , S0 ) =
πN,0 (b, a)Kba (U|Q),
a,b

Z(U|Q, SN , S0 ) =

X

πN,0 (b, a)Zba (U|Q),

a,b

H(U|Q, SN , S0 ) =

X

πN,0 (b, a)Hab (U|Q).

a,b

BSI parameters are defined for blocks of the process; they
This is a direct consequence of the Markov property. A depend on the initial and final states of the block. Invoking (6)
we relate the distribution parameters to their BSI counterparts,
formal derivation can be found in Appendix C.
A notational convention concludes this section. Our analysis
K(U|Q) ≤ K(U|Q, SN , S0 ),
involves the use of some states of blocks of a FAIM process.
Z(U|Q) ≥ Z(U|Q, SN , S0 ),
(23)
We will use ascending letters to denote values of ordered states.
H(U|Q) ≥ H(U|Q, SN , S0 ).
That is, a state with value a occurs before a state with value b,
which, in turn, occurs before a state with value c. In Figure 2
V. FAST P OLARIZATION FOR FAIM P ROCESSES
we illustrate a particular case that will be used in the sequel.
A block of length 2N comprises two adjacent blocks of length
This section contains our main result: fast polarization
N . State S0 , the initial state of the first block, may take value for FAIM processes. First, we show that they polarize by
a, state SN , at the end of the first block and the beginning leveraging the results of [11]. Then, we show fast polarization
of the second block, may take value b, and state S2N , at the of the Bhattacharyya parameter and of the total variation
end of the second block, may take value c. We emphasize that distance to zero.
a, b, c ∈ S are not random variables, but values of the relevant
The notation of Section III-B holds, without change, for
states.
N
FAIM processes. That is, UN
1 , V1 , Qi , Ri , i = 1, . . . , N are
defined using (7). The random variables B1 , . . . , Bn denote
C. Boundary State-Informed Parameters for FAIM Processes random traversal through the polarization tree; they constitute
the binary expansion of i − 1, through which the random variN
Let (XN
1 , Y1 ) be a block of a FAIM process with state
ables Kn = K(Ui |Qi ), Hn = H(Ui |Qi ), and Zn = Z(Ui |Qi )
sequence Sj . Let f (·, ·) be some function independent of the are defined. Random variable Kn+1 is related to Kn by (9).
+
state sequence such that
I.e., Kn+1 = K−
n if Bn+1 = 0 and Kn+1 = Kn if Bn+1 = 1.
Similar relationships hold for Hn and Zn .
N
(U, Q) = f (XN
1 , Y1 )
Let K̂n , Ĥn , and Ẑn denote the boundary state-informed
versions
of Kn , Zn , and Hn , respectively. That is,
and U is binary. We denote
PU,Q,SN |S0 (u, q, b|a)
.
πN |0 (b|a)
(21)
I.e., this is the distribution of U and Q, functions of a block
of length N , conditioned on the initial state being S0 = a and
the final state being SN = b. We further define
Pab (u, q) , PU,Q|SN ,S0 (u, q|b, a) =

(22)
Pab (q) = Pab (0, q) + Pab (1, q).
P
I.e., Pab (q) = PQ|SN ,S0 (q|b, a), and q Pab (q) = 1.
We denote the results of replacing PU,Q (u, q) with Pab (u, q)
in equations (1) to (3) by Zba (U|Q), Kba (U|Q), and Hab (U|Q),
respectively. For example,
X
Kba (U|Q) =
Pab (0, q) − Pab (1, q) .
q

q, b, a) = Pab (u, q) · πN,0 (b, a), we have
Since PU,Q,SN ,S0 (u,P
K(U|Q, SN , S0 ) = a,b πN,0 (b, a)Kba (U|Q). This leads to the
following definition.

K̂n = K(Ui |Qi , SN , S0 ),
Ẑn = Z(Ui |Qi , SN , S0 ),

(24)

Ĥn = H(Ui |Qi , SN , S0 ),
where i − 1 = (B1 B2 · · · Bn )2 . By (23), Kn ≤ K̂n , Zn ≥ Ẑn ,
and Hn ≥ Ĥn for any n. Similar to (9), we have
(
K(Ui + Vi |Qi , Ri , S0 , S2N )
if Bn+1 = 0
K̂n+1 =
K(Vi |Ui + Vi , Qi , Ri , S0 , S2N ) if Bn+1 = 1.
(25)
Relationships akin to (25) hold for Ẑn+1 and Ĥn+1 , with K
replaced with Z and H, respectively. We use the mnemonic
+
K̂−
n+1 = K(Ui + Vi |Qi , Ri , S0 , S2N ) and K̂n+1 = K(Vi |Ui +
Vi , Qi , Ri , S0 , S2N ), and similar mnemonics for the BSI Bhattachryya and conditional entropy processes.
A. Existing Polarization Results for FAIM Processes
In [11], a class of processes with memory was considered.
For this class, the authors showed that the conditional entropy

8

process polarizes and that the Bhattacharyya process polarizes
fast to 0.
Specifically, let
1
N
H(XN
H⋆ (X|Y) , lim
1 |Y1 ).
N →∞ N
This limit exists due to stationarity [18, Section 4.2] and the
N
N
N
N
identity H(XN
1 |Y1 ) = H(X1 , Y1 ) − H(Y1 ).

In particular, for any ǫ > 0,
1
|{i : H(Ui |Qi , S0 , SN ) > 1 − ǫ}| = H⋆ (X|Y),
N
1
lim
|{i : H(Ui |Qi , S0 , SN ) < ǫ}| = 1 − H⋆ (X|Y).
N →∞ N

lim

N →∞

Proof: Consider two adjacent blocks of length N = 2n
and let i − 1 = (B1 B2 · · · Bn )2 . Recall from (10) that
N
2N
2N
(Ui , Qi ) = f (XN
1 , Y1 ) and (Vi , Ri ) = f (XN +1 , YN +1 ),
where the function f depends on the index i (see Figure 2).
Using (20b) we obtain

Theorem 7. [11, Theorems 1,2,4,5] For a strictly stationary
ψ-mixing process (Xj , Yj ), j ∈ Z, with ψ(0) < ∞:
1) Hn polarizes to H∞ with P (H∞ = 1) = H⋆ (X|Y);
2) Zn polarizes fast to 0 with β < 1/2.
PUi ,Vi |Qi ,Ri ,S0 ,SN ,S2N = PUi |Qi ,S0 ,SN PVi |Ri ,SN ,S2N . (29)
In particular, for any ǫ > 0,
1
Thus,
|{i : H(Ui |Qi ) > 1 − ǫ}| = H⋆ (X|Y),
(26a)
lim
N →∞ N


(a) 1
1
Ĥ
=
H(U
|Q
,
S
,
S
)
+
H(V
|R
,
S
,
S
)
n
i
i
0
N
i
i
N
2N
lim
|{i : H(Ui |Qi ) < ǫ}| = 1 − H⋆ (X|Y), (26b)
2
N →∞ N
(b) 1
= H(Ui , Vi |Qi , Ri , S0 , SN , S2N )
and for any β < 1/2,
2
o
(c) 1
1 n
−N β
= H(Ui + Vi , Vi |Qi , Ri , S0 , SN , S2N )
i : Z(Ui |Qi ) < 2
= 1 − H⋆ (X|Y). (27)
lim
2
N →∞ N

(d) 1
To prove Theorem 7, the conditional entropy process Hn
=
H(Ui + Vi |Qi , Ri , S0 , SN , S2N )
2

was shown to be a bounded supermartingale, so it converges
+
H(V
|U
+
V
,
Q
,
R
,
S
,
S
,
S
)
i
i
i
i
i
0
N
2N
almost surely to some random variable H∞ . This latter random
variable was shown to be a {0, 1}-random variable with
(e) 1 
H(Ui + Vi |Qi , Ri , S0 , S2N )
≤
P(H∞ = 1) = 1 − P(H∞ = 0) = H⋆ (X|Y). This yields (26).
2

Equation (27) is based on the observation that
+ H(Vi |Ui + Vi , Qi , Ri , S0 , S2N )
o
n


β
β
1

. (28)
i : Z(Ui |Qi ) < 2−N
P Zn < 2−N =
1 −
N
Ĥn + Ĥ+
=
n ,
2
First, the Bhattacharyya process Zn was also shown to converge almost surely to H∞ . Next, using the mixing property,
+
2
the authors showed that Z−
n ≤ 2ψ(0)Zn and Zn ≤ ψ(0)Zn . where (a) is by stationarity, (b) is by (29), (c) is because the
This allowed them to invoke Lemma 3 and obtain (27).
mapping (U, V) 7→ (U + V, V) is one-to-one and onto, (d) is
Corollary 8. Let (Xj , Yj , Sj ), j ∈ Z be a FAIM process. Then, by the chain rule for entropies, and (e) is by (6c).
By (25) (applied to the BSI conditional entropy), Ĥn is a
1) Its conditional entropy process Hn polarizes to H∞ with
submartingale
sequence:
P (H∞ = 1) = H⋆ (X|Y).
i

h
2) Its Bhattacharyya process Zn polarizes fast to 0 with
1 −
Ĥn + Ĥ+
any β < 1/2.
n = E Ĥn+1 Ĥn , Ĥn−1 , . . . , Ĥ1 ≥ Ĥn .
2
Proof: By Lemma 5, blocks of FAIM processes are ψIt is also bounded, as Ĥn ∈ [0, 1] for any n. Thus, it converges
mixing and satisfy the requirements of Theorem 7.
Theorem 7, and consequently Corollary 8, are silent on the almost surely to some random variable Ĥ∞ ∈ [0, 1], [23,
rate of polarization of Zn to 1. In the sequel we establish a Theorem 35.4].
Denote ∆Hn = Hn − Ĥn . The sequence ∆Hn converges
compatible claim for FAIM processes. To do this, we exploit
almost
surely to the random variable ∆H∞ = H∞ − Ĥ∞ .
the structure of FAIM processes by calling upon the BSI
This
is
because Ĥn converges almost surely to Ĥ∞ , and,
processes Ĥn and K̂n .
by Corollary 8, Hn converges almost surely to H∞ . By (6),
∆Hn ≥ 0 for any n, which implies that ∆H∞ ≥ 0 almost
B. Polarization of the BSI Distribution Parameters
surely. We now show that ∆H∞ = 0 almost surely. To this end,
This section is concerned with proving that the BSI distribu- we will need the following lemma, whose proof is postponed
tion parameters polarize. We achieve this by first showing that to the end of this theorem.
the BSI conditional entropy polarizes and then using Lemma 1
to establish polarization of the BSI Bhattacharyya parameter Lemma 10. The sequence ∆Hn satisfies
and BSI total variation distance.
Theorem 9. Let (Xj , Yj , Sj ), j ∈ Z be a FAIM process.
The BSI conditional entropy process Ĥn polarizes to Ĥ∞ and
Ĥ∞ = H∞ almost surely.

lim E [∆Hn ] = 0.

n→∞

Since ∆Hn converges to ∆H∞ almost surely, we specifically have lim inf n→∞ ∆Hn = ∆H∞ almost surely. Using

9

Fatou’s lemma6 for the non-negative sequence ∆Hn , n =
1, 2, . . . we obtain
i
h
0 ≤ E [∆H∞ ] = E lim inf ∆Hn
n→∞

≤ lim inf E [∆Hn ] = lim E [∆Hn ] = 0.
n→∞

n→∞

Thus, E [∆H∞ ] = 0. By Markov’s inequality, P(∆H∞ ≥ δ) ≤
E [∆H∞ ] /δ = 0 for any δ > 0; consequently, P(∆H∞ =
0) = P(H∞ = Ĥ∞ ) = 1. Put another way, Ĥ∞ = H∞ almost
surely.
Recall that H∞ is a {0, 1} random variable with P(H∞ =
1) = H⋆ (X|Y). Since Ĥ∞ = H∞ almost surely, and


1
P Ĥn > 1 − ǫ =
|{i : H(Ui |Qi , S0 , SN ) > 1 − ǫ}| ,
N


1
P Ĥn < ǫ =
|{i : H(Ui |Qi , S0 , SN ) < ǫ}| ,
N
the proof is complete.
Proof of Lemma 10: By (6), ∆Hn ≥ 0, so E [∆Hn ] ≥ 0
as well.
Using the chain rule for conditional entropies and since the
N
transformation UN
1 = X1 GN is one-to-one and onto,
N

N
N
H(UN
H(XN
1 X
1 |Y1 )
1 |Y1 )
H(Ui |Qi ) =
=
.
E [Hn ] =
N i=1
N
N
h i
N
Similarly, E Ĥn = H(XN
1 |Y1 , S0 , SN )/N . Thus,

1
N
N
N
H(XN
|Y
)
−
H(X
|Y
,
S
,
S
)
E [∆Hn ] =
0
N
1
1
1
1
N


(a) 1
N
=
H(S0 , SN |Y1N ) − H(S0 , SN |XN
1 , Y1 )
N
(b) 2 log (|S|)
2
≤
.
N
To see (a), note that for any 3 random variables A, B, C
we have H(A, B|C) = H(A|C) + H(B|A, C) = H(B|C) +
H(A|B, C). Rearranging and setting A = XN
1 , B = (S0 , SN )
and C = Y1N yields (a). Inequality (b) is since S0 , SN take
values in the finite alphabet S and the conditional entropy is
non-negative.
Combining these inequalities, and recalling that N = 2n ,
we obtain
0 ≤ E [∆Hn ] ≤ 2 log2 (|S|)/2n .

This holds for any n. We take limits and use the sandwich
rule to yield limn→∞ E [∆Hn ] = 0, as desired.
The following corollary is a direct consequence of the
definition of almost-sure convergence, Lemma 1, Corollary 8,
and Theorem 9.
Corollary 11.
1) The sequences Zn and Ẑn polarize to random variables
Z∞ and Ẑ∞ , respectively. Moreover, Z∞ = Ẑ∞ = H∞
almost surely.
2) The sequences Kn and K̂n polarize to random variables
K∞ and K̂∞ , respectively. Moreover, K∞ = K̂∞ = 1 −
H∞ almost surely.
6 Fatou’s lemma [23, Theorem 16.3] states that if A , n = 1, 2, . . . is
n
a sequence of non-negative random variables then E [lim inf n→∞ An ] ≤
lim inf n→∞ E [An ].

Proof: The proofs of both items are essentially the same,
so we prove only the first item.
Recall the definition of almost-sure convergence of a sequence of random variables. Let (Ω, F, P) be a probability
space, and let A, A1 , A2 , . . . be a sequence of F-measurable
random variables defined on this space. A random variable is a
deterministic function from Ω to R. We say that An converges
to A almost surely if the set
n
o
A = ω ∈ Ω : lim An (ω) = A(ω)
n→∞

satisfies P (A) = 1.
Now, let (Ω, F, P) be the probability space in which
Hn , Ĥn , Zn , Ẑn , n = 1, 2, . . . as well as H∞ and Ĥ∞ are
defined.
By Corollary 8 and Theorem 9, Hn and Ĥn converge almost
surely to H∞ and Ĥ∞ , respectively, and H∞ = Ĥ∞ almost
surely. Thus, we denote
n
o
H = ω ∈ Ω : lim Hn (ω) = lim Ĥn (ω) = H∞ (ω) .
n→∞

n→∞

By definition of almost sure convergence, P(H) = 1.
Since H∞ (ω) ∈ {0, 1}, we split H = H0 ∪· H1 , such
that H∞ (ω) = 0 for any ω ∈ H0 and H∞ (ω) = 1pfor any
ω ∈ H1 . By Lemma 1, we have Hn (ω)2 ≤ Zn (ω) ≤ Hn (ω)
for any ω. Thus, limn→∞ Zn (ω) = 0 for any ω ∈ H0
and limn→∞ Zn (ω) = 1 for any ω ∈ H1 . We conclude
that Zn converges almost surely to a {0, 1}-random variable
Z∞ and Z∞ = H∞ almost surely. Using similar arguments,
Ẑn converges almost surely to a random variable Ẑ∞ and
Ẑ∞ = Ĥ∞ almost surely. By Theorem 9, Ĥ∞ = H∞ almost
surely.
C. Fast Polarization of the Bhattacharyya Process to 1
In this section, we prove that the Bhattacharyya process Zn
of a FAIM process polarizes fast to 1.
Theorem 13, the main theorem of this section, relies on an
inequality akin to (13) for the BSI total variation distance. We
state the inequality in Proposition 12, and postpone its proof
to the end of the section.
Proposition 12. Let (Xj , Yj , Sj ), j ∈ Z be a FAIM process.
Then,
(
ψ(0)K̂2n if Bn+1 = 0
K̂n+1 ≤
(30)
2K̂n
if Bn+1 = 1.
Here, ψ(0) is as defined in (19), i.e.,
ψ(0) = max
a

1
1
= max
≥ 1.
b πN (b)
π0 (a)

(31)

Since the state sequence is stationary, finite-state, aperiodic,
and irreducible, ψ(0) < ∞.
Theorem 13. Let (Xj , Yj , Sj ), j ∈ Z be a FAIM process. Then
Zn polarizes fast to 1 and for any β < 1/2,
o
β
1 n
= H⋆ (X|Y). (32)
i : Z(Ui |Qi ) > 1 − 2−N
lim
N →∞ N

10

Proof: Fix β < 1/2. By Corollary 11 and (30), we can
invoke Lemma 3 for K̂n with E = 1/2. Consequently, K̂n
polarizes fast to 0, i.e.,




β
lim P K̂n < 2−N = P K̂∞ = 0
n→∞

= P (H∞ = 1) = H⋆ (X|Y).

P
P
Also, since πN (b) = a∈S πN,0 (b, a) = c∈S π2N,N (c, b),
we have
X
X
µ(b) = π2N,N (c, b),
µ(b) = πN,0 (b, a).
(35)
a∈S

π2N,0 (c, a)PUi ,Vi ,Qi ,Ri |S2N ,S0 (u, v, q, r|c, a)

For any n, by (4b) and (23),
p
1 − Zn ≤ 1 − Zn ≤ Kn ≤ K̂n .

= π0 (a)π2N |0 (c|a)PUi ,Vi ,Qi ,Ri |S2N ,S0 (u, v, q, r|c, a)
= π0 (a)PUi ,Vi ,Qi ,Ri ,S2N |S0 (u, v, q, r, c|a)
X
= π0 (a)
PUi ,Qi ,SN |S0 (u, q, b|a)PVi ,Ri ,S2N |SN (v, r, c|b)

Thus,

b∈S





β
β
P Zn > 1 − 2−N ≥ P K̂n < 2−N .

= π0 (a)

lim P(Zn > 1 − 2

n→∞

=
) ≥ H⋆ (X|Y).

β

lim P(Zn < 2−N ) = 1 − H⋆ (X|Y).

n→∞

β

Since P(Zn < 2−N ) + P(Zn > 1 − 2−N ) ≤ 1 for any n,
we must have


β
lim P Zn > 1 − 2−N = H⋆ (X|Y).
n→∞

To obtain (32), note that by definition of the Bhattacharyya
process,


o
β
β
1 n
P Zn > 1 − 2−N =
.
i : Z(Ui |Qi ) > 1 − 2−N
N
Taking limits completes the proof.
Proof of Proposition 12: The proof follows along the
lines of the proof of Proposition 4.
Consider two adjacent blocks of length N = 2n and let
i − 1 = (B1 B2 · · · Bn )2 . This is illustrated in Figure 2. Recall
from (10) that there is a function f that depends on i such
N
2N
2N
that (Ui , Qi ) = f (XN
1 , Y1 ) and (Vi , Ri ) = f (XN +1 , YN +1 ).
By stationarity,
X
X
K̂n =
πN,0 (b, a)Kba (Ui |Qi ) =
π2N,N (c, b)Kcb (Vi |Ri ).
a,b∈S

b,c∈S

(33)

As in (21), we denote
Pac (u, q) = PUi ,Qi |SN ,S0 (u, q|c, a) = PVi ,Ri |S2N ,SN (u, q|c, a).
The right-most equality is due to stationarity.P
We further
denote Pac (s) = Pac (0, s)+Pac (1, s); in particular, s Pac (s) =
1.
Denote

X

µ(b)Pab (u, q)Pbc (v, r).

(36)

Set Ti = Ui + Vi . Using (9), a single-step polarization from
K̂n to K̂n+1 becomes
X
π2N,0 (c, a)Kca (Ti |Qi , Ri )
if Bn+1 = 0



a,c∈S
K̂n+1 = X


π2N,0 (c, a)Kca (Vi |Ti , Qi , Ri ) if Bn+1 = 1.

a,c∈S

Kca (Ti |Qi , Ri )

Here,
and Kca (Vi |Ti , Qi , Ri ) are computed for
a block of length 2N with initial state S0 = a and final state
S2N = c. At the middle of the block we have state SN = b.
Using (11), we denote
P̄ac (t, v, q, r) = PTi ,Vi ,Qi ,Ri |S2N ,S0 (t, v, q, r|c, a)
= PUi ,Vi ,Qi ,Ri |S2N ,S0 (t + v, v, q, r|c, a)
and
P̄ac (t, q, r) = PTi ,Qi ,Ri |S2N ,S0 (t, q, r|c, a)
=

(34)

P̄ac (t, v, q, r).

v=0

π2N,0 (c, a)Kca (Ti |Qi , Ri )
X
= π2N,0 (c, a)
P̄ac (0, q, r) − P̄ac (1, q, r)
q,r

1
X
(a) X X
=
µ(b)
Pbc (v, r)(Pab (v, q) − Pab (v + 1, q))
q,r

(b) X

≤

v=0

b∈S

µ(b)

q,r,
b∈S

1
X
v=0

Pbc (v, r)(Pab (v, q) − Pab (v + 1, q))

=

X

µ(b) Pab (0, q) − Pab (1, q) · Pbc (0, r) − Pbc (1, r)

=

X

µ(b)Kba (Ui |Qi )Kcb (Vi |Ri )

b∈S

We deliberately omitted the dependence on a, c from this
notation to simplify the expressions that follow. Observe that
by (31),

1
X

Consider first the case Bn+1 = 0:

q,r,
b∈S

µ(b) = π2N |N (c|b)πN |0 (b|a)π0 (a)
π2N,N (c, b) · πN,0 (b, a)
=
.
πN (b)

µ(b) ≤ ψ(0) · π2N,N (c, b) · πN,0 (b, a).

πN |0 (b|a)Pab (u, q)π2N |N (c|b)Pbc (v, r)

b∈S

On the other hand, by Corollary 8,

β

X
b∈S

Taking limits, we obtain that

−N β

c∈S

By (16) and (21),

(c)

≤ ψ(0)

(d)

≤ ψ(0)

X
b∈S

X
b∈S

 

π2N,N (c, b)Kcb (Vi |Ri ) · πN,0 (b, a)Kba (Ui |Qi )

π2N,N (c, b)Kcb (Vi |Ri )

X

b′ ∈S

′

πN,0 (b′ , a)Kba (Ui |Qi ),

11

where (a) is by (36), (b) is by theP
triangle inequality,
P
P(c) is
by (34), and (d) is by the inequality j aj bj ≤ j aj j ′ bj ′ ,
which holds for aj , bj ≥ 0. By (33), the sum over a, c ∈ S
yields
X
π2N,0 (c, a)Kca (Ti |Qi , Ri ) ≤ ψ(0)K̂2n .
a,c∈S

Next, let Bn+1 = 1. We have

1
h(θ)
z(θ)

0.8
0.6
0.4
0.2

π2N,0 (c, a)Kca (Vi |Ti , Qi , Ri )
X
= π2N,0 (c, a)
P̄ac (t, 0, q, r) − P̄ac (t, 1, q, r)

0

0

0.1

0.2

t,q,r

(a) X

=

X

t,q,r b∈S

µ(b)(Pab (t, q)Pbc (0, r) − Psb (t + 1, q)Pbc (1, r))

b∈S

(c) X

≤

µ(b)Pbc (r)(Pab (t, q) − Pab (t + 1, q))

µ(b)Pab (q)

q,
b∈S

+

X
r

X

µ(b)Pbc (r)

r,
b∈S

=

X
b∈S

Pbc (0, r) − Pbc (1, r)

X
q

µ(b)Kcb (Vi |Ri ) +

!

Pab (0, q) − Pab (1, q)

X
b∈S

!

µ(b)Kba (Ui |Qi ),

where (a) is by (36), (b) is by (15), and (c) is by the triangle
inequality. By (35),
X
X
µ(b)Kcb (Vi |Ri ) =
π2N,N (c, b)Kcb (Vi |Ri ) = K̂n ,
a,b,c∈S

b,c∈S

X

µ(b)Kba (Ui |Qi )
a,b,c∈S

=

X

πN,0 (b, a)Kba (Ui |Qi ) = K̂n .

a,b∈S

Thus,
X

π2N,0 (c, a)Kca (Vi |Ti , Qi , Ri ) ≤ 2K̂n .

A PPENDIX A
AUXILIARY P ROOFS FOR S ECTION III
For θ ∈ [0, 1/2] we denote
k(θ) = |θ − (1 − θ)| = 1 − 2θ,
h(θ) = −θ log2 θ − (1 − θ) log2 (1 − θ),
p
z(θ) = 2 θ(1 − θ).

We will need the following lemma.

Lemma 15. For θ ∈ [0, 1/2], we have h(θ) ≤ z(θ).
Proof: We plot h(θ) and z(θ) in Figure 3; indeed h(θ) ≤
z(θ) for 0 ≤ θ ≤ 1/2. We now prove this formally.
Denote g(θ) = h(θ) − z(θ). Since g(0) = g(1/2) = 0,
it suffices to show that g(θ) has a single stationary point in
(0, 1/2), and that this point is a minimum.
The stationary points of g(θ) are the zeros of its derivative


1 − 2θ
1−θ
′
−p
.
g (θ) = log2
θ
θ(1 − θ)
Recalling that θ ∈ [0, 1/2],
g ′′′ (θ) =

a,c∈S

This completes the proof.
since
D. Fast Polarization of the BSI Bhattacharyya Process
Fast polarization of the Bhattacharyya process was established in Corollary 8 and Theorem 13. Implicitly, however,
we have also obtained obtained fast polarization of the BSIBhattacharyya process Ẑn , both to 0 and 1. We now make this
explicit.
Corollary 14. Let (Xj , Yj , Sj ), j ∈ Z be a FAIM process.
Then Ẑn polarizes fast both to 0 and to 1 with any β < 1/2.
Proof: Polarization of Ẑn was obtained directly in Corollary 11. By (23), Zn ≥ Ẑn . Since Zn polarizes fast to 0 with
any β < 1/2, so must Ẑn . We obtain fast polarization of Ẑn
to 1 by replacing the Bhattacharyya parameter with its BSI
counterpart in the proof of Theorem 13.

0.5

Fig. 3. Illustration that h(θ) ≤ z(θ) for 0 ≤ θ ≤ 1/2.

b∈S

+

0.4

θ

(b) 1 X X
µ(b)Pab (q)(Pbc (0, r) − Pbc (1, r))
=
2 t,q,r

X

0.3

p
(1 − 2θ)(4 θ(1 − θ) − ln 8)
≤ 0,
p
5
2
θ(1 − θ) ln 2

p
p
4 θ(1 − θ) − ln 8 < 4 θ(1 − θ) − 2 ≤ 0.

Hence, g ′ (θ) is concave-∩ in [0, 1/2]. Observe that g ′ (1/2) =
0 and limθ→0 g ′ (θ) = −∞, so g ′ (θ) can assume the value
0 for at most one point in (0, 1/2). Assume to the contrary
that g ′ (θ) < 0 for all θ ∈ (0, 1/2). Then, g(θ) has no stationary points in (0, 1/2), which, by the mean value theorem,
contradicts g(0) = g(1/2) = 0. We conclude that g ′ (θ0 ) = 0
for some θ0 ∈ (0, 1/2). Consequently, θ0 is a stationary point
of g(θ). Since g ′ (θ) is concave-∩ and g ′ (1/2) = g ′ (θ0 ) = 0,
then g ′ (θ) > g ′ (θ0 ) for θ0 < θ < 1/2 and g ′ (θ) < g ′ (θ0 )
for 0 < θ < θ0 . This implies that g(θ) ≥ g(θ0 ) for any
θ ∈ [0, 1/2]; i.e., θ0 is the single minimum of g(θ) in [0, 1/2].

12

Proof of Lemma 1: For any q, denote
θ = θ(q) = min{PU|Q (0|q), PU|Q (1|q)}.
Accordingly, 1 − θ = max{PU|Q (0|q), PU|Q (1|q)} and θ ∈
[0, 1/2]. The various distribution parameters are expectations
of functions of θ:
X
Pe (U|Q) =
PQ (q)θ,
q

K(U|Q) =

X

PQ (q)k(θ),

H(U|Q) =

PQ (q)h(θ),

q

Z(U|Q) =

X

PQ (q)z(θ).

q

We directly obtain (4a), as
X
K(U|Q) =
PQ (q)(1 − 2θ)
q

=1−2

X

PQ (q)θ

The right-most inequalities of (4b) and (4c) are immediate
consequences of Lemma 15. Thus, we concentrate on the leftmost inequalities.
For the left-most inequality of (4b), we use the CauchySchwartz inequality to obtain
sX
p
1 − H(U|Q) =
PQ (q)(1 − h(θ))
q

sX 
 p

p
PQ (q) ·
PQ (q)(1 − h(θ))
q

≤
=

X
q

X
q

PQ (q) ·

X
q

This implies the left-most inequality of (4c).
Proof of Lemma 2: We obtain the joint distribution of
(U, Q) by marginalizing PU,Q,S ,
X
PU,Q (u, q) =
PU,Q,S (u, q, s).
The triangle inequality yields (6a):
X
K(U|Q) =
|PU,Q (0, q) − PU,Q (1, q)|
q

=

X X
q

≤

X
q,s

s


PU,Q,S (0, q, s) − PU,Q,S (1, q, s)

|PU,Q,S (0, q, s) − PU,Q,S (1, q, s)|

= K(U|Q, S).

q

= 1 − 2Pe (U|Q).

=

q

s

q

X

Using Jensen’s inequality twice for the convex-∪ function x 7→
x2 ,
X
Z(U|Q)2 + K(U|Q)2 ≤
PQ (q)(z 2 (θ) + k 2 (θ)) = 1.

PQ (q)(1 − h(θ))2

PQ (q)(1 − h(θ))2 .

We derive (6b) using the Cauchy-Schwartz inequality:
Xq
Z(U|Q) = 2
PU,Q (0, q)PU,Q (1, q)
q

=2

X sX
q

≥2

PU,Q,S (0, q, s)

s

X

PU,Q,S (1, q, s′ )

s′

q
Xq
PU,Q,S (0, q, s) PU,Q,S (1, q, s)
q,s

= Z(U|Q, S).

Inequality (6c) is a consequence of Jensen’s inequality for
the concave-∩ function x 7→ −x log2 x. A proof can be found
in [18, Theorem 2.6.5].
A PPENDIX B
E XTENSION TO THE N ON -B INARY C ASE

Our results are readily extended to the non-binary case.
The function ϕ(θ) = (1 − h(θ))2 is convex-∪ for θ ∈ [0, 1/2]
Here,
Xj , j ∈ Z take values in an alphabet U with |U| = L.
as a composition of a convex non-decreasing function (x 7→
As
in
[3],
we use Arıkan’s polarization transform in the non2
x ) and a convex function (1 − h(θ)), [25, Theorem 7.22].
binary
case,
replacing addition of L-ary numbers with moduloThus,
L addition. Thus (7) applies in the non-binary case; addition


1
in (7a) and (7b) is modulo-L.
ϕ(θ) = ϕ (1 − 2θ) · 0 + 2θ ·
2
First, we extend the distribution parameters from Sec 
1
tion III-A to non-binary U. We do this while keeping key
= 1 − 2θ = k(θ),
≤ (1 − 2θ) · ϕ(0) + 2θ · ϕ
2
properties that allows their use in polar code analysis. Then,
we
consider their fast polarization. Fast polarization of the
hence
Bhattacharyya process was established in [4, Chapter 3]. We
X
p
1 − H(U|Q) ≤
PQ (q)k(θ) = K(U|Q).
show that the total variation process satisfies the conditions
q
for fast polarization required for Lemma 3.
For the left-most inequality of (4c), observe that
z 2 (θ) + k 2 (θ) = 4θ(1 − θ) + (θ − (1 − θ))2
= θ2 + 2θ(1 − θ) + (1 − θ)2
2

= (θ + (1 − θ))

= 1.

A. Non-Binary Distribution Parameters
The three distribution parameters we consider — Bhattacharyya parameter, total variation distance, and conditional
entropy — were all defined for random variable pairs (U, Q)
where U is binary. We now show how to extend them to the

13

case where U may take values in an arbitrary finite alphabet
U. We denote |U| = L.
There are two properties of the distribution parameters that
are crucial for the analysis of polar codes. First, they are to
take values in [0, 1]. Second, when each of them approaches
one of the extreme values, so should the others. The suggested
non-binary extension satisfies these properties. The extension
for the Bhattacharyya parameter and conditional entropy are
based on [3], which ensued the study of non-binary polar codes
(see also [4, Chapter 3]).
Denote
X X PQ (q) q
ZL (U|Q) =
PU|Q (u|q)PU|Q (u′ |q),
L−1
q ′
u 6=u

X X PQ (q) PU|Q (u|q) − PU|Q (u′ |q)
,
KL (U|Q) =
L−1
2
q u′ 6=u
XX
HL (U|Q) = −
PQ (q)PU|Q (u|q) logL PU|Q (u|q).

Next, observe that
q
2  P (u|q) − P (u′ |q) 2
U|Q
U|Q
′
PU|Q (u|q)PU|Q (u |q) +
2
2

PU|Q (u|q) + PU|Q (u′ |q)
=
2
P
and that subject to the constraint u PU|Q (u|q) = 1, we have
X X  PU|Q (u|q) + PU|Q (u′ |q) 2
L(L − 1)
.
≤
2
L2
u ′
u 6=u

This can be seen using Lagrange multipliers; the maximum
value is obtained with equality when PU|Q (u|q) = 1/L for all
u ∈ U. Thus, we obtain
ZL (U|Q)2 + KL (U|Q)2 ≤ 1,

which implies the right-most inequality of (37b). This also
shows that indeed ZL (U|Q) ≤ 1 and KL (U|Q) ≤ 1.
For the left-most
√ inequality of (37b), observe that for any
q
u
a, b ≥ 0 we have ab ≥ min{a, b}, by which
As expected, when L = 2 these coincide with (1) – (3).
max{a, b} − min{a, b} √
|a − b| √
+ ab =
+ ab
All three parameters are in [0, 1]. This is well-known for the
2
2
conditional entropy (see, e.g., [18, Chapter 2]); for the total
max{a, b} − min{a, b} + 2 min{a, b}
≥
variation distance and the Bhattacharyya parameter, see the
2
proof of Lemma 16, below. The three parameters achieve their
max{a, b} + min{a, b}
=
extreme values either when PU|Q (u|q) = 1/L for all u or
2
when there is some u0 ∈ U such that PU|Q (u0 |q) = 1 and
a+b
.
=
PU|Q (u|q) = 0 for u 6= u0 .
2
The consequences of Lemma 1 apply in the non-binary case Since
X
X
as well. That is, when one of the three parameters approaches
PU|Q (u|q) =
PU|Q (u′ |q) = L − 1,
an extreme values, so do the other two. This is a consequence
u′ 6=u
u′ 6=u
of the following lemma.
we have
Lemma 16. The non-binary total variation distance, probabilX
X PU|Q (u|q) + PU|Q (u′ |q)
ity of error, conditional entropy, and Bhattacharyya parameter ZL (U|Q) + KL (U|Q) ≥
PQ (q)
2(L − 1)
are related by
′
q
u 6=u

ZL (U|Q)2 ≤ HL (U|Q) ≤ logL (1 + (L − 1)ZL (U|Q)),
(37a)
p
2
(37b)
1 − ZL (U|Q) ≤ KL (U|Q) ≤ 1 − ZL (U|Q) .

= 1.

This yields the left-most inequality of (37b).
Indeed, inequalities (37) imply that when either ZL (U|Q)
or HL (U|Q) approach 0 or 1 then KL (U|Q) approaches 1 or
0, respectively, and vice versa.
Remark 5. Inequality (37b) was also independently derived
In the binary case, the total-variation distance and the
for the binary symmetric case in [21], using a different proof.
probability of error were related by (4a). In the non-binary
Proof: The inequalities in (37a) were derived in [4, case, the probability of error is given by
X
Proposition 3.3]. Thus, we concentrate on showing (37b).
Pe,L (U|Q) =
PQ (q)(1 − max PU|Q (u|q)).
To see the right-most inequality of (37b), note that
u
q

X X PQ (q)
X X PQ (q)
=
= 1.
L(L − 1)
L(L − 1)
q,u ′
q ′
u 6=u

u 6=u

Thus, by Jensen’s inequality,
2
X X PQ (q) q
ZL (U|Q)2
′ |q)
≤
P
(u|q)P
(u
,
U|Q
U|Q
L2
L(L − 1)
q,u u′ 6=u
X X PQ (q)  PU|Q (u|q) − PU|Q (u′ |q) 2
KL (U|Q)2
≤
.
L2
L(L − 1)
2
q,u ′
u 6=u

The non-binary probability of error and total variation distance
are related, as shown in the following lemma.

Lemma 17. The non-binary probability of error and total
variation distance are related by
2
Pe,L (U|Q).
KL (U|Q) ≤ 1 −
L−1
Proof: Let U = {0, 1, . . . , L − 1}. Without loss of
generality we assume that, for a given q ∈ Q,
PU|Q (0|q) ≤ PU|Q (1|q) ≤ · · · ≤ PU|Q (L − 1|q).

(38)

14

We then have
X |PU|Q (u|q) − PU|Q (u′ |q)|
2

u′ 6=u

(a)

=

L−1
X
u=0

(b)

=L−

uPU|Q (u|q) −
L−1
X
u=0

L−1
X
u=0

(L − 1 − u)PU|Q (u|q)

(L − u)PU|Q (u|q) −

= (L − 1) − 2
≤ (L − 1) − 2
= (L − 1) − 2
(c)

were obtained in [4, Lemma 3.5]. We now establish polarization bounds for the total variation distance process that
extend Proposition 4 to the non-binary case. Proposition 12
is similarly extended; we omit the derivation.

L−1
X

L−1
X
u=0

(L − 1 − u)PU|Q (u|q)

(L − 1 − u)PU|Q (u|q)

u=0
L−1
X

u=0
L−2
X

min{1, L − 1 − u}PU|Q (u|q)
PU|Q (u|q)

u=0

= (L − 1) − 2(1 − max PU|Q (u|q)).

Proposition 19. Assume that (Xj , Yj ), j ∈ Z is a memoryless
process, where Xj ∈ U such that |U| = L, and Yj ∈ Y. Then,

2(L − 1) 2


K
if Bn+1 = 0

L  n
(40)
Kn+1 ≤ 
L


Kn if Bn+1 = 1.
 1+
2

Observe that when L = 2, the right-hand-side of (40)
coincides with that of (13).
Proof: As in Proposition 4, we fix B1 , . . . , Bn and let
i − 1 = (B1 B2 · · · Bn )2 . This also fixes the value of Kn .
We denote PUi ,Vi ,Qi ,Ri (u, v, q, r) = P (u, q)P (v, r). Slightly
abusing notation, we further denote P (u, q) = P (q)P (u|q).
We set Ti = Ui + Vi ; this is modulo-L addition, so

u

To see (a), note that |a − b| = max{a, b} − min{a, b}. Using
the ordering (38), we construct two L × L matrices: one with
constant columns, with value PU|Q (u|q) in column (u+1), and
one with constant rows, with value PU|Q (u|q) in row (u + 1),
u = 0, 1, . . . , L − 1 . We compute the difference of the two
matrices; the desired sum equals thePsum of elementsPabove
the diagonal. Then, (b) is because
uPU|Q (u|q) + (L −
u)P
(u|q)
=
L,
and
(c)
is
by
the
ordering
(38) and since
P U|Q
P
(u|q)
=
1.
Thus,
for
any
q
∈
Q,
u U|Q
X |PU|Q (u|q) − PU|Q (u′ |q)|

2(1 − maxu PU|Q (u|q))
.
L−1
u′ 6=u
(39)
Using (39) in the definition of KL (U|Q) and recalling the
expression for Pe,L (U|Q), we obtain the desired inequality.
The following corollary tightens [4, Proposition 3.2].
2(L − 1)

PTi ,Vi ,Qi ,Ri (t, v, q, r) = P (t − v, q)P (v, r),
where t − v is computed modulo-L.
We shall need the following inequality:
X
|PU|Q (u|q) − PU|Q (u′ |q)|
u′ 6=u

(a)

≥
(b)

L−1
ZL (U|Q).
2
Proof: This is a consequence of the left-hand inequality
of (37b) and Lemma 17.
The non-binary distribution parameters are all natural extensions of their versions when U is binary. In particular, the
non-binary parameters have the same form as their binary
counterparts. As shown above, the consequences of Lemma 1
apply to the non-binary parameters as well. They also satisfy
Lemma 2; the extension of its proof is straightforward. Thus,
the non-binary distribution parameters may be used to define
the relevant processes as in (8) and (24).
Pe,L (U|Q) ≤

In the binary case, fast polarization is obtained by Lemma 3,
which requires polarization bounds on the Bhattacharyya and
total variation distance processes. In the non-binary case, the
relevant polarization bounds for the Bhattacharyya process

(41)

Here,
(a) is by the triangle inequality and (b) is because
P
P
u U|Q (u|q) = 1.
We compute Kn+1 using (14). For the case Bn+1 = 0, note
that
X X
v

t′ 6=t

P (v|r)(P (t − v|q) − P (t′ − v|q))



X
1
′
=
P (v|r) −
P (t − v|q) − P (t − v|q)
L
t′ 6=t v



(b) X X
1
P (t − v|q) − P (t′ − v|q)
≤
P (v|r) −
L
′
v
(a) X

t 6=t

(c) X X

=

t′ 6=t v

=

X
v

B. Polarization of the Distribution Parameters

(PU|Q (u|q) − PU|Q (u′ |q))

u′ 6=u

= (L − 1)PU|Q (u|q) − (1 − PU|Q (u|q))
1
= L PU|Q (u|q) −
.
L

≤ 1−

Corollary 18. The non-binary Bhattacharyya parameter
upper-bounds the probability of error according to

X

(d)

P (v|r) −

P (v|r) −

1
· P (t − v|q) − P (t′ − v|q)
L

1 X
·
P (t − v|q) − P (t′ − v|q)
L ′
t 6=t

X
1X
≤
P (v|r) − P (v ′ |r) ·
P (t|q) − P (t′ |q) ,
L ′
′
v 6=v

t 6=t

P
where (a) is because v P (t − v|q) = v P (t′ − v|q) for any
t, t′ , (b) is by the triangle inequality, (c) is because |ab| =
P

15

|a| · |b|, and (d) is by (41) and since the sum over t, t′ is
unaffected by the shift in v. Thus,
KL (Ti |Qi , Ri )
X P (q)P (r) X X
P (v|r)(P (t − v|q) − P (t′ − v|q))
=
2(L
−
1)
′
v
q,r

N
N
AN
M+1 = (XM+1 , YM+1 )

L
L
AL
1 = (X1 , Y1 )

d

c

b

a

SN

SM

SL

S0

t6=t

2(L − 1) 2
Kn .
≤
L
Recalling (14), this proves the top inequality of (40).
For the case Bn+1 = 1, note that by (15) and the triangle
inequality, when v ′ 6= v we have
2 P (t − v|q)P (v|r) − P (t − v ′ |q)P (v ′ |r)



= P (t − v|q) + P (t − v ′ |q) P (v|r) − P (v ′ |r)




+ P (v|r) + P (v ′ |r) P (t − v|q) − P (t − v ′ |q)



≤ P (t − v|q) + P (t − v ′ |q) · P (v|r) − P (v ′ |r)



+ P (v|r) + P (v ′ |r) · P (t − v|q) − P (t − v ′ |q)

Fig. 4. Two blocks of a FAIM process, not necessarily of the same length.
The initial state of the first block, S0 , assumes value a ∈ S. The final state
of the first block, SL , assumes value b ∈ S. The initial state of the second
block, SM , assumes value c ∈ S. The final state of the second block, SN ,
assumes value d ∈ S.

Proof of Lemma 5: The function ψ(N ) was defined
in (19). We repeat the definition below using a notation that
highlights the random variables at play. We deliberately do
not use the notation (17), to explicitly show which random
variables are being marginalized.

PSN |S0 (b|a)


if N > 0
max
a,b
PS0 (b)
ψ(N ) =


max 1
if N = 0.
a PS0 (a)

Recall that by stationarity, PS0 = PSN for any N , so
PSN |S0 (b|a)/PS0 (b) = PSN |S0 (b|a)/PSN (b).
Since Sj , j = 1, 2, . . . is an aperiodic and irreducible
stationary
finite-state Markov chain, ψ(N ) is non-increasing
+ P (t − v|q) − P (t − v ′ |q) .
and ψ(N ) → 1 as N → ∞. This is evident from the properties
of such Markov chains; for a formal proof of this statement,
The last inequality is due to the upper bound P (v|r) + see [24, Theorem 7.14]. For such Markov chains P (a) > 0
S0
P (v ′ |r) ≤ 1 when v ′ 6= v. Hence,
for
any
a
∈
S,
so
ψ(0)
<
∞.
XX
It remains to show that PAL1 ,AN
≤ ψ(M − L)PAL1 PAN
.
|P (t − v|q)P (v|r) − P (t − v ′ |q)P (v ′ |r)|
M +1
M +1
Consider
first
the
case
M
>
L.
Denote
by
a,
b,
c,
d
the
values
t v ′ 6=v
X
of states S0 , SL , SM , and SN , respectively (see Figure 4).
≤
P (v|r) − P (v ′ |r)
Then,
′



≤ P (t − v|q) + P (t − v |q) · P (v|r) − P (v ′ |r)
′

v 6=v

1 XX
P (t − v|q) − P (t − v ′ |q)
2 t ′
v 6=v
X
LX
=
P (v|r) − P (v ′ |r) +
P (t|q) − P (t′ |q) .
2
′
′
+

v 6=v

t 6=t

PAL1 ,AN
XM +1
PAL1 ,AM
N
=
L+1 ,AM +1
αM
L+1

=

This proves the bottom inequality of (40).
The bounds in (40) are of the form required in Lemma 3,
allowing its use to establish fast polarization of the total
variation distance process.

AUXILIARY

A PPENDIX C
P ROOFS FOR S ECTION IV

We denote Aj = (Xj , Yj ), j ∈ Z, with realization αj . Then,
N
N
N
AN
M = (XM , YM ) with realization αM . For brevity, we denote
N
PAN
≡ PAN
(αM ), and similarly PSN ≡ PSN (sN ).
M
M

PS0
N
PAL1 ,AM
L+1 ,AM +1 ,SN |S0

XX

PAN
PAM
PS0
P L
M +1 ,SN |SM
L+1 ,SM |SL A1 ,SL |S0

αM
L+1

Consequently,
KL (Vi |Ti , Qi , Ri )
X X P (q)P (r)
|P (t − v|q)P (v|r) − P (t − v ′ |q)P (v ′ |r)|
=
q,r, v ′ 6=v 2(L − 1)

t
L
Kn .
≤ 1+
2

XX

=

d,a

d,c, αM
L+1
b,a

=

X
d,c,
b,a

=




PAN
M +1 ,SN |SM

X

αM
L+1



 PAL ,S |S PS0
PAM
L 0
1
L+1 ,SM |SL

X

PSM |SL PAL1 ,SL |S0 PS0
PAN
M +1 ,SN |SM

X

PSM
PAN
M +1 ,SN |SM

d,c,
b,a

=

d,c,
b,a

≤ ψ(M − L)

X

PSM |SL
PAL1 ,SL |S0 PS0
PSM

PSM PAL1 ,SL |S0 PS0
PAN
M +1 ,SN |SM

d,c,
b,a

= ψ(M − L)PAL1 PAN
.
M +1

16

We proceed similarly for the case M = L. Again, a and
d represent the values of states S0 and SN . Both b and b′
represent values of state SL ; this distinction is to distinguish
the summation variables of two different sums over values of
SL . Thus,
X
PSL
PAL1 ,SL |S0 PS0
=
PAL1 ,AN
PAN
L+1
L+1 ,SN |SL P
SL
a,b,
d

≤ ψ(0)

X
d,b



PSL · 
PAN
L+1 ,SN |SL

= ψ(0)PAL1 PAN
;
L+1

X
b′ ,a



PAL1 ,SL |S0 PS0 

where the inequality is because PAL1 ,SL |S0 ≤

P

b′

PAL1 ,SL |S0 .

Proof of Lemma 6: Due to aperiodicity and irreducibility
of the state sequence, PSM (a) > 0 for any a ∈ S. By the
Markov Property,
N
PAM
=
1 ,AM +1 |SM

=

PSM ,AM
N
1 ,AM +1
PSM
· PAN
M
PSM · PAM
1 |SM
M +1 |SM ,A1
PSM

.
· PAN
= PAM
1 |SM
M +1 |SM
This proves (20a).
To derive (20b), some more care is required to avoid division
by 0. By the Markov property,
N
PS0 ,SM ,SN · PAM
1 ,AM +1 |S0 ,SM ,SN
N
= PS0 ,SM ,SN ,AM
1 ,AM +1

M
= PS0 ,SM · PAM
· PSN ,AN
1 |S0 ,SM
M +1 |S0 ,SM ,A1

= PS0 ,SM · PAM
· PSN ,AN
1 |S0 ,SM
M +1 |SM

= PS0 ,SM · PAM
· PSN |SM · PAN
1 |S0 ,SM
M +1 |SM ,SN

· PAN
= PS0 ,SM · PSN |SM ,S0 · PAM
1 |S0 ,SM
M +1 |SM ,SN
= PS0 ,SM ,SN · PAM
· PAN
.
1 |S0 ,SM
M +1 |SM ,SN

Recalling the definition of conditional probability [23, Section
33], this implies (20b).
R EFERENCES
[1] E. Arıkan, “Channel polarization: a method for constructing capacityachieving codes for symmetric binary-input memoryless channels,” IEEE
Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, July
2009.
[2] E. Arıkan and E. Telatar, “On the rate of channel polarization,” in Proc.
IEEE International Symposium on Information Theory, June 2009, pp.
1493–1495.
[3] E. Şaşoğlu, E. Telatar, and E. Arıkan, “Polarization for arbitrary discrete
memoryless channels,” in 2009 IEEE Information Theory Workshop,
October 2009, pp. 144–148.
[4] E. Şaşoğlu, “Polar Coding Theorems for Discrete Systems,”
Ph.D. dissertation, IC, Lausanne, 2011. [Online]. Available:
https://infoscience.epfl.ch/record/168993/files/EPFL TH5219.pdf
[5] S. B. Korada and R. L. Urbanke, “Polar codes are optimal for lossy
source coding,” IEEE Transactions on Information Theory, vol. 56, no. 4,
pp. 1751–1768, April 2010.
[6] E. Arıkan, “Source polarization,” in 2010 IEEE International Symposium
on Information Theory, June 2010, pp. 899–903.
[7] E. Hof and S. Shamai, “Secrecy-achieving polar-coding,” in 2010 IEEE
Information Theory Workshop, August 2010, pp. 1–5.

[8] H. Mahdavifar and A. Vardy, “Achieving the secrecy capacity of wiretap
channels using polar codes,” IEEE Transactions on Information Theory,
vol. 57, no. 10, pp. 6428–6443, October 2011.
[9] J. Honda and H. Yamamoto, “Polar coding without alphabet extension
for asymmetric models,” IEEE Transactions on Information Theory,
vol. 59, no. 12, pp. 7829–7838, December 2013.
[10] E. Arıkan, N. ul Hassan, M. Lentmaier, G. Montorsi, and J. Sayir,
“Challenges and some new directions in channel coding,” Journal of
Communications and Networks, vol. 17, no. 4, pp. 328–338, August
2015.
[11] E. Şaşoğlu and I. Tal, “Polar coding for processes with memory,” in 2016
IEEE International Symposium on Information Theory (ISIT). IEEE,
2016, pp. 225–229.
[12] R. Wang, J. Honda, H. Yamamoto, R. Liu, and Y. Hou, “Construction
of polar codes for channels with memory,” in 2015 IEEE Information
Theory Workshop - Fall (ITW), October 2015, pp. 187–191.
[13] R. G. Gallager, Information Theory and Reliable Communication. New
York, NY, USA: John Wiley & Sons, Inc., 1968.
[14] B. Marcus, R. Roth, and P. Siegel, “Constrained systems and coding
for recording channels,” in Handbook of Coding Theory, V. Pless and
W. Huffman, Eds. Amsterdam: Elsevier, 1998, pp. 1635–1764.
[15] H. D. Pfister, J. B. Soriaga, and P. H. Siegel, “On the achievable
information rates of finite state isi channels,” in IEEE Global Telecommunications Conference, 2001, pp. 2992–2996.
[16] D. Arnold and H. A. Loeliger, “On the information rate of binaryinput channels with memory,” in IEEE International Conference on
Communications, 2001, pp. 2692–2695.
[17] J. Chen and P. H. Siegel, “Markov processes asymptotically achieve
the capacity of finite-state intersymbol interference channels,” IEEE
Transactions on Information Theory, vol. 54, no. 3, pp. 1295–1303,
March 2008.
[18] T. Cover and J. Thomas, Elements of Information Theory, 2nd ed. Wiley,
2006.
[19] I. Tal, “A simple proof of fast polarization,” CoRR, vol. abs/1704.07179,
2017. [Online]. Available: http://arxiv.org/abs/1704.07179
[20] M.
Alsan,
“Re-proving
Channel
Polarization
Theorems,”
Ph.D. dissertation, IC, Lausanne, 2015. [Online]. Available:
https://infoscience.epfl.ch/record/203886/files/EPFL TH6403.pdf
[21] I. Dumer, “Polar codes with a stepped boundary,” in 2017 IEEE
International Symposium on Information Theory (ISIT), June 2017, pp.
2618–2622.
[22] S. B. Korada, “Polar codes for channel and source coding,”
Ph.D. dissertation, EPFL, Lausanne, 2009. [Online]. Available:
https://infoscience.epfl.ch/record/138655/files/EPFL TH4461.pdf
[23] P. Billingsley, Probability and Measure, 3rd ed. Wiley, 1995.
[24] R. Bradley, Introduction to Strong Mixing Conditions. Kendrick Press,
2007, vol. 1.
[25] A. Beck, Introduction to Nonlinear Optimization: Theory, Algorithms,
and Applications with MATLAB. PA, USA: SIAM, 2014.

