Binary causal-adversary channels

In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x₁, ..., x_n) bit-by-bit over a communication channel. The adversarial jammer can view the transmitted bits x_i one at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in an online or causal manner. Namely, for each bit x_i the jammer´s decision on whether to corrupt it or not (and on how to change it) must depend only on x_j for j ¿ i. This is in contrast to the ¿classical¿ adversarial jammer which may base its decisions on its complete knowledge of x. We present a non-trivial upper bound on the amount of information that can be communicated. We show that the achievable rate can be asymptotically no greater than min{1 - H(p), (1 - 4p)⁺}. Here H(.) is the binary entropy function, and (1 - 4p)⁺ equals 1 - 4p for p ¿ 0.25, and 0 otherwise.