Fixed-Length Strong Coordination
Giulia Cervia Tobias Oechtering Mikael Skoglund



Dust emissivity and absorption cross section 
 in DustPediaDustPedia is a collaborative focused research project supported by the European Union under the Seventh Framework Programme (2007- 2013) call (proposal no. 606824, P.I. J. I. Davies, http://www.dustpedia.com). The DustPedia data is publicly available at http://dustpedia.astro.noa.gr. 
  late-type galaxies
    
S. Bianchi1
V. Casasola2,1
M. Baes3
C. J. R. Clark4
E. Corbelli1
J. I. Davies5
I. De Looze6,3
P. De Vis5
W. Dobbels3
M. Galametz7
F. Galliano7
A. P. Jones8
S. C. Madden7
L. Magrini1
A. Mosenkov9,10
A. Nersesian11,12
S. Viaene13,3
E. M. Xilouris11
N. Ysard8

    
=============================================================================================================================================================================================================================================================================================================================================================================




  
We consider the problem of synthesizing joint distributions of signals and actions over noisy channels in the finite-length regime.
For a fixed blocklength n and an upper bound on the distance ε, a coding scheme is proposed such that the induced joint distribution is ε-close in L^1 distance to a target i.i.d. distribution. 
The set of achievable target distributions and rate for asymptotic strong coordination can be recovered from the main result of this paper by having n that tends to infinity.
 
 
 




§ INTRODUCTION


The problem of cooperation of autonomous devices in a decentralized  network, initially raised in the context of game theory by  <cit.>, has been introduced in information theory in <cit.>. Instead of using the channel between the agents to convey information reliably, coordination is intended as a way to induce a prescribed behavior. Two metrics to measure the level of coordination have been defined: empirical coordination, which requires the empirical distribution
of the actions to approach a target distribution with high probability, and strong coordination, which requires the L^1 distance of the distribution of sequences of actions to converge to an i.i.d. target distribution <cit.>.

While a number of works have studied  the strong coordination region with error free links, namely <cit.>, only a few works have focused on coordination with noisy channels.  However, since in a realistic scenario the communication links are usually noisy, and the signals exchanged over the physical channel are a part of what can be observed, we investigate joint strong coordination of signals and actions over a noisy links as in <cit.>. 

We consider a two-node network composed of an information source and a noisy channel, in which both nodes have access to a common source of randomness. Although the exact coordination region is still unknown, <cit.> presents an inner and an outer bound for the region.
For the inner bound derived in <cit.>, <cit.> proposes a practical polar coding scheme which achieves strong coordination. However, the computational cost of polar codes makes them impractical for delayed-constraint applications because it involves a chaining construction over a large number of blocks. 

For this reason, we investigate strong coordination in the finite-length regime for the same point-to-point setting of <cit.>, introducing the notion of fixed-length strong coordination.
Using the finite-length techniques of <cit.>, combined with the random binning approach inspired by <cit.>, we present an inner bound for the fixed-length strong coordination region.
We develop a joint source-channel scheme in which an auxiliary codebook allows us to jointly coordinate signals and actions.

The rest of the document is organized as follows. 
 introduces the notation and some preliminary results, and describes the model under investigation.  In particular, the results on strong coordination in the asymptotic setting are recalled.

Then,  studies the problem of strong coordination in the non-asymptotic setting, and derives an inner bound for the fixed-length strong coordination region.






§ SYSTEM MODEL AND BACKGROUND






 §.§ Preliminaries

We define the integer interval a,b as the set of integers between a and b.
We use the notation ‖·‖_1  and 𝔻 (··) to denote the L^1  distance  and Kullback-Leibler (K-L) divergence respectively.  


We recall some useful definition and results.


Given A ∼ P_A and (A,B) ∼ P_AB


  * Information: h_P_A(a)log1/P_A(a);

  * Conditional information:
h_P_A|B (a|b)log1/P_A|B(a|b);

  * Information density: _P_AB(a,b)logP_AB(a,b)/P_A(a) P_B(b).









  * ‖ P_A- P̂_A‖_1≤‖ P_AB-P̂_AB‖_1, see <cit.>,

  * ‖ P_A- P̂_A‖_1=‖ P_AP_B|A-P̂_A P_B|A‖_1, see <cit.>,


  *  If ‖ P_A P_B|A- P'_A P'_B|A‖_1 = ε,  then 
there exists a ∈𝒜 such that 
‖ P_B|A=a-P'_B |A= a‖_1≤ 2 ε, see <cit.>.






A coupling of  P_A and P_A' on  𝒜 is any  
P̂_AA' on 𝒜×𝒜  whose marginals are P_A and P_A'.



Given A ∼ P_A, A' ∼ P_A', any coupling 
P̂_AA' of P_A, P_A' satisfies

    ‖ P_A- P_A'‖_1≤ 4  ℙ_P̂_AA'{A ≠ A'}.

















 §.§ Point-to-point setting

We consider the two-nodes network of Figure <ref>, comprised of an i.i.d. source with distribution P̅_U, and a discrete memoryless channel  P̅_Y |X.
Two agents, an encoder and a decoder, share a source of common randomness C ∈ 1,2^nR_0.
The encoder selects a signal X^n= f_n(U^n,  C),  f_n: 𝒰^n  × 1,2^nR_0→𝒳^n, which is is transmitted over P̅_Y |X.
The decoder observes  Y^n and common randomness C, and it selects an action V^n = g_n(Y^n, C), g_n: 𝒴^n  × 1,2^nR_0→𝒱^n.
For block length n, the pair (f_n , g_n )  constitutes a code. 







 §.§ Asymptotic case



In the asymptotic regime, a pair (P̅_UXYV, R_0) is achievable for strong coordination  for the setting of Figure <ref> if  



    lim_n →∞‖ P_U^n  X^n Y^n  V^n- P̅_UXYV^⊗ n‖_1=0,
where P_U^n X^n Y^n  V^n is the joint distribution induced by the code, and the strong coordination region is the closure of the set of achievable  (P̅_UXYV, R_0) (see <cit.>).

While the joint strong coordination region of signals (X^n and Y^n) and actions (U^n and V^n) is still unknown, the best known inner bound is derived in <cit.>:



    [l]
    (P̅_UXYV,R_0) : 
      P̅_UXYV=P̅_UP̅_X|UP̅_Y|XP̅_V|UXY
      ∃  W∈𝒲,   W ∼P̅_W|UXYV s.t. 
      P̅_UWXYV=P̅_UP̅_W|UP̅_X|UWP̅_Y|XP̅_V|WY
       I(W;U) ≤ I(W;Y)
       R_0 ≥ I(W;UXV|Y)
    .





 In <cit.>,  the key idea of the achievability proof is to define two coding schemes: a random binning scheme for the target i.i.d. distribution, and a random coding scheme which and to prove that they have the same statistics through  output statics of random binning.








§ NON-ASYMPTOTIC CASE 




We introduce the notion of fixed-length strong coordination.
[Fixed-length strong coordination]
A pair (P̅_UXYV, R_0) is (ε,n)-achievable for strong coordination if for a fixed n>0,
there exists ε>0 and a code (f_n,g_n) with common randomness rate R_0, such that

    ‖ P_U^n  X^n Y^n  V^n- P̅_UXYV^⊗ n‖_1≤ε,

where P_U^n X^n Y^n  V^n is the joint distribution induced by the code.
Then, the  fixed-length strong coordination region ℛ is the closure of the set of achievable  (P̅_UXYV, R_0).




For the setting of Figure <ref>, the main result of this paper is the following inner bound for the fixed-length n strong coordination region when ε is a multiple of 1/√(n). 




[Inner bound]
Let P̅_U and P̅_Y|X be the given source and channel distributions, then 
ℛ_in⊆ ℛ:



    ℛ_in[l]
    (P̅_UXYV,R_0) :
      P̅_UXYV=P̅_UP̅_X|UP̅_Y|XP̅_V|UXY
      ∃ W∈𝒲,  W ∼P̅_W|UXYV s.t. 
      P̅_UWXYV=P̅_UP̅_W|UP̅_X|UWP̅_Y|XP̅_V|WY
       I(W;U) ≤ I(W;Y) + c_1 ε  +  O( log n/n) 
       I(W;U) + + Q^-1(c_2 ε +O( 1/√(n) ) ) √(V_P̅/n)
       R_0 ≥  I(W;UXV|Y) +c_3  ε+  O(log n/n ) 
       R_0 + + Q^-1(c_2  ε + O( 1/√(n))) √(V_P̅/n)
where the constants (c_1, c_2, c_3) are defined in (<ref>), Q(t)= ∫_t^∞1/√(2 π) e^-x^2/2 dx  is the tail distribution function of the standard normal distribution, and V_P̅ is the dispersion of the channel P̅_Y|W as defined in <cit.>.





  
*Outline of the proof of Theorem <ref>
The achievability proof is based on  non-asymptotic  output statics of random binning <cit.> and requires the following steps:


  A. preliminary definitions and results on random binning;

  B. two schemes are defined  for the one-shot problem, a random binning and a random coding scheme;

  C. the scheme is generalized  for a fixed n, by repeating the  one-shot scheme n times. Using the properties of random binning, it is possible to derive an upper bound on the  L^1 distance between the i.i.d. random binning distribution P^RB and random coding distribution P^RC. With common randomness greater than H(W|Y)+constant·ε, a first bound on ‖ P^RB - P^RC‖_1 is found.
Then, a second bound ε_Tot is recovered, by reducing the rate of common randomness to obtain the conditions in (<ref>).

  D. the term ε_Tot is analyzed;

  E. the rate conditions are summarized.




 
Observe that, as we will see in Section <ref>,  the final  bound ε_Tot on  the L^1 distance between P^RB and P^RC is worst than the one found in Section <ref>.
However, by worsening the L^1 distance, we reduce the rate of common randomness.
 




Note that, for both the asymptotic and the fixed-length case, the decomposition of the target joint distribution is the same (see (<ref>) and (<ref>)). Perhaps more interestingly,  in the asymptotic regime ε vanishes, and 

    constant·ε+ O (log n/n)+ Q^-1(constant·ε + O( 1/√(n))) √( V_P̅/n)
goes to zero since log n/n goes to zero and so does the last term because 

    √( V_P̅)Q^-1(constant·ε + O( 1/√(n)))/√(n)∼√( V_P̅)log√(n)/√(n)→ 0.
Hence, we can recover the inner bound for the asymptotic region of (<ref>) from the inner bound for the fixed-length  (<ref>). 
Moreover, the bound ε_Tot on the  L^1 distance between the two distribution goes to zero as 1/√(n), as we will see in (<ref>).








 §.§ Preliminaries on random binning

Let (A,B) ∼ P_AB be a discrete source and 
φ: 𝒜 → 1,2^R, a ↦ k, be a uniform random binning of A, with Kφ(A).
We denote the distribution induced by the binning as

    P^RB (a,b,k ) P_AB(a,b)  1 {φ(a)=k }.


The first objective consists of ensuring that the binning is almost uniform and almost independent from the source
so that the random binning scheme and the random coding scheme generate joint distributions that have the same statistics.


[]
 Given P_AB, for every distribution T_B on ℬ and any γ∈ℝ^+, P^RB the marginal of (<ref>)
 satisfies
 
    𝔼‖  P^RB (b,k) - Q_K(k) P_B(b) ‖_1≤ε_App, 
       ε_App P_AB( 𝒮_γ_1 (P_AB T_B )^c)+2^-γ+1/2,
where for a set X, we denote with Q_X the uniform distribution over 𝒳 and

    𝒮_γ(P_AB T_B ){  (a,b) : h_P_AB(a,b)- h_T_B(b) - nR > γ}.



Before stating the second property,  we recall the definition of a mismatch stochastic likelihood coder (SLC).
[Mismatch SLC]
Let T_AB be an arbitrary probability mass function, and  φ: 𝒜→ 1,2^R, a ↦ k a uniform random binning of A. A  mismatch SLC is defined by the following induced conditional distribution
 
    T̂_Â|BK (â|b,k)T_A|B(â|b)  1 {φ(â)=k }/∑_a̅∈𝒜 T_A|B(a̅|b)  1 {φ(a̅)=k }.


Then, the following result is used to bound the error probability of decoding A when the decoder has access to the side information B as well as to bin indices φ(A)=K.
[]
 Given P_AB and any distribution T_AB, the following bound on the error probability of mismatch SLC holds
 
    𝔼[ P[ℰ] ] ≤ P_AB(𝒮_γ_1 (T_AB)^c) + 2^-|γ| =: ε_Dec,
where γ is an arbitrary positive number and 
 
    𝒮_γ (T_AB){ (a,b) : nR -h_T_A|B (a|b) > γ}.















 §.§ One-shot coordination scheme

We consider the setting of Figure <ref>.
The encoder and the decoder share a source of uniform randomness K ∈ 1,2^R_0. The encoder observes the source  U ∈𝒰  and selects a signal  X= f(U,  K),  f: 𝒰× 1,2^R_0→𝒳, which is then transmitted over the discrete channel P̅_Y |X.
Then, the decoder selects an action V= g(Y, K), where g: 𝒴× 1,2^R_0→𝒱.  






  §.§.§ Random binning scheme


Let P̅_UXYV be the target distribution,

    P̅_UP̅_X| UP̅_Y|XP̅_V|UXY.

We introduce an auxiliary random variable W such that the sequence (U, X, W, Y, V) 
has distribution 

    P̅^osP̅_UP̅_W| UP̅_X| W UP̅_Y|XP̅_V|W Y.

We consider two uniform random binnings for W:


  * binning K = φ_1(W), where  φ_1: 𝒲→ 1,2^R_0,  

  * binning M= φ_2(W), where φ_2: 𝒲→ 1,2^ R,  
and the decoder reconstructs Ŵ via the mismatch SLC
 
    T̂_Ŵ|YKM (ŵ|y, k, m) P̅_W|Y(ŵ|y)  1 {φ(ŵ)=(k,m) }/∑_w̅∈𝒲P̅_W|Y(w̅|y)  1 {φ(w̅)= (k, m)}.

This induces a joint distribution:

    P^RB,osP̅_U P̅_W|UP̅_X|W UP̅_K|WP̅_M|WP̅_Y|XP̅_V|WYT̂_Ŵ|YKM.
In particular, P^RB,os_W|KMU is well defined.





  §.§.§ Random coding scheme

Suppose that in the setting of Figure <ref>, the encoder and decoder have access not only to common randomness K but also to extra randomness M, where K is generated uniformly at random  in 1,2^R_0 with distribution Q_K and M is generated uniformly at random in 1,2^R with distribution Q_M independently of K. 
Then, the encoder generates W according to P^RB,os_W|KMU defined above, and X according to P̅_X|U W.
The encoder sends X through the channel.
The decoder obtains Y and (K,M) and reconstructs W 
via the conditional distribution  T̂_Ŵ|YKM. 
The decoder then generates V according to the distribution 
P^RC,os_V|Ŵ Y(v̂|ŵ, y)=P̅_V| W Y(v̂|ŵ, y),
where ŵ is the output of the mismatch SLC.
This defines a joint distribution:

    P^RC,os Q_K Q_M P̅_U P^RB,os_W|KMUP̅_X|W UP̅_Y|XT̂_Ŵ|YKM P^RC,os_V|Ŵ Y.







  §.§.§ Analysis of the L^1 distance

We denote  

    ‖P̅_U P̅_W|UP̅_X|W UP̅_K|WP̅_M|WP̅_Y|X
            - Q_K Q_M P̅_U P^RB,os_W|KMUP̅_X|W UP̅_Y|X‖_1
       (a)=‖P̅_U P̅_W|UP̅_K|WP̅_M|W-  Q_K Q_M P̅_U P^RB,os_W|KMU‖_1≤ε'_App
       𝔼[ P[ℰ] ] ≤ε'_Dec
where (a) comes from (<ref>) in Lemma <ref>, and ε'_App and  ε'_Dec are defined in Theorem <ref> and  Theorem <ref> respectively, i.e.,

    ε'_App   P̅_UKM( 𝒮_γ'_1^c) +2^-γ'_1+1/2,
    ε'_Dec   P̅_WY(𝒮_γ'_2^c) + 2^-|γ'_2 |,
where γ'_1 and γ'_2 are arbitrary positive numbers and 
 
    𝒮_γ'_1   𝒮_γ'_1 (P̅_UKMP̅_U )
    
     =    {  ( u, w)| h_P̅(u, w)
    -h_P̅ (u) - (R+R_0) >γ'_1 },
    𝒮_γ'_2   𝒮_γ'_2 (P̅_WY)= { (w,y) | (R+R_0) -h_P̅ (w| y) > γ'_2 }.

Then, we have

    ‖P̅_U P̅_W|UP̅_X|W UP̅_K|WP̅_M|WP̅_Y|XT̂_Ŵ|YKM 
     - 
        Q_K Q_M P̅_U P^RB,os_W|KMUP̅_X|W UP̅_Y|XT̂_Ŵ|YKM‖_1≤ε'_App+ε'_Dec
       𝕍 (  P̅_U P̅_W|UP̅_X|W UP̅_K|WP̅_M|WP̅_Y|XT̂_Ŵ|YKM,   
        Q_K Q_M P̅_UP^RB,os_W|KMUP̅_X|W UP̅_Y|XT̂_Ŵ|YKM ) ≤1/2 ( ε'_App+ε'_Dec)
To conclude, observe that in the random binning scheme V ∼P̅_V|WY, W ∼P̅_W|U, while in the random coding scheme V ∼ P^RC,os_V|Ŵ Y, Ŵ∼T̂_Ŵ|YKM. Then, by Proposition <ref>,

    𝕍( P^RB,os , P^RC,os ) ≤1/2(ε'_App+ε'_Dec)+ 2ε'_Dec =1/2(ε'_App+5ε'_Dec).







 §.§ Fixed-length coordination scheme

Now, we consider the setting of Figure <ref>.
Assume that 
U^n, X^n, W^n, Y^n and V^n 
are jointly i.i.d. with distribution 

    P̅(P̅^os)^⊗ n=P̅_U^nP̅_W^n| U^nP̅_X^n| W^n U^nP̅_Y^n|X^nP̅_V^n|W^n Y^n.






  §.§.§ Random binning and random coding scheme

We repeat the one-shot schemes of Section <ref> for n i.i.d. uses of the source P̅_U^⊗ n and of the channel P̅_Y|X^⊗ n:


    P^RB   (P^RB,os)^⊗ n= P^RB_U^n  X^n  Y^n  V^n  W^n Ŵ^n CF
    
     =   P̅_U ^nP̅_W^n|U^nP̅_X^n|W^n U^nP̅_C|W^nP̅_F|W^n 
       P̅_Y^n|X^nT̂_Ŵ^n|Y^n C FP̅_V^n|W^n Y^n 
    
     P^RC   (P^RC,os)^⊗ n=P^RC_U^n  X^n  Y^n  V^n  W^n Ŵ^n CF
    
     =    Q_C Q_FP̅_U^n P^RB_W^n|C F U^nP̅_X^n|W^n U^n
       P̅_Y^n|X^nT̂_Ŵ^n|Y^n C F P^RC_V^n|Ŵ^n Y^n
where C  K^n, F M^n, and for  T_W^n|Y^n∏_i=1^n P̅_W|Y the mismatch SLC is:
 
    [1.2]
      T̂_Ŵ^n|Y^n C F (𝐰̂|𝐲, 𝐜, 𝐟)
       T_W^n|Y^n(𝐰̂|𝐲)  1 {φ(𝐰̂)=( 𝐜, 𝐟) }/∑_𝐰̅∈𝒲^n T_W^n|Y^n(𝐰̅|𝐲)  1 {φ(𝐰̅)= ( 𝐜, 𝐟)}
       = ∏_i=1^n P̅_W|Y(ŵ_i|y_i)  1 {φ(ŵ_̂î)=( k_i, m_i) }/∑_w̅_̅i̅∈𝒲∏_i=1^n P̅_W|Y(w̅_̅i̅|y_i)  1 {φ(w̅_i) = ( k_i,m_i)}.


Observe that the distribution P^RB is by construction trivially close in L^1 distance to the target distribution P̅. 
We use the properties of random binning to show that the random binning and the random coding scheme are ε-close in L^1 distance, and therefore so are P^RC and  P̅.


 



  §.§.§ Strong coordination of (U^n , X^n , Y^n , V^n , W^n ) — First bound

By applying Theorem <ref> and  Theorem <ref> to  n i.i.d. copies of P^RB,os and P^RC,os, we have  

    ‖ P^RB_U^n W^n X^n  Y^n   CF  - P^RC_U^n W^n X^n  Y^n   CF‖_1
       (a)=‖P̅_U^n P̅_W^n|U^nP̅_C|W^nP̅_F|W^n-  Q_C Q_FP̅_U^nP^RB_W^n|CFU^n‖_1≤ε_App,
       𝔼[ P[ℰ] ] ≤ε_Dec,
where (a) comes from (<ref>) in Lemma <ref>, and


    ε_App   P̅_U^n CF( 𝒮_γ_1^c) +2^-γ_1+1/2,
    ε_Dec   P̅_W^n Y^n(𝒮_γ_2^c) + 2^-|γ_2 |,
with γ_1 and γ_2 arbitrary positive numbers, and 
 
 
    𝒮_γ_1    𝒮_γ_1 (P̅_U^n CFP̅_U^n )
    
    =   {  ( 𝐮,𝐰): h_P̅(𝐮, 𝐰)
     - h_P̅ (𝐮) - n(R+R_0)>γ_1 },
    𝒮_γ_2   𝒮_γ_2 (P̅_W^n Y^n)
    ={(𝐰, 𝐲) : n(R+R_0)-h_P̅ (𝐰|𝐲) > γ_2 }
    (b)=   { (𝐰, 𝐲) : n(R+R_0) -∑_i=1^n h_P̅ (w_i|y_i) > γ_2},
 where (b) comes from the choice of the mismatch SLC (<ref>).
Then, we have

    ‖ P^RB_U^n W^n X^n  Y^n   CFT̂_Ŵ^n|Y^n C F -   P^RC_U^n W^n X^n  Y^n   CFT̂_Ŵ^n|Y^n C F‖_1
       = ‖ P^RB_U^n W^n X^n  Y^n   CF Ŵ^n  -   P^RC_U^n W^n X^n  Y^n   CF Ŵ^n‖_1≤ε_App+ε_Dec.

To conclude, observe that in the random binning scheme we have V^n ∼P̅_V^n|W^nY^n, W^n ∼P̅_W^n|U^n, while in the random coding scheme we have V^n ∼ P^RC_V^n|Ŵ^n Y^n, Ŵ^n ∼T̂_Ŵ^n|Y^nCF. Then, by Proposition <ref>,

    ‖ P^RB - P^RC‖_1≤ε_App+5  ε_Dec.








  §.§.§ Reducing the rate of common randomness — Final bound

Even though the extra randomness F is required
to coordinate (U^n , X^n , Y^n , V^n , W^n ), we do not need it in order to coordinate
only (U^n , X^n , Y^n , V^n  ).
We would like to reduce the amount of common randomness by having the two nodes agree on an instance F = 𝐟. To do so, we apply 
Theorem <ref> to A=W^n, B=(U^n, X^n, Y^n, V^n), P_B=  P^RB_U^n X^n Y^n V^n, P_AB= P^RB_U^n X^n Y^n V^n W^n and K=F. Then, we have 
 
    ‖  P^RB_U^n X^ nY^n V^n F - Q_FP^RB_U^n X^n Y^n V^n  ‖_1≤ε_App,2,
where
 

 
 
    ε_App,2
      P^RB( 𝒮_γ_3^c)+2^-γ_3+1/2,
       𝒮_γ_3𝒮_γ_3 (P^RB_U^n X^n Y^n V^n W^n P^RB_U^n X^n Y^n V^n )
        =



 
Now, we recall that  by (<ref>) in Lemma <ref>, we have

    ‖ P^RB_U^n X^n Y^n V^n  F-P^RC_U^n  X^n Y^n V^n F‖_1   ≤‖ P^RB- P^RC‖_1
       ≤ε_App+5 ε_Dec.



Combining  (<ref>) and (<ref>) with  the triangle inequality, we have
 
    [2]
     ‖ Q_F P^RB_U^n X^n Y^n V^n-Q_F P^RC_U^n X^n Y^n V^n  ‖_1
       ≤‖ P^RB_U^n X^n Y^n V^n F - Q_F P^RB_U^n X^n Y^n V^n  ‖_1
         + ‖ P^RB_U^n X^n Y^n V^n F - P^RC_U^n X^n Y^n V^n F ‖_1
       ≤ε_App,2 +ε_App+5 ε_Dec.
By (<ref>) in Lemma <ref>, there exists an instance F= 𝐟, such that 
 

 
 
    ‖ P^RB_U^n X^n Y^n V^n| F=𝐟, P^RC_U^n X^n Y^n V^n| F=𝐟‖_1≤ε_Tot,
       ε_Tot2  (ε_App,2 +  ε_App+5 ε_Dec).







 §.§ Analysis of the L^1 distance

Substituting (<ref>), (<ref>), and (<ref>) into (<ref>), the bound on the L^1 distance in (<ref>) becomes

    ε_Tot=   2  P̅_U^n CF( 𝒮_γ_1^c)+ 10 P̅_W^n Y^n(𝒮_γ_2^c)+   2  P^RB( 𝒮_γ_3^c)
            + 2  (2^-γ_1+1/2 +5 · 2^-|γ_2 |+ 2^-γ_3+1/2).

We treat separately the terms 𝒮_γ_i^c, i=1,2,3 to 
understand  which rate conditions we have to impose in order to minimize the measure of the sets as a function of  γ_i, i=1,2,3. In a second instance, we choose the parameters (γ_2, γ_2, γ_3) such that ε_Tot  defined above is small.






  §.§.§ Analysis of 𝒮_γ_1^c
 
To bound P̅_U^n CF( 𝒮_γ_1^c) we want to find rate conditions such that  𝒮_γ_1 includes the typical set 𝒯_ε_1^(n). Observe that if  𝐮 is ε_1-typical and (𝐮,𝐰) are jointly  ε_1-typical,  then
 
    2^-nH_P̅(U)(1+ε_1)≤P̅_U^n    (𝐮) ≤ 2^-nH_P̅(U)(1-ε_1)
    
      2^-nH_P̅(U,W)(1+ε_1)≤P̅_U^n W^n   (𝐮, 𝐰) ≤ 2^-nH_P̅(U,W)(1-ε_1)
which imply
 
    h_P̅ (𝐮)= - logP_U^n(𝐮)≤ 
    nH_P̅(U)(1+ε_1),
        h_P̅(𝐮, 𝐰)=- logP_U^n W^n(𝐮, 𝐰)≥ 
    nH_P̅(U,W)(1-ε_1),
         h_P̅(𝐰|𝐮) ≥ n H_P̅(W|U) - n ε_1(H_P̅(UW)+H_P̅(U))_ε_2.

 Suppose we choose (R,R_0) that satisfy

    R+R_0 <  H_P̅(U,W)- H_P̅(U)- ε_2 -γ_1/n.
Then, if for every ε_1-typical sequence, the following chain of inequalities is verified,

    h_P̅(𝐰| 𝐮) -  γ_1 ≥  n H_P̅(W|U) - n ε_2  -  γ_1> n(R+R_0).
Thus, 𝒮_γ_1 contains the typical set, and there exists a set 𝒮, 𝒯_ε_1^(n)⊆𝒮⊆𝒮_γ_1, such that for every (𝐮,𝐰) ∈𝒮, we have  

    n H_P̅(W|U)- n ε_2  >n(R+R_0)+γ_1.
Therefore, we have 𝒮_γ_1^c⊆𝒮^c, and since the rate condition (<ref>) holds, 𝒮^c is empty and the measure P̅_U^n CF( 𝒮_γ_1^c) is zero.



To bound P̅_U^n CF( 𝒮_γ_1^c) we want to find rate conditions such that  𝒮_γ_1 includes the typical set 𝒯_ε_1^(n).
Observe that, if  𝐮 is ε_1-typical and (𝐮,𝐰) are jointly  ε_1-typical,  then
 
    2^-nH_P̅(U)(1+ε_1)≤P̅_U^n    (𝐮) ≤ 2^-nH_P̅(U)(1-ε_1)
    
      2^-nH_P̅(U,W)(1+ε_1)≤P̅_U^n W^n   (𝐮, 𝐰) ≤ 2^-nH_P̅(U,W)(1-ε_1)
which imply
 
    h_P̅ (𝐮)= - logP_U^n(𝐮)≤ 
    nH_P̅(U)(1+ε_1),
        h_P̅(𝐮, 𝐰)=- logP_U^n W^n(𝐮, 𝐰)≥ 
    nH_P̅(U,W)(1-ε_1).
Hence the following  holds for all (𝐮, 𝐰) ∈𝒯_ε_1^(n),  


    [5]
      nH_P̅(U,W)- nH_P̅(U) - n ε_1(H_P̅(UW)+H_P̅(U))_ε_2
    
        ≤ h_P̅(𝐮, 𝐰)-h_P̅ (𝐮)

Thus, if (R, R_0) are such that ∀𝐮, 𝐯

    R+R_0<H_P̅(W|U) - ε_2- γ_1/n,
by combining (<ref>) and (<ref>), for all (𝐮, 𝐰) ∈𝒯_ε_1^(n) we have

    n(R+R_0) < nH_P̅(W|U) -n ε_2- γ_1 ≤ h_P̅(𝐮, 𝐰)-h_P̅ (𝐮) - γ_1,
which implies that all the typical sequences belong to 𝒮_γ_1.
Since

    𝒮_γ_1^c⊆{  (𝐮,𝐰) : n H_P̅(W|U)- n ε_2- n(R+R_0) >γ_1}^c,
if (<ref>) holds, the right-hand side. of (<ref>) is empty and the measure P̅_U^n CF( 𝒮_γ_1^c) is zero.




If (R_0, R) are such that 

    n(R+R_0) < 
    h_P̅(𝐮, 𝐰)- h_P̅ (𝐮)- γ_1,   ∀𝐮, 𝐯


then the set 𝒮_γ_1^c is  empty, and
 𝒮_γ_1 includes  all the typical set. Observe that, if  𝐮 is ε_1-typical and (𝐮,𝐰) are jointly  ε_1-typical,  then
 
    2^-nH_P̅(U)(1+ε_1)≤P̅_U^n    (𝐮) ≤ 2^-nH_P̅(U)(1-ε_1)
    
      2^-nH_P̅(U,W)(1+ε_1)≤P̅_U^n W^n   (𝐮, 𝐰) ≤ 2^-nH_P̅(U,W)(1-ε_1)
which imply
 
    h_P̅ (𝐮)= - logP_U^n(𝐮)≥ 
    nH_P̅(U)(1-ε_1),
        h_P̅(𝐮, 𝐰)=- logP_U^n W^n(𝐮, 𝐰)≤ 
    nH_P̅(U,W)(1+ε_1).
Hence, the chain of inequalities

    n(R+R_0)    < h_P̅(𝐮, 𝐰)-h_P̅ (𝐮)- γ_1
       ≤ nH_P̅(U,W)(1+ε_1)- nH_P̅(U)(1-ε_1) - γ_1
implies

    𝒮_γ_1⊇{  (𝐮,𝐰) : n H_P̅(W|U)+ ε_2- n(R+R_0) > γ_1}


    ε_2ε_1(H_P̅(UW)+H_P̅(U))

and P̅_U^n CF( 𝒮_γ_1^c) is small if

    R+R_0<H_P̅(W|U) + (ε_2- γ_1)/n.

[inline]check!!!






  §.§.§ Analysis of 𝒮_γ_3^c

 Similarly to above, 𝒮_γ_3 contains all the typical sequences, and  P^RB( 𝒮_γ_3^c) vanishes if

    R< H_P̅(W|UXYV) -ε_1  (H_P̅(UWXYV)+ H_P̅(W))_ε_3- γ_3/n.









  §.§.§ Analysis of 𝒮_γ_2^c

We recall the Berry-Esseen CLT.


[Berry-Esseen CLT ]
Given n>0 and Z_i, i=1, …,n  independent r.v.s. Then, for any real t,


 
    |ℙ{∑_i=1^n Z_i >n (μ_n +t √(V_n/n))} -Q(t) |≤B_n/√(n),
where μ_n = 1/n∑_i=1^n 𝔼 [Z_i], V_n  = 1/n∑_i=1^n Var [Z_i], T_n =1/n∑_i=1^n 𝔼 [| Z_i - μ_i |^3], and B_n = 6 T_n/V_n^3/2, and Q(·)  is the tail distribution function of the standard normal distribution.


We want to use Theorem <ref> to estimate P̅_W^n Y^n(𝒮_γ_2^c), where 𝒮_γ_2 is defined in (<ref>). We observe that, given W^n=𝐰, the terms
Z_i= h_P̅(w_i|Y_i) for i=1, … n are mutually independent because of the choice for the mismatch SLC (<ref>). 
 Then, if 
 

 
    [5]
     n(R+R_0)>∑_i=1^n 𝔼_P̅_Y_i|w_i [h_P̅(w_i|Y_i)]_n μ_n 
         + Q^-1 (ε_4) √(∑_i=1^n Var_P̅_Y_i|w_i (h_P̅(w_i|Y_i)))_n  √( V_n/n) + γ_2,

the chain of inequalities
  
    ∑_i=1^n h_P̅(W|Y) >n(R+R_0)-γ_2> n(μ_n + t√(V_n/n))
implies that 𝒮_γ_2^c is contained in 
   
    {  (𝐰,𝐲) : ∑_i=1^n  h_P̅(w_i|y_i)> nμ_n + n   Q^-1(ε_4) √(V_n/n)}.equation
Therefore, if we apply Theorem <ref> to the right-hand side of (<ref>), and we choose 
 
    Q(t)=ε_4=ε_5 + B_n/√(n),
we have
    
    |ℙ{∑_i=1^n  h_P̅(w_i|y_i)>nμ_n + n  Q^-1(ε_4) √(V_n/n)} -ε_4  |≤B_n/√(n),
          ℙ{∑_i=1^n  h_P̅(w_i|y_i)>nμ_n 
    + n  Q^-1(ε_4) √(V_n/n)}≤ε_5.
Finally, (<ref>) combined with (<ref>) implies P̅_W^n Y^n(𝒮_γ_2 ^c)≤ε_5.
 

 

Observe that



 
    μ_n    1/n∑_i=1^n 𝔼_P̅_Y_i|w_i [h_P̅(w_i|Y_i)]
    
        =  𝔼_w𝔼_P̅_Y|W [h_P̅(W|Y)|W]
        = 𝔼_(w,y)  [h_P̅(W|Y)|W]=H_P̅(W|Y),
    
     V_n   1/n∑_i=1^n Var_P̅_Y_i|w_i (h_P̅(w_i|Y_i))
        = 𝔼_w[  Var_P̅_Y|W (h_P̅(W|Y)|W) ]
       = 𝔼_w[  Var_P̅_Y|W (_P̅(W;Y)|W) ],
 and V_P̅=min_P̅_W𝔼_w[  Var_P̅_Y|W (_P̅(W;Y)|W) ] is the dispersion of the channel P̅_Y|W as defined in <cit.>.
Hence, (<ref>) can be rewritten as
 
    n(R+R_0)>n H_P̅(W|Y)  + n  Q^-1(ε_4) √(V_P̅/n) + γ_2.







  §.§.§ Choice of (γ_1, γ_2, γ_3)
 

If we choose (γ_1, γ_2, γ_3)=( logn,  1/2logn,  logn), (<ref>), (<ref>), and (<ref>) become



    R+R_0 > H_P̅(W|Y) + Q^-1(ε_4) √(V_P̅/n)+ (logn/2  n),
        R+R_0 < H_P̅(W|U) - ε_2- (logn/n) ,
        R< H_P̅(W|UXYV) - ε_3- ( logn/n),
and the bound (<ref>)  on the L^1 distance becomes



    ‖  P^RB_U^n X^n Y^n V^n - P^RC_U^n X^n Y^n V^n‖_1≤ε_Tot ,
       ε_Tot= 2 P̅_U^n CF( 𝒮_γ_1^c) +  10 P̅_W^n Y^n(𝒮_γ_2^c)+  2  P^RB( 𝒮_γ_3^c)+10 +2√(2)/√(n)
       ε_Tot =≤  10 ε_5 +10+2√(2)/√(n).








 §.§ Rate conditions

With this choice for γ_i, (<ref>) can be rewritten as:



    I_P̅(W;U) < I_P̅(W;Y)+ ε_2+3 logn/2  n_(γ_1+γ_2)/n + Q^-1(ε_4) √(V_P̅/n),
        R_0>I_P̅(W;UXV|Y)+ε_3+3 logn/2  n_(γ_2+ γ_3)/n+ Q^-1(ε_4) √(V_P̅/n),
where (ε_2,ε_3,ε_4) are defined in (<ref>), (<ref>), and (<ref>).



 
Observe that in order to minimize  ε_Tot, we can choose ε_5 equal to zero in (<ref>) and (<ref>). On the other hand,  this would require more common randomness since Q^-1(·) increases as its argument approaches zero.
Note that one can minimize ε_Tot (for example, we can have ε_Tot= constant· e^-n) simply by choosing greater (γ_1, γ_2, γ_3) in  (<ref>),  but this increases the rate conditions (<ref>).



IEEEtran










