# Complexity of sending an $n$-bit string

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?

• I think some definitions are missing here. What is a communication protocol? What is a deterministic protocol? What is a randomized protocol? When does a deterministic protocol solve your communication problem? When does a randomized protocol solve your communication problem? – Yuval Filmus Feb 13 '19 at 19:36

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).$$
• Can you explain what is $h$? and how did you get the first inequality? – user91015 Feb 13 '19 at 20:35