A bit of delay is sufficient and stochastic encoding is necessary to overcome online adversarial erasures

We consider the problem of communicating a message m in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to pn bits, out of n transmitted bits X = (x
₁
, ..., x
_n
). The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit x
_i
depends on his observations (x
₁
, ..., x
_i
) was recently characterized [1], [2] to be 1 - 2p. In this work we show two (perhaps) surprising phenomena. Firstly, we demonstrate via a novel code construction that if Calvin is delayed by even a single bit, i.e. Calvin's decision of whether or not to erase bit x
_i
depends only on (x
₁
, ..., x
_i-1
) (and is independent of the “current bit” x
_i
) then the capacity increases to 1 - p when the encoder is allowed to be stochastic. Secondly, we show via a novel jamming strategy for Calvin that, in the single-bit-delay setting, if the encoding is deterministic (i.e. the transmitted codeword X is a deterministic function of the message m) then no rate asymptotically larger than 1 - 2p is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of 1- p against a one-bit-delayed Calvin.