1

Shannon Capacity is Achievable for Binary
Interactive First-Order Markovian Protocols
Assaf Ben-Yishai, Ofer Shayevitz and Young-Han Kim

arXiv:1801.01022v1 [cs.IT] 30 Dec 2017

Abstract
We address the problem of simulating an arbitrary binary interactive first-order Markovian protocol over
a pair of binary symmetric channels with crossover probability ε. We are interested in the achievable rates of
reliable simulation, i.e., in characterizing the smallest possible blowup in communications such that a vanishing
error probability (in the protocol length) can be attained. Whereas for general interactive protocols the output
of each party may depend on all previous outputs of its counterpart, in a (first-order) Markovian protocol this
dependence is limited to the last observed output only.
In this paper we prove that the one-way Shannon capacity, 1 − h(ε), can be achieved for any binary firstorder Markovian protocol. This surprising result, is to the best of our knowledge, the first example in which
non-trivial interactive protocol can be simulated in the Shannon capacity. Our scheme is based on two simple
notions: non-interactive simulation, block-wise interactive communication. Previous results in the field discuss
different families of protocol and mostly assess the achievable rates at the limit where ε → 0.
We also show that for higher order Markovian protocols, if the transmission functions are drawn uniformly
i.i.d, the probability of drawing a non-capacity achieving protocol goes to zero with n.

I. I NTRODUCTION
Suppose Alice and Bob wish to communicate using some interactive communication protocol, where
at time point i Alice sends the bit Ai and Bob, after having observed Alice’s transmission, replies with
the bit Bi . The transcript associated with this protocol is therefore
A1 , B1 , A2 , B2 , · · · , An , Bn
where

Ai = fi Bi−1 ;


Bi = gi Ai .

(1)
def

The protocol consists of the sets of Alices transmission functions f n = {f1 (·), . . . , fn (·)} and Bob’s
def
transmission functions gn = {g1 (·), . . . , gn (·)}.
Now, suppose that Alice and Bob are connected by a pair of Binary symmetric channels (BSC’s)
with a crossover probability ε. Namely, the channel from Alice to Bob is
Yj = Xj + Zj
and the channel from Bob to Alice is
Vj = Uj + Wj .
The symbol“+” denotes addition over GF(2) and Zj , Wj are mutually independent Bernoulli i.i.d.
sequence with Pr(Zj = 1) = Pr(Wi = 1) = ε. Alice and Bob would like to devise a coding scheme
that will enable a reliable simulation of the original transcript over the noisy BSC’s. Reliable simulation
A. Ben-Yishai and O. Shayevitz are with the Department of EE–Systems, Tel Aviv University, Tel Aviv, Israel. Y.-H. Kim is with
the Department of Electrical and Computer Engineering, University of California, San Diego, La Jolla, CA 92093 USA. Emails:
{assafbster@gmail.com, ofersha@eng.tau.ac.il, yhk@ucsd.edu}. The work of A. Ben-Yishai was partially supported by an ISF grant
no. 1367/14. The work of O. Shayevitz was supported by an ERC grant no. 639573, a CIG grant no. 631983, and an ISF grant no.
1367/14.

2

in this context means that for any protocol, the probability of either Alice or Bob making an error
in recovering the original transcript goes to zero with the transcript length. The coding scheme would
comprise Alice’s and Bob’s transmission policies. Namely, the coding scheme will determine Alice’s
and Bob’s transmissions (Xj and Uj respectively) which depend on their transmission functions (f n and
gn respectively) and their corresponding sets of previously received inputs. Since the transmissions can
depend on the received inputs, the coding scheme itself might also be interactive. It is important to note
that while in the original transcript the order of speakers was alternating on a symbol basis (Alice, Bob,
Alice, Bob etc.), this is not necessarily the case with the order of transmissions over BSC. Specifically,
Alice or Bob can use the channel for several consecutive channel uses while the other party is silent.
We count the total number of channel uses on either channel and denote it by ñ.
The rate of any communication scheme that attempts to simulate the original transcript is therefore
2n
(2)
ñ
where 2n is the length of the original transcript. As usual, one is interested in characterizing the capacity,
namely the maximal rate for which reliable simulation is possible.
The problem described above was originally introduced and studied by Schulman [1]. In this seminal
work, he showed that reliable simulation with a positive rate (i.e., a positive capacity) can be achieved
for any ε 6= 1/2. Kol and Raz [2] p
further studied the problem in the limit of ε → 0 and introduced a
scheme achieving a rate of 1 − O( h(ε)) (where h(·) denotes the binary entropy function). They also
showed
pthat for a larger class of protocols with non-alternating rounds the rate is upper bounded by
1−Ω( h(ε)). These results demonstrate a separation between one-way and interactive communications,
as the one-way capacity is given by 1 − h(ε). In [3], Haeupler examined a more flexible channel model
than ours, in which at every time slot Alice and Bob can independently decide if they want to use
the channel as a transmitter or as a receiver. This flexibility
√ can potentially lead to collisions, but was
shown to eventually increase the achievable rate to 1 − O( ε). Haeupler also conjectured that this rate
is order-wise tight under adaptive
transmission order, i.e., that the rate of any such reliable scheme is
√
upper bounded by 1 − Ω( ε). We note that the general problem of exactly determining the capacity
for any fixed ε in the interactive setup is still wide open.
In order to better understand the gap between the one-way and interactive setups for ε → 0, Haeupler
and Velingker [4] considered a more restrictive family of protocols that are “less interactive”, where
Alice and Bob have some limited average lookahead, i.e., can often speak for a while, without requiring
further input from their counterpart (hence, can use short error correcting codes). They showed (also
for adversarial noise) that when this average lookahead is poly(1/ε) then the capacity is 1 − O(h(ε)),
i.e., is order-wise the same as the one-way capacity.
In this study, rather than restricting the “interactiveness” of the protocol as above, we restrict the
memory of the protocol. Specifically, we consider Markovian protocols for which the lookahead can
be as short as one (i.e. highly interactive), but where Alice and Bob need only recall the last bit they
have received. For these Markovian Protocols, we show that reliable simulation is possible at any rate
smaller than Shannon capacity. This surprising result is, to the best of our knowledge, the first example
in which Shannon capacity is achievable in a non-trivial interactive setup. This result closes the question
proposed in our previous study [5] in which only achievable simulation rates where given.
R=

II. M ARKOVIAN P ROTOCOLS
A (first-order) Markovian protocol is a protocol in which each party needs to know only the last
transmission of its counterpart in order to decide what to send next, and not the entire set of past
transmissions. Namely,
Ai = fi (Bi−1 );

Bi = gi (Ai ).

3

where now, in contrast to (1), the transmission functions fi (·), gi (·) depend only on what was last
received (Bi−1 and Ai respectively).
The probability of error attained by a scheme is defined to be the maximal probability that either Alice
or Bob fail to exactly simulate the original transcript, where the maximum is taken over all possible
Markovian protocols. A sequence of schemes with rate at least R and error probability approaching zero
is said to achieve the rate R. The capacity for Markovian protocols over BSC’s is the supremum over
all such achievable rates, and is denoted by CMarkov (ε). Note that CMarkov (ε) cannot exceed the one-way
Shannon capacity of the BSC, i.e.,
CMarkov (ε) ≤ 1 − h(ε),
as this is the maximal achievable rate for the special case of non-interactive protocols. In the sequel we
prove that CMarkov (ε) = 1 − h(ε) by giving an explicit capacity achieving coding scheme.
III. ACHIEVING THE S HANNON C APACITY FOR M ARKOVIAN P ROTOCOLS
We start by noting that the Markovian transmission functions fi (·), gi (·), are binary functions that
map a single input bit to a single output bit. There are only four such functions, µ1 , µ2 , µ3 , µ4 as in
the following exhaustive table:
Y
0
1

µ1 :
X =Y +0
0
1

µ2 :
X =Y +1
1
0

µ3 :
µ4 :
X=0 X=1
0
1
0
1

We observe that µ1 and µ2 are additive, i.e. X = Y + ξ and ξ is either 0 or 1. µ3 and µ4 are constant
functions, namely, the output is 0 or 1 regardless the input. In the sequel we refer to the locations where
µ3 and µ4 are used as “stuck positions”. The capacity achieving scheme is based on the properties of
these functions and two simple principles termed non-interactive simulation, and block-wise interactive
coding defined herein.
A. Non-Interactive Simulation
We observe that if Bob knows all Alice’s transmission functions, he can simulate the entire transcript
off-line (i.e. without using the channel). Then, he can send his part of the transcript to Alice, which
can in-turn simulate her part.
Since there are only four transmission functions, Alice needs at most two bits for the representation
of each function. In addition, if Bob has some side information that reduces the number of functions
used by Alice, she can use less than two bits (e.g. if Bob knows that Alice’s functions are additive, she
can use only a single bit).
A simple non-interactive (and not capacity achieving) scheme can be built as follows: Alice sends
Bob all here functions, and then Bob simulates the transcript off-line and feed his part of the protocol
to Alice. Alice, needs to send 2n bits and Bob needs n bits. Both parties can use capacity achieving
block codes for their transmissions so a rate of 2/3 the Shannon capacity can be trivially achieved.
B. Block-Wise Interactive Coding
Let us start with the following simple example. Suppose the transcript is
A1 , B1 , A2 , B2 , A3 , B3 , A4 , B4 .
The length of the transcript is eight, and both Alice and Bob transmit four times. The order of speakers
is Alice, Bob, Alice, Bob etc. By the Markovity assumption, B1 is a Markovian function of A1 , A2 is
a Markovian function of B1 and so on.

4

Now, assume that A3 = 0, i.e. it is set to zero and not a function of B2 . Also suppose that Bob
knows that A3 is a “stuck position”, i.e. he knows that A3 is set to either zero or independently of his
transmission B2 . However, he does not know the specific value (zero or one) to which A3 is set. Having
this assumption, the protocol can also be simulated in the following order:
A1 , A3 , B1 , B3 , A2 , A4 , B2 , B4
| {z } | {z } | {z } | {z }
Alice

Bob

Alice

Bob

where the identity of the speaker is written under the brace. Namely, Alice sends two consecutive
transmissions, then Bob sends two consecutive transmissions etc. This transmission order is possible
because A3 is not an interactive point anymore, i.e. it is set to be zero and does not depend on the
history of the protocol to-point.
Let us now generalize this example by considering a protocol of length 2n in which the stuck
positions are uniformly spaced. I.e. suppose the n = p × m and that A1+i×p are stuck position for all
i = 0, ..., m − 1. So, the values of A1+i×p are either zero or one, regardless the history of the protocol.
Alice knows the values of A1+i×p explicitly, and Bob only knows that they are stuck. The following
order of speakers is therefore possible:
A1 , A1+p , A1+2p , · · ·, B1 , B1+p , B1+2p , · · ·, · · ·
|
{z
} |
{z
}
Alice

Bob

Note that now, Alice and Bob communicate in blocks of length m, but the transmissions within every
block are independent and hence non-interactive. Therefore a block code can be used for every block.
Also note, that the interaction is being carried out between consecutive blocks, which explains the term
block-wise interactive. Now, if m (the length of every block is) sufficiently large, and the number of
blocks 2p is not too large (the notion of large is made rigorous in the sequel), Shannon’s capacity can
be achieved reliably. In the sequel we show that capacity can be achieved also in the case where the
stuck positions are not uniformly spaced, and m is not large.
C. Capacity Achieving Scheme
In the first step of the scheme, Alice partitions her transmission functions into segments, possibly of
non-uniform length, all starting with stuck positions. Then she conveys the partitioning to Bob. This is
done as follows:
1) Regard A1 as a stuck position, and repeat sequentially: suppose the last block
so far starts with a
√
stuck position at time j. Look for the first stuck position at time k ≥ j + n. Then
√ the next block
will start at time k.
The
length
of
each
block
created
in
this
process
is
at
least
n. The number
√
of blocks is m ≤ n.
2) Alice communicates to Bob the starting
√ point of every block. This can be regarded as a binary
sequence
of length n with at most n ones. It can be described to Bob using no more than
√
( n + 1) log(n), where the total number of ones, and the location of every one in the sequence
are described using log(n) bits. We note that while more efficient compression methods can be
considered, the overhead inflicted by this method is negligible when normalizing by n and taking
n to infinity.
After performing these steps, Alice and Bob are coordinated with regard to the partition into blocks
as depicted
in Fig. 1. The figure divides the original transcript into two parts: Part A contains the
√
first n bits in each block and Part B contains all the rest, which can be of varying lengths. Note that
by definition, there are no stuck positions in Part B. We will use a different communication protocol
for each part. There are two cases which are determined by the value of m.
1
1) If m > n 4 we use block-wise
interactive coding for Part A and non-interactive simulation for Part
√
B. In Part A we have 2 n block each having m information bit. We would like to encode them

5

√

n

..
.

.
m ..

Part A

Part B

Fig. 1. Division of the transmission functions into blocks

√
using 2 n block codes of length m/R, where the rate R is arbitrarily close to the capacity. The
decoding error can be upper bounded using error exponents and the union bound as follows:


 n  14
√ − m E(R)
1
ln(n) −
≤ 2 exp
E(R) .
Pe ≤ 2 ne R
2
R
Then for any R < 1 − h(ε), the error exponent E(R) is strictly positive. So Pe will go to zero for
n → ∞.
As for the non-interactive simulation, it is assured by construction that there are no stuck positions
in Part B. Therefore, Alice can describe the transmission functions of Part B using a single bit each.
These bits can be appended to the last block Alice sends in the block-wise interaction phase, and
due to the large block length can be reliably decoded. Then, Bob can simulate his transmissions
of Part B off-line and send them to Alice.
1
2) If m < n 4 non-interactive simulation can be used for both Part A and Part B. For Part A, two bits
per transmission function are required and in Part B only a single bit per transmission function is
required. The number of bits Alice needs in order to represent her functions is thus:




√
√
1
m
2 · nm + 1 · (n − nm) = n 1 + √
≤ n 1 + n− 4 .
| {z } |
{z
}
n
Part A

Part B

This term approached n as n → ∞, which implies that asymptotically Alice needs n(1 + o(n))
in order to represent her functions. Bob then needs n bits to send his part of the transcript (after
simulating it off-lines). Both Alice’s and Bob’s transmissions can be sent in large blocks using
capacity achieving codes, thus
lim ñ =

n→∞

2n
1 − h(ε)

which by the definition in (2) implies that R is Shannon’s capacity for BSC(ε).
IV. H IGHER O RDER M ARKOVIAN M ODELS
We define a kth order Markovian protocol as ones whose transmission functions obey:
Ai = fi (Bi−1
i−k );

Bi = gi (Aik−i+1 ).

It is appealing to use the capacity achieving scheme introduced before for these protocols. However,
k
note that the number of possible k’th order transmission functions is 22 . The number
of stuck
functions


2k
is still two, so the number of bits required for every instance in Part B is log2 2 − 1 which larger
than one for k > 1. So using the previous scheme will not yield Shannon’s capacity trivially.

6

A trivial lower bound for the capacity using non-interactive simulation is trivially 1/(2k +1) Shannon’s
capacity. While an upper bound is still under investigation, it can be shown that if Alice’s transmission
functions are uniformly drawn i.i.d, the probability of drawing a protocol that does not achieve Shannon’s
capacity goes to zero with n.
The proof follows similar lines to the ones of the first-order Markovian with a little tweak.
√ The
segmentation is done as before, by starting the blocks with a stuck series and then jumping n time
instances ahead and searching for the next one. A stuck series is a generalization of the stuck position
for k’th order Markovian and is defined as a sequence of k constant function.
However, the search
for the following stuck series is done within an opportunity window with length
p√
√
n). If the segmentation process succeeds, we end up with m blocks with lengths
o( n) (for example
p
√
√
√
between n and n +
n. It is then assured that the number of blocks is large enough to enable
reliable block-wise simulation of Part A. It is also assured that total the number of functions in Part B
is negligible, so they can be fully described and still not decrease the rate asymptotically. So all in all
Shannon’s capacity can be achieved.
It is also easy to prove that the probability of drawing a protocol that cannot be segmented vanished
with n. This is since the probability of drawing non-constant functions is constant (in n), but the length
of opportunity windows increases with n. So, the probability of not having a stuck position within an
opportunity window goes to zero, and the probability of the entire process not to be successful can be
upper bounded using the union bound, and be shown to approach zero as well.
R EFERENCES
[1] L. J. Schulman, “Coding for interactive communication,” IEEE Transactions on Information Theory, vol. 42, no. 6, pp. 1745–1756,
1996.
[2] G. Kol and R. Raz, “Interactive channel capacity,” in Proceedings of the forty-fifth annual ACM symposium on Theory of computing.
ACM, 2013, pp. 715–724.
[3] B. Haeupler, “Interactive channel capacity revisited,” in Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium
on. IEEE, 2014, pp. 226–235.
[4] B. Haeupler and A. Velingker, “Bridging the capacity gap between interactive and one-way communication,” in Proceedings of the
Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017, pp.
2123–2142.
[5] A. Ben-Yishai, O. Shayevitz and Y.-H. Kim, “Interactive Coding for Markovian Protocols,” in Proc. 55nd Allerton Conf.
Communication, Control Computing, Oct. 2017.

