Polar codes for empirical coordination over noisy channels with strictly causal encoding
Giulia Cervia Laura Luzzi Maël Le Treust Matthieu R. Bloch
Slowdown of the surface diffusion during early stages of bacterial colonization
    C. Cassier-Chauvat
    December 30, 2023
===============================================================================





§ INTRODUCTION



In decentralized networks of connected objects,
such as wireless sensors, medical and wearable devices, smart energy meters, 
home appliances, and self-driving cars, devices sense their environment and choose their actions in order 
to achieve a general objective.
It is essential that these devices, considered as autonomous decision-makers, cooperate and coordinate their actions to induce a global behavior, represented by a utility function to be maximized.

Within the framework of information theory, two different metrics have been proposed to measure the level of 
coordination:  empirical coordination requires the joint histogram of the actions to approach a target distribution, 
while strong coordination requires the joint distribution of actions to converge in total variation to an i.i.d. target distribution <cit.>. 

We consider a two-node network with an information source and a noisy channel in which the input and output signals should be empirically coordinated with the source and the reconstruction. 
In <cit.>, the authors provide a characterization of the coordination region when the encoder is strictly causal. 
Inspired by the binning technique using polar codes in <cit.>, we propose an explicit coding scheme that achieves a subset of the coordination region in <cit.> by turning the argument of <cit.> into an explicit polar coding proof. 
The scenario in which both the encoder and the decoder are non-causal has already been considered for empirical  coordination
with polar codes <cit.>. Here, we focus on the setting in which the encoder is strictly causal.


In this paper, we only achieve a subset of the coordination region because of the use of binary polar codes, but the whole region can be achieved using non-binary polar codes. 

The remainder of the paper is organized as follows.  introduces the notation, describes the model under investigation and states the main achievability result.  details the proposed coordination scheme using polar codes. 
Finally, Section <ref> proves the main result.




§ PROBLEM STATEMENT





 §.§ Notation

We define [a,b] as the set of the integers between a and b.
For n=2^m, m ∈ℕ, we note G_n:= [ 1 0; 1 1 ]^⊗ m the source polarization transform defined in <cit.>. 
Given X^1:n:= (X^1, …, X^n) a random vector, we note X^1:j the first j components of X^1:n and X[A], where A⊂ [1,n], the components X^j such that j∈A.
We note 𝕍 (· , ·) and 𝔻 (··) the variational distance and the Kullback-Leibler divergence between two distributions, respectively. 




 §.§ System model and main result










We consider two agents, Node 1 and Node 2, who have access to a shared randomness source C ∈𝒞_n (Figure <ref>). 
Node 1 observes an i.i.d. sequence of actions  S^1:n∈𝒮^n with discrete probability distribution P_S. 
Node 1 then selects a signal X^1:n such that X^i= f_i(S^1:i-1, C), where f^n={f_i}_i=1^n, f_i: 𝒮^i-1×𝒞_n → is the strictly causal encoder. 
The signal X^1:n is transmitted over a discrete memoryless channel with transition probability P_Y |X.
Upon receiving Y^1:n∈𝒴^n, Node 2 selects an action S^1:n = g^n(Y^1:n, C), where g^n: 𝒴^n  ×𝒞_n →𝒮^n is the non-causal decoder.
For block length n, the pair (f^n , g^n )  constitutes a code.
Node 1 and Node 2 wish to coordinate in order to obtain a joint distribution of actions and signals that is close to a target distribution P_SXYS.
We focus on the empirical coordination metric defined in <cit.>.

A distribution P_SXYS is achievable if for all 
ε >0 there exists a sequence of codes {(f^n , g^n )}_n ∈ℕ 
such that

    lim_n→∞ℙ{𝕍(  T_S^1:n X^1:n Y^1:nS^1:n,P_SXYS) > ε} =0,

where T_S^1:n X^1:n Y^1:nS^1:n(s,x,y,ŝ) 
is the empirical distribution of the tuple (S^1:n, X^1:n, Y^1:n, S^1:n) 
induced by the code.

The empirical coordination region 𝒞 is the set of achievable distributions P_SXYS.


[Strictly causal encoder <cit.>] 
Let P_S and P_Y|X be the given source and channel parameters. When the encoder is strictly causal,
 the coordination region  is given by
 
    := 
    P_SXYS : 
    P_SXYS=  P_S  P_X  P_Y|X  P_S|SXY
    ∃ U 
     
     P_SXYU S= P_S P_X P_U|XS P_Y|X P_S|UY
     I(X,U;S) ≤ I(X,U;Y)
    |𝒰|≤|𝒮||𝒳||𝒴||𝒮|+1

 
 


If the encoder is strictly causal, the source S^1:n and the signal X^1:n have to be independent of each other to achieve coordination of the tuple (S^1:n, X^1:n, Y^1:n, S^1:n).



 
By the chain rule, we have


  •I(X,U;S)= I(U;S|X)+I(X;S)=I(U;S|X) since S^1:n and X^1:n are independent;

  • I(X,U;Y)= I(U;Y|X)+I(X;Y)=I(X;Y) because of the Markov chain U-X-Y.

Hence the condition I(X,U;S) ≤ I(X,U;Y) in (<ref>) becomes I(U;S|X)≤ I(X;Y).

 
 

For all P_SXYS∈𝒞 such that  𝒰 = { 0,1},
there exists an explicit polar coding scheme that achieves empirical coordination with vanishing rate of common randomness.



Since U is binary we only achieve a subset of 𝒞. The proof can be generalized to the case where |𝒰| is a prime number using non-binary polar codes. 






§ POLAR CODING SCHEME



Consider the random vectors S^1:n, U^1:n, X^1:n, Y^1:n and S^1:n
generated i.i.d. according to P_SXUY S that factorize as in (<ref>) with the same mutual information and cardinality constraints.





  
Polarize X
Let Z^1:n=X^1:nG_n be the polarization of X^1:n, where G_n is the source polarization transform.
For some , let δ_n: = 2^-n^ β and define the very high and high entropy sets:

    𝒱_X:     ={j∈[1,n]:H(Z^j|Z^1:j-1)>1-δ_n },
    ℋ_X:     ={j∈[1,n]:H(Z^j|Z^1:j-1)>δ_n },  equation
    ℋ_X | Y:     ={j∈[1,n]:H(Z^j|Z^1:j-1 Y^1:n)>δ_n } .

Partition the set [1,n] into four disjoint sets:

    A_1 := 𝒱_X∩ℋ_X|Y ,       A_2 : = 𝒱_X∩ℋ_X|Y^c,
    
    A_3 := 𝒱_X^c ∩ℋ_X|Y ,      A_4 := 𝒱_X^c ∩ℋ_X|Y^c.



We have:


  • 𝒱_X⊂ℋ_X and lim_n →∞|ℋ_X∖𝒱_X|/n = 0 <cit.>,
 
  • A_1 ∪ A_2 = 𝒱_X and lim_n →∞|𝒱_X|/n  = H(X)  <cit.>,
 
  •  A_1 ∪ A_3 = ℋ_X|Y and lim_n →∞|ℋ_X | Y|/n = H(X|Y) <cit.>.

Since  lim_n →∞| A_2| - | A_3 |/n= H(X)- H(X|Y) = I(X;Y)≥ 0 
this implies directly that for n large enough | A_2 |≥| A_3 |.






  
Polarize U
Let V^1:n=U^1:nG_n be the polarization of U^1:n and define:

    𝒱_U|XS:     ={j∈[1,n]:H(V^j|V^1:j-1X^1:nS^1:n)>1-δ_n },
    ℋ_U | XS:     ={j∈[1,n]:H(V^j|V^1:j-1 X^1:nS^1:n)>δ_n }, 
    ℋ_U | X:     ={j∈[1,n]:H(V^j|V^1:j-1 X^1:n)>δ_n }equation.



Partition the set [1,n] into four disjoint sets:

    B_1 := 𝒱_U|XS∩ℋ_U|X=𝒱_U|XS ,     B_2 : = 𝒱_U|XS∩ℋ_U|X^c=∅,
        B_3 := 𝒱_U|XS^c ∩ℋ_U|X ,  
     B_4 := 𝒱_U|XS^c ∩ℋ_U|X^c=ℋ_U|X^c.



We have:


  • 𝒱_U|XS⊂ℋ_U|XS and lim_n →∞|ℋ_U|XS∖𝒱_U|XS|/n = 0 <cit.>,
 
  • B_1  = 𝒱_U|XS and lim_n →∞|𝒱_U|XS|/n  = H(U|XS) <cit.>,
  
  •  B_4 = ℋ_U|X^c and lim_n →∞|𝒱_U|X^c |/n = 1 - H(U|X)   <cit.>,
 
  •  B_3 ∪ B_4 =𝒱_U|XS^c and lim_n →∞|𝒱_U|XS^c |/n = 1 - H(U|XS) <cit.>.

Note that  H(U|X)- H(U|XS) = I(X, U;S)≥ 0 and
 | B_3 |/n tends to I(X, U;S). Since I(X,U;Y) = I(X;Y), the inequality I(X,U;S) ≤ I(X,U;Y)  implies directly that for n large enough | B_3 |≤| A_2| - | A_3 |.

















  
Encoding


We use a chaining construction over multiple blocks. 
The encoder observes (S_0^1:n, S_1^1:n, …, S_k^1:n), 
where S_0^1:n is a uniform random sequence and S_i^1:n for i∈ [1, k] are k blocks of the source.
It then generates for each block i∈ [1, k] random variables Z_i^1:n and V_i^1:n following the procedure described in Algorithm 1.
In particular, the chaining construction proceeds as follows.
The bits in  A_1 ⊂_X and B_1 ⊂_U|XS are chosen with uniform probability using uniform randomness sources (C_1,C_2) shared with Node 2, and their value is reused over all blocks.
In the first block the bits in  A_2 ⊂_X are chosen with uniform probability using a local randomness source M.
The bits in A_3 ∪ A_4  and B_3 ∪ B_4 are generated according to the previous bits using successive cancellation encoding 
<cit.>.
Note that it is possible to sample efficiently from  P_Z^j | Z^1:j-1  and
P_V^j | V^1:j-1X^1:nS^1:n (given S^1:n and X^1:n) respectively <cit.>.

From the second block, let A'_3 and B'_3 be two disjoint subsets of A_2 such that | A'_3 |= | A_3 | and | B'_3 |= | B_3 |.  
The existence of those disjoint subsets is guaranteed by Remark <ref> and Remark <ref>.
The bits of A_3 and B_3 in block i are used as A'_3 and B'_3 in block i+1 using one time pads with keys K_1 and K_2 respectively. 
Thanks to the Crypto Lemma  <cit.>, if we choose K_1 of size | A_3 | and  K_2 of size | B_3 | 
to be uniform random keys, the bits in A'_3 and B'_3 in the block i+1 are uniform. The bits in A'_2:=A_2 ∖ (A'_3 ∪ B'_3) are chosen with uniform probability using the local randomness source M.

The encoder then computes 
X_i^1:n=Z_i^1:n G_n  for i=1, …, k and sends it over the channel.
We use an extra (k+1)-th block to send 
a version of Z_k[A_3] encoded with a good channel code as in <cit.>.





  
Decoding The decoder observes (Y_1^1:n, …, Y_k+1^1:n) and the (k+1)-th block allows it to decode in reverse order.
In block i ∈ [1,k], the decoder has access to Z_i[A_1∪ A_3]= Z_i[ℋ_X| Y] and 
V_i[B_1∪ B_3]= V_i[ℋ_U |X]: the bits in A_1 and B_1 correspond to shared randomness (C_1, C_2),
in block i ∈ [1, k-1] the bits in A_3 and B_3 are obtained by successfully recovering A_2 in block i+1 and
in block k they are recovered from Y_k+1^1:n as in <cit.>.
For each block i=k, …, 1 the decoder recovers the estimates Z_i^1:n and V_i^1:n using Algorithm 2. 
From Y_i^1:n and Z_i[A_1 ∪ A_3] the successive cancellation decoder can retrieve Z_i[A_2 ∪ A_4] and therefore V_i[B_4].
Note that, as shown in <cit.>, V^1:n is equal to  V^1:n with high probability.
The decoder computes U_i^1:n = V_i^1:n G_n. 
It then generates S_i^1:n symbol by symbol using: P_S_i^j | U_i^j Y_i^j (s|u,y)=P_S | UY(s|u,y).
 

The rate of common randomness is negligible, since:

    lim_n →∞ k →∞| A_1 | +   | A_3 | + | B_1  | +  | B_3 |/kn  = lim_n →∞ k →∞|𝒱_X|Y| + |ℋ_U|X|/nk
       = lim_k →∞H(X|Y)+ H(U|X)/k =0.








§ PROOF OF THEOREM <REF>

Given ε >0, we want to prove that: 

    lim_n →∞ℙ{𝕍(T_S^1:n_1:k+1 X^1:n_1:k+1 Y^1:n_1:k+1S^1:n_1:k+1, P_SXYS) > ε} =0.

This requires a few steps:

1. ∀  i∈[1,k ],
lim_n →∞ℙ{𝕍(T_S^1:n_iX^1:n_iU^1:n_i, P_SXU) > ε} =0;

2. ∀  i∈[1,k ],
lim_n →∞ℙ{𝕍(T_S^1:n_iX^1:n_iU^1:n_i Y^1:n_i, P_SXUY) > ε} =0;

3. ∀i∈[1,k ],
lim_n →∞ℙ{𝕍(T_S^1:n_iX^1:n_iU^1:n_i Y^1:n_iŜ^1:n_i,P_SXUYŜ) > ε} =0;

4. Convergence in each block implies overall convergence;

5. The theorem follows from the fact that 

    𝕍(T_S^1:n_1:k+1X^1:n_1:k+1  Y^1:n_1:k+1S^1:n_1:k+1,P_SXY S) ≤
       𝕍(T_S^1:n_1:k+1X^1:n_1:k+1U^1:n_1:k+1 Y^1:n_1:k+1S^1:n_1:k+1,P_SXUY S).





 
  Step 2. Equation (<ref>) implies 

    lim_n →∞ℙ{𝕍(T_S^1:n_iX^1:n_iU^1:n_i Y^1:n_i, P_SXUY) > ε} =0;


  Step 3. Equation (<ref>) implies 

    lim_n →∞ℙ{𝕍(T_S^1:n_iX^1:n_iU^1:n_i Y^1:n_iS^1:n_i, P_SXUY S) > ε} =0;


Note that since the steps 2 to 5 have already been proved in <cit.>, we only need to prove the first step.
For all ε_0 >0, we define

    𝒯_ε_0( P_SXU) := { (𝐬,𝐱, 𝐮) | 𝕍( P_SXU, T_(𝐬,𝐱, 𝐮)) ≤ε_0}

Observe that for the i.i.d. distribution, we have lim_n →∞ℙ{  (𝐬,𝐱, 𝐮) ∈𝒯_ε_0( P_SXU) }=1.

Let i ∈ [1,k], we have:

    ℙ{𝕍( T_S^1:n_i X^1:n_i U^1:n_i , P_SXU) > ε_0}
        = ∑_𝐬,𝐱, 𝐮 P_S^1:n_i X^1:n_i U^1:n_i(𝐬,𝐱, 𝐮)1{ (𝐬,𝐱, 𝐮) ∉𝒯_ε_0( P_SXU) }
        =  ∑_𝐬,𝐱, 𝐮 ( P_S^1:n_i  X^1:n_i U^1:n_i(𝐬,𝐱, 𝐮) - P _S^1:nX^1:n U^1:n(𝐬,𝐱, 𝐮) 
        +  P _S^1:nX^1:n U^1:n(𝐬,𝐱, 𝐮) ) 1{ (𝐬,𝐱, 𝐮) ∉𝒯_ε_0( P_SXU) }
       ≤𝕍 ( P_S^1:nX^1:nU^1:n, P_S^1:nX^1:n U^1:n) + ℙ{ (𝐬,𝐱,𝐮 ) ∉𝒯_ε_0( P_SXU) }

which tends to 0 thanks to a typicality argument and the following result.


For i ∈ [1,k], let δ_n = 2^-n^ β where 0<β<1/2,
 
    𝕍(P_S_i^1:nX_i^1:nU_i^1:n, P_S^1:n X^1:n U^1:n) ≤ 2 √(log2)√(n δ_n).


By the chain rule, we have

    𝔻( P_S^1:n X^1:n U^1:n  P_S_i^1:nX_i^1:nU_i^1:n) equation
    
    
        = 𝔻(  P_X^1:n| S^1:n P_X_i^1:n| S_i^1:n| P_S^1:n)
       +  𝔻(P_U^1:n |X^1:n S^1:n   P_U_i^1:n| X_i^1:n S_i^1:n| P_X^1:n S^1:n)

We call D_1 and D_2 the first and the second term.



  • D_1= 𝔻( P_X^1:n| S^1:n  P_X_i^1:n| S_i^1:n| P_S^1:n);

  • D_2=  𝔻(  P_U^1:n |X^1:n S^1:n P_U_i^1:n| X_i^1:n S_i^1:n| P_X^1:n S^1:n).


Then: 

    D_1    (a)=𝔻(  P_X^1:n P_X_i^1:n) (b)=𝔻(  P_Z^1:n P_Z_i^1:n) equation
       (c)=∑_j=1^n 𝔻( P_ Z_i^j|  Z_i^1:j-1   P_Z_i^j| Z_i^1:j-1| P_ Z_i^1:j-1)
       (d)=∑_j ∈ A_1 ∪ A_2𝔻(  P_ Z_i^j|  Z_i^1:j-1 P_Z_i^j| Z_i^1:j-1| P_ Z_i^1:j-1)
       (e)=∑_j ∈ A_1 ∪ A_2(1- H(Z_i^j|  Z_i^1:j-1))  (f)< n |𝒱_X |≤ n δ_n

where (a) comes from the fact that X is independent of S, (b) from the invertibility of G_n,  (c) from the chain rule, (d) from (<ref>), (e) from the fact that the conditional distribution P_Z_i^j| Z_i^1:j-1 is uniform for j in A_1 and A_2 and (f) from Definition (<ref>).

Similarly, D_2 <n δ_n. Then D_1+D_2 < 2 n δ_n and the proof is completed using Pinsker's inequality. 


    D_2  (a)=𝔻(P_V_i^1:n|  Z_i^1:n S_i^1:n  P_V_i^1:n| Z_i^1:n S_i^1:n| P_Z_i^1:n S_i^1:n) equation
       (b)=∑_j=1^n 𝔻( P_V_i^j|  V_i^1:j-1 Z_i^1:nS_i^1:n P_V_i^j| V_i^1:j-1Z_i^1:nS_i^1:n | P_V_i^1:j-1Z_i^1:nS_i^1:n  )
       (c)=∑_j ∈ B_1 ∪ B_2𝔻(P_V_i^j|  V_i^1:j-1 Z_i^1:nS_i^1:n  P_V_i^j| V_i^1:j-1Z_i^1:nS_i^1:n | P_V_i^1:j-1Z_i^1:nS_i^1:n )
       (d)=∑_j ∈ B_1 ∪ B_2(1- H(U_i^j|  U_i^1:j-1 X_i^1:n S_i^1:n))  (e)< n |𝒱_U|XS|≤ n δ_n

where (a) comes from the invertibility of G_n,  (b) from the chain rule, (c) from (<ref>), (d) from the fact that the conditional distribution P_V_i^j| V_i^1:j-1Z_i^1:n S_i^1:n is uniform for j in B_1 and B_2 and (e) from Definition (<ref>).










  §.§.§ Proof of Step 2

This step follows from Step 1 and <cit.>.
To prove this step we use the following result, proved in <cit.>.

Let P_A a distribution, A^1:n a random vector,
B^1:n a random vector generated from A^1:n with i.i.d. conditional distribution P_B|A and suppose
lim_n→∞ℙ{𝕍(T_A^1:n, P_A)> ε} =0.
Then for all ε'>ε we have:

    lim_n→∞ℙ{𝕍( T_A^1:n B^1:n, P_AB) > ε'} =0.




  §.§.§ Proof of Step 3

To simplify the notation we set T_i:=T_S^1:n_iX^1:n_iU^1:n_i Y^1:n_iS^1:n_i for all i ∈ [1,k+1].
To prove this step we can apply <cit.> to the result of Step 2 and add S. Notice that S is generated using U and not by U. 

Note that, by the previous step, ∀ε > ε' for i ∈ [1,k] we have 

    lim_n →∞ℙ{𝕍( T_i,P_SXUYS) > ε| U_i^1:n = U_i^1:n} =0.

We can write:

    ℙ{𝕍( T_i,P_SXUYS) > ε}
       =ℙ{𝕍( T_i,P_SXUYS) > ε| U_i^1:n = U_i^1:n}ℙ{U_i^1:n = U_i^1:n}
       + ℙ{𝕍( T_i,P_SXUYS) > ε| U_i^1:n≠U_i^1:n}ℙ{U^1:n_i ≠U^1:n_i  }.

Note that the last term tends to 0 since U^1:n is equal to U^1:n with high probability <cit.>.




  §.§.§ Proof of Step 3 and Step 4

This steps have already been proved in <cit.>.

 We set the joint type as T :=  T_S^1:n_1:k+1X^1:n_1:k+1U^1:n_1:k+1 Y^1:n_1:k+1S^1:n_1:k+1. The convergence in probability of T to  P_S  XUYS follows from the convergence in probability of T_i to P_SXUYS for i ∈ [1,k] (coordination in the first k blocks). In fact, observe that

    𝕍(  T,  P_S XUYS)
     ≤1/k+1∑_i=1^k+1𝕍(T_i,P_SXUYS).

This is a consequence of the following result, proved in <cit.>.

 Let X^1:n, X^1:n two possibly dependent random sequences taking values in ^n and define
 
    T_(X^1:n,X^1:n)(x):= 1/2n∑_i=1^n (  1 {X^i=x} +  1 {X^i=x}).
 
Then for any distribution P  on ,

    𝕍(T_(X^1:n,X^1:n), P) ≤1/2𝕍(T_X^1:n, P) + 1/2𝕍(T_X^1:n, P).


Lemma <ref> implies that:

    𝔼[ 𝕍(  T,  P_SXUYS) ]
    ≤1/k+1∑_i=1^k+1𝔼[ 𝕍(T_i,P_SXUYS) ].

The right hand side in (<ref>) goes to zero since: 


  * for i ∈ [1,k] we already have the convergence in probability of 𝕍(T_i,P_SXUYS) to zero, therefore the convergence in mean (since  T_i  and consequently 𝕍(T_i,P_SXUYS) are bounded for all i);

  * for i=k+1, since T_k+1 and P_SXUYS are probability distributions, 𝕍( T_k+1,P_SXUYS) ≤ 2. For k large enough 2/(k+1) goes to zero, then 𝔼 [2]/(k+1)=2/(k+1) goes to zero and empirical coordination still holds.

Then, the left hand side in (<ref>) goes to zero and because convergence in mean implies convergence in probability, we have the convergence in probability of 𝕍(  T,  P_SXUYS) to zero.


  §.§.§ Proof of Step 5
 
To conclude we only need the following lemma.

𝕍(T_X^1:n,P_X ) ≤𝕍(T_X^1:n Y^1:n,P_XY).






    0.9

 IEEEtran
 






