Communications in Information and Systems
Volume 0, Number 0, 1–9, 0000

arXiv:1803.09871v1 [cs.IT] 27 Mar 2018

Rate-distortion functions of non-stationary Markoff
chains and their block-independent approximations
Mukul Agarwal

It is proved that the limit of the normalized rate-distortion functions of block independent approximations of an irreducible, aperiodic Markoff chain is independent of the initial distribution of the
Markoff chain and thus, is also equal to the rate-distortion function
of the Markoff chain.
AMS 2000 subject classifications: Primary 00K00 *, 00K01; secondary 00K02 *.
Keywords and phrases: * .

1. Introduction
Consider a random source which evolves on a finite set. It follows from existing literature, see for example [1] and [2] (Pages 491-500, in particular, see
Definition (9.8.3) and Theorem 9.8.3 for achievability), that the limit of the
normalized rate-distortion functions of block-independent approximations of
a a stationary, ergodic source is equal to the rate-distortion function of the
source. Specializing this theorem to irreducible, aperiodic Markoff chains, it
follows that the limit of rate-distortion functions of block-independent approximations of an irreducible, aperiodic Markoff chain which starts in the
stationary distribution is equal to the rate-distortion function of this Markoff
chain. It is known that the rate-distortion function of an irreducible, aperiodic Markoff chain is independent of its initial distribution (follows from
[3]). In this paper, it will be proved that the limit of the normalized ratedistortion functions of block-independent approximations of an irreducible,
aperiodic Markoff chain is independent of its initial distribution. It follows,
then, that the rate-distortion function of an irreducible, aperiodic Markoff
chain and the limit of the normalized rate-distortion functions of its block
independent approximations are equal and these functions are independent
of the initial distribution of the Markoff chain.
Literature on rate-distortion theory is vast. The seminal works are [1] and [4].
A work for rate-distortion theory for random processes is [5]. Much of the
1

2
classical point-to-point literature on rate distortion theory gets subsumed
under the books [2] and [3]. Another reference is [6]. The reader is refered to
these three books and references therein for the literature on rate-distortion
theory. In particular, the reader is referred to [3] because non-stationary
sources are dealt with in great detail in this book, and the concern here is
with a non-stationary process, albeit, a non-stationary Markoff chain. For
understanding Markoff chains, the reader is referred to [7], [8], and [9].

2. Notation and definitions
X and Y denote the source input and source reproduction spaces respectively.
Both are assumed to be finite sets. Asume that X = Y. Assume that the
cardinality of X is greater than or equal to 2. d : X × Y → [0, ∞) is the
single-letter distortion measure. Assume that d(x, x) = 0 ∀x ∈ X and that
d(x, y) > 0 if x 6= y. Denote
(1)

Dmax , max d(x, y), Dmin ,
x∈X,y∈Y

min

{x∈X,y∈Y|d(x,y)>0}

d(x, y)

In what follows, the distortion levels will be assumed to be strictly greater
than 0. For xn ∈ Xn , y n ∈ Yn , the n-letter rate-distortion measure is defined
additively:
(2)

dn (xn , y n ) ,

n
X

d(xn (i), y n (i))

i=1

where xn (i) denotes the ith component of xn and likewise for y n .
Let X1 , X2 , . . ., be a Markoff chain with transition probability matrix P ,
where each Xi is a random-variable on X. For x, x′ ∈ X, pxx′ denotes the
probability that the Markoff chain is in state x′ at time t + 1 given that it
is in state x at time t. pxx′ is independent of t. Assume that the Markoff
chain is irreducible, aperiodic. This implies that it has a stationary distribution, henceforth denoted by π, which will be reserved exclusively for the
stationary distribution. In order to specify the Markoff chain completely, we
need to specify its initial distribution. If X1 ∼ π ′ denote the Markoff chain
(X1 , X2 , . . .) by X[π′ ,P ] . Recall that P is the transition probability matrix
n
of the Markoff chain. X[π′ ,P ] will be called the Markoff X[π′ ,P ] chain. X[π
′ ,P ]
will denote (X1 , X2 , . . . , Xn ).

3
The above mentioned assumptions that X = Y, d(x, x) = 0 and d(x, y) > 0
is x 6= y, that the distortion levels are strictly greater than zero, and that,
the Markoff chain is irreducible, aperiodic, will be made throughtout this
paper and will not be re-stated.
A rate R source-code is a sequence:
n
n
⌊nR⌋ } and f n : {1, 2, . . . , 2⌊nR⌋ } →
< en , f n >∞
1 , where e : X → {1, 2, . . . , 2
Yn .

We say that rate R is achievable for source-coding the Markoff X[π′ ,P ] 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 sup E
n→∞




1 n n n n n
d (Xπ′ , f (e (X[π′ ,P ] ))) ≤ D
n

E
(D).
The infimum of all achievable rates is the rate-distortion function RX
[π ′ ,P ]
T
The block-independent approximation (henceforth shortened to BIA) X[π
′ ,P ]
source is a sequence of random vectors (S1 , S2 , . . . , Sn , . . .), where Si are
T
independent, and ∀i, Si ∼ X[π
′ ,P ] . To simplify notation, we will sometimes
n
denote (S1 , S2 , . . .) by S. S will denote (S1 , S2 , . . . , Sn ). Note that BIA
T
X[π
′ ,P ] source is an i.i.d. vector source and will also be called the vector
T
T
i.i.d. X[π
′ ,P ] source. Since the BIA X[π ′ ,P ] source is an i.i.d vector source,
the rate-distortion function for it is defined in exactly the same way as for an
i.i.d. source. The details are as follows: The source input space for the BIA
T
T and the source reproduction space is YT . Denote these
X[π
′ ,P ] source is X
by S and T respectively. A generic point in S is a T -length sequence s. The ith
component of s is denoted by s(i). A generic point in T is a T -length sequence
t. The ith component of t is denoted by t(i). The single letter distortion
P
measure is denoted by d′ and is defined as d′ (s, t) , Tj=1 d(s(j), t(j)). For
sn ∈ Sn , tn ∈ Tn , the n-letter distortion measure d′n is defined additively:
P
d′n (sn , tn ) , ni=1 d′ (sn (i), tn (i)). Note that s can be thought of as either
a scalar in S or a T dimensional vector in XT . With this identification,
d′ = dT and d′n can be thought of as dnT . A rate R source code is a sequence
n
n
⌊nR⌋ } and f n : {1, 2, . . . , 2⌊nR⌋ } →
< en , f n >∞
1 , where e : S → {1, 2, . . . , 2
T
Tn . We say that rate R is achievable for source-coding the BIA X[π
′ ,P ] source
within distortion-level D under the expected distortion criterion if there exist

4
a sequence of rate R source codes < en , f n >∞
1 such that
(4)




1 ′n n n n n
lim sup E
d (S , f (e (S ))) ≤ D
n
n→∞

The infimum of all achievable rates corresponding to a given distortion level
D is the operational rate-distortion function at that distortion level, henceE
(D). The normalized rate-distortion function at
forth denoted by RX
T
′
[π ,P ]

block-length T and distortion level D is defined as
(5)

1 E
R T (T D)
T X[π′ ,P ]

and the limit is
(6)

1 E
R T (T D)
T →∞ T X[π′ ,P ]
lim

E
(D) and (6), and
The theorems in this paper prove the equality of RX
[π ′ ,P ]
′
that these functions do not depend on π . The statements of these theorems
are stated in Section 3. Before that, we carry out a discussion on the ratedistortion function of a non-stationary Markoff chain.

2.1. Discussion
To be entirely correct, the rate-distortion function of a Markoff source should
in
be defined as follows: Let n be the block-length. Denote Ui , X(i−1)n+1
.
n
n
∞
Each Ui is thus, a random vector of length n. Let < e , f >1 be a source
to code the source X[P,π′ ] . When the block length is n, we would like to
use the source-code successively over all intervals of time of block-length n.
Thus, it is more logical to define the distortion as:


1 n
n n
lim sup sup E
(7)
d (Ui , f (e (Ui )))
n
n→∞ i∈N
and correspondingly define the rate-distortion function. This does not end
up making a difference, and hence, we stick to the originally given definition
for distortion. Note that if π ′ = π, the stationary distribution, the sup in
the above definition can be removed since the distribution of X(i−1)n+1 is
independent of i.

5

3. The theorems
E
E
(D) where π is the stationary distribution
(D) = RX
Theorem 1. RX
[π,P ]
[π ′ ,P ]
′
and π is an arbitrary probability distribution on X

Proof. Follows from [3] or see Appendix A for an independent proof tailored
for Markoff chains.
Theorem 2. For D > 0,
(8)

1 E
R T (T D) exists, and is independent of π ′
T →∞ T X[π′ ,P ]
lim

This theorem will be proved in Section 5.
Theorem 3.
(9)
E
E
RX
(D) = RX
(D) = lim
[π,P ]
[π ′ ,P ]

T →∞

1 E
1 E
R T (T D) = lim RX
(T D)
T
[π ′ ,P ]
T →∞ T
T X[π,P ]

where π is the stationary distribution and π ′ is an arbitrary distribution on
X.
Proof. Follows from Theorems 1, 2 and [2], Pages 490-500.
In order to prove Theorem 2, we need more notation and this is the subject
of the next section. The theorem is proved in the section following the next.

4. Further notation
T
The information-theoretic rate-distortion function of the vector i.i.d. X[π
′ ,P ]
source is denoted and defined as
I
RX
T
′

(10)

[π ,P ]

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

T
where X T ∼ X[π
′ ,P ] and W is the set of W : S → P(T) defined as

(11)



W, W


X

s∈S,y∈T

T
(s)W (t|s)d′ (s, t) ≤ D
pX[π
′ ,P ]





6
T
T
denotes the distribution corresponding to X[π
where pX[π
′ ,P ] . Note that
′ ,P ]
this is the usual definition of the information-theoretic rate-distortion function for an i.i.d. source; just that the source under consideration is vector
i.i.d.

Let s ∈ S. Denote by Jτ the projection transformation. Jτ (s) , (s(τ +
1), s(τ + 2), . . . s(T )). Fix s. Denote A , {t ∈ S | Jτ (t) = Jτ (s)}. Under the
T
distribution induced by X[π
′ ,P ] , the probability of the set A is
(12)

π ′(τ ) (s(τ + 1))

TY
−1

ps(i)s(i+1)

i=τ +1

for some distribution π ′(τ ) on X which satisfies π ′(τ ) (x) → π(x) as τ → ∞
∀x ∈ X. Note further, that if π ′ = π, π ′(τ ) = π. For x ∈ X, denote π ′(τ ) (x) =
π(x) + δ(τ ) (x) where δ(τ ) (x) → 0 as τ → ∞. δ(τ ) (x) may be negative.
T
T −τ which causes
Denote by Jτ (X[π
′ ,P ] ), the probability distribution on X
the probability of a sequence r ∈ XT −τ to be

(13)

π

′(τ )

(r(1))

TY
−1

pr(i)r(i+1)

i=1

T
T
Note that Jτ (X[π
′ ,P ] ) is the marginal of X[π ′ ,P ] on the last T − τ dimensions.
T
An i.i.d. source can be formed from Jτ (X[π
′ ,P ] ) by taking a sequence of indeT
pendent random vectors, each distributed as Jτ (X[π
′ ,P ] ). This will be called
T
the vector i.i.d. Jτ (X[π′ ,P ] ) source. The rate-distortion function for the vecT
tor i.i.d. Jτ (X[π
′ ,P ] ) source in defined in the same way as the rate-distortion
T
function for the vector i.i.d. X[π
′ ,P ] source: For T − τ length sequences, the
P −τ
single-letter distortion measure is defined as d′′ (p, q) = Ti=1
d(p(i), q(i))
where p ∈ XT −τ , q ∈ YT −τ
.
The
n-letter
rate-distortion
measure
is defined
Pn
′′n
n
n
′′
n
n
n
T
−τ
n
additively: d (p , q ) = i=1 d (p (i), q (i)) where p ∈ (X
) and q n ∈
T
−τ
n
n
n
(Y
) . A sequence of rate R source codes is a sequence < e , f >∞
1 , where
n
e : (XT −τ )n → {1, 2, . . . , 2⌊nR⌋ } and f n : {1, 2, . . . , 2⌊nR⌋ } → (YT −τ )n . The
T
rate-distortion functions for i.i.d. Jτ (X[π
′ ,P ] ) source when the distortion meaT
sure is d” is defined analogously as for the i.i.d. X[π
′ ,P ] vector source; the
details are omitted. Denote the operational rate-distortion function for the
T
E
vector i.i.d. Jτ (X[π
′′ ,P ] ) source by RJ (X T
) (·) and denote the informationτ
′
[π ,P ]

theoretic rate-distortion function for the same source by RJI τ (X T ′

[π ,P ]

) (·).

7
For the same reason as that stated before regarding d′ , d′′ = dT −τ and d′′n
can be thought of as dn(T −τ ) .

5. Proof of the Theorem 2
Before we prove the theorem, note the following:
Lemma 1. Let f : [0, ∞) → [0, ∞) be a convex ∪ non-increasing function.
Let f (0) = K. Let 0 < a < a′ . Then,
f (a) − f (a′ ) ≤

(14)

K ′
(a − a)
a

Proof.
f (a) − f (a′ )
f (0) − f (a)
K ′
(a − a) ⇐=
≤
′
a
a −a
a

a
f (a′ ) − f (a)
f (a) − f (0)
a
⇐=
≥
⇐= 1 − ′ f (0) + ′ f (a′ ) ≥ f (a)
a′ − a
a−0
a
a
⇐= Definition of convexity, see for example [10]

(15)

f (a) − f (a′ ) ≤

This lemma is a direct result of the the definition of convexity and this
observation will be used crucially in the proof of the theorem , which follows
below.
Proof of Theorem 2:
E
Proof. By the rate-distortion theorem, RX
T
′

[π ,P ]

I
(T D) = RX
T
′

(T D). Com-

[π ,P ]

paring definitions with [2], Page 491,
(16)
1 I
R T (T D) (notation in this document) = RT (D) (notation in [2])
T X[π,P ]
By Theorem 9.8.1 in [2], it follows that
(17)

1 E
R T (T D) exists
T →∞ T X[π,P ]
lim

(17) will be used crucially towards the end of the proof.

8
The proof follows three steps:
1. Bound the difference between RJEτ (X T ′

[π ,P ]

2. Relate

RJEτ (X T ′ ) (·)
[π ,P ]

and

) (·)

and RJEτ (X T

[π,P ] )

(·).

E
(·).
RX
T
[π ′ ,P ]

3. Use these relations to prove the desired result by computing various
bounds.
The first step in the proof is to come up with a bound for the difference
between RJEτ (X T ′ ) (·) and RJEτ (X T ) (·). To this end, we first do the same
[π,P ]

[π ,P ]

for RJI τ (X T ′

[π ,P ]

I
) (·) and RJτ (X T

[π,P ]

) (·). To this end, denote the distribution cor-

T
T −τ by Q′ , and the distribution corresponding
responding to Jτ (X[π
′ ,P ] ) on X
T
1
′
to Jτ (X[π,P
] ) by Q. The l distance between Q and Q,

(18)

X

l1 (Q′ , Q) ,

Q′ (xT −τ ) − Q(xT −τ )

xt−τ ∈XT −τ

X

=

|π ′

(τ )

=

|δ

(τ )

T −τ
Y−1

pxt−τ (i)xt−τ (i+1)

i=1

xt−τ ∈Xt−τ

X

(xt−τ (1) − π (τ ) (xt−τ (1)|

(x)|

x∈X
(τ )

,δ

In the above calculation, we have used the fact that if π ′ = π, π ′(τ ) = π.
Condition (Z) stated in [11] holds based on the assumptions we have made,
Lemma 2 in [11] can be applied, and it follows that for τ sufficiently large
(reasoning stated below after a few lines) and any T > τ ,
(19)
1
1
1
RJI τ (X T ′ ) ((T − τ )D) −
RJI τ (X T ) ((T − τ )D) ≤ Kδ(τ ) log (τ )
[π,P
]
[π
,P
]
T −τ
T −τ
δ
where
(20)

K=


1 7d∗
log XT −τ YT −τ
T − τ d˜

9
In (19) , δ(τ ) log δ(τ1 ) is defined as zero if δ(τ ) is zero. |XT −τ | and |YT −τ | denote
the cardinalities of the input and output spaces on which the random source
T
∗ is defined as
Jτ (X[π
′ ,P ] ) is defined. d
(21)

d∗ ,

max

xT −τ ∈XT −τ ,yT −τ ∈YT −τ

d′′ (xT −τ , y T −τ = (T − τ )Dmax

and d˜ is defined as
(22)
d˜ ,

min

{xT −τ ∈XT −τ ,y T −τ ∈YT −τ

|

d′′ (xT −τ ,y T −τ )>0}

d′′ (xT −τ , y T −τ ) = (T − τ )Dmin

It follows that
K=7

(23)

Dmax
(log(|X|) + log(|Y|))
Dmin

Note that K is a constant independent of T, τ, D.
Also, we said above that (19) holds for τ sufficiently large: this is because
by Lemma 2 in [11], we need τ large enough so that
δ(τ ) ≤ 4

(24)

Dmin
Dmax

which is possible considering the fact that δ(τ ) → 0 as τ → ∞, and it is for
this reason that we require τ to be sufficiently large.
Note that the bound in (24) is independent of T, τ . It then follows from (19)
and the equality of information-theoretic and operational rate-distortion
functions for i.i.d. sources, that for τ sufficiently large and any T > τ ,
(25)
1
1
1
RE T
((T − τ )D) −
RE T ((T − τ )D) ≤ Kδ(τ ) log (τ )
T − τ Jτ (X[π′ ,P ] )
T − τ Jτ (X[π,P ] )
δ
The bound (25) will be used crucially later, towards the end of the proof.
E
(·). We will argue the followNext step is to relate RJEτ (X T ′ ) (·) and RX
T
[π ′ ,P ]
[π ,P ]
ing:

(26)

E
RX
T
′

[π ,P ]

((T − τ )D + τ Dmax ) ≤ RJEτ (X T ′

[π ,P ]

) ((T

− τ )D)

10
and
RJEτ (X T ′

(27)

[π ,P ]

) (T D)

E
(T D)
≤ RX
T
′
[π ,P ]

Very rough idea to prove (26) is the following: Given a sequence of rate
T
R source codes for the vector i.i.d. Jτ (X[π
′ ,P ] ) source, we can use the same
T
sequence of rate R source-codes for the vector i.i.d. X[π
′ ,P ] source by not codT
ing the time-slots which were not projected onto when defining Jτ (X[π
′ ,P ] ).
These banished slots will incur a maximum distortion of τ Dmax per symbol
T
of X[π
′ ,P ] . (26) follows. See Appendix B for precise argument.
Very rough idea to prove (27) is the following: Consider a two-dimensional
random vector (A, B) on some space and the i.i.d. source got by taking i.i.d.
copies of (A, B). Consider a distortion measure which is additive over the
two dimensions. Consider, also, the i.i.d. source formed by taking identical
copies of A. Then, for a given distortion level, the rate-distortion function of
the vector i.i.d. (A, B) source is greater than or equal to the rate-distortion
function of the i.i.d. A source. This is stated more rigorously in Appendix B.
T
T
Note that Jτ (X[π,P
] ) is a projection of X[π,P ] onto certain dimensions and
the distortion measure over these dimensions is additive. (27) follows from
this.
Next, we get to Step 3. Assuming T D > τ Dmax , by replacing D in (26) by
D=

(28)

T D − τ Dmax
T −τ

and by (27), it follows that
RJEτ (X T ′

(29)

[π ,P ]

) (T D)

E
(T D) ≤ RJEτ (X T ′
≤ RX
T
′

[π ,P ]

[π ,P ]

) (T D

− τ Dmax )

It follows from (29) by rearranging, that
(30)
E
0 ≤ RX
T
′

[π ,P ]

(T D) − RJEτ (X T ′

[π ,P ]

By noting that RJEτ (X T ′

[π ,P ]

) (T D)

) (D)

≤ RJEτ (X T ′

[π ,P ]

) (T D

− τ Dmax ) − RJEτ (X T ′

[π ,P ]

is a non-increasing, convex ∪ function of D

which is upper bounded by (T − τ ) log |X| at D = 0, it follows, assuming
that T D > τ Dmax , by Lemma 1 that
(31)

RJEτ (X T ′

[π ,P ]

) (T D

− τ Dmax ) − RJEτ (X T ′

[π ,P ]

) (T D)

≤ τ Dmax log |X|

) (T D)

11
From (31) and (30), it follows that
lim

(32)

T →∞




1 E
1 E
R T (T D) − RJτ (X T ′ ) (T D) = 0
[π ,P ]
T X[π′ ,P ]
T

E
Note further, by noting that RX
T
′

(T D) ≤ T log |X|, that

[π ,P ]

(33)
lim

T →∞

1
τ
1 E
(T D) ≤ lim
RE T (T D) − RX
T log |X| = 0
T
[π ′ ,P ]
T →∞ T (T − τ )
T − τ X[π′ ,P ]
T

Also, by noting that RJEτ (X T ′

[π ,P ]

) (D)

is a non-increasing, convex ∪ function

of D which is upper bounded by (T − τ )|X|, it follows by use of Lemma 1
that
(34)
lim

T →∞

1
1
((T − τ )D) ≤
RJEτ (X T ′ ) (T D) −
RE T
[π ,P ]
T −τ
T − τ Jτ (X[π′ ,P ] )
log |X|
lim
τ D → 0 as T → ∞
T →∞ (T − τ )D

It follows, then, from (32), (33), (34) and by noting that
(35)

lim an + lim bn + lim cn = lim (an + bn + cn )

n→∞

n→∞

n→∞

n→∞

if the three limits on the left hand side exist (follows from definitions, see
for example [10]), that
(36)

lim

T →∞




1
1 E
E
((T − τ )D) = 0
R T (T D) −
R
T
T X[π′ ,P ]
T − τ Jτ (X[π′ ,P ] )

From (25) and (36), it follows by the use of triangle inequality, that for τ
sufficiently large and T > τ ,
(37)
1
1
1 E
RX T ′ (T D) −
RJEτ (X T ) ((T − τ )D) ≤ Kδ(τ ) log (τ ) + κτ,T
[π,P ]
[π ,P ]
T
T −τ
δ
for some κτ,T → 0 as T → ∞.

12
The above equation holds for π ′ = π too, that is, for τ sufficiently large and
T > τ,
(38)
1 E
1
1
RX T (T D) −
RJEτ (X T ) ((T − τ )D) ≤ Kδ(τ ) log (τ ) + ητ,T
[π,P ]
[π,P ]
T
T −τ
δ
for some ητ,T → 0 as T → ∞.
From (37) and (38), by use of the triangle inequality, it follows, that for τ
sufficiently large and T > τ ,

(39)

1
1 E
1 E
(T D) ≤ 2Kδ(τ ) log (τ ) + ητ,T + κτ,T
RX T ′ (T D) − RX
T
[π,P ]
[π ,P ]
T
T
δ

From (39) and (17), and by noting that δ(τ ) log δ(τ1 ) → 0 as τ → ∞, ητ,T → 0
as T → ∞, and κτ,T → 0 as T → ∞, it follows that
(40)

lim

T →∞

1 E
R T (T D) exists and is independent of π ′
T X[π′ ,P ]

This finishes the proof
The assumptions X = Y, d(x, x) = 0, d(x, y) > 0 if x 6= y which have
been made are not necessary, and can be replaced by weaker assumptions.
Nothing is lost in terms of idea of the proof by making these assumptions,
and making these assumptions prevents one from thinking of pathological
cases; for these reasons they have been made.

6. ψ-mixing sources or a variant?
A set of sources to which this result may be generalizable with the proof
technique used is ψ-mixing sources or close variants, appropriately defined.
See [12], [13] and [14] for mixing of sources and [13], [14], in particular,
for results on ψ-mixing sources. The main property (among others) that
made ψ-mixing sources amenable to the result in [14] is the decomposition
in Lemma 1 in [14], wherein, a stationary ψ-mixing source is written as a
convex combination of an i.i.d. distribution and another general distribution

13
where the i.i.d. distribution dominates as memory is lost with time. Precisely,
the equation is Equation (19) in [14]:
(41)

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

where λτ → 0 as τ → ∞. This lemma, though, required stationarity. If a
variant of (41) would hold for non-stationary sources, then, there is a possibility that the result in this paper be generalized to such sources. Irreducible,
aperiodic Markoff chains statisfy this property, with PT (B) taken as the stationary distribution, and P ′ is some distribution depending on the initial
distribution of the Markoff chain. An important bound in proving Theorem
2 in this paper is the l1 distance between Q and Q′ , see (18). This result will
hold for sources which satisfy (41) or a variant. Similarly, proving (26) and
(27) in the proof of Theorem 2 or similar equations may also be possible.
The rest of the proof of Theorem 2 is bounding various differences of ‘close
by’ rate-distortion functions and this may be possible too. This is just an
idea at this point and needs to be studied carefully to see if any of this is at
all possible.

7. Recapitulation and research directions
In this paper, it was proved that the limit of the normalized rate-distortion
functions of block independent approximations of an irreducible, aperiodic
Markoff chain is independent of the initial distribution and is equal to the
rate-distortion function of the Markoff chain.
It would be worthwhile trying to generalize this theorem to ergodic sources
to the extent possible, not necessarily Markoff sources, in particular, to ψmixing sources; this would not only make the result general, but also shed
light on the ‘internal workings’ of rate-distortion theory. Further, it would be
worthwhile trying to prove this result using existing literature, in particular,
see if it follows directly from some result, for example, in [3]; this would help
with generalization and insight into the ‘internal workings’ of rate-distortion
theory, too.

8. Acknowledgements
The author is infinitely grateful to Prof. Robert Gray for ten’s of hours of
his time spent in insightful discussions with the author.

14

References
[1] C. E. Shannon, “Coding theorems for a discrete source with a fidelity
criterion,” Institute of Radio Engineers, National Convention Record,
vol. 7, part 4, pp. 142–163, March 1959.
[2] R. G. Gallager, Information theory and reliable communication. Wiley,
January 1968.
[3] R. M. Gray, Entropy and information theory. Springer-Verlag, February 2011.
[4] C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379–423 (Part 1) and pp. 623–656
(Part 2), July (Part 1) and October (Part 2) 1948.
[5] A. N. Kolmogorov, “Theory of transmission of information,” Acad. R.
P. Romine An. Romino-Soviet, vol. 28, no. 1, pp. 5–33, 1959, translated
in American Mathematical Society Translations, Series 2, Volume 33,
1963.
[6] T. Berger, Rate-distortion theory: mathematical basis for data compression, ser. Prentice-Hall series in information and system sciences. Prentice Hall, October 1971.
[7] B. V. Gnedenko, The theory of probability.
pany, New York, N. Y., 1962.

Chelsea Publishing Com-

[8] A. N. Shiryaev, Probability, 2nd ed. Springer, 1984.
[9] W. Feller, An introduction to probability theory and its applications,
Volume 1, 3rd ed. Wiley, 1968.
[10] V. A. Zorich, Mathematical Analysis, I and II. Springer, March 2016.
[11] H. Palaiyanur and A. Sahai, “On the uniform continuity of the ratedistortion function,” in 2008 IEEE International Symposium on Information Theory.
[12] Y. V. Prohorov and Y. A. Rozanov, Probability theory: basic concepts,
limit theorems, random processes, 1st ed., ser. Die Grundlehren der
Mathematischen Wissenschaften in Einzeldarstellungen mit besonderer
Berucksichtigung der Anwendungsgebiete, Band 157. Springer-Verlag,
1969.
[13] R. C. Bradley, “Basic properties of strong mixing conditions. a survey
and some open questions,” Probability surveys, vol. 2, pp. 107–144, 2005.

15
[14] M. Agarwal, S. Mitter, and A. Sahai, “Layered black-box, behavioral interconnection perspective and applications to problems in communications, Part II: sources satisfying ψ-mixing criterion,” Communications
in Information and Systems, vol. 17, no. 4, 2017.

Appendix A. Proof of Theorem 1
Proof. Consider two Markoff chains X[π′ ,P ] = (X1′ , X2′ , . . .) and X[π′′ ,P ] =
(X1′′ , X2′′ , . . .), where π ′ and π ′′ probability distributions on X.
Denote (X1′ , X2′ , . . . , Xn′ ) by X ′ n and (X1′′ , X2′′ , . . . , Xn′′ ) by X ′′ n . Let τ be
an integer. Think of n as large and τ to be much smaller than n. Denote
the distribution
of Xτ′ by µ′ and the
of Xτ′′ by µ′′ . Denote,
P distribution
P
′′
′
′′
′
ǫ =
x∈X |µ (x) − π(x)| , where π is the
x∈X |µ (x) − π(x)| and ǫ =
stationary distribution of the Markoff chain (note that both Markoff chains
have the same transition probability matrix P ). For every ǫ > 0, ∃τǫ∗ such
that ǫ′ < 2ǫ and ǫ′′ < 2ǫ ∀τ ≥ τǫ∗ . Let < en , f n >∞
1 be a source-code. Let
∗
the block-length be n. Think of n large and τǫ << n. Use (en , f n ) to code
K ′ n , (Xτ′ ǫ∗ +1 , Xτ′ ǫ∗ +2 , . . . , Xτ′ ǫ∗ +n ) and K ′′ n , (Xτ′′ǫ∗ +1 , Xτ′′ǫ∗ +2 , . . . , Xτ′′ǫ∗ +n ).
Note that
(42)




1 n ′n n n ′n
1 n ′′ n n n ′ n
d (K , f (e (K ))) − E
d (K , f (e (K ))) ≤ ǫDmax
E
n
n


For δ > 0 (think of δ small), D > 0, let < e′ n , f ′ n >∞
1 be a source-code
E
with rate ≤ R[P,π′ ] (D) + δ to code the X[P,π′ ] source with distortion D.
Construct a source code < e′′ n , f ′′ n >∞
1 to code the X[P,π ′′ ] source as follows. When the block-length is n + τǫ∗ , code X1′′ , X2′′ , . . . , Xτ′′ǫ∗ arbitrarily. and
code (Xτ′′ǫ∗ +1 , Xτ′′ǫ∗ +2 , . . . , Xτ′′ǫ∗ +n ) using (e′ n , f ′ n ). It follows, by calculation of
the distortion achieved for (X1′′ , X2′′ , . . . , Xτ′′∗ +n ) by use of this code, in the
process, using (42)


τǫ∗
E
E
RX[π′′ ,P ] D + ∗
(43)
(D) + δ
Dmax + ǫDmax ≤ RX
[π ′ ,P ]
τǫ + n
ǫ can be made arbitrarily small, τǫ∗ will depend on ǫ and n can be made arbiE
(D + α) ≤
trarily large. It follows that for every α > 0, every δ > 0, RX
[π ′′ ,P ]
E
E
(D) in D, it follows that ∀δ > 0
(D) + δ. By the continuity of RX
RX
[π ′ ,P ]
[π ′ ,P ]

16
E
E
(D)+ δ. It follows, then, since α > 0 can be arbitrarily
(D) ≤ RX
RX
[π ′ ,P ]
[π ′′ ,P ]
E
E
(D). By interchanging π ′ and π ′′ , it follows
(D) ≤ RX
small, that RX
[π ′ ,P ]
[π ′′ ,P ]
E
E
E
E
(D).
(D) = RX
(D) Thus, RX
(D) ≤ RX
that, RX
[π ′′ ,P ]
[π ′ ,P ]
[π ′′ ,P ]
[π ′ ,P ]

Appendix B. Proofs of (26) and (27)
To prove (26):
T
Proof. Let < en , f n >∞
1 be the source code for the i.i.d. vector Jτ (X[π,P ] )
source.

Note that en : (XT −τ )n → {1, 2, . . . , 2⌊nR⌋ } and
f n : {1, 2, . . . , 2⌊nR⌋ } → (YT −τ )n .
T
Let sn ∈ Sn be a realization of S n , the n-blocklength vector i.i.d. X[π,P
]
source which needs to be coded.

sn = (sn (1), sn (2), . . . sn (n)) where each sn (i) ∈ S:
sn (i) = (sn (i)(1), sn (i)(2), . . . , sn (i)(T )).
Recall the projection operator, Jτ (sn (i)) = (sn (i)(τ + 1), . . . , sn (i)(T )).
Denote Jτn (sn ) = (Jτ (sn (1)), Jτ (sn (2)), . . . , Jτ (sn (n))).
Then, Jτn (sn ) is an element of (XT −τ )n . Denote f n (en (Jτn (sn ))) = t′n .
Note that t′n = (t′n (1), t′n (2), . . . , t′n (n)) where
t′n (i) = (t′n (i)(1), t′n (i)(2), . . . , t′n (i)(T − τ )).
Fix a random y ∈ Y. Define the extension transformation,
Eτ (t′n (i)) = (y, y, . . . , y, t′n (i)(1), t′n (i)(2), . . . , t′n (i)(T − τ )), where the initial y’s occur τ times.
Denote Eτn (t′n ) = (Eτ (t′n (1)), Eτ (t′n (2)), . . . , Eτ (t′n (n))).
Note that < en ◦ Jτn , Eτn ◦ f n >∞
1 is a rate R source code to code the i.i.d.
T
′n (sn , E n (f n (en (J n (sn ))))) ≤ d′′n (s′n , t′n ) +
vector X[π,P
source
and
that,
d
τ
τ
]
nτ Dmax . (26) follows.
To prove (27):

17
Proof. Let (A, B) be a random vector on A × B. Let (A1 , B1 ), (A2 , B2 ), . . .
be a sequence where (Ai , Bi ) are independent of each other and (Ai , Bi ) ∼
(A, B). This sequence is the vector i.i.d (A, B) source. A × B is the source
space. Let the source reproduction space be A′ × B′ . d1 : A × A′ → [0, ∞) is
a distortion measure. d2 : B′ × B′ → [0, ∞) is a distortion measure. Assume
that A, A′ , B, B′ are finite sets. Define: d0 ((a, b), (a′ , b′ )) , d1 (a, a′ )+d2 (b, b′ ).
dn1 and dn2 , dn0 are respectively defined additively from d1 , d2 and d0 . We can
then define the rate-distortion functions for the i.i.d. A source and the i.i.d.
E (·) and RE
(A, B) source, denoted, respectively, by RA
(A,B) (·). Then,
(44)

E
E
RA
(D) ≤ R(A,B)
(D)

(44) is proved as follows: Given a code to code the i.i.d. (A, B) source, think
of Bi s as a source of common randomness, and use the obvious variant of
the same code for coding the i.i.d. A source. Since the same code is used,
(44) follows. Existence of a random code with a certain distortion implies
the existence of a deterministic code with the same or lesser distortion. From
this, (44) follows for deterministic codes.
Mukul Agarwal
Department of Electrical and Computer Engineering
Boston University
E-mail address: magar@alum.mit.edu
Received December 7, 2012

