On the Common Randomness Capacity of a Special Class of Two-way Channels
Saeed Hajizadeh




 
On the Common Randomness Capacity of a Special Class of Two-way Channels
    Saeed Hajizadeh
    December 30, 2023
========================================================================





§ ABSTRATC

In this paper, we would like to study the common randomness (CR) capacity of intertwined two-way channels, namely those whose marginal channel transition probabilities depends also on the signal they transmit. We bring a few special settings and provide constructive schemes with which the two nodes can agree upon a common randomness. We then provide an outer bound on the CR capacity of intertwined receiver-decomposable (RD) two-way channel and will provide a bound on the cardinality of the available auxiliary variables. We will also show this outer bound is bounded above by  Venkatesan-Anantharam's CR capacity which makes it tight for decomposing two-way setting.



§ INTRODUCTION

 The concept of CR capacity of different settings has been introduced and studied by Ahlswede and Csiszar <cit.>. The CR capacity of decoupling two-way settings, namely those with general transition function factored as p(y_1,y_2|x_1,x_2) = p(y_1|x_2)p(y_2|x_1),  has been solved by Venkatesan and Anantharam <cit.>. Recently, two-way channel transmission capacities have been studied <cit.>, <cit.>, <cit.>. We would like to study the CR capacity of intertwined two-way settings, namely those with p(y_1,y_2|x_1,x_2) = p(y_1|x_1,x_2)p(y_2|x_1,x_2). To get a better understanding of what one means by the maximum rate of generating common randomness in this setting, and also observe the difference of the CR capacity of a setting with its transmission capacity, we look at an example which at this point it is unknown how complicated finding its CR capacity can be. Consider two terminals, e.g. Alice and Bob, communicate over a special intertwined two-way setting in the absence of any external random sources. In other words, each symbol transmitted through the channel is only a function of the past symbols received. The setting is as follows: Assume Alice's transmitted and received symbols are X_1 and Y_1 and Bob's transmitted and received symbols are X_2 and Y_2, respectively. Assuming 0 ≤ p_1,q_1,p_2,q_2 ≤1/2, the transition functions are defined as follows,
rCl
Y_1|X_1=0,X_2 ∼BSC(p_1)         Y_1|X_1=1,X_2 ∼BSC(p_2) 

Y_2|X_1,X_2=0 ∼BSC(q_1)         Y_2|X_1,X_2=1 ∼BSC(q_2)

We now explain different case,


  i. p_1 = p_2 = q_1 = 0 and q_2 = 1/2: In this case, at the end of each block, Bob can receive some randomness, depending on whether he has sent X_2 = 1 or not at the beginning of that block, while Alice receives no randomness. The channel from Bob to Alice is always a BSC(0) so set X_1 = 1 at all blocks. Also to start, set X_2 = 1 in the first block and in blocks b=2,...,n Bob sends whatever he receives back to Alice using the-always-BSC(0) backward channel. With this coding scheme it is clear that the first Y_2=0 random bit received by Bob stops the random communication from thereon. It can be seen that the average number of random bits per step generated this way is
rCl
∑_i=1^ni(1/2)^i/n

which vanishes as n →∞. However, we can use an even more adaptive coding scheme. In this scheme, Alice always sends X_1=1 and Bob starts the first block by sending X_2 = 1. If Bob receives Y_2 = 1, he sends back X_2 = 1 in the next block to agree on that bit with Alice and can still receive a random bit at the end of second block from Alice. This scheme continues until Bob receives Y_2 = 0. When he receives 0 in block N_1, he sends it back to Alice in block N_1+1 and starts a new block of communication by sending X_2 =1. Notice that N_1, i.e. the first time Bob receives 0, is distributed geometrically and N_1/N_1 + 1 bits per step is transmitted in the first N_1 + 1 blocks. This scheme continues and in the next set of blocks N_2/N_2 + 1 random bits per step are generated and agreed upon. Call each N_i + 1 blocks of communication a stage. Communication takes place in n stages and the number of common random bits per step generated in n stages is 
rCl
Z_1 + Z_2 + ... + Z_n/n

where Z_i ≜N_i/N_i + 1. Since clearly Z_i's are i.i.d, if the number of stages is large, the law of large numbers states that 𝔼(Z_i) common random bits per step are generated and it is easy to see that,
rCl
𝔼(Z_i)     =     𝔼(N_i/N_i + 1) 

    (a)=     lim_n →∞∑_j=1^nj/j + 1(1/2)^j 

    =     ∑_j=1^∞j/j + 1(1/2)^j = 0.613706.

where (a) follows from the fact that each N_i is distributed geometrically.
Notice that the sum-rate transmission capacity of this setting is at least 1.5 bits per channel use.

  ii. p_1 = p_2 = q_2 = 1/2 and q_1 = 0: In this case, set X_2 = 0 and as a result, Y_1 after each block of communication is a random bit distributed according to Y_1|X_2=0 ∼ BSC(1/2) and can send it back noiselessly to terminal 2, Bob. Therefore, after n symbol transmissions, Alice and Bob can agree upon n - 1 uniformly common bits and thus R = log(2^n-1)/n bits per step of communication is achievable. Clearly, 1 bit per step of communication is the maximum amount of CR that Alice and Bob can agree upon and thus C=1 bits/step.

  iii. p_1 = q_1 = 0 and p_2 = q_2 = 1/2: In this case, Alice and Bob communicate in n blocks. On the first block X_2 sends 0 to set the Y_2|X_1 channel as a BSC(0) and X_1 sends 1 to set Y_1|X_2 as a BSC(1/2). In the next block, Alice who has receives the bit from X_2 randomly retransmitts that bit back to Bob and Bob sends X_2 = 0 to open up a noiseless medium to receive the random bit generated in the first block. What X_2 sends in the first block is irrelevant. With this scheme, after n transmissions, Alice and Bob can generate and agree upon n/2 bits of randomness which achieves a CR rate of log(2^n/2)/n bits per step.

A clear defect in this schemes is Bob's inactiveness in the first block of each transmission cycle. Another approach could be this: In the first block, Alice and Bob each send symbol 1 and each receive a (possibly different) random bit. To make the generated random bit common, in the next two blocks, Alice and Bob take turn in sending 0 to open up the lane for its partner to deliver the random bit noiselessly. With this scheme, 2n/3 bits are generated and agreed upon in n steps of communication and thus the achievable CR rate is improved to be 2/3 bits per step. Notice that an outer bound on the CR capacity of this setting is 1 bit per step. I did not understand how you got 0.75 bit per step. Could you please write it with more detail?

  iv. p_1 = p_2 = 0: In this case, Y_1|X_2 ∼ BSC(0) at all times thus set, say, X_1 = 0. In every block, set X_2,i = Y_2,i-2, i=1,2,…,n. To begin the show, set X_2,1 = 0. As a result, Y_2,1=0 w.p. q_1 and Y_2,1=1 w.p. 1 - q_1 hence in the second block, the channel switches to BSC(q_2) w.p. 1-q_1 and stays at BSC(q_1) w.p. q_1. Similarly, the channel transition function wavers when it is a BSC(q_2). The whole setting is depicted in Fig. <ref>. So nC_FS bits of randomness are generated in this case and can be agreed upon in the other direction. But are they uniformly distributed? Constructively, it is not clear how we can achieve CR in this setting. It turns out that the entropy rate of the output might be the CR of this setting.



Now let us define the problem formally.



§ DEFINITION

We begin with the definition of a special class of intertwined two-way channels,
 
A special class of two-way channels, depicted as in Fig. <ref>, which we call the receiver-decomposable (RD) two-way channel is described as those in which the channel transition matrix is factored as follows,
rCl
p(y_1,y_2|x_1,x_2) = p(y_1|x_1,x_2)p(y_2|x_1,x_2)



We desire to find the maximum amount of common randomness the two terminals can agree upon after a block of n uses of the channel. In other words, let the terminals communicate through the channel in n blocks and after gathering the corresponding outputs, each of them can compute a common random output. This random output will take its values from a set, say 𝒦. The supremum of the cardinality of 𝒦 devided by the number of communication steps, i.e. lim sup_n 1/nK, is the common randomness capacity of RD two-way channel. To make it more precise, let X_1, X_2, Y_1, and Y_2 take values from finite sets 𝒳_1, 𝒳_2, 𝒴_1, and 𝒴_2, respectively. Also let (f,g) be a strategy for transmission by the terminals defined as follows,
rCl
f = (f_1,f_2,...,f_n)

and
rCl
g = (g_1,g_2,...,g_n)

The terminals would then try to communicate over a certain number of steps, say n. In the first step, terminal 1 (T1) sends f_1 ∈𝒳_1 and T2 sends g_1 ∈𝒳_2. In step k,2 ≤ k ≤ n, T1 constructs from the received symbols in the previous steps, i.e. Y_1^k-1, the symbol f_k(Y_1^k-1) ∈𝒳_1. Similarly, T2 sends g_k(Y_2^k-1) ∈𝒳_2. Come the end of the communication steps, the terminals have the sequence of their received signals, namely Y_1^n and Y_2^n. T1 and T2 map Y_1^n and Y_2^n via Φ: 𝒴_1^n ↦ [1:K] ∪{e} and Ψ: 𝒴_2^n ↦ [1:K] ∪{e} for some 𝒦 = {1,2,...,K} and with {e} being the error event in the common randomness generation. We would like to design the strategy such that for every λ > 0
rCl 
1 - λ/K ≤Pr{ Φ(Y_1^n) = Ψ(Y_2^n) = l } ≤1 + λ/K   for each l=1,2,...,K.

This is called an (n,K,λ) strategy to generate common randomness. 
We claim that a non-negative number R is an achievable common randomness if there exists a sequence of (n,K_n,λ_n) strategy such that,
rCl
lim inf_n →∞ logK_n/n ≥R   and   lim_n →∞ λ_n = 0.

We also claim that a non-negative number R is an outer bound on the common randomness capacity if for every strategy (n,K_n,λ) we have,
rCl
lim_λ→0lim sup_n →∞ logK_n/n ≤R.

The rate R is said to be an strong outer bound on the common randomness capacity of a setting if for every strategy (n,K_n,λ) satisfying (<ref>) we have
rCl
lim sup_n →∞ logK_n/n ≤R.         for every λ≥0

The strong converse, from the definition, only assures strong convergence of the inner bound and the outer bound but by no means, can necessarily give us a better outer bound.

Notice that in an (n,K,λ) protocol, the decoding functions Φ and Ψ could be taken as the following mappings,
rCl
Φ: 𝒳_1^n ×𝒴_1^n  ↦[1:K] ∪{e}          and         Ψ: 𝒳_2^n ×𝒴_2^n  ↦[1:K] ∪{e}

However, it is clear that since each X_k,i, k=1,2, is a function of Y_k^i-1, mapping from the sequence of received output is sufficient.

Now to find an outer bound on the CR capacity of the RD two-way setting introduced in Definition <ref>, let us first bound some entropies. Starting with the joint entropy of the outputs, we have,
rCl
H(Y_1^n,Y_2^n)     =     ∑_i=1^nH(Y_1,i,Y_2,i|Y_1^i-1,Y_2^i-1) 

    (a)=     ∑_i=1^nH(Y_1,i,Y_2,i|Y_1^i-1,Y_2^i-1,X_1,i,X_2,i) 

    (b)=     ∑_i=1^nH(Y_1,i,Y_2,i|X_1,i,X_2,i) 

    (c)=     ∑_i=1^nH(Y_1,i|X_1,i,X_2,i) + H(Y_2,i|X_1,i,X_2,i) 

    =     n(H(Y_1|X_1,X_2) + H(Y_2|X_1,X_2))

where (a) follows since X_k,i is a function of Y_k^i-1, k=1,2, (b) follows from the memorylessness of the setting, and (c) follows from the RD (receiver decompose) property of the channel.
We now bound the marginal entropy of each output,
rCl
H(Y_1^n)     =     ∑_i=1^nH(Y_1,i|Y_1^i-1) 

    (a)=     ∑_i=1^nH(Y_1,i|Y_1^i-1,X_1,i) 

    =     ∑_i=1^nH(Y_1,i|Y_1^i-1,X_1,i) + H(Y_1,i|X_1,i,X_2,i) - H(Y_1,i|X_1,i,X_2,i) 

    =     ∑_i=1^nH(Y_1,i|X_1,i,X_2,i) + I(X_2,i;Y_1,i|X_1,i,Y_1^i-1) 

    =     ∑_i=1^nH(Y_1,i|X_1,i,X_2,i) + I(X_2,i;Y_1,i|X_1,i,U_i) 

    =     n(H(Y_1|X_1,X_2) + I(X_2;Y_1|X_1,U))

where (a) follows since X_k,i is a function of Y_k^i-1, k=1,2 and in the penultimate equality we have defined U_i ≜ Y_1^i-1.
Similarly,
rCl
H(Y_2^n)     =     ∑_i=1^nH(Y_2,i|Y_2^i-1) 

    =     ∑_i=1^nH(Y_2,i|Y_2^i-1,X_2,i) 

    =     ∑_i=1^nH(Y_2,i|X_1,i,X_2,i) + I(X_1,i;Y_2,i|X_2,i,Y_2^i-1) 

    =     ∑_i=1^nH(Y_2,i|X_1,i,X_2,i) + I(X_1,i;Y_2,i|X_2,i,V_i) 

    =     n(H(Y_2|X_1,X_2) + I(X_1;Y_2|X_2,V))

where V_i ≜ Y_2^i-1.
Notice that this selection of the auxiliary RVs induces the distribution of p(u,v)p(x_1|u)p(x_2|v) and thus the Markov chains U → V → X_2 and V → U → X_1.

We also have,
rCl
I(Y_1^n;Y_2^n)     =     H(Y_1^n) + H(Y_2^n) - H(Y_1^n,Y_2^n) 

    =     n(I(X_2;Y_1|X_1,U) + I(X_1;Y_2|X_2,V))

To bound the cardinality of U and V, fix p(x_1|u) and p(x_2|v). Take the following |𝒳_1|.|𝒳_2|+1 continuous functions of p(v|u),

g_j(p(v|u)) = {
[                   p(x_1,x_2|u) = ∑_vp(v|u)p(x_1|u)p(x_2|v)                                  j = 1,2,…,|𝒳_1|.|𝒳_2| - 1;                                             H(Y_1|X_1,U=u)                                            j = |𝒳_1|.|𝒳_2|; p(v,x_2,y_2|u) = ∑_x_1p(v|u)p(x_1|u)p(x_2|v)p(y_2|x_1,x_2)                                        j = |𝒳_1|.|𝒳_2| + 1 ]
.
 
The first set of functions preserve p(x_1,x_2) which for the fixed channel transition, preserves H(Y_1|X_1,X_2). The second function preserves H(Y_1|X_1,U) and the last function preserves p(v,x_2,y_2) and thus H(Y_2|X_2,V). Therefore 𝒰 suffices to be taken |𝒰^'| ≤ |𝒳_1|.|𝒳_2|+1. Let the corresponding RV of V, after replacing U by U^' be denoted by V^'. Now for fixed U^' take the following |𝒳_1|.|𝒳_2| functions of p(x_1,x_2|u^',v^'),

h_j(p(x_1,x_2|u^',v^')) = {
[        p(x_1,x_2|u^',v^') j = 1,2,…,|𝒳_1|.|𝒳_2| - 1;      H(Y_2|X_2,V^' = v^')           j = |𝒳_1|.|𝒳_2| ]
.
 
Similarly, V^'|U^' = u^' suffices to be taken to satisfy |𝒱^”| ≤ |𝒳_1|.|𝒳_2|.
However, the aforementioned Markov chains are still not necessarily satisfied by these RVs. An option to construct new RVs to satisfy the aforementioned Markov chains, which may not be necessary, can be to define,
rCl
V^”' ≜(V^”,X_2)          U^” ≜(U^',X_1) 
and the Markov chains are also satisfied and also,
rCl
I(X_2 ; Y_1 |X_1,U^”)     =     I(X_2 ; Y_1 |X_1,U^') = I(X_2 ; Y_1 |X_1,U) 

I(X_1 ; Y_2 |X_2,V^”')     =     I(X_1 ; Y_2 |X_2,V^”) = I(X_1 ; Y_2 |X_2,V^') = I(X_1 ; Y_2 |X_2,V) 
Thus we can take
rCl
|𝒰| ≤|𝒳_1|.(|𝒳_1|.|𝒳_2| + 1)      and     |𝒱| ≤|𝒳_1|.|𝒳_2|^2

Now notice that from (<ref>) we have,
rCl
p(S=T)     ≥    k Pr{ Φ= Ψ= l } 

    =     Pr{ ∪_l ∈[1:K] { Φ= Ψ= l } } ≥1 - λ
Therefore,
rCl
P(Φ≠Ψ) ≤λ
Now from Fano's inequality we have,
rCl
max{H(Ψ| Φ) , H(Φ| Ψ)} ≤1 + λlog(K)   

We also have,
rCl 
H(Φ,Ψ)     (a)≥     - ∑_l=1^KPr{Φ= Ψ= l} log(Pr{Φ= Ψ= l}) 

    (b)≥     ∑_l=1^K1 - λ/K log( K/1 + λ ) 

    ≥    (1 - λ) log(K) - 1 

where (a) follows from conditioning on the event A ≜{Φ = Ψ} and (b) follows from (<ref>).
From (<ref>) and (<ref>) we have
rCl
min{ H(Ψ), H(Φ) } ≥(1 - 2λ) log(K) - 2 

Thus from (<ref>) and (<ref>) we have for every 0 ≤λ≤ 1
rCl
-3 + (1 - 3λ) log(K)     ≤    H(Φ, Ψ) ≤H(Y_1^n , Y_2^n) 

-2 + (1 - 2λ) log(K)     ≤    min{H(Φ) , H(Ψ)} ≤min{H(Y_1^n) , H(Y_2^n)} 

-1 + (1 - λ) log(K)     ≤    I(Y_1^n;Y_2^n)

and thus we have the following Theorem, 

For instance for every 0 ≤λ≤ 1 we have,
rCl
-3 + (1 - 3λ) log(K)     ≤    H(Y_1^n , Y_2^n) = n(H(Y_1|X_1,X_2) + H(Y_2|X_1,X_2)) 

and thus,
rCl
-3/n + (1 - 3λ)/n log(K)     ≤    H(Y_1|X_1,X_2) + H(Y_2|X_1,X_2)



The CR capacity of the intertwined two-way setting as described in Definition <ref> is dominated by,
rCl
R ≤min{ A, B, C, D } 
where
rCl
A     ≜    H(Y_1|X_1,X_2) + H(Y_2|X_1,X_2) 

B     ≜    H(Y_1|X_1,X_2) + I(X_2;Y_1|X_1,U) 

C     ≜    H(Y_2|X_1,X_2) + I(X_1;Y_2|X_2,V) 

D     ≜    I(X_2;Y_1|X_1,U) + I(X_1;Y_2|X_2,V) 
for some distribution p(u,v)p(x_1|u)p(x_2|v) with |𝒰| ≤ |𝒳_1|.(|𝒳_1|.|𝒳_2| + 1) and |𝒱| ≤ |𝒳_1|.|𝒳_2|^2.

Notice that time-sharing RV Q is used in the achievable rates to convexify (and possibly enlarge) the region. Here, however, we do not need to make the outer bound convex and enlarge it. Hence, there is no point in using a time-sharing RV in the outer bound.
Now let us compare this outer bound with Venkatesan-Anantharam's CR capacity,
rCl
A     =     H(Y_1|X_1,X_2) + H(Y_2|X_1,X_2) = H(Y_1|X_2) + H(Y_2|X_1)  

B     =     H(Y_1|X_1,X_2) + I(X_2;Y_1|X_1,U) ≤H(Y_1|X_2) + I(X_2;Y_1)  

C     =     H(Y_2|X_1,X_2) + I(X_1;Y_2|X_2,V) ≤H(Y_2|X_1) + I(X_1;Y_2)   

D     =     I(X_2;Y_1|X_1,U) + I(X_1;Y_2|X_2,V) ≤I(X_2;Y_1) + I(X_1;Y_2) 

Therefore, for the case of p(y_1,y_2|x_1,x_2) = p(y_1|x_2)p(y_2|x_1), our outer bound is bounded above as follows,

From (<ref>) and (<ref>) we have
rCl
R     ≤    H(Y_1|X_2) + min{ H(Y_2|X_1) , I(X_2;Y_1) } 

and from (<ref>) and (<ref>) we have,
rCl
R     ≤    I(X_1;Y_2) + min{ H(Y_2|X_1) , I(X_2;Y_1) } 

Therefore, from (<ref>) and (<ref>) we have,
rCl
R     ≤    min{ H(Y_1|X_2) , I(X_1;Y_2) } + min{ H(Y_2|X_1) , I(X_2;Y_1) }

which is the CR capacity of decomposing two-way setting of Anantharam. Therefore, our outer bound is tight in that case and the CR capacity of  RD decomposing setting p(y_1,y_2|x_1,x_2) = p(y_1|x_1,x_2)p(y_2|x_1,x_2) is no more than CR capacity of decomposing setting p(y_1,y_2|x_1,x_2) = p(y_1|x_2)p(y_2|x_1).




IEEEtran

