arXiv:1710.03210v1 [] 9 Oct 2017

Joint Coordination-Channel Coding for Strong
Coordination over Noisy Channels
Based on Polar Codes
Sarah A. Obead, Jörg Kliewer

Badri N. Vellambi

Department of Electrical and Computer Engineering
New Jersey Institute of Technology
Newark, New Jersey 07102
Email:sao23@njit.edu, jkliewer@njit.edu

Research School of Computer Science
Australian National University
Acton, Australia 2601
Email: badri.n.vellambi@ieee.org

Abstract—We construct a joint coordination-channel polar
coding scheme for strong coordination of actions between two
agents X and Y, which communicate over a discrete memoryless
channel (DMC) such that the joint distribution of actions
follows a prescribed probability distribution. We show that
polar codes are able to achieve our previously established inner
bound to the strong noisy coordination capacity region and
thus provide a constructive alternative to a random coding
proof. Our polar coding scheme also offers a constructive
solution to a channel simulation problem where a DMC and
shared randomness are together employed to simulate another
DMC. In particular, our proposed solution is able to utilize
the randomness of the DMC to reduce the amount of local
randomness required to generate the sequence of actions at
agent Y. By leveraging our earlier random coding results for
this problem, we conclude that the proposed joint coordinationchannel coding scheme strictly outperforms a separate scheme
in terms of achievable communication rate for the same amount
of injected randomness into both systems.

I. I NTRODUCTION
A fundamental problem in decentralized networks is to
coordinate activities of different agents with the goal of
reaching a state of agreement. Such a problem arises in a
multitude of applications, including networks of autonomous
robots, smart traffic control, and distributed computing problems. For such applications, coordination is understood to
be the ability to arrive at a prescribed joint distribution
of actions at all agents in the network. In information
theory, two different notions of coordination are explored: (i)
empirical coordination, which only requires the normalized
histogram of induced joint actions to approach a desired
target distribution, and (ii) strong coordination, where the
sequence of induced joint actions must be statistically close
(i.e., nearly indistinguishable) from a given target probability
mass function (pmf).
A significant amount of work has been devoted to finding
the capacity regions of various coordination problems based
on both empirical and strong coordination [1]–[10], where
[4], [6]–[8], [10] focus on small to moderate network settings.
This work is supported by NSF grants CCF-1440014, CCF-1439465.

While all these works address the noiseless case, coordination over noisy channels has received only little attention in
the literature so far. However, notable exceptions are [11]–
[13]. For example, in [11] joint empirical coordination of
the channel inputs/outputs of a noisy communication channel
with source and reproduction sequences is considered. Also,
in [12] the notion of strong coordination is used to simulate a
discrete memoryless channel via another channel. Recently,
[13] explored the strong coordination variant of the problem
investigated in [11].
As an alternative to the impracticalities of random coding,
solutions for empirical and strong coordination problems
have been proposed based on low-complexity polar-codes
introduced by Arikan [14], [15]. For example, polar coding
for strong point-to-point coordination is addressed in [16],
[17], and empirical coordination for cascade networks in
[18], respectively. The only existing design of polar codes
for the noisy empirical coordination case [19] is based on the
joint source-channel coordination approach in [11]. However,
to the best of our knowledge, polar code designs for noisy
strong coordination have not been proposed in the literature.
In this work we consider the point-to-point coordination
setup depicted in Fig. 1 where only source and reproduction sequences are coordinated via a suitable polar coding
scheme over DMCs. In particular, we design an explicit lowcomplexity nested polar coding scheme for strong coordination over noisy channels that achieves the inner bound of
the two-node network capacity region of our earlier work
[20]. In this work, we show that a joint coordination-channel
coding scheme is able to strictly outperform a separationbased scheme in terms of achievable communication rate
if the same amount of randomness is injected into the
system. Note that our proposed joint coordination-channel
polar coding scheme employs nested codebooks similar to the
polar codes for the broadcast channel [21]. Further, our polar
coding scheme also offers a constructive solution to a channel
simulation problem where a DMC is employed to simulate
another DMC in the presence of shared randomness [12].
The remainder of the paper is organized as follows. Sec-

tion II introduces the notation, the model under investigation,
and a random coding construction. Section III provides our
proposed joint coordination-channel coding design and a
proof to show that this design achieves the random coding
inner bound.
II. P ROBLEM S TATEMENT
A. Notation
Let N , 2n , n ∈ N. We denote the source polarization
transform as Gn = RF ⊗n , where R is the bit-reversal
mapping defined in [14], F = [ 10 00 ] , and F ⊗n denotes the nth Kronecker power of F. Given X 1:N , (X 1 , X 2 , . . . , X N )
and A ⊂ J1, N K, we let X N [A] denote the components X i
such that i ∈ A. Given two distributions PX (x) and QX (x)
defined over an alphabet X , we let D(PX (x)||QX (x)) and
kPX (x) − QX (x)kT V denote the Kullback-Leibler (KL)
divergence and the total variation, respectively. Given a pmf
PX (x) we let min∗ (PX ) = min {PX (x) : PX (x) > 0}.
B. System Model
The point-to-point coordination setup considered in this
work is depicted in Fig. 1. Node X receives a sequence
of actions X N ∈ X N specified by nature where X N is
i.i.d. according to a pmf pX . Both nodes have access to
shared randomness J at rate Ro bits/action from a common
source, and each node possesses local randomness M` at rate
ρ` , ` = 1, 2.

strong coordination-channel random code with parameters
(Rc , Ro , Ra , N ) [20], where I , J1, 2N Rc K, J , J1, 2N Ro K,
and K , J1, 2N Ra K, consists of
1) Nested codebooks: A codebook C of size 2N (Ro +Rc )
is generated
QN i.i.d. according to a pmf PC , i.e.,
N
Cij
∼ l=1 PC (·) for all (i, j) ∈ I × J . A codebook A is generated by randomly selecting AN
ijk ∼
QN
N
l=1 PA|C (·|Cij ) for all (i, j, k) ∈ I × J × K.
2) Encoding functions:
C N : J1, 2N Rc K×J1, 2N Ro K → C N ,
AN : J1, 2N Rc K×J1, 2N Ro K×J1, 2N Ra K → AN .
3) The indices I, J, K are independent and uniformly
distributed over I, J , and K, respectively. These
N
indices select the pair of codewords CIJ
and AN
IJK
from codebooks C and A.
4) The selected codeword AN
IJK is sent through the
communication DMC PB|A , whose output B N is used
N
to decode codeword CIJ
ˆ , and both are then passed
through a DMC PY |BC to obtain Y N .
The corresponding scheme is displayed in Fig. 2.

Source of
Common Randomness
J

XN

Node X
Encoder

J

AN

DMC

BN

PB|A

Node Y
Decoder

M1

YN
M2

Fig. 1. Point-to-point strong coordination over a DMC.

We wish to communicate a codeword AN corresponding to
the coordination message over the rate-limited DMC PB|A to
Node Y. The codeword AN is constructed based on the input
action sequence X N , the local randomness M1 at Node X,
and the common randomness J. Node Y generates a sequence
of actions Y N ∈ Y N based on the received codeword B N ,
common randomness J, and local randomness M2 .
By assumption, the common randomness is independent of
the action specified at Node X. A strong coordination coding
scheme with rates (Rc , Ro , ρ1 , ρ2 ) is deemed achievable if
for each  > 0, there exists an N ∈ N such that the joint
pmf of actions P̃X N ,Y N induced by this scheme and the N
i.i.d. copies of desired joint pmf (X, Y ) ∼ qXY , QX N Y N ,
are close in total variation, i.e.,
kP̃X N Y N − QX N Y N kT V < .

(1)

C. Random Coding Construction
Consider auxiliary random variables A ∈ A and C ∈ C
with (A, C) ∼ PAC be jointly correlated with (X, Y )
as PXY ABC
= PAC PX|AC PB|A PY |BC . The joint

Fig. 2. Joint strong coordination-channel coding scheme.

The following theorem provides the inner bound for strong
coordination region achieved by such joint coordinationchannel code.
Theorem 1. (Strong coordination inner bound [20]) A tuple
(Ro , ρ1 , ρ2 ) is achievable for the strong noisy communication
setup in Fig. 1 if for some Ra , Rc ≥ 0,
Ra + Ro + Rc > I(XY ; AC),

(2a)

Ro + Rc > I(XY ; C),

(2b)

Ra + Rc > I(X; AC),

(2c)

Rc > I(X; C),

(2d)

Rc < I(B; C),

(2e)

ρ1 > Ra + Rc − I(X; AC),

(2f)

ρ2 > H(Y |BC).

(2g)

The underlying proofs and details of the coding mechanism for this joint coordination-channel coding scheme for
noisy strong coordination are based on a complex channel
resolvability framework [20]. Channel resolvability has been
successfully used to study different strong coordination problems due to its ability to approximate channel output statistics
with random codebooks [22]. We now propose a scheme

based on polar codes that achieves the inner bound stated
by Theorem 1 for the strong coordination region as follows.
III. N ESTED P OLAR C ODE FOR S TRONG C OORDINATION
OVER N OISY C HANNELS
Since the proposed joint coordination-channel coding
scheme is based on a channel resolvability framework, we
adopt the channel resolvability-based polar construction for
noise-free strong coordination [17] in combination with polar
coding for the degraded broadcast channel [21].
A. Coding Scheme
b distributed
Consider the random variables X, Y, A, B, C, C
according to QXY ABC Cb over X × Y × A × B × C such that
b − Y . Assume that |A| = 2 and the
X − (A, C) − (B, C)
distribution QXY is achievable with |C| = 2 † . Let N , 2n .
We describe the polar coding scheme as follows:

β

and δN , 2−N we define the very high and high entropy
sets
VC , {i ∈ J1, N K : H(U2i |U21:i−1 ) > 1 − δN },
VC|X , {i ∈ J1, N K : H(U2i |U21:i−1 X N ) > 1 − δN },

VC|XY , {i ∈ J1, N K : H(U2i |U21:i−1 X N Y N ) > 1 − δN },
HC|B , {i ∈ J1, N K : H(U2i |U21:i−1 B N ) > δN },
HC|A , {i ∈ J1, N K : H(U2i |U21:i−1 AN ) > δN },

(5)
which by [24, Lemma 7] satisfy
|VC|X |
|VC |
= H(C),
lim
= H(C|X),
lim
N →∞
N →∞ N
N
|HC|B |
|VC|XY |
= H(C|XY ),
lim
= H(C|B),
lim
N →∞
N →∞
N
N
|HC|A |
lim
= H(C|A).
N →∞
N
These sets are illustrated in Fig. 4. Note that the set
HC|B indicates the noisy bits of the DMC PB|C (i.e., the
unrecoverable bits of the codeword C N intended for the
weaker user in the DM-BC setup in Fig. 3) and is in general
not aligned with other sets. Let
L1 , VC \ HC|A ,

Fig. 3. Block diagram of the superposition polar code.

Consider a 2-user physically degraded discrete memoryless
broadcast channel (DM-BC) PAB|A in Fig. 3 where A
denotes the channel input and A, B denote the output to
the first and second receiver, respectively. In particular, the
channel DMC PB|A is physically degraded with respect to
the perfect channel PA|A (i.e., PA|A  PB|A ), leading to
the Markov chain A − A − B. We construct the nested polar
coding scheme in a similar fashion as in [21] as this mimics
the nesting of the codebooks C and A in Step 1) of the
random coding construction in Section II-C. Here, the second
(weaker) user is able to recover its intended message I, while
the first (stronger) user is able to recover both messages
K and I. Let C be the auxiliary random variable (cloud
center) required for superposition coding over the DM-BC
leading to the Markov chain C − A − (A, B). As a result,
the channel PB|C is also degraded with respect to PA|C
(i.e., PA|C  PB|C ) [21, Lemma 3]. Let V be a matrix of
the selected codewords AN and C N as
 N
A
V ,
.
(3)
CN
Now, apply the polar linear transformation Gn as
 N
U
U , 1N = V Gn .
U2

(4)

First, consider C N , U2N Gn from (3) and (4) where U2N
is generated by the second encoder E2 in Fig. 3. For β < 12
† For the sake of exposition, we only focus on the set of joint distributions over X × Y that are achievable with binary auxiliary random variables
C, A, and over a binary-input DMC. The scheme can be generalized to
non-binary C, A with non-binary polar codes in a straightforward way [23].

L2 , VC \ HC|B ,

where the set HC|A indicates the noisy bits of the DMC
PA|C (i.e., the unrecoverable bits of the codeword C N intended for the stronger user). From the relation PA|C  PB|C
c
c
we obtain HC|B
⊆ HC|A
. This ensures that the polarization
indices are guaranteed to be aligned (i.e., L2 ⊆ L1 ) [25],
[21, Lemma 4]. As a consequence, the bits decodable by the
weaker user are also decodable by the stronger user.
Now, consider AN , U1N Gn (see (3) and (4)), where
U1N is generated by the first encoder E1 with C N as a side
information as seen in Fig. 3. We define the very high entropy
sets illustrated in Fig. 5 as

Fig. 4. Index sets for codeword C.

Fig. 5. Index sets for codeword A.

VA , {i ∈ J1, N K : H(U1i |U11:i−1 ) > 1−δN},

VA|C , {i ∈ J1, N K : H(U1i |U11:i−1 C N ) > 1−δN},

VA|CX , {i ∈ J1, N K : H(U1i |U11:i−1 C N X N ) > 1−δN},

VA|CXY , {i ∈ J1, N K : H(U1i |U11:i−1 C N X N Y N ) > 1−δN}
(6)

satisfying
|VA|CX |
|VA |
lim
= H(A),
lim
= H(A|CX),
N →∞ N
N →∞
N
|VA|CXY |
|VA|C |
= H(A|C), lim
= H(A|CXY ).
lim
N →∞
N →∞
N
N
Note that, in contrast to Fig. 4, here there is no channel
dependent set overlapping with all other sets as PA|A is a
noiseless channel with rate H(A) and hence HA|A = ∅.
Accordingly, in terms of the polarization sets in (5) and
(6) we define the sets combining channel resolvability for
strong coordination and broadcast channel construction
c
F1 , (VC|X \ VC|XY ) ∩ HC|B
,
c
F2 , VC|XY ∩ HC|B
,
c
F3 , VC|X
∩ HC|B = HC|B \ HC|BX ,

F4 , VC|X ∩ HC|B = HC|BX ,
F̂4 , HC|BXY ,

Fig. 6. Chaining construction for block encoding.

the following block i + 1. This is possible by following
the decodability constraint (see (2d), (2e) of Theorem 1)
c
that ensures that the size of the set F3 is smaller than the
F5 , (VC \ VC|X ) ∩ HC|B ,
combined size of the sets F1 and F2 [19]. However, since
F6 , VA|CX \ VA|CXY ,
these sets originally contain uniformly distributed common
F7 , VA|CXY ,
randomness J [17], the bits of F3 can be embedded while
maintaining the uniformity of the randomness by taking
F8 , VA|C \ VA|CX ,
advantage of the Crypto Lemma [27, Lemma 2]. Then, to
F9 , VA \ VA|C .
ensure that F3 is equally distributed over F1 ∪ F2 , F3 is
Finally, with Y N , T N Gn , we define the very high partitioned according to the ratio between |F1 | and |F2 |. To
(i)
entropy set:
utilize the Crypto Lemma, we introduce F32 and F31 , which
represent uniformly distributed common randomness used to
VY |BC , {i ∈ J1, N K : H(T i |T 1:i−1 B N C N ) > log |Y|−δN },
randomize the information bits of F3 . The difference is that
(7)
F32 , as F2 , represents a fraction of common randomness
satisfying
that can be reused over k blocks whereas a realization of the
|VY |BC |
(i)
= H(Y |BC).
lim
randomness in F31 needs to be provided in each new block.
N →∞
N
This set is useful for expressing the randomized generation Note that, as visualized in Fig. 6, both the subsets F́31 ⊂ F1
of Y N via simulating the channel PY |BC in Fig. 2 as a source and F́32 ⊂ F2 represent the resulting uniformly distributed
polarization operation [17]. We now proceed to describe the bits of F3 of the previous block, where |F́31 | = |F31 | and
|F́32 | = |F32 |. Finally, in an additional block k + 1 we use a
encoding and decoding algorithms.
1) Encoding: The encoding protocol described in Algo- good channel code to reliably transmit the set F3 of the last
rithm 1 is performed over k ∈ N blocks of length N . Since block k.
2) Decoding: The decoder is described in Algorithm 2.
for strong coordination the goal is to approximate a target
Recall that we are only interested in the message Iˆ intended
joint distribution with a minimum amount of randomness,
for the weak user channel given by PB|A in Figure 3. As a
the encoding scheme performs channel resolvability while
result, we only state the decoding protocol at D2 that recovers
reusing a fraction of the common randomness over several
b N . Note that the decoding is done in reverse
the codeword C
blocks (i.e., randomness recycling) as in [17]. However, since
order after receiving the extra k + 1 block containing the bits
the communication is over a noisy channel, the encoding
of set F3 of the last block k. In particular, in each block
scheme also considers a block chaining construction to
i ∈ [1, k − 1] the bits in F3 are obtained by successfully
mitigate the channel noise influence as in [19], [24]–[26].
recovering the bits in both F1 and F2 in block i + 1.
More precisely, as demonstrated in Fig. 2, we are interested
in successfully recovering the message I that is intended for
B. Scheme Analysis
the weak user channel given by PB|A in Fig. 3. However,
the challenge is to communicate the set F3 that includes bits
We now provide an analysis of the coding scheme of
of the message I that are corrupted by the channel noise. Section III. The analysis is based on KL divergence which
This suggests that we apply a variation of block chaining upper bounds the total variation in (1) by Pinsker’s inequality.
only at encoder E2 generating the codeword C N as follows We start the analysis with a set of sequential lemmas. In
(see Fig. 6). At encoder E2 , the set F3 of block i ∈ J1, kK particular, Lemma 1 is useful to show in Lemma 2 that the
is embedded in the reliably decodable bits of F1 ∪ F2 of strong coordination scheme based on channel resolvability
F̌4 , HC|BX \HC|BXY ,

Algorithm 1: Encoding algorithm at Node X for strong
coordination

Algorithm 2: Decoding algorithm at Node Y for strong
coordination

N
Input: X1:k
, uniformly distributed local randomness bits
M11:k of the size k|F6 |, common randomness bits J¯ =
(J¯1 , J¯2 ) of sizes |F2 ∪ F̂4 |, and |F7 |, respectively, and
J1:k of size k|F̌4 ∪ F1 | shared with Node Y.
eN
Output: A
1:k
1. for i = 2, . . . , k do
e N bit-by-bit as follows:
2. E2 in Fig. 3 constructs U
2i
if i = 1 then
e N [F1 ∪ F̌4 ] ← Ji
• U
2i
N
e
• U2i [F2 ∪ F̂4 ] ← J¯1
else
(i)
• Let F3 , F32 be sets of the size (|Fm | ×
1
|F3 |)/(|F1 | + |F2 |) for m ∈ {1, 2}.
e N [(F1 \ F́3 ) ∪ F̌4 ], F (i) ← Ji
•
U
2i
1
31 
e N [(F2 \ F́3 ) ∪ F̂4 ], F3 ← J¯1
•
U
2i
2
2
e N [F́3 ] ← U
e N [F3 \ F3 ] ⊕ F (i)
• U
2i
2i−1
1
2
31
e N [F́3 ] ← U
e N [F3 \ F3 ] ⊕ F3
• U

N
Input: B1:k
, uniformly distributed common randomness,
¯
J1 , and J1:k shared with Node X.
N
Output: Ye1:k
1. For block i = k, . . . , 1 do
b N bit-by-bit as follows:
2. D2 in Fig. 3 constructs U
2i

b N [(F1 \ F́ ) ∪ F̌4 ], F (i) ← Ji
•
U
31
2i
31 
b N [(F2 \ F́3 ) ∪ F̂4 ], F3 ← J¯1
•
U
2i
2
2
N
bN
• Given B
successively draw the components of U

2i

2

2i−1

1

2

end
N
• Given Xi , successively draw the remaining come N according to P̃ j 1:j−1 N defined
ponents of U
2i
U2 |U2
Xi
i
i
by
(
QU j |U 1:j−1
j ∈ VCc ,
2
2
P̃U j |U 1:j−1 X N ,
2i
2i
i
QU j |U 1:j−1 X N j ∈ F3 ∪ F5 .
2
2
(8)
N
N
e
e
3. Ci ← U2i Gn
e N bit-by-bit as follows:
4. E1 in Fig. 3 constructs U
1i
e N [F6 ] ← M1
• U
1i
i
e N [F7 ] ← J¯2
• U
1i
N
e N , successively draw the remaining
• Given Xi and C
i
e N according to P̃ j 1:j−1 N N
components of U
1i
U1 |U1
Ci Xi
i
i
defined by

c
j ∈ VA
,
QU1j |U11:j−1

j ∈ F9 ,
P̃U j |U 1:j−1 C N X N , QU j |U 1:j−1 C N
1i
1i
i
i

 1 1
QU j |U 1:j−1 C N X N j ∈ F8 .
1
1
(9)
eN ← U
e N Gn
5. A
1i
i
eN
6. Transmit A
i
7. end for

holds for each block individually regardless of the randomness recycling.

2i

i

according to P̃U j |U j−1 ,B N defined by
2i
2i
i
(
QU j |U 1:j−1
j ∈ VCc ,
2
2
P̃U j |U j−1 B N ,
2i
2i
i
QU j |U 1:j−1 B N j ∈ F́32 ∪ F́31 ∪F5 .
2
2
i
(10)
3. if i = k then
b N [F3 ] ← B N
• U
2i
k+1
else
b N [F3 \ F3 ] ← U
b N [F́3 ] ⊕ F (i+1)
• U
2i
2i+1
2
1
31
N
b [F3 \ F3 ] ← U
b N [F́3 ] ⊕ F3
• U
2i
2i+1
1
2
2
4. Let
b N [F́ ] ← F (i)
• U
2i
31
31
b N [F́3 ] ← F3
• U
2i
2
2
N
N
b
b
5. Ci ← U2i Gn
b N and Bi N , successively
6. Channel simulation: given C
i
N
e
draw the components of Ti according to
(
1/|Y|
j ∈ VY |BC ,
P̃T j |T 1:j−1 B N C N ,
i
i
i
i
QT j |T 1:j−1 B N C N j ∈ VYc |BC .
(11)
5. YeiN ← TeiN Gn
6. end for

Proof. We have

N
N)
D(QAN C N X N ||P̃AN
i Ci Xi

(a)

= D(QU1N U2N X N ||P̃U1N U2N XiN )
i
i
h
i
(b)
= EQX N D(QU1N U2N |X N ||P̃U1N U2N |XiN )
i
i
h
i
= EQX N D(QU2N |X N QU1N |U2N X N ||P̃U2N |XiN P̃U1N |U2N XiN )
i
i
i
h
(c)
= EQX N D(QU2N |X N ||P̃U2N |XiN )
i
i
+ D(QU1N |U2N X N ||P̃U1N |U2N XiN )
i

Lemma 1. For block i ∈ J1, kK, we have

N
(d) X
=
EQ

1:j−1
U2
X

j=1

N
N ) ≤ 2N δN .
D(QAN C N X N ||P̃AN
i Ci Xi

+

N
X
j=1

EQ

i

h
D(QU j |U 1:j−1 X N ||P̃U j
N

1:j−1 N N
U1
U2 X

2

2

2i

|U21:j−1 XiN )

i

i

h
i
D(QU j|U 1:j−1U NX N||P̃U j |U 1:j−1U NX N )
1

1

2

1i

1i

2i

i

(e)

h

X

=

EQ

j ∈F
/ 3 ∪F5

1:j−1 N
U2
X

X
+ EQ

1:j−1 N
U1
U2 X

j ∈F
/ 8

(f )

X

=

EQ
X

+

2

1:j−1
XiN
2i |U2i

2

h
D(QU j |U 1:j−1U NX N ||P̃U j
N
1

1:j−1
U2
X

c ∪V
j∈VC
C|X

D(QU j |U 1:j−1 X N ||P̃U j
1

2

1i

1i

2i

i

1:j−1
XiN
2i |U2i

2

1:j−1 N N
U1
U2 X

D(QU j |U 1:j−1 U N X N ||P̃U j
1

=

X 

)

i

h
EQ

c ∪V
j∈VA
A|CX ∪VA\VA|C

(g)

D(P̃XiN YiN ||QX N Y N )

i
|U 1:j−1U NX N )

h
D(QU j |U 1:j−1 X N ||P̃U j
N
2

Lemma 2. For block i ∈ J1, kK, we have

i
)

1

1:j−1 N
U2 XiN
1i |U1i
i

2

H(U2j |U21:j−1 ) − H(U2j |U21:j−1 X N )

)

i



c
j∈VC

X 

+


1 − H(U2j |U21:j−1 X N )

X 

H(U1j |U11:j−1 ) − H(U1j |U11:j−1 U2N X N )



c
j∈VA

X 

+

1 − H(U1j |U11:j−1 U2N X N )


X

H(U1j |U11:j−1 U2N ) − H(U1j |U11:j−1 U2N X N )



c
c
j∈VA|C
\VA

(h)

=

X 

H(U2j |U21:j−1 ) − H(U2j |U21:j−1 X N )



X 

1 − H(U2j |U21:j−1 X N )



+

1−

+

i

i

i

i

i

= D(QB N |AN QCbN |B N ||QB N |AN P̃CbN |B N )
i



H(U1j |U11:j−1 C N X N )

i

= D(QCbN |B N ||P̃CbN |B N )
i

j∈VA|CX

X

i

(a)

c
j∈VA

+

(f) follows from the chain rule of KL divergence [28];
(g) holds by [17, Lemma 14], where

µACB Cb , min∗a,c,b,ĉ QACB Cb ,

µY B Cb , min∗y,b,ĉ QY B Cb ;

D(QB N CbN |AN C N ||P̃B N CbN |AN C N )


H(U1j |U11:j−1 ) − H(U1j |U11:j−1 C N X N )

X 

√
(2)
where δN , O( N 3 δN ).
Proof. Consider the argument shown at the top of the following page. In this argument:
(a) - (b) results from the Markov chain X N − AN C N −
b N −Y N ;
BN C
(c) follows from [17, Lemma 16] where
p
√
(2)
δ̂N , −N log(µXACB CY
b ) 2 ln 2 2N δN ,

∗
µXACB CY
;
b , minx,y,a,c,b,ĉ QXACB CY
b

i

j∈VC|X

X 

i

(h) holds by bounding the terms
D(QB N CbN |AN C N ||P̃B N CbN |AN C N ), and
i
i
i
i
D(QY N |B N CbN ||P̃Y N |B N CbN ), as follows:

c
j∈VC

+

i



j∈VA|CX

+

i

i

i

i

(d) follows from the chain rule of KL divergence [28];
(e) holds by Lemma 1 and [17, Lemma 14] where
p
√
(1)
δN , −N log(µXAC ) 2 ln 2 2N δN ,

µXAC , min∗x,a,c QXAC ;

j∈VC|X

+

(2)

≤ D(P̃X N AN C N B N CbN Y N ||QX N AN C N B N CbN Y N ) ≤ δN

i

(b)



H(U1j |U11:j−1 C N ) − H(U1j |U11:j−1 C N X N )



= D(QUb N |B N ||P̃Ub N |B N )
i

N
(c) X
=
EQ

c
c
j∈VA|C
\VA

(i)

1:j−1 N
B
U2

j=1

c
≤ (|VCc | + |VC|X | + |VA|XC | + |VA|C
|)δN ≤ 2N δN

(d)

=

where
(a) holds by invertibility of Gn ;
(b) - (d) follows from the chain rule of the KL divergence
[28];
(e) results from the definitions of the conditional distributions in (8), and (9);
(f) follows from the definitions of the index sets as shown
in Figures 4 and 5;
e N and U
e N bit-by-bit
(g) results from the encoding of U
1i
2i
at E1 and E2 , respectively, with uniformly distributed
randomness bits and message bits. These bits are generated by applying successive cancellation encoding using
previous bits and side information with conditional
distributions defined in (8) and (9);
(h) holds by the one-to-one relation between U2N and C N ;
(i) follows from the sets defined in (5) and (6).


X

EQ

1:j−1 N
U2
B

X

=

2

X

2

2i

|U21:j−1 BiN )

2

1:j−1 N
U2
B

i

i

D(QU j |U 1:j−1 B N ||P̃U j
h

EQ

j∈HC|B ∪VC|X
(e)

D(QU j |U 1:j−1 B N ||P̃U j

h

c
j∈VC

+

i

h

)

i

1:j−1 N
Bi
2i |U2i

2

D(QU j|U 1:j−1B N||P̃U j |U 1:j−1B N)
2

2

2i

H(U2j |U21:j−1 ) − H(U2j |U21:j−1 B N )

2i

i

i



c
j∈VC

X

+




1 − H(U2j |U21:j−1 B N )

j∈HC|B ∪VC|X
(f )

≤ |VCc |δN + |HC|B ∪ VC|X |δN ≤ N δN ,

where
b and
(a) results from the Markov chain C − A − B − C
N
N
the fact that P̃BiN |AN
=
Q
;
B |A
i
(b) holds by the one-to-one relation between U2N and
CN ;
(c) follows from the chain rule of KL divergence [28];

D(P̃X N AN C N B N CbN Y N ||QX N AN C N B N CbN Y N )
i

i

i

i

i

i

= D(P̃Y N |X N AN C N B N CbN P̃X N AN C N B N CbN ||QY N |X N AN C N B N CbN QX N AN C N B N CbN )
i

i

i

i

i

i

i

i

i

i

i

(a)

= D(P̃Y N |B N CbN P̃X N AN C N B N CbN ||QY N |B N CbN QX N AN C N B N CbN )
i

i

i

i

i

i

i

i

N ||Q N
= D(P̃Y N |B N CbN P̃B N CbN |X N AN C N P̃XiN AN
bN QB N C
bN |X N AN C N QX N AN C N )
Y |B N C
i Ci
i

i

i

i

i

i

i

i

(b)

N ||Q N
= D(P̃Y N |B N CbN P̃B N CbN |AN C N P̃XiN AN
bN QB N C
bN |AN C N QX N AN C N )
Y |B N C
i Ci
i

i

(c)

≤

(2)
δ̂N

i

i

i

i

i

N ||P̃ N
+ D(P̃Y N |B N CbN P̃B N CbN |AN C N P̃XiN AN
bN P̃B N C
bN |AN C N QX N AN C N )
Y |B N C
i Ci
i

i

i

i

i

i

i

i

i

i

i

i

i

i

+ D(P̃Y N |B N CbN P̃B N CbN |AN C N QX N AN C N ||QY N |B N CbN QB N CbN |AN C N QX N AN C N )
i

i

(d)

=

(2)
δ̂N

(e)

i

i

i

i

i

N ||QX N AN C N ) + D(P̃ N
+ D(P̃XiN AN
bN QB N C
bN |AN C N )
bN P̃B N C
bN |AN C N ||QY N |B N C
Y |B N C
i Ci
i

i

(2)

(1)

(2)
δ̂N

+

(1)
δN

+

(1)
δN

i

i

i

i

i

≤ δ̂N + δN + D(P̃Y N |B N CbN P̃B N CbN |AN C N ||QY N |B N CbN QB N CbN |AN C N )
i

(f )

i

i

i

i

i

i

+ D(P̃Y N |B N CbN ||QY N |B N CbN ) + D(P̃B N CbN |AN C N ||QB N CbN |AN C N )
i
i
i
i
i
i
i
q
(g)
√
(2)
(1)
≤ δ̂N + δN − N log(µY B Cb ) 2 ln 2 D(QY N |B N CbN ||P̃Y N |B N CbN )
i
i
i
q
√
− N log(µACB Cb ) 2 ln 2 D(QB N CbN |AN C N ||P̃B N CbN |AN C N )
=

i

(h)

≤

(2)
δ̂N

i

=

j=1
(b)

=

X

EQT 1:j−1BNCb N D(QT j |T 1:j−1B NCbN ||P̃T j |T 1:j−1B NCbN )
i

=

i

i

Lemma 4. We have
i

X 

i

i

log |Y| − H(T j |T 1:j−1 B N C N )

i



N Y N ||
D P̃X1:k
1:k

k
Y

P̃XiN YiN



(3)

≤ (k − 1)δN

i=1

where

(3)
δN

is defined in Lemma 3.

Proof. We reuse the proof of [17, Lemma 4] with substitutions p̃Yi1:N ← P̃XiN YiN , and R̄1 ← J¯1 . This will result
N
N
N eN
in the Markov chain X1:i−2
Ye1:i−2
− J¯1 Xi−1
Yi−1 − XiN YeiN
replacing the chain in [17, Lemma 4].


j∈VY |BC
(d)

≤ |VY |BC |δN ≤ N δN ,
where
(a) follows from the chain rule of KL divergence [28];
(b) - (c) results from the definitions of the conditional
distribution in (11);
(d) follows from the set defined in (7).


Now, Lemmas 3 and 4 provide the independence between
two consecutive blocks and the independence between all
blocks based on the results of Lemma 2.
Lemma 3. For block i ∈ J2, kK, we have



i

i
h
EQT 1:j−1BNCb N D(QT j |T 1:j−1B NCbN ||P̃T j |T 1:j−1B NCbN )
i

i

p̃Yi1:N ← P̃YiNXiN , and R̄1 ← J¯1 . This will result in the
N eN
Markov chain Xi−1
Yi−1 − J¯1 − XiNYeiN replacing the chain
in [17, Lemma 3].


i

h

j∈VY |BC
(c)

i

i

p
p
√
− N log(µY B Cb ) 2 ln 2 N δN − N log(µACB Cb ) 2 ln 2 N δN

(d) - (e) results from the definitions of the conditional
distributions in (10);
(f) follows from the sets defined in (5).
D(QY N |B N CbN ||P̃Y N |B N CbN )
N
(a) X

i

√

Finally, by the results of Lemma 4 we can show in
Lemma 5 that the target distribution QX N Y N is approximated
asymptotically over all blocks jointly.
Lemma 5. We have


(4)
N Y N ||QX 1:kN Y 1:kN
D P̃X1:k
≤ δN .
1:k
(4)

1/8

where δN , O(k 3/2 N 23/8 δN )
Proof. We reuse the proof of [17, Lemma 5] with substitutions qY 1:N ← QX N Y N , p̃Yi1:N ← P̃YiN XiN .


(3)

N
N
N YN J
D(P̃Xi−1:i
¯ P̃ N N ) ≤ δN
Yi−1:i
J¯1 ||P̃Xi−1
i−1 1 Xi Yi
√
(3)
where δN , O( 4 N 15 δN ).

Proof. We reuse the proof of [17, Lemma 3] with substitutions qU 1:N ← QC N , qY 1:N ← QX NY N , p̃Ui1:N ← P̃CiN ,

Theorem 2. The polar coding scheme described in Algorithms 1, 2 achieves the region stated in Theorem 1. It
satisfies (1) for a binary input DMC channel and a target
distribution qXY defined over X ×Y, with an axillary random
variable C defined over the binary alphabet.

Proof. The common randomness rate Ro is given as
|VC|XY | + k|VC|X \ VC|XY |
|J¯1 | + |J1:k |
=
kN
Nk
|VC|XY | |VC|X \ VC|XY |
=
+
kN
N
N →∞ H(C|XY )
−−−−→
+ I(Y ; C|X)
k
k→∞
−−−−→ I(Y ; C|X).

(12)

The communication rate Rc is given as
k|VC \ VC|X |
|VC \ VC|X |
k|F5 ∪ F3 |
=
=
kN
Nk
N
N →∞
−−−−→ I(X; C),

(13)

whereas Ra can be written as
|VA|CXY | + k|F8 |
|VA|CXY | + k|VA|C \ VA|CX |
=
kN
kN
|VA|CXY | |VA|C \ VA|CX |
=
+
kN
N
H(A|CXY )
N →∞
−−−−→ I(A; X|C) +
k
k→∞
−−−−→ I(A; X|C).
(14)
The rates of local randomness ρ1 and ρ2 , respectively, are
given as
ρ1 =

k|VA|CX \ VA|CXY |
|VA|CX \ VA|CXY |
k|F6 |
=
=
kN
Nk
N
N →∞
−−−−→ I(A; Y |CX) and
(15)
k|VY |BC | N →∞
ρ2 =
−−−−→ H(Y |BC).
(16)
kN

Finally we see that conditions (2a)-(2g) are satisfied by
(12)-(16). Hence, given Ra , Ro , Rc satisfying Theorem 1,
based on Lemma 5 and Pinsker’s inequality we have


N Y N − QX 1:kN Y 1:kN ||T V
E ||P̃X1:k
1:k
i
hq
N Y N ||QX 1:kN Y 1:kN )
≤ E 2D(P̃X1:k
1:k
q 
 N →∞
N Y N ||QX 1:kN Y 1:kN )
≤ 2E D(P̃X1:k
−→ 0.
(17)
1:k
As a result, from (17) there exists an N ∈ N for which the
polar code-induced pmf between the pair of actions satisfies
the strong coordination condition is given by (1).

R EFERENCES
[1] E. Soljanin, “Compressing quantum mixed-state sources by sending
classical information,” IEEE Trans. Inf. Theory, vol. 48, no. 8, pp.
2263–2275, Aug. 2002.
[2] P. W. Cuff, H. H. Permuter, and T. M. Cover, “Coordination capacity,”
IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4181–4206, 2010.
[3] A. A. Gohari and V. Anantharam, “Generating dependent random
variables over networks,” in Proc. IEEE Inf. Theory Workshop, Paraty,
Brazil, Oct. 2011, pp. 698–702.
[4] F. Haddadpour, M. H. Yassaee, A. Gohari, and M. R. Aref, “Coordination via a relay,” in Proc. IEEE Int. Sympos. on Inform. Theory,
Cambridge, MA, USA, Jul. 2012, pp. 3048–3052.
[5] P. Cuff, “Distributed channel synthesis,” IEEE Trans. Inf. Theory,
vol. 59, no. 11, pp. 7071–7096, 2013.

[6] A. Bereyhi, M. Bahrami, M. Mirmohseni, and M. R. Aref, “Empirical
coordination in a triangular multi-terminal network,” in Proc. IEEE
Int. Sympos. on Inform. Theory, Istanbul, Turkey, 2013, pp. 2149–
2153.
[7] M. R. Bloch and J. Kliewer, “Strong coordination over a line network,”
in Proc. IEEE Int. Sympos. on Inform. Theory, Istanbul, Turkey, Jul.
2013, pp. 2319–2323.
[8] ——, “Strong coordination over a three-terminal relay network,” in
Proc. IEEE Inf. Theory Workshop, Hobart, Australia, Nov. 2014, pp.
646–650.
[9] M. H. Yassaee, A. Gohari, and M. R. Aref, “Channel simulation via
interactive communications,” IEEE Trans. Inf. Theory, vol. 61, no. 6,
pp. 2964–2982, 2015.
[10] B. N. Vellambi, J. Kliewer, and M. R. Bloch, “Strong coordination
over multi-hop line networks,” arXiv preprint, 2016. [Online].
Available: http://arxiv.org/abs/1602.09001
[11] P. Cuff and C. Schieler, “Hybrid codes needed for coordination over
the point-to-point channel,” in Proc. 49th Annual Allerton Conf. on
Commun., Control, and Comp., Monticello, IL, Sep. 2011, pp. 235–
239.
[12] F. Haddadpour, M. H. Yassaee, S. Beigi, A. Gohari, and M. R. Aref,
“Simulation of a channel with another channel,” IEEE Trans. Inf. Theory, vol. 63, no. 5, pp. 2659–2677, May 2017.
[13] G. Cervia, L. Luzzi, M. L. Treust, and M. Bloch, “Strong coordination
of signals and actions over noisy channels,” in Proc. IEEE Int. Sympos. on Inform. Theory, Aachen, Germany, June 2017, pp. 2835–2839.
[14] E. Arikan, “Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,”
IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, July 2009.
[15] ——, “Source polarization,” in Proc. IEEE Int. Sympos. on Inform. Theory, June 2010, pp. 899–903.
[16] M. R. Bloch, L. Luzzi, and J. Kliewer, “Strong coordination with polar
codes,” in 50th Annual Allerton Conference on Commununication,
Control, and Computing, Monticello, IL, USA, Oct. 2012, pp. 565–
571.
[17] R. A. Chou, M. Bloch, and J. Kliewer, “Empirical and strong
coordination via soft covering with polar codes,” arXiv preprint,
2016. [Online]. Available: http://arxiv.org/abs/1608.08474
[18] R. Blasco-Serrano, R. Thobaben, and M. Skoglund, “Polar codes for
coordination in cascade networks,” in International Zurich Seminar
on Communications (IZS). Eidgenössische Technische Hochschule
Zürich, 2012, pp. 55–58.
[19] G. Cervia, L. Luzzi, M. R. Bloch, and M. L. Treust, “Polar coding for
empirical coordination of signals and actions over noisy channels,” in
Proc. IEEE Inf. Theory Workshop, Sept 2016, pp. 81–85.
[20] S. A. Obead, B. N. Vellambi, and J. Kliewer, “Strong coordination over
noisy channels: Is separation sufficient?” in Proc. IEEE Int. Sympos. on
Inform. Theory, Aachen, Germany, June 2017, pp. 2840–2844.
[21] N. Goela, E. Abbe, and M. Gastpar, “Polar codes for broadcast
channels,” IEEE Trans. Inf. Theory, vol. 61, no. 2, pp. 758–782, Feb
2015.
[22] T. S. Han and S. Verdú, “Approximation theory of output statistics,”
IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 752–772, 1993.
[23] E. Şaşoğlu, E. Telatar, and E. Arikan, “Polarization for arbitrary
discrete memoryless channels,” in Proc. IEEE Inf. Theory Workshop,
Oct 2009, pp. 144–148.
[24] R. A. Chou and M. R. Bloch, “Polar coding for the broadcast
channel with confidential messages: A random binning analogy,” IEEE
Trans. Inf. Theory, vol. 62, no. 5, pp. 2410–2429, May 2016.
[25] M. Mondelli, S. H. Hassani, I. Sason, and R. L. Urbanke, “Achieving
Marton’s region for broadcast channels using polar codes,” IEEE
Trans. Inf. Theory, vol. 61, no. 2, pp. 783–800, Feb 2015.
[26] E. E. Gad, Y. Li, J. Kliewer, M. Langberg, A. A. Jiang, and J. Bruck,
“Asymmetric error correction and flash-memory rewriting using polar
codes,” IEEE Trans. Inf. Theory, vol. 62, no. 7, pp. 4024–4038, July
2016.
[27] G. D. Forney Jr., “On the role of MMSE estimation in approaching
the information-theoretic limits of linear Gaussian channels: Shannon
meets Wiener,” in Proc. 41st Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, Oct 2003, pp.
430–439.
[28] T. M. Cover and J. Thomas, Elements of Information Theorey, 2nd ed.,
ser. Wiley Series in Telecommunications and Signal Processing.
Wiley-Interscience, 2006.

