Complexity of sending an $n$-bit string

Question

Consider a $2$-party communication model in which $A$ wish to send to $B$ an $n$-bit string. It is very easy to prove that any deterministic protocol for this problem requires $\Omega(n)$ bits to be transmitted. It is also well-known that any randomized protocol for this problem also requires $\Omega(n)$ bits to be transmitted. Although this considered to be a trivial fact, I failed to formally prove (or find a formal proof) for this. So my question is: how to show that any randomized protocol for this problem requires $\Omega(n)$ bits to be transmitted?

Answer 1

You haven't defined when a randomized protocol is declared to be successful, so I will assume that at the end of the protocol, Bob tells a judge what he thinks the message is, and we want that for each message $x$, the probability that Bob is correct is at least $1-\epsilon$.

Let $X$ be a random $n$-bit string, and let $\Pi$ be the corresponding transcript. Let $R$ be the randomness in the protocol (i.e., given $R$ the protocol is deterministic, and Bob's output is deterministic). Let $Y$ be Bob's output, and let $B$ be an indicator variable for the event $X=Y$.

The definition of correctness of the protocol shows that $$ \begin{align*} H(X|\Pi R) &\leq H(BX|\Pi R) \\ &= H(B|\Pi R) + H(X|\Pi RB) \\ &\leq 1 + \Pr[B=1] H(X|\Pi R,B=1) + \Pr[B=0] H(X|\Pi R,B=0) \\ &\leq 1 + 1 \cdot 0 + \epsilon \cdot n \\ &= \epsilon n + 1. \end{align*} $$ This implies that $$ H(\Pi|R) = H(X\Pi|R) - H(X|\Pi R) = H(X) - H(X|\Pi R) \geq (1-\epsilon) n - 1, $$ since $H(X\Pi | R) = H(X | R)$ (given $R$, Alice's input $X$ determines the transcript $\Pi$) and $H(X|R) = H(X)$ (since Alice's input and the randomness are independent).

We conclude that the communication complexity is at least $$ (1-\epsilon) n - 1 = \Omega(n). $$