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












Department of Electrical and Computer Engineering

Boston University

e1



 






Department of Electrical and Computer Engineering, Boston University









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. 


 

[class=AMS]
[Primary ]00K00  *
00K01
[; secondary ]00K02   *



* 





0.5





§ INTRODUCTION

Consider a random source which evolves on a finite set. It follows from existing  literature, see for example <cit.> and <cit.> (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  <cit.>). In this paper, it will be proved that the limit of the normalized rate-distortion 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 <cit.> and <cit.>. 
A work for rate-distortion theory for random processes is <cit.>. Much of the  classical point-to-point literature on rate distortion theory gets subsumed  under the books <cit.> and  <cit.>. Another reference is <cit.>. 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 <cit.> 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 <cit.>, <cit.>, and <cit.>.



§ NOTATION AND DEFINITIONS
 


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

    D_max≜max_x ∈𝕏, y ∈𝕐d(x,y), 
    D_min≜min _{x ∈𝕏, y ∈𝕐 | d(x,y) > 0} d(x,y)

In what follows, the distortion levels will be assumed to be strictly greater than 0.
For x^n ∈𝕏^n, y^n ∈𝕐^n, the n-letter rate-distortion measure is defined additively:

    d^n(x^n, y^n) ≜∑_i=1^n d(x^n(i), y^n(i))

where x^n(i) denotes the i^th component of x^n and likewise for y^n.

Let X_1, X_2, …, be a Markoff chain with transition probability matrix P, where each X_i is a random-variable on 𝕏.  For x, x' ∈𝕏, p_xx' 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. p_xx' 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 X_1 ∼π' denote the Markoff chain (X_1, X_2, …) by X_[π', P]. Recall that P is the transition probability matrix of the Markoff chain. X_[π',P] will be called the Markoff X_[π',P] chain. X^n_[π', P] will denote (X_1, X_2, …, X_n).

The above mentioned assumptions that 𝕏 = 𝕐, d(x,x) = 0 and d(x,y)> 0 is x ≠ 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:

<e^n, f^n>_1^∞, where e^n: 𝕏^n →{1, 2, …, 2^⌊ nR  ⌋} and f^n: {1, 2, …, 2^⌊ nR  ⌋}→𝕐^n.

 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 <e^n, f^n>_1^∞ such that 

    lim sup_n →∞ E  [  1/n d^n(X^n_π', f^n(e^n(X^n_[π', P])))  ] ≤ D



The infimum of all achievable rates is the rate-distortion function R^E_X_[π', P](D).

The block-independent approximation (henceforth shortened to BIA) X^T_[π',P] source is a sequence of random vectors (S_1, S_2, …, S_n, …), where S_i are independent, and ∀ i, S_i ∼ X^T_[π',P]. To simplify notation, we will sometimes denote (S_1, S_2, …) by S. S^n will denote (S_1, S_2, …, S_n). Note that BIA X^T_[π',P] source is an i.i.d. vector source and will also be called the vector i.i.d. X^T_[π',P] source. Since the BIA X^T_[π',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 X^T_[π',P] source is 𝕏^T and the source reproduction space is 𝕐^T. Denote these by 𝕊 and 𝕋 respectively. A generic point in 𝕊 is a T-length sequence s. The i^th component of s is denoted by s(i). A generic point in 𝕋 is a T-length sequence t. The i^th component of t is denoted by t(i). The single letter distortion measure is denoted by d' and is defined as d'(s,t) ≜∑_j=1^T d(s(j),t(j)). For s^n ∈𝕊^n, t^n ∈𝕋^n, the n-letter distortion measure d'^n is defined additively: d'^n(s^n, t^n) ≜∑_i=1^n d'(s^n(i),t^n(i)). Note that s can be thought of as either a scalar in 𝕊 or a T dimensional vector in 𝕏^T. With this identification, d' = d^T and d'^n can be thought of as d^nT. A rate R source code is a sequence <e^n, f^n>_1^∞, where e^n: 𝕊^n →{1, 2, …, 2^⌊ nR  ⌋} and f^n: {1, 2, …, 2^⌊ nR  ⌋}→𝕋^n. We say that rate R is achievable for source-coding the BIA X^T_[π',P] source within distortion-level D under the expected distortion criterion  if there exist a sequence of rate R source codes <e^n, f^n>_1^∞ such that 

    lim sup_n →∞ E  [  1/n d'^n(S^n, f^n(e^n(S^n)))  ] ≤ D
 
The infimum of all achievable rates corresponding to a given distortion level D is the operational rate-distortion function at that distortion level, henceforth denoted by 
R^E_X^T_[π',P](D). The normalized rate-distortion function at block-length T  and distortion level D is defined as 

    1/T R^E_X^T_[π',P](TD)

and the limit is

    lim_T →∞1/T R^E_X^T_[π',P](TD)

The theorems in this paper prove the equality of R^E_X_[π', P](D) and (<ref>), and that these functions do not depend on π'. The statements of these theorems are stated in Section <ref>. Before that, we carry out a discussion on the rate-distortion function of a non-stationary Markoff chain.


 §.§ Discussion

To be entirely correct, the rate-distortion function of a Markoff source should be defined as follows: Let n be the block-length. Denote U_i ≜ X_(i-1)n+1^in. Each U_i is thus, a random vector of length n. Let <e^n, f^n>_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:

    lim sup_n →∞sup_i ∈ℕ E  [1/n d^n(U_i, f^n(e^n (U_i)))  ]

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.


§ THE THEOREMS
 

R^E_X_[π', P](D) = R^E_X_[π,P](D) where π is the stationary distribution and π' is an arbitrary probability distribution on 𝕏


Follows from <cit.> or see Appendix <ref> for an independent proof tailored for Markoff chains.

 
For D > 0,

    lim_T →∞1/T R^E_X^T_[π', P](TD)


This theorem will be proved in Section <ref>.


    R^E_X_[π',P](D) = R^E_X_[π,P](D) = lim_T →∞1/T R^E_X^T_[π, P](TD) =lim_T →∞1/T R^E_X^T_[π', P](TD)

 where π is the stationary distribution and π' is an arbitrary distribution on 𝕏.


Follows from Theorems <ref>, <ref> and <cit.>, Pages 490-500.

In order to prove Theorem <ref>, we need more notation and this is the subject of the next section. The theorem is proved in the section following the next.


§ FURTHER NOTATION
 
The information-theoretic rate-distortion function of the vector i.i.d. X^T_[π',P] source is denoted and defined as

    R^I_X^T_[π',P](D) ≜inf_𝕎
    I(X^T; Y^T)

where X^T  ∼ X^T_[π',P]  and  𝕎  is the set of W: 𝕊→ℙ(𝕋) defined as

    𝕎≜{ W   | ∑_s ∈𝕊, y ∈𝕋
    p_X^T_[π',P](s)W(t|s) d'(s,t) ≤ D   . }
 
where p_X^T_[π',P] denotes the distribution corresponding to X^T_[π',P]. Note that 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 ∈𝕊. Denote by J_τ the projection transformation. 
J_τ(s) ≜ (s(τ+1), s(τ+2), … s(T)).
Fix s. Denote
𝔸≜{t ∈𝕊 |   J_τ(t) = J_τ(s) }.
Under the distribution induced by X^T_[π', P], the probability of the set 𝔸 is

    π'^(τ)(s(τ+1))∏_i=τ+1^T-1 p_s(i)s(i+1)

for some distribution π'^(τ) on 𝕏 which satisfies π'^(τ)(x) →π(x) as τ→∞ ∀ x ∈𝕏. Note further, that if π'=π, π'^(τ) = π. For x ∈𝕏, denote  
π'^(τ)(x) = π(x) + δ^(τ)(x)
where δ^(τ)(x) → 0 as τ→∞. δ^(τ)(x) may be negative.


Denote by J_τ(X^T_[π', P]), the probability distribution on 𝕏^T-τ which causes the probability of a sequence r ∈𝕏^T-τ to be

    π'^(τ)(r(1)) ∏_i=1^T-1 p_r(i)r(i+1)

Note that J_τ(X^T_[π', P]) is the marginal of X^T_[π', P] on the last T-τ dimensions. An i.i.d. source can be formed from J_τ(X^T_[π', P]) by taking  a sequence of independent random vectors, each distributed as J_τ(X^T_[π', P]). This will be called the vector i.i.d. J_τ(X^T_[π', P]) source. The rate-distortion function for the vector i.i.d. J_τ(X^T_[π', P]) source in defined in the same way as  the rate-distortion function for the vector i.i.d. X^T_[π', P] source: 
For T-τ length sequences, the single-letter distortion measure is defined as d”(p,q) = ∑_i=1^T-τ d(p(i), q(i)) where p ∈𝕏^T-τ, q ∈𝕐^T-τ.  The n-letter rate-distortion measure is defined additively: d”^n(p^n,q^n) = ∑_i=1^n d”(p^n(i), q^n(i)) where p^n ∈ (𝕏^T-τ)^n and q^n ∈ (𝕐^T-τ)^n. A sequence of rate R source codes is a sequence <e^n, f^n>_1^∞, where 
e^n: (𝕏^T-τ)^n →{1, 2, …, 2^⌊ nR  ⌋} 
and  f^n: {1, 2, …, 2^⌊ nR  ⌋}→(𝕐^T-τ)^n. The rate-distortion functions for i.i.d. J_τ(X^T_[π', P]) source when the distortion measure is d” is defined analogously as for the i.i.d. X^T_[π', P] vector source; the details are omitted. Denote the operational rate-distortion function for the vector i.i.d. J_τ(X^T_[π”, P]) source by R^E_J_τ(X^T_[π', P])(·) and  denote the information-theoretic rate-distortion function for the same source by R^I_J_τ(X^T_[π', P])(·).

For the same reason as that stated before regarding d', d” = d^T-τ and d”^n can be thought of as d^n(T-τ).



§ PROOF OF THE THEOREM <REF>
 
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,

    f(a) - f(a') ≤K/a(a'-a)




    f(a)-f(a') ≤K/a(a'-a) f(a)-f(a')/a'-a≤f(0)-f(a)/a
       f(a')-f(a)/a'-a≥f(a)-f(0)/a-0 (1-a/a' )f(0) + a/a' 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 <ref>:

By the rate-distortion theorem, R^E_X^T_[π', P](TD) = R^I_X^T_[π', P](TD).  Comparing definitions with <cit.>, Page 491,

    1/TR^I_X^T_[π, P](TD)    = R_T(D)

By Theorem 9.8.1 in <cit.>, it follows that

    lim_T →∞1/T R^E_X^T_[π, P](TD)

(<ref>) will be used crucially towards the end of the proof.

The proof follows three steps:


  * Bound the difference between R^E_J_τ (X^T_[π', P])(·) and R^E_J_τ (X^T_[π, P])(·).

  * Relate R^E_J_τ(X^T_[π', P])(·) and R^E_X^T_[π', P](·).

  * 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 R^E_J_τ (X^T_[π', P])(·) and R^E_J_τ (X^T_[π, P])(·). To this end, we first do the same for R^I_J_τ (X^T_[π', P])(·) and R^I_J_τ (X^T_[π, P])(·). To this end, denote the distribution  corresponding to J_τ(X^T_[π', P]) on 𝕏^T-τ by Q', and  the distribution corresponding to J_τ(X^T_[π, P]) by Q. The l^1 distance between Q' and Q,

    l^1(Q',Q)    ≜∑_x^t-τ∈𝕏^T-τ |Q'(x^T-τ) -  Q(x^T-τ ) |  
       = ∑_x^t-τ∈𝕏^t-τ |π'^(τ)(x^t-τ(1) - π^(τ)(x^t-τ(1)| ∏_i=1^T-τ-1p_x^t-τ(i)x^t-τ(i+1)
       =∑_x ∈𝕏 |δ^(τ)(x)| 
       ≜δ^(τ)

In the above calculation, we have used the fact that if π'=π, π'^(τ) = π.


Condition (Z) stated in <cit.> holds based on the assumptions we have made, Lemma 2 in <cit.> can be applied, and it follows that for τ sufficiently large (reasoning stated below after a few lines) and any T > τ,

    |  1/T-τ R^I_J_τ(X^T_[π', P])((T-τ)D) - 1/T-τ R^I_J_τ(X^T_[π, P])((T-τ)D)  | ≤ K δ^(τ)log1/δ^(τ)
 
where

    K = 1/T-τ7d^*/d̃log ( |𝕏^T-τ |  |𝕐^T-τ |  )

In (<ref>) , δ^(τ)log1/δ^(τ) is defined as zero if δ^(τ) is zero. |𝕏^T-τ| and |𝕐^T-τ| denote the cardinalities of the input and output spaces on which the random source J_τ(X^T_[π', P]) is defined. d^* is 
defined as

    d^*   ≜max_x^T-τ∈𝕏^T-τ, ^yT-τ∈𝕐^T-τ
                                   d”(x^T-τ, y^T-τ 
           = (T-τ) D_max

and
d̃ is defined as 

    d̃≜min_{ x^T-τ∈𝕏^T-τ, y^T-τ∈𝕐^T-τ |  
            d”(x^T-τ, y^T-τ) > 0} d”(x^T-τ, y^T-τ) 
                    = (T-τ) D_min


It follows that 

    K = 7 D_max/D_min 
             (log (|𝕏|) +  log (|𝕐|))


Note that K is a constant independent of T, τ, D.

Also, we said above that (<ref>) holds for τ sufficiently large: this is because by Lemma 2 in <cit.>, we need τ large enough so that

    δ^(τ)≤ 4 D_min/D_max

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 (<ref>) is independent of T, τ. It then follows from (<ref>) and the equality of information-theoretic and operational rate-distortion functions for i.i.d. sources, that for τ sufficiently large and any T > τ,

    |  1/T-τ R^E_J_τ(X^T_[π', P])((T-τ)D) - 1/T-τ R^E_J_τ(X^T_[π, P])((T-τ)D)  | ≤ K δ^(τ)log1/δ^(τ)
 
The bound (<ref>) will be used crucially later, towards the end of the proof.



Next step is to relate R^E_J_τ(X^T_[π', P])(·) and R^E_X^T_[π', P](·).
 We will argue the following:

    R^E_X^T_[π', P]((T-τ)D + τ D_max) ≤ R^E_J_τ(X^T_[π', P])((T-τ)D)

and

    R^E_J_τ(X^T_[π', P])(TD) ≤ R^E_X^T_[π', P](TD)

Very rough idea to prove (<ref>) is the following: Given a sequence of  rate R source codes for the vector i.i.d. J_τ(X^T_[π', P]) source, we can use the same sequence of rate R source-codes for the vector  i.i.d. X^T_[π', P] source by not coding the time-slots which were not projected onto when defining  J_τ(X^T_[π', P]). These banished slots will incur a maximum distortion of τ D_max per symbol of X^T_[π', P]. (<ref>) follows. See Appendix <ref> for precise argument.

Very rough idea to prove (<ref>) 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 <ref>. Note that J_τ(X^T_[π, P]) is a projection of X^T_[π, P] onto certain dimensions and the distortion measure over these dimensions is additive. (<ref>) follows from this.


Next, we get to Step 3. 
Assuming TD>τ D_max, by replacing D in (<ref>)  by

    D =  TD-τ D_max/T-τ
 
 and by  (<ref>), it follows that

    R^E_J_τ(X^T_[π', P])(TD) 
    ≤  R^E_X^T_[π', P](TD) 
     ≤ R^E_J_τ(X^T_[π', P]) ( TD-τ D_max)

It follows from (<ref>) by rearranging, that

    0 ≤  R^E_X^T_[π', P](TD) - R^E_J_τ(X^T_[π', P])(TD) ≤
     R^E_J_τ(X^T_[π', P]) ( TD-τ D_max) - R^E_J_τ(X^T_[π', P])(TD)

By noting that  R^E_J_τ(X^T_[π', P])(D) is a non-increasing, convex ∪ function of D which is upper bounded by (T-τ)log |𝕏| at D = 0, it follows, assuming that TD > τ D_max,  by Lemma <ref> that

    R^E_J_τ(X^T_[π', P]) ( TD-τ D_max) -  R^E_J_τ(X^T_[π', P])(TD)  ≤τ D_maxlog |𝕏|

















From (<ref>) and (<ref>), it follows that 

    lim_T →∞ [  1/TR^E_X^T_[π', P](TD)  -  1/TR^E_J_τ(X^T_[π', P])(TD)  ] = 0

Note further, by noting that R^E_X^T_[π', P](TD) ≤ T log |𝕏|, that 

    lim_T →∞ | 1/T-τR^E_X^T_[π', P](TD) -  1/TR^E_X^T_[π', P](TD)  |
    ≤lim_T →∞τ/T(T-τ) T log|𝕏| = 0








Also, by noting that R^E_J_τ(X^T_[π', P])(D) is a non-increasing, convex ∪ function of D which is upper bounded by (T-τ)|𝕏|, it follows by use of Lemma <ref> that

    lim_T →∞ | 1/T-τR^E_J_τ(X^T_[π', P])(TD) - 
     1/T-τR^E_J_τ(X^T_[π', P])((T-τ)D)   |   ≤
       lim_T →∞log|𝕏|/(T-τ)Dτ D → 0   T →∞







 
 
 
 


It follows, then, from (<ref>), (<ref>), (<ref>) and by noting that

    lim_n →∞ a_n + lim_n →∞ b_n + lim_n →∞ c_n = lim_n →∞ (a_n + b_n + c_n)
 
if the three limits on the left hand side exist (follows from definitions, see for example <cit.>), that

    lim_T →∞ [ 1/TR^E_X^T_[π', P](TD)  - 
                                                     1/T-τR^E_J_τ(X^T_[π', P])((T-τ)D)   ] = 0
 





From (<ref>) and (<ref>), it follows by the use of triangle inequality, that for τ sufficiently large and T > τ,

    | 1/TR^E_X^T_[π', P](TD)  - 
                                                     1/T-τR^E_J_τ(X^T_[π, P])((T-τ)D)  |
                                                      ≤ Kδ^(τ)log1/δ^(τ) + κ_τ,T

for some κ_τ,T→ 0 as T →∞.


The above equation holds for π' = π too, that is, for τ sufficiently large and T > τ,

    | 1/TR^E_X^T_[π, P](TD)  - 
                                                     1/T-τR^E_J_τ(X^T_[π, P])((T-τ)D)  |
                                                      ≤ Kδ^(τ)log1/δ^(τ) + η_τ,T

for some η_τ,T→ 0 as T →∞.

From (<ref>) and (<ref>), by use of the triangle inequality, it follows, that for τ sufficiently large and T > τ,


    |  1/TR^E_X^T_[π', P](TD)  - 1/TR^E_X^T_[π, P](TD)  |
    ≤ 2K δ^(τ)log1/δ^(τ)  + η_τ,T + κ_τ,T



From (<ref>) and (<ref>),  and by noting that δ^(τ)log1/δ^(τ)→ 0 as τ→∞, η_τ,T→ 0 as T →∞, and κ_τ,T→ 0 as T →∞, it follows that

    lim_T →∞1/TR^E_X^T_[π', P](TD)

This finishes the proof 

The assumptions 𝕏=𝕐, d(x,x) =0, d(x,y) > 0 if x ≠ 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.



§ Ψ-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 <cit.>, <cit.> and <cit.> for mixing of sources and <cit.>, <cit.>, in particular, for results on ψ-mixing sources. The main property (among others) that made ψ-mixing sources amenable to the result in <cit.> is the decomposition in Lemma 1 in <cit.>, wherein, a stationary ψ-mixing source is written as a convex combination of an i.i.d. distribution and another general distribution where the i.i.d. distribution dominates as memory is lost with time. Precisely, the equation is Equation (19) in <cit.>:

    (X_t+τ+1^t+τ+T∈𝔹|X_1^t ∈𝔸) = (1-λ_τ)P_T(𝔹) + λ_τ P'_t, τ, T, 𝔸(𝔹)

where λ_τ→ 0 as τ→∞. This lemma, though, required stationarity. If a variant of (<ref>) 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 P_T(𝔹) 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 <ref> in this paper is the l^1 distance between Q and Q', see (<ref>). This result will hold for sources which satisfy (<ref>) or a variant. Similarly, proving  (<ref>) and (<ref>) in the proof of Theorem <ref>  or similar equations  may also be possible. The rest of the proof of Theorem <ref>  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.



§ 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 <cit.>; this would help with generalization and insight into the `internal workings' of rate-distortion theory, too.



§ 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.
IEEEtran













§ PROOF OF THEOREM <REF>
 

Consider two Markoff chains X_[π', P] = (X'_1, X'_2, …) and X_[π”, P] = (X”_1, X”_2, …), where π' and π” probability distributions on 𝕏. 

Denote (X'_1, X'_2, …, X'_n) by X'^n and (X”_1, X”_2, …, X”_n) 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 distribution of X”_τ by μ”.  Denote, ϵ' = ∑_x ∈𝕏 |μ'(x) - π(x)| and ϵ” = ∑_x ∈𝕏 |μ”(x) - π(x)| , where π is the 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 <e^n, f^n>_1^∞ be a source-code. Let the block-length be n. Think of n large and τ^*_ϵ << n. Use (e^n, f^n) to code K'^n ≜ (X'_τ^*_ϵ+1, X'_τ^*_ϵ + 2, …, X'_τ^*_ϵ+n) and K”^n ≜ (X”_τ^*_ϵ+1, X”_τ^*_ϵ + 2, …, X”_τ^*_ϵ+n). 
Note that 

    | E  [  1/n d^n(K”^n, f^n(e^n(K'^n)))   ] - 
     E  [  1/n d^n(K'^n, f^n(e^n(K'^n)))  ]   |  ≤ϵ D_max

For δ > 0 (think of δ small), D > 0,  let <e'^n, f'^n>_1^∞ be a source-code with rate ≤ R^E_[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 X”_1, X”_2, …, X”_τ^*_ϵ arbitrarily. and code (X”_τ^*_ϵ+1, X”_τ^*_ϵ+2, …, X”_τ^*_ϵ+n) using (e'^n, f'^n). It follows, by calculation of the distortion achieved for (X”_1, X”_2, …, X”_τ^*+n) by use of this code, in the process, using (<ref>)

    R^E_X_[π”, P] (D+ τ^*_ϵ/τ^*_ϵ+n D_max + ϵ D_max ) ≤ R^E_X_[π', P](D) + δ

ϵ can be made arbitrarily small, τ^*_ϵ will depend on ϵ and n can be made arbitrarily large. It follows that for every α > 0, every δ > 0,
R^E_X_[π”, P](D + α ) ≤ R^E_X_[π', P](D) + δ.
By the continuity of R^E_X_[π', P](D) in D, it follows that ∀δ > 0
R^E_X_[π”, P](D) ≤ R^E_X_[π', P](D) + δ. It follows, then, since α > 0 can be arbitrarily small, that
R^E_X_[π”, P](D) ≤ R^E_X_[π', P](D).
By interchanging π' and π”, it follows that,
R^E_X_[π', P](D) ≤ R^E_X_[π”, P](D)
Thus,
R^E_X_[π', P](D) =  R^E_X_[π”, P](D).







§ PROOFS OF (<REF>) AND (<REF>)
 


To prove (<ref>): 

Let <e^n, f^n>_1^∞ be the source code for the  i.i.d. vector J_τ(X^T_[π, P]) source. 

Note that e^n: (𝕏^T-τ)^n →{1, 2, …, 2^⌊ nR  ⌋}  and  

f^n: {1, 2, …, 2^⌊ nR  ⌋}→(𝕐^T-τ)^n. 

Let s^n ∈𝕊^n be a realization of S^n, the n-blocklength vector i.i.d. X^T_[π, P] source which needs to be coded. 

s^n = (s^n(1), s^n(2), … s^n(n))
where each s^n(i) ∈𝕊: 

s^n(i) = (s^n(i)(1), s^n(i)(2), …, s^n(i)(T)).

Recall the projection operator,
J_τ(s^n(i)) = (s^n(i)(τ+1), …, s^n(i)(T)).


Denote
J^n_τ(s^n) = (J_τ(s^n(1)),J_τ(s^n(2)),…,J_τ(s^n(n))).


Then, J^n_τ(s^n) is an element of (𝕏^T-τ)^n. Denote f^n(e^n(J^n_τ(s^n))) = 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 ∈𝕐. 
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 <e^n ∘ J^n_τ,  E^n_τ∘ f^n>_1^∞ is a rate R source code to code the i.i.d. vector X^T_[π, P] source and that,
d'^n(s^n, E^n_τ(f^n(e^n(J^n_τ(s^n))))) ≤ d”^n(s'^n, t'^n) + n τ D_max.
(<ref>) follows.

To prove (<ref>):

Let (A,B) be a random vector on 𝔸×𝔹. Let (A_1, B_1), (A_2, B_2), … be a sequence where (A_i, B_i) are independent of each other and (A_i, B_i) ∼ (A, B). This sequence is the vector i.i.d (A, B) source. 𝔸×𝔹 is the source space. Let the source reproduction space be 𝔸' ×𝔹'. 
d_1: 𝔸×𝔸' → [0, ∞) is a distortion measure.
d_2: 𝔹' ×𝔹' → [0, ∞) is a distortion measure. 
Assume that 𝔸, 𝔸', 𝔹, 𝔹' are finite sets.
Define:
d_0((a,b), (a',b')) ≜ d_1(a,a') + d_2(b,b'). d_1^n and d_2^n, d_0^n are respectively defined additively from d_1, d_2 and d_0. We can then define the rate-distortion functions for the i.i.d. A source and the i.i.d. (A, B) source, denoted, respectively, by R^E_A(·) and R^E_(A, B)(·).
Then, 

    R^E_A(D) ≤ R^E_(A,B)(D)

(<ref>) is proved as follows: Given a code to code the i.i.d. (A,B) source,   think of B_is 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, (<ref>) 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, (<ref>) follows for deterministic codes.






