Polar codes for empirical coordination over noisy channels with
strictly causal encoding
Giulia C ERVIA1 , Laura L UZZI1 , Maël L E T REUST1 , Matthieu R. B LOCH2
1 ETIS

UMR 8051, Université Paris Seine, Université Cergy-Pontoise, ENSEA, CNRS, Cergy, France.

2 School

arXiv:1802.09795v1 [cs.IT] 27 Feb 2018

of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia
{giulia.cervia, laura.luzzi, mael.le-treust}@ensea.fr, matthieu.bloch@ece.gatech.edu

Résumé – Dans ce travail, nous proposons un schéma de codage basé sur les codes polaires pour la coordination empirique d’appareils
autonomes. Nous considérons un réseau simple composé de deux nœuds reliés par un lien bruité, et nous cherchons à coordonner les signaux
en entrée et en sortie du canal, avec la source et sa reconstruction. Lorsque l’encodeur est strictement causal, nous montrons que les codes
polaires atteignent la région optimale de coordination empirique, à condition que les deux nœuds partagent une source aléatoire, dont le débit est
asymptotiquement négligeable.

Abstract – In this paper, we propose a coding scheme based on polar codes for empirical coordination of autonomous devices. We consider a
two-node network with a noisy link in which the input and output signals have to be coordinated with the source and the reconstruction. In the
case of strictly causal encoding, we show that polar codes achieve the empirical coordination region, provided that a vanishing rate of common
randomness is available.

1

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 [1].
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 [2], the authors provide a characterization of
the coordination region when the encoder is strictly causal. Inspired by the binning technique using polar codes in [3], we
propose an explicit coding scheme that achieves a subset of the
coordination region in [2] by turning the argument of [4] 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 [5]. 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. Section 2
introduces the notation, describes the model under investigation and states the main achievability result. Section 3 details
the proposed coordination scheme using polar codes. Finally,
Section 4 proves the main result.

2
2.1

Problem statement
Notation

We define [a, b] as the set of the integers between a and b. For
h
i⊗m
1 0
n = 2m , m ∈ N, we note Gn := 1 1
the source polarization transform defined in [6]. 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 V(·, ·) and D(·k·) the variational distance
and the Kullback-Leibler divergence between two distributions, respectively.

2.2

System model and main result
C
S 1:n

Node
1

X 1:n

PY |X

Y 1:n

Node
2

Sb1:n

F IGURE 1 – Coordination of signals and actions for a two-node network with a noisy channel.

We consider two agents, Node 1 and Node 2, who have access to a shared randomness source C ∈ Cn (Figure 1).
Node 1 observes an i.i.d. sequence of actions S 1:n ∈ S n
with discrete probability distribution PS . Node 1 then selects a signal X 1:n such that X i = fi (S 1:i−1 , C), where
f n = {fi }ni=1 , fi : S i−1 × Cn → X is the strictly causal encoder. The signal X 1:n is transmitted over a discrete memoryless channel with transition probability PY |X . Upon receiving
Y 1:n ∈ Y n , Node 2 selects an action Sb1:n = g n (Y 1:n , C),
where g n : Y n × Cn → Sbn 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
PSXY Sb. We focus on the empirical coordination metric defined
in [1].

Polarize X Let Z 1:n = X 1:n Gn be the polarization of
X 1:n , where Gn is the source polarization transform. For some
β
0 < β < 1/2, let δn := 2−n and define the very high and high
entropy sets :

VX : = j ∈ [1, n] : H(Z j |Z 1:j−1 ) > 1 − δn ,

HX : = j ∈ [1, n] : H(Z j |Z 1:j−1 ) > δn ,
(2)

j
1:j−1 1:n
HX|Y : = j ∈ [1, n] : H(Z |Z
Y ) > δn .
Partition the set [1, n] into four disjoint sets :
A1 := VX ∩ HX|Y ,

c
,
A2 := VX ∩ HX|Y

c
A3 := VX
∩ HX|Y ,

c
c
.
A4 := VX
∩ HX|Y

Remark 6. We have :

|HX \ VX |
= 0 [6],
n
|VX |
• A1 ∪ A2 = VX and lim
= H(X) [7],
n→∞ n
|HX|Y |
= H(X|Y ) [6].
• A1 ∪ A3 = HX|Y and lim
n→∞
n
|A2 | − |A3 |
Since lim
= H(X) − H(X|Y ) = I(X; Y ) ≥ 0
n→∞
n
this implies directly that for n large enough |A2 | ≥ |A3 |.
• VX ⊂ HX and lim

n→∞

Definition 1. A distribution PSXY Sb is achievable if for all ε >
0 there exists a sequence of codes {(f n , g n )}n∈N such that


lim P V TS 1:n X 1:n Y 1:n Sb1:n , PSXY Sb > ε = 0,
n→∞

where TS 1:n X 1:n Y 1:n Sb1:n (s, x, y, ŝ) is the empirical distribution of the tuple (S 1:n , X 1:n , Y 1:n , Sb1:n ) induced by the code.
The empirical coordination region C is the set of achievable
distributions PSXY Sb.
Theorem 2 (Strictly causal encoder [2]). Let PS and PY |X be
the given source and channel parameters. When the encoder is
strictly causal, the coordination region C is given by


PSXY Sb : PSXY Sb = PS PX PY |X PS|SXY
b








∃ U taking values in U


PSXY U Sb = PS PX PU |XS PY |X PS|U
(1)
C :=
b Y






I(X,
U
;
S)
≤
I(X,
U
;
Y
)




b +1
|U| ≤ |S||X ||Y||S|
Remark 3. 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 (1) becomes
I(U ; S|X) ≤ I(X; Y ).
Theorem 4. For all PSXY Sb ∈ C such that U = {0, 1}, there
exists an explicit polar coding scheme that achieves empirical
coordination with vanishing rate of common randomness.
Remark 5. Since U is binary we only achieve a subset of C.
The proof can be generalized to the case where |U| is a prime
number using non-binary polar codes.

3

Polar coding scheme

Consider the random vectors S 1:n , U 1:n , X 1:n , Y 1:n and
1:n
b
S
generated i.i.d. according to PSXU Y Sb that factorize
as in (1) with the same mutual information and cardinality
constraints.

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

VU |XS : = j ∈ [1, n] : H(V j |V 1:j−1 X 1:n S 1:n ) > 1 − δn ,

HU |XS : = j ∈ [1, n] : H(V j |V 1:j−1 X 1:n S 1:n ) > δn ,

HU |X : = j ∈ [1, n] : H(V j |V 1:j−1 X 1:n ) > δn .
(3)
Partition the set [1, n] into four disjoint sets :
c
B1 := VU |XS ∩ HU |X = VU |XS , B2 := VU |XS ∩ HU
|X = ∅,
B3 := VUc |XS ∩ HU |X ,

c
c
B4 := VUc |XS ∩ HU
|X = HU |X .

Remark 7. We have :

|HU |XS \ VU |XS |
= 0 [6],
n
|VU |XS |
• B1 = VU |XS and lim
= H(U |XS) [7],
n→∞
n
c
|VU |X |
c
• B4 = H U
lim
= 1 − H(U |X) [7],
|X and n→∞
n
c
|VU |XS |
• B3 ∪B4 = VUc |XS and lim
= 1−H(U |XS) [7].
n→∞
n
Note that H(U |X)−H(U |XS) = I(X, U ; S) ≥ 0 and |B3 |/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 |B3 | ≤ |A2 | − |A3 |.
• VU |XS ⊂ HU |XS and lim

n→∞

Encoding We use a chaining construction over multiple
blocks. The encoder observes (S01:n , S11:n , . . . , Sk1:n ), where
S01:n is a uniform random sequence and Si1:n for i ∈ [1, k] are k
blocks of the source. It then generates for each block i ∈ [1, k]
e1:n and Ve 1:n following the procedure desrandom variables Z
i
i
cribed in Algorithm 1. In particular, the chaining construction
proceeds as follows. The bits in A1 ⊂ V X and B1 ⊂ V U |XS
are chosen with uniform probability using uniform randomness

Algorithm 1: Encoding algorithm at Node 1
Input : (S01:n , . . . , Sk1:n ), local randomness (uniform
random bits) M and common randomness
C = (C1 , K1 , C2 , K2 ) shared with Node 2 :
• C1 of size |A1 | and K1 of size |A3 | ;
• C2 of size |B1 | and K2 of size |B3 |.
e1:n ), (Ve 1:n , . . . , Ve 1:n )
Output: (Ze11:n , . . . , Z
1
k
k
if i = 1 then
Ze1 [A1 ] ←− C1
Ze1 [A2 ] ←− M
for j ∈ A3 ∪ A4 do
ej according to
Successively draw the bits Z
i


ei:j−1
ej | Z
PZ j |Z i:j−1 Z
i
i

(4)

Ve1 [B1 ] ←− C2
for j ∈ B3 ∪ B4 do
Given S11:n , successively draw the bits Ve1j
according to


n
ein Si−1
PV j |V 1:j−1 X 1:n S 1:n Veij | Vei1:j−1 X

(5)

for i = 2, . . . , k do
ei [A0 ] ←− M
Zei [A1 ] ←− C1 Z
2
ei [A03 ] ←− Zei−1 [A3 ] ⊕ K1
Zei [B30 ] ←− Vei−1 [B3 ] ⊕ K2 Z
for j ∈ A3 ∪ A4 do
ej according to (4)
Successively draw the bits Z
i
Vei [B1 ] ←− C2
for j ∈ B3 ∪ B4 do
Successively draw the bits Veij according to (5).

sources (C1 , C2 ) shared with Node 2, and their value is reused
over all blocks. In the first block the bits in A2 ⊂ V X are chosen with uniform probability using a local randomness source
M . The bits in A3 ∪ A4 and B3 ∪ B4 are generated according
to the previous bits using successive cancellation encoding [6].
Note that it is possible to sample efficiently from PZ j |Z 1:j−1
and PV j |V 1:j−1 X 1:n S 1:n (given S 1:n and X 1:n ) respectively [6].
From the second block, let A03 and B30 be two disjoint subsets
of A2 such that |A03 | = |A3 | and |B30 | = |B3 |. The existence of
those disjoint subsets is guaranteed by Remark 6 and Remark 7.
The bits of A3 and B3 in block i are used as A03 and B30 in block
i + 1 using one time pads with keys K1 and K2 respectively.
Thanks to the Crypto Lemma [8, Lemma 3.1], if we choose K1
of size |A3 | and K2 of size |B3 | to be uniform random keys,
the bits in A03 and B30 in the block i + 1 are uniform. The bits
in A02 := A2 \ (A03 ∪ B30 ) are chosen with uniform probability
using the local randomness source M .
e 1:n = Ze1:n Gn for
The encoder then computes X
i
i
i = 1, . . . , k and sends it over the channel. We use an extra
ek [A3 ] encoded with a
(k + 1)-th block to send a version of Z
good channel code as in [5, Section III.B].
1:n
Decoding The decoder observes (Y11:n , . . . , Yk+1
) and the
(k + 1)-th block allows it to decode in reverse order. In block

F IGURE 2 – Chaining construction for block Markov encoding

Algorithm 2: Decoding algorithm at Node 2
1:n
Input : (Y11:n , . . . , Yk+1
), C = (C1 , K1 , C2 , K2 )
common randomness shared with Node 1
Output: (Zb11:n , . . . , Zbk1:n ), (Vb11:n , . . . , Vbk1:n )
for i = k, . . . , 1 do
bi [A1 ] ←− C1
Z
Vbi [B1 ] ←− C2
if i = k then
1:n
1:n
Zbk [A3 ] ←− Yk+1
Vbk [A3 ] ←− Yk+1

else
bi+1 [A0 ] ⊕ K1
Zbi [A3 ] ← Z
3
Vbi [B3 ] ← Zbi+1 [B30 ] ⊕ K2
for j ∈ A2 ∪ A4 do
Successively draw the bits according to
(
0 if Ln (Yi1:n , Zi1:j−1 ) ≥ 1
j
Zbi =
1 else



b1:j−1 Yi1:n
PZ j |Z 1:j−1 Y 1:n 0 | Z
i
i
i
i


Ln (Yi1:n , Zi1:j−1 ) =
b1:j−1 Y 1:n
PZ j |Z 1:j−1 Y 1:n 1 | Z
i
i
i

i

i

for j ∈ B4 do
Successively draw the bits according to
(
1:n
0 if Ln (Xi+1
, Vi1:j−1 ) ≥ 1
j
b
Vi =
1 else

bi [A1 ∪ A3 ] = Z
bi [HX|Y ]
i ∈ [1, k], the decoder has access to Z
and Vbi [B1 ∪ B3 ] = Vbi [HU |X ] : the bits in A1 and B1 correspond to shared randomness (C1 , C2 ), in block i ∈ [1, k − 1] the
bits in A3 and B3 are obtained by successfully recovering A2
1:n
in block i + 1 and in block k they are recovered from Yk+1
as
in [5, Section III.C]. For each block i = k, . . . , 1 the decoder
recovers the estimates Zbi1:n and Vbi1:n using Algorithm 2. From
bi [A1 ∪ A3 ] the successive cancellation decoder can
Yi 1:n and Z
b
retrieve Zi [A2 ∪ A4 ] and therefore Vbi [B4 ]. Note that, as shown
in [6, Theorem 3], Ve 1:n is equal to Vb 1:n with high probability.
b 1:n = Vb 1:n Gn . It then generates Sb1:n
The decoder computes U
i
i
i
symbol by symbol using : PSbj |Ub j Y j (s|u, y) = PS|U
b Y (s|u, y).
i

i

i

Remark 8. The rate of common randomness is negligible,
since :
|VX|Y | + |HU |X |
|A1 | + |A3 | + |B1 | + |B3 |
= n→∞
lim
lim
n→∞
kn
nk
k→∞
k→∞

i

i

i

Proof. By the chain rule, we have
w


w
D PS 1:n X 1:n U 1:n wPS 1:n Xe 1:n Ue 1:n
w i i i


w
= D PX 1:n |S 1:n wPXe 1:n |S 1:n PS 1:n
i
wi


w
+ D PU 1:n |X 1:n S 1:n wPUe 1:n |Xe 1:n S 1:n PX 1:n S 1:n
i

i

=

(7)

i

i

n
(c) X

(6)

i

We call D1 and D2 the first and the second term. Then :
w
w

 (b) 

(a)
w
w
D1 = D PX 1:n wPXe 1:n =D PZ 1:n wPZe1:n
w


w
D PZ j |Z 1:j−1 wPZej |Ze1:j−1 PZ 1:j−1
i

i

i

i

i

j=1
(d)

=

H(X|Y ) + H(U |X)
= 0.
= lim
k→∞
k

4

β

Lemma 9. For i ∈ [1, k], let δn = 2−n where 0 < β < 1/2,


p
p
V PS 1:n Xe 1:n Ue 1:n , PS 1:n X 1:n U 1:n ≤ 2 log 2 nδn .

X

w


w
D PZ j |Z 1:j−1 wPZej |Ze1:j−1 PZ 1:j−1
i

i

i

i

i

j∈A1 ∪A2
(e)

Proof of Theorem 4

=

X




 (f )
1 − H Zij |Zi1:j−1
< n|VX | ≤ nδn

j∈A1 ∪A2

Given ε > 0, we want to prove that :
n 

o
lim P V TS 1:n X 1:n Y 1:n Sb1:n , PSXY Sb > ε = 0.

n→∞

1:k+1

1:k+1

1:k+1

1:k+1

This requires a few steps :
1. ∀i ∈[1, k], lim P{V(TS 1:nXe 1:n Ue 1:n, PSXU ) > ε} = 0;
n→∞

i

i

i

2. ∀i ∈[1, k], lim P{V(TS 1:nXe 1:n Ue 1:n Y 1:n , PSXU Y ) > ε} = 0;
n→∞

i

i

i

i

3. ∀i ∈[1, k], lim P{V(TS 1:nXe 1:n Ue 1:n Y 1:nŜ 1:n , PSXU Y Ŝ )>ε}= 0;
i
i
i
i
i
n→∞
4. Convergence in each block implies overall convergence ;
5. The theorem follows from the fact that


V TS 1:n Xe 1:n Y 1:n Sb1:n , PSXY Sb ≤
1:k+1

1:k+1

V(TS 1:n

1:k+1

1:k+1

1:n
e 1:n e 1:n
b1:n
1:k+1 X1:k+1 U1:k+1 Y1:k+1 S1:k+1

, PSXU Y Sb).

Note that since the steps 2 to 5 have already been proved in
[5, Section IV], we only need to prove the first step. For all
ε0 > 0, we define


Tε0 (PSXU ) := (s, x, u) V PSXU , T(s,x,u) ≤ ε0
Observe that for the i.i.d. distribution, we have
limn→∞ P {(s, x, u) ∈ Tε0 (PSXU )} = 1.
Let i ∈ [1, k], we have :
n 

o
P V TSi1:n Xi1:n Ui1:n , PSXU > ε0
X
=
PS 1:n Xe 1:n Ue 1:n (s, x, u) 1 {(s, x, u) ∈
/ Tε0 (PSXU )}
i

i

i

s,x,u

=

X

(PS 1:n Xe 1:n Ue 1:n (s, x, u) − PS 1:n X 1:n U 1:n (s, x, u)
i

i

i

s,x,u

+ PS 1:n X 1:n U 1:n (s, x, u))1{(s, x, u) ∈
/ Tε0 (PSXU )}
≤ V(PS 1:nXe 1:nUe 1:n , PS 1:nX 1:nU 1:n )+P{(s,x,u) ∈
/ Tε0 (PSXU )}
which tends to 0 thanks to a typicality argument and the following result.

where (a) comes from the fact that X is independent of S,
(b) from the invertibility of Gn , (c) from the chain rule, (d)
from (4), (e) from the fact that the conditional distribution
PZej |Ze1:j−1 is uniform for j in A1 and A2 and (f ) from Dei
i
finition (2).
Similarly, D2 < nδn . Then D1 + D2 < 2nδn and the proof
is completed using Pinsker’s inequality.

References
[1] P. Cuff, H. Permuter, and T. Cover, “Coordination capacity,” IEEE Transactions on Information Theory, vol. 56, no. 9, pp. 4181–4206, 2010.
[2] P. Cuff and C. Schieler, “Hybrid codes needed for coordination over the
point-to-point channel,” in Proc. of Allerton Conference on Communication, Control and Computing, 2011, pp. 235–239.
[3] R. A. Chou and M. R. Bloch, “Polar coding for the broadcast channel with
confidential messages : A random binning analogy,” IEEE Transactions
on Information Theory, vol. 62, no. 5, pp. 2410–2429, 2016.
[4] C. Choudhuri, Y.-H. Kim, and U. Mitra, “Capacity-distortion trade-off in
channels with state,” in Proc. of Allerton Conference on Communication,
Control and Computing, 2010, pp. 1311–1318.
[5] 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.
of IEEE Information Theory Workshop, 2016, pp. 81–85.
[6] E. Arıkan, “Source polarization,” in Proc. of IEEE International Symposium on Information Theory (ISIT), 2010, pp. 899–903.
[7] R. A. Chou, M. R. Bloch, and E. Abbe, “Polar coding for secret-key generation,” IEEE Transactions on Information Theory, vol. 61, no. 11, pp.
6213–6237, 2015.
[8] M. Bloch and J. Barros, Physical-layer security : from information theory
to security engineering. Cambridge University Press, 2011.

