✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 219 — #1
✐

✐

Communications in Information and Systems
Volume 17, Number 4, 219–247, 2017

arXiv:1703.05348v2 [] 23 Mar 2018

Layered black-box, behavioral
interconnection perspective and
applications to problems in
communications, Part II: stationary
sources satisfying ψ-mixing criterion
Mukul Agarwal, Sanjoy Mitter, and Anant Sahai

Theorems from Part 1 of this paper are generalized to stationary,
ψ-mixing sources in this paper. As a consequence, these theorems
are proved for Markoff chains and order m Markoff chains. The
main result is the generalization of Theorem 1 in Part 1.

1. Introduction
In this paper, we generalize results Theorems 1-4 from Part 1 of this paper
[2] to the case when the source X is not necessarily i.i.d. but stationary and
satisfies a mixing condition, the ψ-mixing criterion (which implies that the
process is also ergodic). As a corollary, the results hold for Markoff chains
and order m Markoff chains.
In Part 1 of this paper, a direct equivalence was drawn between the
problem of communicating an i.i.d. source X to within a certain distortion
level D over an essentially unknown channel and reliable communication at
rates less than the rate-distortion function RX (D) over the channel. As a
result, assuming random codes are permitted, a source-channel separation
theorem was proved for communication over a general, compound channel,
where the channel model is general in the sense of Verdu-Han and compound
in the sense that the channel may belong to a set. These theorems were then
generalized to the unicast, multi-user setting where the sources were still
assumed to be i.i.d.
In this paper, these theorems from Part 1 are generalized to the case
when the source (also sources in the unicast multi-user setting) are not
necessarily i.i.d. but satisfy a mixing criterion called the ψ-mixing criterion.
219

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 220 — #2
✐

✐

220

M. Agarwal, S. Mitter, and A. Sahai

2. Paper outline
In Section 3, the notation and denitions used in this paper are described.
This is followed by a description of the ψ-mixing condition, its properties
and intuition for it in Section 4; the proofs of these properties can be found
in Appendix A. In Section 5, the high-level idea of the proof of the generalization of Theorem 1 of [2] to this paper is stated. A simulation procedure
is required in order to bring this high-level idea to fruition and this is the
subject of Section 6. This is followed by the statement of the main lemma of
this paper, Lemma 6, which uses the simulation procedure of the previous
section to prove a result which is the heart of this paper and the heart of
what is needed in order to generalize Theorem 1 of [2] to ψ-mixing sources:
this is the subject of Section 7. Lemma 6 and a technical lemma relating
rate-distortion functions under the expected and the probability of excess
distortion criteria is needed in order to generalize Theorem 1 of [2] to ψmixing sources; this technical lemma, Lemma 7, is the subject of Section 8.
By use of Lemmas 6 and 7, the main theorem of this paper, Theorem 1,
the generalization of Theorem 1 of [2] to ψ-mixing sources, can be stated
and proved and this is done in Section 9 . Application to this theorem to
Markoff and order m Markoff sources is stated and proved in Section 10.
Some discussions are carried out in Section 11 where in part, it is discussed,
how to generalize Theorems 2, 3 and 4 of [2] to ψ-mixing sources. Section 12
discusses future research directions.

3. Notation and definitions
Let X1 , X2 , . . . , Xn , . . ., be a sequence of random variables defined on a probability space (Ω, Σ, P ). The range of each Xi is assumed to be a finite set X.
Denote this sequence of random variables by X. Such a sequence is called a
source. Further discussion and assumption on the source will be carried out
in Section 4.
Sets will be denoted by latex mathbb notation, example, X, Y, and random variables by basic mathematical notation, for example X, Y . Sigma
fields will be denoted by mathcal notation for example, S.
The source space at each time, as stated before, is X, and is assumed
to be a finite set. The source reproduction space is denoted by Y which is
assumed to be a finite set. Assume that X = Y.
d : X × Y → [0, ∞) is the single-letter distortion measure. Assume that
d(x, x) = 0 ∀x ∈ X.

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 221 — #3
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

221

For xn ∈ Xn , y n ∈ Yn , the n-letter rate-distortion measure is defined additively:
n
X
d(xn (i), y n (i))
dn (xn , y n ) ,
i=1

where xn (i) denotes the ith component of xn and likewise for y n .
(X1 , X2 , . . . , Xn ) will be denoted by X n .
A rate R source-code with input space X and output space Y is a sequence < en , f n >∞
1 , where
en : Xn → {1, 2, . . . , 2⌊nR⌋ } and f n : {1, 2, . . . , 2⌊nR⌋ } → Yn .
We say that rate R is achievable for source-coding the source X within
distortion-level D under the expected distortion criterion if there exists a
rate R source code < en , f n >∞
1 such that


1 n n n n n
lim sup E
(1)
d (X , f (e (X ))) ≤ D
n
n→∞
The infimum of all achievable rates under the expected distortion is an
E (D).
operational rate-distortion function, denoted by RX
We say that rate R is achievable for source-coding the source X within
distortion-level D under the probability of excess distortion criterion if there
exists a rate R source code < en , f n >∞
1 such that


1 n n n n n
lim Pr
(2)
d (X , f (e (X ))) > D = 0
n→∞
n
The infimum of all achievable rates under the probability of excess distorP (D)
tion criterion is an operational rate-distortion function, denoted by RX
We used lim sup in (1) and lim in (2); in (2), we can equivalently use
lim sup. This is because for a sequence of non-negative real numbers an ,
limn→∞ an = 0 is equivalent to lim supn→∞ an = 0.
The block-independent approximation (henceforth shortened to BIA)
X T source is a sequence of random vectors (S1 , S2 , . . . , Sn , . . .), where Si
are independent, and ∀i, Si ∼ X T . To simplify notation, we will sometimes
denote (S1 , S2 , . . .) by S. S n will denote (S1 , S2 , . . . , Sn ). Note that BIA X T
source is an i.i.d. vector source and will also be called the vector i.i.d. X T
source.
The rate-distortion function for the vector i.i.d. X T source is defined in
the same way as above; just that the source input space would be XT , the

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 222 — #4
✐

✐

222

M. Agarwal, S. Mitter, and A. Sahai

source output space will be YT , the single letter distortion function would
now be on T -length sequences and is defined additively, and when forming
block-codes, we will be looking at blocks of T -length vectors. Details are as
follows:
The source input space is XT . Denote it by S. The source reproduction
space is YT . Denote it by T. Denote a generic element of the source space
by s and that of the source reproduction space by t. Note that s and t are
T -length sequences. Denote the ith component by s(i) and t(i) respectively.
The single letter distortion function, now, has inputs which are length
T vectors. It is denoted by dT and is defined additively using d which has
been defined before:
P
dT (s, t) , Ti=1 d(s(i), t(i)).
Note that dT is the same as dT ; just that we use superscript T for T
length vectors, but now, we want to view a T -length vector as a scalar, and
on this scalar, we denote the distortion measure by dT .
sn will denote a block-length n sequence of vectors of length T . Thus,
n
s (i), which denotes the ith component of sn is an element of K. sn (i)(j)
will denote the j th component of sn (i).
The n-letter distortion function is defined additively using dT :
For sn ∈ Sn , P
tn ∈ Tn ,
n
n
n
dT (s , t ) , ni=1 dT (sn (i), tn (i)).
When coding the vector i.i.d. X T source (for short, denoted by S), a rate
n
n
⌊nR⌋ }
R source code is a sequence < en , f n >∞
1 , where e : S → {1, 2, . . . , 2
n
⌊nR⌋
n
and f : {1, 2, . . . , 2
}→T .
We say that rate R is achievable for source-coding the vector i.i.d. X T
source within distortion-level D under the expected distortion criterion if
there exists a rate R source code < en , f n >∞
1 such that
(3)

lim E

n→∞




1 n n n n n
dT (S , f (e (S ))) ≤ D
n

(Note that S n denotes (S1 , S2 , . . . , Sn )).
The infimum of all achievable rates under the expected distortion criteE (D).
rion is the operational rate distortion function, denoted by RX
T
The information-theoretic rate-distortion function of the vector i.i.d. X T
source is denoted and defined as
(4)

T
I
;Y T)
RX
T (D) , inf I(X
T

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 223 — #5
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

223

where T is the set of W : S → P(T) defined as



W, W


(5)

X

pX T (s)W (t|s)dT (s, t) ≤ D





s∈S,y∈T

where pX T denotes the distribution corresponding to X T .
Note that this is the usual definition of the information-theoretic ratedistortion function for an i.i.d. source; just that the source under consideration is vector i.i.d.
E (D) = RI (D).
By the rate-distortion theorem, RX
T
XT
Further, it is also known that
1 E
RX T (T D)
T →∞ T

E
RX
(D) = lim

(6)

The channel is a sequence c =< cn >∞
1 where
(7)
(8)

cn :Xn → P(Yn )
xn → cn (·|xn )

When the block-length is n, the channel acts as cn (·|·); cn (y n |xn ) is the
probability that the channel output is y n given that the channel input is xn .
When the block-length is n, a rate R deterministic channel encoder
is a map ench : MnR → Xn and a rate R deterministic channel decoder is a
n : Yn → M̂n where M̂n , Mn ∪ {e} is the message reproduction set
map fch
R
R
R
where ‘e’ denotes error. The encoder and decoder are allowed to be random
in the sense that encoder-decoder is a joint probability distribution on the
n >∞ is the rate R
space of deterministic encoders and decoders. < ench , fch
1
channel code.
Denote
(9)

n
n
n
∞
g =< g n >∞
1 ,< ech ◦ c ◦ fch >1

gn has input space MnR and output space M̂nR . Consider the set of channels
(10)

GA , {e ◦ c ◦ f | c ∈ A}

g ∈ GA is a compound channel. Rate R is said to be reliably achievable over
n >∞ and a sequence
g ∈ GA if there exists a rate R channel code < ench , fch
1

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 224 — #6
✐

✐

224

M. Agarwal, S. Mitter, and A. Sahai

< δn >∞
1 , δn → 0 as n → ∞ such that
sup gn ({mn }c |mn ) ≤ δn ∀c ∈ A

(11)

mn ∈Mn
R

Supremum of all achievable rates is the capacity of c ∈ A. Note that this is
the compound capacity, but will be referred to as just the capacity of c ∈ A.
The channel c ∈ A is said to communicate the source X directly within
distortion D if with input X n to cn , the output is Y n (possibly depending
on the particular c ∈ A) such that
(12)

Pr



1 n n n
d (X , Y ) > D
n



≤ ωn ∀c ∈ A

for some ωn → 0 as n → ∞.

4. Mixing condition used in this paper
In this section, ψ-mixing processes are defined, properties of ψ-mixing processes are stated (and proved in the appendix) and intuition on ψ-mixing
provided.
4.1. Definition of ψ-mixing process
Let X1 , X2 , . . . , Xn , . . . be a sequence of random variables defined on a probability space (Ω, Σ, P ). The random variables from Xa to Xb will be denoted
by Xab , 1 ≤ a ≤ b ≤ ∞. The whole sequence X1∞ will be denoted by X ∞ or
just by X. The range of each Xi is assumed to be contained in a finite set X.
Note that time is assumed to be discrete. Note further, that it is assumed
that the process is one-sided in time, that it runs from time 1 to ∞, not
−∞ to ∞. The Borel sigma-field on X∞ is defined in the standard way, and
is denoted by F ∞ ; see Pages 1, 2 of [10] for details.
Xba will denote the set corresponding to the ath to the bth coordinates
of X∞ , 1 ≤ a ≤ b < ∞. A sequence within these coordinates will be denoted
by xba , a random variable, by Xab . The Borel sigma-field on Xba is denoted by
b
Fab . Note that if a and b are finite, Fab = 2Xa , the power set of Xba .
∞
For A ∈ Fat and B ∈ Ft+τ
+1 , we will have occasion to talk about the
following probabilities:

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 225 — #7
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

225

Pr(X1t ∈ A)

(13)

∞
Pr(Xt+τ
+1 ∈ B)
∞
Pr(X1t ∈ A, Xt+τ
+1 ∈ B)
∞
The intuitive meaning is clear: for example, Pr(X1t ∈ A, Xt+τ
+1 ∈ B)
refers to the probability that the random variable X1t takes values in the
∞
set A and the random variables Xt+τ
+1 take values in the set B. Mathematically, this is defined as follows. Define:

(14)

A′ = {(a1 , a2 , . . . , an , . . .)|(a1 , a2 , . . . , at ) ∈ A}
B′ = {(b1 , b2 , . . . , bn , . . .)|(bt+τ +1 , bt+τ +2 , . . .) ∈ B}

Then,
(15)

Pr(X1t ∈ A) , P (X ∞ ∈ A′ )
∞
∞
′
Pr(Xt+τ
+1 ∈ B) , P (X1 ∈ B )
∞
∞
′
′
Pr(X1t ∈ A, Xt+τ
+1 ∈ B) , P (X1 ∈ A ∩ B )

(16)
Further, if Pr(X1t ∈ A) > 0, the following definition will be used:
(17)

∞
t
Pr(Xt+τ
+1 ∈ B|X1 ∈ A) ,

∞
Pr(X1t ∈ A, Xt+τ
+1 ∈ B)
Pr(X1t ∈ A)

The one-sided version of ψ-mixing criterion of [4] will be used in this
document, This is because the stochastic process under consideration in
this document is one-sided in time, whereas the stochastic process under
consideration in [4] is two-sided in time.
Define, for τ ∈ W, the set of whole numbers (non-negative integers),
(18) ψ(τ ) = sup

sup

∞
t
∞
t∈N A∈F1t ,B∈Ft+τ
+1 ,Pr(X1 ∈A)>0,Pr(Xt+τ +1 ∈B)>0
∞
Pr(X1t ∈ A, Xt+τ
+1 ∈ B)
t
∞
Pr(X1 ∈ A) Pr(Xt+τ +1 ∈ B)

−1

The process X is said to be ψ-mixing if ψ(τ ) → 0 as τ → ∞.
The changes in (18) from [4] are:

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 226 — #8
✐

✐

226

M. Agarwal, S. Mitter, and A. Sahai
• The first sup is taken over t ∈ Z in [4], see Page 111 of [4]. Also, t is
denoted by j in [4]. However, the sup in (18) is over j ∈ W. This is because the process in [4] is two-sided in time, whereas we are considering
a one-sided process.
• A change of notation, where probabilities in (18) are written in terms
of random-variables taking values in certain sets, whereas [4] considers
the underlying probability space and writes probabilities of sets on
that space, see Page 110, 111 of [4].
• The set A ∈ F1t in (18), whereas if one used the denition in [4], the set
t . This is, again, because the process in [4] is
A would belong to F−∞
two-sided whereas the process in this paper is one-sided.

The reader is referred to [4] and [8] for an overview of various kinds of
mixing conditions. [4] gives a thorough overview of strong mixing conditions.
[8] mentions both weak mixing and strong mixing conditions though the
coverage of strong mixing conditions is less thorough than in [4].
t+T
Let X be stationary. For B ⊂ XT , denote the probability P (Xt+1
∈ B)
(which is independent of t since X is stationary), by PT (B). Note that PT
is a probability distribution on XT where the underlying sigma-field is the
T
canonical sigma-field 2X .
4.2. Properties of ψ-mixing processes
Lemma 1. Let X be stationary, ψ-mixing. Then, ∀t ∈ N, ∀τ ∈ W, ∀T ∈
W, ∀A ⊂ Xt , ∀B ⊂ XT , P (X1t ∈ A) > 0,
(19)

t+τ +T
t
′
Pr(Xt+τ
+1 ∈ B|X1 ∈ A) = (1 − λτ )PT (B) + λτ Pt,τ,T,A (B)

′
T
for some probability distribution Pt,τ,T,
A on X (under the canonical sigma
field on XT ) which may depend on t, τ, T, A, and λτ → 0 as τ → ∞.

Proof. See Appendix A.



Lemma 2. If X is stationary, ψ-mixing, then X is ergodic.
Proof. See Appendix A.



Lemma 3. Let X = (X1 , X2 , . . . , Xn , . . .) be a stationary, irreducible, aperiodic Markoff chain evolving on a finite set X. Then, X is ψ-mixing.
Proof. See Appendix A.



✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 227 — #9
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

227

Lemmas 2 and 3 have been proved in [4] for two-sided ψ-mixing processes. The proof of Lemma 3 uses the result from [4] on two-sided processes.
Lemma 4. Let X = (X1 , X2 , . . .) be a stationary, ψ-mixing process evolving
tL
on a set X. For L ∈ N, define Zt = X(t−1)L+1
. Then, Z = (Z1 , Z2 , . . .) is a
stationary, ψ-mixing process evolving on the set XL .
Proof. See Appendix A.



Lemma 5. Let X be a stationary, order m Markoff chain evolving on a
tL
finite set X. Define Zt = X(t−1)L+1
. Note that Z = (Z1 , Z2 , . . .) is a Markoff
chain evolving on the set Z = XL . Assume that Z is irreducible, aperiodic.
Then X is ψ-mixing.
Proof. See Appendix A.



It should be noted here, that a ψ-mixing process can have a rate of
mixing as slow as is desired whereas a Markoff ψ-mixing chain implies exponential rate of convergence to the stationary distribution [3], [7]. Thus, the
set of ψ-mixing processes is strictly larger than the set of Markoff or order
m Markoff chains.
These lemmas are the same as the lemmas in [4] but for 1-sided ψ-mixing
processes, not 2-sided ψ-mixing processes. Many of the proofs use the result
from [4] for 2-sided ψ-mixing processes and via a suitable construction, prove
the same for 1-sided ψ-mixing processes.
4.3. Intuition on ψ-mixing
∞
Assume that X is stationary. Note (A.2). X1t and Xt+τ
+1 are independent
if

(20)

∞
t
∞
P (Xt+τ
+1 ∈ B|X1 ∈ A) = P (Xt+τ +1 ∈ B) = PT (B)

Thus, (A.2) says that the process ‘becomes more and more independent’
with time, further, this happens at a rate proportional to a factor λτ → 0
as τ → ∞ which is independent of the sets A and B in question, and also a
multiplicative factor which depends on the probability of the set B. This dependence on the probability of B is intuitively pleasing in the sense that, for
example, if PT (B) = 10−10 and λτ = 10−5 , then without the multiplicative
factor PT (B), it says nothing meaningful; however, with the multiplicative
factor PT (B), it says something meaningful. A mixing condition can indeed

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 228 — #10
✐

✐

228

M. Agarwal, S. Mitter, and A. Sahai

be defined where PT (B) does not exist on the right hand side in (20), this
is the φ-mixing criterion in [4]. An even weaker condition is the α-mixing
condition [4] where independence is measured in the sense of
(21)

P (A ∩ B) = P (A)P (B)

instead of
(22)

P (B|A) = P (B)

The φ-mixing criterion has been used in the source coding literature,
see for example [12] and [11]. In [12], it is proved that if a certain version
of the goldwashing algorithm is applied to encode a stationary, φ-mixing
source, the expected distortion performance converges to the distortion-rate
function of the source as the codebook length goes to ∞. In [11], it is proved
that for sources which are φ-mixing and have summable mixing coefficients,
the redundancy of the fixed-database Lempel-Ziv algorithm with database
size n is lower bounded by a certain function of n as described in [11].

5. Idea of the proof
Theorem 1 of [2] will be generalized to ψ-mixing sources in this paper. This
will be done by reducing the problem to the case when the source is i.i.d.,
and then, use Theorem 1 of [2].
The basic idea of the proof is the following: Choose τ, T , where τ is small
3T +2τ
compared to T . Denote K1 = X1T , K2 = XT2T+τ+τ+1 , K3 = X2T
+2τ +1 , . . .. Each
Ki has the same distribution; denote it by K. By Lemma 1, each Ki has
distribution close to PT in the sense of (19). Thus, K1 , K2 , K3 , . . ., is close
to an i.i.d. process. Theorem 1 from [2] can be used and rates approximately
(23)

T 1 E
R (T D)
T +τ T K

are achievable for communication over a channel which is known to communicate the source X to within a distortion D. Take T → ∞ and it follows
E (D) are achievable, where X is the ψ-mixing source. Finally,
that rates < RX
since the description of the channel is in terms of a probability of excess disP (D) ≤ RE (D) and this will prove
tortion criterion, we will prove that RX
X
E
that if a certain rate RX (·) is achievable for the channel-coding problem,
P (D).
then so is the rate RX
A lot of technical steps are needed and this will be the material of the
future sections. Note also, that there are various definitions of mixing in the

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 229 — #11
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

229

literature which will make K1 , K2 , . . ., almost independent, but the proof
will not work for all these definitions. The definition of ψ-mixing is used
primarily because (19) holds and this can be used to simulate the source X
in a way discussed in the next section, and this simulation procedure will be
a crucial element of the proof.

6. A simulation procedure for the stationary source X which
satisfies ψ-mixing
By using Lemma 1, a procedure to simulate the source X = (Xt , t = 1, 2, . . .)
will be described.
Fix T and τ , both strictly positive integers. Denote n = (T + τ )k for
some strictly positive integer k.
′
We will generate a (X1′ , X2′ , . . . , X(T
+τ )k ), as described below.
First divide time into chunks of time T , τ , T , τ , T , τ , and so on . . .
Call these slots A1 , B1 , A2 , B2 , . . ., Ai , Bi , . . ., Ak , Bk .
Thus,
A1 contains X ′ T1 .
B1 contains X ′ TT +τ
+1 .
2T +τ
′
A2 contains X T +τ +1 .
+2τ
B2 contains X ′ 2T
2T +τ +1 .
.. .. .. .. .. .. .. ..
. . . . . . . .
iT +(i−1)τ

Ai contains X ′ (i−1)(T +τ )+1 .
i(T +τ )

Bi contains X ′ iT +(i−1)τ +1 .
.. .. .. .. .. .. .. ..
. . . . . . . .
kT +(k−1)τ
Ak contains X ′ (k−1)(T +τ )+1 .
k(T +τ )

Bk contains X ′ kT +(k−1)τ +1 .
Let C1 = 1.
Generate C2 , C3 , . . . , Ck i.i.d., where Ci is 1 with probability (1 − λτ )
and 0 with probability λτ .
(g)
(b)
If Ci = 1, denote Ai by Ai and if Ci = 0, denote Ai by Ai . Think of
superscript ‘g’ as ‘good’ and ‘b’ as ‘bad’.
′
Generation of (X1′ , X2′ , . . . , X(T
+τ )k ) is carried out as follows:
′
The order in which the Xi s in the slots will be generated is the following:
A1 , A2 , B1 , A3 , B2 , . . . , Ai , Bi−1 , Ai+1 , . . ..
(g)
Generate X ′ T1 (slot A1 ) by the distribution PT .
Assume that all Xi have been generated until slot Ai−1 , in other words,
the generation in the following slots in the following order has happened:

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 230 — #12
✐

✐

230

M. Agarwal, S. Mitter, and A. Sahai

A1 , A2 , B1 , A3 , B2 , . . . , Ai−1 , Bi−2 .
The next two slots to be generated, as per the order stated above, is Ai
and then Bi−1 .
For slot Ai ,
iT +(i−1)τ
If it is a ‘g’ slot, generate X ′ (i−1)(T +τ )+1 using PT .
(k−1)T +(k−2)τ

(k−1)T +(k−2)τ

If it is a ‘b’ slot, if P (X1
= x′ 1
) > 0, generate
iT +(i−1)τ
′
′
X (i−1)(T +τ )+1 using Pt,τ,T,A with t = (k − 1)T + (k − 2)τ and A =
(k−1)T +(k−2)τ

(k−1)T +(k−2)τ

{x′ 1
} where x′ 1
is the simulated process realization
(k−1)T +(k−2)τ
(k−1)T +(k−2)τ
′
so far. If P (X1
=x1
) > 0, no process generation
needs to be carried out anyway.
(i−1)(T +τ )
During the slot Bi−1 , X ′ (i−1)T +(i−2)τ +1 is generated using the probability
measure P of the stationary process given the values of the process already
(k−1)T +(k−2)τ
iT +(i−1)τ
generated, that is, given x′ 1
and x′ (i−1)(T +τ )+1 .
This finishes the description of the generation of the (X1′ , X2′ , . . . ,
′
X(T +τ )k ) sequence.
Note that by Lemma 1 and the way the above simulation has been
′
carried out, (X1′ , X2′ , . . . , X(T
+τ )k ) ∼ (X1 , X2 , . . . , X(T +τ )k ).
(g)

Note also, that during slots Ai , the source has distribution X T and is
independent over these slots. This fact is of importance in the next section.

7. The main lemma: channel-coding theorem
Lemma 6. Let c =< cn >∞
1 directly communicate the source X, assumed
to be ψ-mixing, within distortion D.
Let λ > 0 (think of λ small; λ << 1). Choose β > 0 (think of β small;
β << 1 − λ). Choose τ large enough so that λτ ≤ λ. Then, rates
(24)

1 − λτ − β E
R<
RX T
T +τ



(T + τ )D
1 − λτ − β



are reliably achievable over c ∀T ≥ 1 (think of T large).
Proof. Choose T ≥ 1.
Let n = (T + τ )k for some large k. n is the block-length.
Generate C1 , C2 , . . . as described previously.
Generate 2⌊nR⌋ codewords of block-length (T + τ )k = n by use of the
simulation procedure described previously. Note that C1 , C2 , . . . is the same
for generating all the 2⌊nR⌋ codewords.

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 231 — #13
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

231

(g)

Note that over Ai time slots, the codewords are generated i.i.d., as
(g)
in Shannon’s random-coding argument; this generation during Ai is done
i.i.d. X T .
Recall the behavior of the channel which directly communicates the
source X within distortion D. End-to-end,


1 n n n
lim Pr
(25)
d (X , Y ) > D = 0
n→∞
n
(g)

Let us look at the behavior of the channel restricted to time slots Ai .
Assume that the fraction of ‘g’ slots among the k Ai slots is ≥ 1 − λτ − β.
(g)
That is, number of Ai slots is larger than or equal to ⌊(1 − λτ − β)k⌋ + 1.
Denote N = ⌊(1 − λτ − β)k⌋ + 1. This is a high probability event and the
probability → 1 as k → ∞ for any β. If this even does not happen, we will
declare decoding error; hence, in what follows, assume that this is the case.
(g)
Restrict attention to the first N Ai slots. Rename these slots G1 , G2 ,
. . ., GN .
Denote the part of the source during slot Gi by Si . Note that Si is a
T -length vector.
Denote S = (S1 , S2 , . . . , SN ).
Denote the channel output during slot Gi by Ti . Note that Ti is a T length vector. Denote T = (T1 , T2 , . . . , TN ).
Recall the definition of the distortion function dT for T -length vectors,
and its n-block additive extension.
Over Gi slots, then,
lim Pr

(26)

N →∞

N
1 X
(T + τ )kD
dT (Si , Ti ) >
N
N
i=1

!

=0

By substituting N = ⌊(1 − λτ − β)k⌋ + 1, it follows, after noting that
1
k
≤
⌊(1 − λτ − β)k⌋ + 1
1 − λτ − β

(27)
that
(28)



1
lim Pr 
k→∞
⌊(1 − λτ − β)k⌋ + 1

⌊(1−λτ −β)k⌋+1

X
i=1


(T + τ )D 
dT (Si , Ti ) >
=0
1 − λτ − β

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 232 — #14
✐

✐

232

M. Agarwal, S. Mitter, and A. Sahai

Recall again that Si are i.i.d. X T and that, codeword generation over
Gi slots is i.i.d.
We have reduced, then, the problem to that where it is known that
an i.i.d. source is directly communicated over a channel within a certain
probability of excess distortion and we want to calculate a lower bound on
the capacity of the channel – this is Theorem 1 of [2].
If each Gi is considered to be a single unit of time, or in other words,
over Gi , the uses of the channel is considered as a single channel use, we are
thus able, by use of Theorem 1 of [2] to communicate at rates


(T + τ )D
E
R < RX T
(29)
(per channel use)
1 − λτ − β
Total time of communication, though, has been (T + τ )k and there are ⌊(1 −
λτ − β)k⌋ + 1 Gi slots over which the communication takes place. Noting
that
(30)

1 − λτ − β
⌊(1 − λτ − β)k⌋ + 1
≥
(T + τ )k
(T + τ )

it follows that rates
(31)

1 − λτ − β E
R<
RX T
(T + τ )



(T + τ )D
1 − λτ − β



are achievable for reliable communication over the original channel c per
channel use of c.

Roughly, the details of codebook generation and decoding are as follows:
Let reliable communication be desired at a rate R which is such that
there exist τ, β, T such that


1 − λτ − β E
(T + τ )D
R<
RX T
(32)
T +τ
1 − λτ − β
Generate C1 , C2 , . . .. Assume that this knowledge is available at both
encoder and decoder
Generate 2⌊k(T +τ )R⌋ codewords using the simulation procedure.
If the number of ‘g’ slots is less than ⌊(1 − λτ − β)k⌋, declare error.
(g)
Else, restrict attention only the first ⌊(1 − λτ − β)k⌋ Ai slots which
have been renamed G1 , G2 , . . ..
Over these slots, the codebook generation is i.i.d., and then, use the
procedure from Theorem 1 of [2].

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 233 — #15
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

233

E
8. RP
X (D) ≤ RX (D) if X is stationary and satisfies ψ-mixing

Lemma 7. Let X = (Xt , t = 1, 2, 3, . . .) be stationary process which satisP (D) ≤ RE (D).
fies ψ-mixing. Then, RX
X
Proof. By Lemma 2, X is ergodic. Thus, X is stationary, ergodic.
The proof now, relies on [5], Pages 490-499, where the rate-distortion
theorem is proved for stationary, ergodic sources.
First, note the notation in [5]. [5] defines RL (D) and R(D), both on
Page 491. Note that by the rate-distortion theorem for an i.i.d. source, it
follows that
(33)

RL (D) (notation in [5]) =

1 E
R T (T D) (our notation)
T X

Thus,
(34)

E
R(D) (notation in [5]) = lim RX
T (T D) (our notation)
T →∞

E
= RX
(D) (our notation)

Look at Theorem 9.8.2 of [5]. This theorem holds if probability of excess distortion criterion is used instead of the expected distortion criterion: see (9.8.10) of [5]. By mapping the steps carefully, it follows that rate
R1 (D − ǫ) (notation in [5]) is achievable for source-coding the source X under a probability of excess distortion D for all ǫ > 0. Note that it follows
that rates R1 (D − ǫ) are achievable, not necessarily rates R1 (D). This is
because in (9.8.10), when making further arguments, dˆ is made D + 2δ and
not D. Hence, we need to keep a distortion level smaller than D in R1 (·) to
make this rate achievable for the probability of excess distortion criterion.
Next, we construct the Lth order super source as described on Page 495 of
tL
[5]: Define X ′ t = X(t−1)L+1
. Then, X ′ = (X ′ t , t = 1, 2, 3, . . .) is the nth order
′
super-source. X is stationary, ψ-mixing because X is (Lemma 4), and thus,
stationary, ergodic, by Lemma 2. One can thus use Theorem 9.8.2 of [5]
again to argue that rate RL (D − ǫ) (notation of [5]) is achievable for sourcecoding the source X under a probability of excess distortion D for all ǫ > 0.
By taking a limit as L → ∞ (the limit exists by Theorem 9.8.1 in [5]), it
follows that rate R(D − ǫ) (notation in [5]) is achievable for source-coding
the source X under a probability of excess distortion D for all ǫ > 0. As
stated at the end of the proof of Theorem 9.8.1 in [5], R(D) is a continuous function of D. Thus, it follows that rates < R(D) are achievable for

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 234 — #16
✐

✐

234

M. Agarwal, S. Mitter, and A. Sahai

source-coding the source X under a probability of excess distortion D. At
this point, the lemma follows from (34).


9. Generalization of Theorem 1 in Part I to stationary
sources satisfying ψ-mixing
Before we prove the theorem, note the following: Let f : [0, ∞) → [0, ∞) be
a convex ∪ non-increasing function. Let f (0) = K. Let 0 < a < a′ . Then,
(35)

|f (a) − f (a′ )| ≤

K ′
(a − a)
a

Theorem 1. Let c be a channel over which the source X, assumed to be
stationary, ψ-mixing, is directly communicated within probability of excess
P (D) are reliably achievable over c.
distortion D, D > 0. Then, rates < RX
P (D) ≤ RE (D) by Lemma 7 and since it is known that
Proof. Since RX
X

(36)

1 E
RX T (T D)
T →∞ T

E
RX
(D) = lim

it is sufficient to prove that rates less than
(37)

1 E
RX T (T D)
T →∞ T
lim

are reliably achievable over c.
To this end, denote
(38)

D′ ,

D
1 − λτ − β

Then,
(39)
(40)
(41)
(42)
(43)

1 E
1 − λτ − β E
′
RX T ((T + τ )D ′ ) − lim RX
T (T D )
T →∞ T
T +τ
1
1 − λτ − β E
RX T ((T + τ )D ′ ) −
RE T ((T + τ )D ′ )
=
T +τ
T +τ X
1
1 E
′
+
RE T ((T + τ )D ′ ) − RX
T ((T + τ )D )
T +τ X
T
1 E
1 E
′
R T (T D ′ )
+ RX
T ((T + τ )D ) −
T
T X
1 E
1 E
′
+ RX
RX T (T D ′ )
T (T D ) − lim
T →∞ T
T

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 235 — #17
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

235

Expression in (40) is
(44)

−λτ − β E
RX T ((T + τ )D ′ )
T +τ

Note that
(45)

′
E
RX
T ((T + τ )D ) ≤ T log |X|

Thus, the absolute value of the expression in (40) is upper bounded by
(λτ + β) log |X|.
Expression in (41) is
(46)

−τ
T




1
′
E
R T ((T + τ )D )
T +τ X

Note that
(47)

′
E
RX
T ((T + τ )D ) ≤ T log |X|

It then follows that expression in (41) → 0 as T → ∞.
Expression in (42) is
(48)

 1
τ
1 E 
′
E
RX T T (D ′ + D ′ ) − RX
T (T D )
T
T
T

1 E
T RX T (T D)

is a convex ∪ non-negative function of D, upper bounded by
log |X|. It follows that

(49)

 1
τ
1 E 
E
′
RX T T (D ′ + D ′ ) − RX
T (T D )
T
T
T

log |X|  ′ τ ′
′
≤
D
)
−
D
(D
+
D′
T
→ 0 as T → ∞

Expression in (43) → 0 as T → ∞.
By noting the bound on the absolute value of expression (40) proved
above and by noting, as proved above, that expressions in (41), (42), and
(43) → 0 as T → ∞, it follows that ∃ ǫT → 0 as T → ∞, possibly depending

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 236 — #18
✐

✐

236

M. Agarwal, S. Mitter, and A. Sahai

on λτ and β such that
(50)

1 − λτ − β E
1 E
′
RX T ((T + τ )D ′ ) − lim RX
T (T D ) ≤ (λτ + β)|X| + ǫT
T →∞ T
T +τ

By Lemma 6, and by recalling that D ′ = 1−λDτ −β it follows that rates
less than


D
1 E
(51)
− (λτ + β)|X| − ǫT
lim RX T T
T →∞ T
1 − λτ − β
are achievable reliably over c.
By using the fact that λτ and β can be made arbitrarily small and ǫT → 0
as T → ∞, and that, the function
(52)

1 E
RX T (T D)
T →∞ T
lim

is continuous in D, it follows that rates less than
(53)

E
lim RX
T (T D)

T →∞

are reliably achievable over c from which, as stated at the beginning of the
P (D) are reliably
proof of this theorem, it follows that rates less than RX
achievable over c.

Note that statements concerning resource consumption have not been
made either in Theorem 1 or Lemma 6 in this paper whereas they are part
of Theorem 1 in [2]. For the corresponding statements concerning resource
consumption, see Section 11. Further, the way Theorem 1 or Lemma 6 are
stated in this paper, the channel does not belong to a set whereas in Theorem
1 in [2], the channel may belong to a set. For the corresponding statement
where the channel may belong to a set, see Section 11.

10. Application to Markoff chains and order m
Markoff chains
Let X = (Xt , t = 1, 2, . . .) be a stationary, irreducible, aperiodic Markoff
chain evolving on a finite set X. By Lemma 3, X is ψ-mixing. X is thus,
stationary, ψ-mixing and thus, Theorem 1 holds for stationary, irreducible
Markoff chains evolving on a finite set.
Let X = (Xi , i ∈ N) be an order m stationary Markoff chain. Define
im
Zi = X(i−1)m+1
. Then, Z = (Zi , i ∈ N) is a Markoff chain. By Lemma 4, Z

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 237 — #19
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

237

is stationary. Assume that this Z is irreducible, aperiodic. By Lemma 5, X
is ψ-mixing, and thus, Theorem 1 holds.

11. Discussion
It is really (19) that is crucial to the proof, not that ψ-mixing criterion;
this is because it is (19) which is needed for carrying out the simulation
procedure described in Section 6. Other places where ψ-mixing criterion is
used in minor ways is to prove ergodicity and some other properties needed
to finish parts of the proof but it is possible that they can be proved by use
of (19) too (or can just be taken as assumptions). However, the assumption
of ψ-mixing suffices, and since this condition holds for Markoff and order m
Markoff sources (under stationarity, irreducibility, aperiodicity assumptions
as stated above), the theorem has been proved for quite a large class of
sources.
In Theorem 1 of [2], the channel may belong to a set whereas the way
Lemma 6 and Theorem 1 are stated in this paper, the channel does not
belong to a set. However, it is easy to see that the proof of Lemma 7 does
not require knowledge of the channel transition probability; only the endto-end description that the channel communicates the source to within the
distortion level is needed; for this reason, Theorem 1 in this paper generalizes
to the case when the channel belongs to a set for the same reason as [2].
A source-channel separation theorem has also been stated and proved in
Theorem 2 in [2]; this can be done in this paper too. Statements concerning
resource consumption have not been made in this paper in Lemma 6 or
Theorem 1. They follow for the same reason as in [2]: in this context, note
that the codebook in the proof of Lemma 7 consists of codewords which are
independent of each other and further, each codeword has the distribution
as the process X; this point is the only observation needed to prove the
statements concerning resource consumption. Finally, generalization to the
unicast, multi-user setting, namely Theorem 3 and 4 of [2] follow for the
same reason as in [2]. In this context, the only observation that needs to
be made is the same as above that the codewords in the proof of Lemma 7
follow the distribution of the process X.

12. Future research directions
• Generalize Theorem 1 to arbitrary stationary, ergodic processes, not
just those which satisfy ψ-mixing, to the extent possible.

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 238 — #20
✐

✐

238

M. Agarwal, S. Mitter, and A. Sahai
• In particular, explore a generalization to B-processes [6], the closure
of the set of Markoff chains of finite order.
• Consider an alternate proof strategy for proving Theorem 1 which
uses methods from classical ergodic and rate-distortion theory, that is,
methods similar to, for example, [5] and [6], and thus, does not rely on
the decomposition (19). This might help prove Theorem 1 for general
stationary, ergodic sources, not just those which satisfy ψ-mixing.
• Further, consider a strategy based on the theory of large deviations,
in the first instance, for irreducible, aperiodic Markoff chain source.
For i.i.d. sources, a large deviations based method was indeed used in
Part 1 [2].
• Generalize Theorem 1 to stationary, ergodic sources which evolve continuously in space and time (some assumptions might be needed on
the source). Since only the end-to-end description of the channel as
communicating the source X within distortion level D is used and not
the exact dynamics of the channel, the proof given in Part 1 for Theorems 2 and 4, and for similar theorems in this paper, directly holds
for channels which evolve continuously in space and time. The channel
k =< kn >∞
1 would however need to be rigorously defined for continuous time evolution. Further, the encoder-decoder < en , f n >∞
1 would
need to be defined on appropriate spaces so that the interconnection
< en ◦ kn ◦ f n >∞
1 makes sense.
• Research the possibility of an operational rate-distortioon theory for
stationary, ergodic sources (satisfying other conditions). An operational theory for i.i.d. sources has been presented in [1].
• The channel has been assumed to belong to a set in Part I [2] and
the same is the case in this paper. However, the source is assumed
to be known. Research the generalization of results in this paper to
compound sources.

13. Acknowledgements
The authors are extremely grateful to Prof. Robert Gray for his time and
many insightful discussions. The authors also thank Prof. Richard Bradley
for many important e-mail conversations which helped shed more light on
the ψ-mixing criterion.

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 239 — #21
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

239

Appendix A. Proofs of properties of ψ-mixing sequences
Proof of Lemma 1 :
Proof. From (18) and (17), it follows that ψ(τ ) can be alternatively be written as
(A.1) ψ(τ ) = sup

sup

∞
t
∞
t∈N A∈F1t ,B∈Ft+τ
+1 ,Pr(X1 ∈A)>0,Pr(Xt+τ +1 ∈B)>0
t
∞
Pr(Xt+τ
+1 ∈ B|X1 ∈
∞
Pr(Xt+τ
+1 ∈ B)

A)

−1

From (A.1), it follows that ∃λτ → 0 as τ → ∞ such that ∀t ∈ N, ∀τ ∈ W,
∞
t
∞
∀A ∈ F1t , ∀B ∈ Ft+τ
+1 , Pr(X1 ∈ A) > 0, Pr(Xt+τ +1 ∈ B) > 0,
∞
t
∞
∞
(A.2) | Pr(Xt+τ
+1 ∈ B|X1 ∈ A) − Pr(Xt+τ +1 ∈ B)| ≤ λτ Pr(Xt+τ +1 ∈ B)

From (A.2), it follows tha ∃λτ → 0 as τ → ∞ such that ∀t ∈ N, ∀τ ∈ W,
∞
t
∞
∀A ∈ F1t , ∀B ∈ Ft+τ
+1 , Pr(X1 ∈ A) > 0, Pr(Xt+τ +1 ∈ B) > 0,
(A.3)

∞
∞
t
(1 − λτ ) Pr(Xt+τ
+1 ∈ B) ≤ Pr(Xt+τ +1 ∈ B|X1 ∈ A)

Specializing (A.3), it follows that,
(A.4)

t+τ +T
t+τ +T
t
(1 − λτ ) Pr(Xt+τ
+1 ∈ B) ≤ Pr(Xt+τ +1 ∈ B|X1 ∈ A)

t+τ +T
∀t ∈ N, ∀τ ∈ W, ∀T ∈ W, ∀A ⊂ Xt , ∀B ⊂ XT , Pr(X1t ∈ A) > 0, Pr(Xt+τ
+1 ∈
B) > 0.
t+τ +T
Note that Pr(Xt+τ
+1 ) = PT (B) . Substituting this into (A.4), it follows that ∀t ∈ N, ∀τ ∈ W, ∀T ∈ W, ∀A ⊂ Xt , ∀B ⊂ XT , Pr(X1t ∈ A) > 0,
t+τ +T
Pr(Xt+τ
+1 ∈ B) > 0,

(A.5)

t+τ +T
t
(1 − λτ )PT (B) ≤ Pr(Xt+τ
+1 ∈ B|X1 ∈ A)

t+τ +T
t
If λτ = 0, it follows from (A.2), that for Pr(Xt+τ
+1 ∈ B) > 0, P (X1 ∈ A) >
0,

(A.6)

t+τ +T
t
Pr(Xt+τ
+1 ∈ B|X1 ∈ A) = (1 − λτ )PT (B)

and the above equation also holds if PT (B) = 0 but P (X1t ∈ A) > 0; thus,
′
T
(19) holds with any probability distribution Pt,τ,T,
A on X .

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 240 — #22
✐

✐

240

M. Agarwal, S. Mitter, and A. Sahai
If λτ > 0, define
′
Pt,τ,T,
A (B)

(A.7)

t+τ +T
t
P (Xt+τ
+1 ∈ B|X1 ∈ A) − (1 − λτ )PT (B)
=
λτ

From (A.5) , it follows that ∀t ∈ N, ∀τ ∈ W, ∀T ∈ W, ∀A ∈ Xt , ∀B ∈ XT ,
t+τ +T
P (X1t ∈ A) > 0, P (Xt+τ
+1 ∈ B) > 0, ∃λτ → 0 as τ → ∞ such that
(A.8)

t+τ +T
t
′
P (Xt+τ
+1 ∈ B|X1 ∈ A) = (1 − λτ )PT (B) + λτ Pt,τ,T,A (B)

′
T
for some probability distribution Pt,τ,T,
A on X which may depend on t, τ,
T, A.
Finally, note that if PT (B) = 0, (19) still holds with definition (A.7) for
′
Pt,τ,T,A since all the three probabilities in question are individually zero.
This finishes the proof of the lemma.


Proof of Lemma 2:
Proof. In order to prove this lemma, it is sufficient to prove the condition
on Page 19 in [10] (which implies ergodicity as is proved on the same page
of [10]), and which can be re-stated as
(A.9)

N −1
1 X
+T
P (X1t = at1 , Xττ+1
= bT1 ) = P (X1t = at1 )P (X1T = bT1 )
N →∞ N

lim

τ =0

∀t ∈ N, ∀T ∈ N, ∀at1 ∈ Xt , ∀bT1 ∈ XT .
To this end, note, first, that from (A.2), it follows that ∃λτ → 0 as
∞
t
∞
τ → ∞ such that ∀t ∈ N, ∀A ∈ F1t , ∀B ∈ Ft+τ
+1 , P (X1 ∈ A) > 0, P (Xt+τ +1 ∈
B) > 0,
(A.10)

∞
∞
t
(1 − λτ )P (Xt+τ
+1 ∈ B) ≤ P (Xt+τ +1 ∈ B|X1 ∈ A)
∞
≤ (1 + λτ )P (Xt+τ
+1 ∈ B)

∞
t
Thus, ∃λτ → 0 as τ → ∞ such that ∀t ∈ N, ∀A ∈ F1t , ∀B ∈ Ft+τ
+1 , P (X1 ∈
∞
A) > 0, P (Xt+τ
+1 ∈ B) > 0,
∞
(1 − λτ )P (X1t ∈ A)P (Xt+τ
+1 ∈ B)
∞
≤ P (X1t ∈ A, Xt+τ
+1 ∈ B)

(A.11)

∞
≤ (1 + λτ )P (X1t ∈ A)P (Xt+τ
+1 ∈ B)

If P (X1t = at1 ) = 0, then both the left hand side and the right hand side
in (A.9) are zero. If P (X1T = bT1 ) = 0, by use of the assumption that X is

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 241 — #23
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

241

+T
stationary and thus noting that P (Xττ+1
) = P (X1T ) , it follows that both the
left hand side and the right hand side in (A.9) are zero. If neither P (X1t =
at1 ) = 0 nor P (X1T = bT1 ) = 0 is zero, it follows from (A.11) that for τ ≥ t,
+T
(1 − λτ −t )P (X1t = at1 )P (Xττ+1
= bT1 )
+T
≤ P (X1t = at1 , Xττ+1
= bT1 )
+T
≤ (1 + λτ −t )P (X1t = at1 )P (Xττ+1
= bT1 )

(A.12)
Denote

C,

(A.13)

t−1
X

+T
P (X1t = at1 , Xττ+1
= bT1 )

τ =0

It follows from (A.12) by taking a sum over τ that and by noting that since
+T
the process is stationary, P (Xττ+1
= bT1 ) = P (X1T = bT1 ) and substituting
(A.13) in (A.12)

C+

N −t−

N
−1
X

λτ −t

τ =t

≤

N
−1
X

!

P (X1t = at1 )P (X1T = bT1 )

+T
P (X1t = at1 , Xττ+1
= bT1 )

τ =0

≤C+

(A.14)

N −t+

N
−1
X
τ =t

λτ −t

!

P (X1t = at1 )P (X1T = bT1 )

After noting that C and t are constants, that λτ → 0 as τ → ∞, after dividing by N and taking limits as N → ∞ in (A.14) , it follows that

(A.15)

lim

N →∞

N
−1
X

+T
P (X1t = at1 , Xττ+1
= bT1 ) = P (X1t = at1 )P (X1T = bT1 )

τ =0

thus proving (A.9) , and thus, proving that the process X is ergodic if it is
stationary, ψ-mixing.

Proof of Lemma 3 :

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 242 — #24
✐

✐

242

M. Agarwal, S. Mitter, and A. Sahai

Proof. Consider the two-sided extension V = (Vt , t ∈ Z) of X, defined on a
probability space (Ω′′ , Σ′′ , P ′′ ). That is,
(A.16)

P ′′ (Vt+1 = j|Vt = i) = pij ,

−∞ < t < ∞

where pij denotes the probability
(A.17)

P (Xt+1 = j|Xt = i),

1≤t<∞

which is independent of t since X is Markoff. Such an extension is possible, see for example [9]. Denote by XZ , the set of doubly-infinite sequences
taking values in X. The Borel-sigma field on XZ is the standard construction, see Pages 1-5 of [10]. Note that V is finite-state, stationary, irreducible,
aperiodic.
∞ and as was the case when
Denote the Borel-sigma field on XZ by H−∞
b
defining Fa , denote the Borel sigma-field on Xba by Hab , −∞ ≤ a ≤ b ≤ ∞.
For the process V , consider the standard definition of ψ-mixing as stated
in [4], and thus, define
(A.18) ψV (τ ) , sup

sup

t
∞
′′
′′
t∈Z K∈Ht−∞ ,L∈H∞
t+τ +1 ,P (V−∞ ∈K)>0,P (Vt+τ +1 ∈L)>0
∞
t
∈ K, Vt+τ
P ′′ (V−∞
+1 ∈ L)
t
∞
′′
′′
P (V−∞ ∈ K)P (Zt+τ +1 ∈ L)

−1

The process V is said to be ψ-mixing if ψV (τ ) → 0 as τ → ∞. Since V is
stationary, irreducible, aperiodic, finite-state Markoff chain, by Theorem 3.1
of [4], V is ψ-mixing.
Let A ∈ F1t . Consider the set A′′ defined as follows:
(A.19)

A′′ = {(. . . , a−n , . . . a−1 , a0 , a1 , . . . , at )|(a1 , a2 , . . . , at ) ∈ A}

Then, since X is stationary and V is the double-sided extension of X,
(A.20)

t
P ′′ (V−∞
∈ A′′ ) = P (X1t ∈ A)

and by use of the Markoff property, and again, noting that V is the doublesided extension of X, it follows that
(A.21)

t
∞
t
∞
P ′′ (V−∞
∈ A′′ , Vt+τ
+1 ∈ B) = P (X1 ∈ A, Xt+τ +1 ∈ B)

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 243 — #25
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

243

By use of (A.20) and (A.21), it follows that
(A.22)
t
∞
∞
P ′′ (V−∞
∈ A′′ , Vt+τ
P (X1t ∈ A, Xt+τ
+1 ∈ B)
+1 ∈ B)
−
1
−1
=
t
∞
t
∞
′′
′′
′′
P (V−∞ ∈ A )P (Vt+τ +1 ∈ B)
P (X1 ∈ A)P (Xt+τ +1 ∈ B)
∞
t
∞
where A ∈ F1t , B ∈ Ft+τ
+1 , P (X1 ∈ A) > 0, P (Xt+τ +1 ∈ B) > 0.
Thus,

(A.23)
∞
t
P ′′ (V−∞
∈ A′′ , Vt+τ
+1 ∈ B)
−1
t
∞
P ′′ (V−∞ ∈ A′ )P ′′ (Vt+τ
+1 ∈ B)

sup
∞
t
∞
A∈F1t ,B∈Ft+τ
+1 ,P (X1 ∈A)>0,P (Xt+τ +1 ∈B)>0

=

∞
P (X1t ∈ A, Xt+τ
+1 ∈ B)
−1
t
∞
P (X1 ∈ A)P (Xt+τ +1 ∈ B)

sup
∞
t
∞
A∈F1t ,B∈Ft+τ
+1 ,P (X1 ∈A)>0,P (xt+τ +1 ∈B)>0

Thus,
(A.24)
sup
t
∞
t
∞
′′
′′
K∈G−∞
,L∈Gt+τ
+1 ,P (V1 ∈K)>0,P (Vt+τ +1 ∈L)>0

≥

sup
∞
t
∞
A∈F1t ,B∈Ft+τ
+1 ,P (X1 ∈A)>0,P (Xt+τ +1 B)>0

t
∞
P ′′ (V−∞
∈ K, Vt+τ
+1 ∈ L)
−1
t
∞
′′
′′
P (V−∞ ∈ K)P (Vt+τ +1 ∈ L)

∞
P (X1t ∈ A, Xt+τ
+1 ∈ B)
−1
t
∞
P (X1 ∈ A)P (Xt+τ +1 ∈ B)

t
∞
This is because there are sets K ∈ G−∞
and L ∈ Gt+τ
+1 which are not of the
′′
′′
form A and B respectively.
Denote the function ψ, defined in (18) for the process X by ψX . It follows
from (A.24) that ψZ (τ ) ≥ ψX (τ ) . Since Z is ψ-mixing as stated above, by
definition, ψZ (τ ) → 0 as τ → ∞. Thus, ψX (τ ) → 0 as τ → ∞, and thus, X
is ψ-mixing.


Proof of Lemma 4:
Proof. Stationary of Z follows directly from the definition of stationarity.
Denote the ψ function for X and Z by ψX and ψZ respectively. Note
that the ψ function for the process Z can be written as follows:
(A.25) ψZ (τ ) , sup

sup

∞
tL
∞
t∈N A∈F1tL ,B∈FtL+τ
L+1 ,P (X1 ∈A)>0,P (XtL+τ L+1 ∈B)>0

∞
P (X1tL ∈ A, XtL+τ
L+1 ∈ B)
−1
tL
∞
P (X1 ∈ A)P (XtL+τ L+1 ∈ B)

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 244 — #26
✐

✐

244

M. Agarwal, S. Mitter, and A. Sahai

Note that when calculating the ψ function for Z, the supremum is taken
over a lesser number of sets than when calculating the ψ function for X. It
follows that ψZ (τ ) ≤ ψX (τ ). Since X is ψ-mixing, ψX (τ ) → 0 as τ → ∞. It
follows that ψZ (τ ) → 0 as τ → ∞. Thus, Z is ψ-mixing.

Proof of Lemma 5:
Proof. Note that Z is stationary by Lemma 4. Thus, Z is a stationary,
irreducible, aperiodic, finite-state Markoff chain, evolving on a finite set,
and by Lemma 3 , ψ-mixing.
Since the set Z is finite, the Borel sigma field on Z∞ can be constructed
analogously to that on X∞ ; see Page 1-2 of [10]. Denote this Borel sigma
field by G ∞ . Define the Borel sigma fields Gab , analogously as was done for
F1∞ . Denote the underlying probability space by (Ω′ , Σ′ , P ′ )
An element of Z∞ is denoted by (z1 , z2 , . . .) where zi ∈ Z = XL . The j th
component of zi will be denoted by zi (j) .
Define
(A.26) ψX (τ ) , sup

sup

∞
t
∞
t∈N A∈F1t ,B∈Ft+τ
+1 ,P (X1 ∈A)>0,P (Xt+τ +1 ∈B)>0
∞
t
P (X1 ∈ A, Xt+τ
+1 ∈ B)
t
∞
P (X1 ∈ A)P (Xt+τ +1 ∈ B)

−1

and
(A.27) ψZ (τ ) =, sup

sup

∞
t
∞
′
′
′
′
t∈N A′ ∈G1t ,B′ ∈Gt+τ
+1 ,P (Z1 ∈A )>0,P (Zt+τ +1 ∈B )>0
′
∞
P ′ (Z1t ∈ A′ , Zt+τ
+1 ∈ B )
∞
′
P ′ (Z1t ∈ A′ )P ′ (Zt+τ
+1 ∈ B )

−1

By definition, the processes X and Z are ψ-mixing if ψX (τ ) and ψZ (τ )
tend to zero as τ → ∞, respectively.
∞
t
∞
For A ∈ F1t , B ∈ Ft+τ
+1 , P (X1 ∈ A) > 0, P (Xt+τ +1 ∈ B) > 0, define,
(A.28)

κX (t, τ, A, B) ,

∞
P (X1t ∈ A, Xt+τ
+1 ∈ B)
−1
t
∞
P (X1 ∈ A)P (Xt+τ +1 ∈ B)

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 245 — #27
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

245

Define

 
t
k1 ,
L


t+τ +1
k2 ,
L

(A.29)

Assume that τ ≥ 4L. It follows that k1 ≤ k2 (a weaker assumption is
possible, but this suffices).
Given A and B, define A′ and B′ by
(A.30)

A′ , {(a1 , a2 , . . . , ak1 L )|(a1 , a2 , . . . , at ) ∈ A}
B′ , {(bk2 L+1 , bk2 L+2 , . . .)|(bt+τ +1 , bt+τ +2 , . . .) ∈ B}

Think, now of (a1 , . . . , ak1 L ) as a′ = (a′1 , . . . , a′k1 ), a k1 length sequence,
where a′i ∈ Z. This can be done by defining a′i = aiL
(i−1)L+1 . Analogously,
′
′
′
′
think of (bk2 L+1 , bk2 L+2 , . . .) as (bk2 +1 , bk2 +2 , . . .) where b′ki is defined analogously to how a′i was defined. Think of A′ and B′ , now, as sequences of
elements in Z in the obvious way.
∞
Define, for J ∈ G1q , U ∈ Gq+q
′ +1 ,
(A.31)

κZ (q, q ′ , J, U) ,

∞
P ′ (Z1t ∈ J, Zt+τ
+1 ∈ U)
−1
t
∞
′
′
P (Z1 ∈ J)P (Zt+τ +1 ∈ U)

Then, it follows that for τ ≥ 4L,
(A.32)

κX (t, τ, A, B) = κZ (k1 , k2 − k1 , A′ , B′ )

Denote
(A.33) µX (t, τ ) =

sup
∞
t
∞
A∈F1t ,B∈Ft+τ
+1 ,P (X1 ∈A)>0,P (Xt+τ +1 ∈B)>0

∞
P (X1t ∈ A, Xt+τ
+1 ∈ B)
−1
t
∞
P (X1 ∈ A)P (Xt+τ +1 ∈ B)

µZ (q, q ′ ) =

sup
q
∞
∞
′
′
J∈G1q ,U∈Gq+q
′ +1 ,P (Z1 ∈J)>0,P (Zt+τ +1 ∈U)>0

∞
P ′ (Z1t ∈ J, Zt+τ
+1 ∈ U)
−1
t
∞
P ′ (Z1 ∈ J)P ′ (Zt+τ +1 ∈ U)

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 246 — #28
✐

✐

246

M. Agarwal, S. Mitter, and A. Sahai

∞
It follows from (A.32) by taking supremum over sets A ∈ F1t and B ∈ Ft+τ
+1
k1
∞
and then, noting that there are sets J ∈ G1 and U ∈ Gk2 +1 which are not of
the form A′ and B′ , that
  
  
t
t+τ +1
t
µX (t, τ ) ≤ µZ (k1 , k2 − k1 ) = µZ
(A.34)
,
−
L
L
L

Thus,
(A.35)

  
  
t
t+τ +1
t
ψX (τ ) ≤ sup µZ
,
−
L
L
L
t∈N

The right hand side in the above equation → 0 as τ → ∞ since Z is ψ−
mixing. Thus, ψX (τ ) → 0 as τ → ∞, and thus, X is ψ-mixing.


References
[1] M. Agarwal, A universal, operational theory of multi-user communication with fidelity criteria, Ph.D. thesis, Massachusetts Institute of
Technology (2012).
[2] M. Agarwal, S. K. Mitter, and A. Sahai, Layered black-box, behavioral
interconnection perspective and applications to the problem in communications, Part I: i.i.d. sources, Communications in Information and
Systems 17 (2017), no. 4, 193–217.
[3] R. Bradley, On the ψ-mixing condition for stationary random sequences,
Transactions of the American Mathematical Society 276 (1983), no. 1,
55–66.
[4] R. C. Bradley, Basic Properties of Strong Mixing Conditions. A Survey
and Some Open Questions, Probability surveys 2 (2005), 107–144.
[5] R. G. Gallager, Information theory and reliable communication, Wiley
(1968).
[6] R. M. Gray, Entropy and information theory, Springer-Verlag (2011).
[7] H. Kesten and G. L. O. Brien, Examples of mixing sequences, Duke
Mathematical Journal 43 (1976), no. 2, 405–415.
[8] Y. V. Prohorov and Y. A. Rozanov, Probability theory: basic concepts,
limit theorems, random processes, Die Grundlehren der Mathematischen
Wissenschaften in Einzeldarstellungen mit besonderer Berucksichtigung
der Anwendungsgebiete, Band 157, Springer-Verlag, 1st edition (1969).

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 247 — #29
✐

✐

Part II: stationary sources satisfying ψ-mixing criterion

247

[9] E. M. R. Douc and D. Stoffer, Nonlinear time series: theory, methods
and applications with R examples, Chapman and Hall/CRC, 1st edition
(2014).
[10] P. C. Shields, The ergodic theory of discrete sample paths, American
Mathematical Society (1996).
[11] E. Yang and J. C. Kieffer, On the redundancy of the fixed-database
Lempel-Ziv algorithm for φ-mixing sources, IEEE Transactions on Information Theory 43 (1997), no. 4, 1101–1111.
[12] Z. Zhang and E. Yang, An on-line universal lossy data compression
algorithm via continuous codebook refinement — Part 2: optimality for
phi-mixing source models, IEEE Transactions on Information Theory
42 (1996), no. 3, 822–836.
Navi Mumbai, 410210, Maharashtra, India
E-mail address: magar@alum.mit.edu
Laboratory for information and decision systems
Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology
Cambridge, MA 02139-4307, USA
E-mail address: mitter@mit.edu
Department of Electrical Engineering and Computer Sciences
University of California, Berkeley
Berkeley, CA 94720-1770, USA
E-mail address: sahai@eecs.berkeley.edu

✐

✐
✐

✐

✐

✐

“2-Agarwal” — 2018/3/28 — 3:34 — page 248 — #30
✐

✐

✐

✐
✐

✐

