I am freely using known terms from communication complexity.

Let $u$ be a distribution on $X\times Y$, and $P$ a randomized (private randomness) communication protocol.

We define $IC(u,P) = I(P;X|Y)+I(P;Y|X)$ , where the probability space is both $u$, and the public randomness which are independent.

How do I show that $IC(u,P) \leq E[P_A] + E[P_B]$? Where $P_A$ is how many bits player $A$ sent, and $P_B$ how many bits player $B$ sent.

In fact more is true, $I(P;X|Y) \leq E[P_A]$, indeed intuitively player $B$ can learn from the protocol about $X$ at most what player $A$ says.

I am able to prove this for deterministic protocols. But the randomness makes it hard for me to formalize. By viewing public randomness as distribution on deterministic protocols, I can show the inequality if we have $I(P;X|Y,r)$ with $r$ the public randomness, and intuitively that should be enough, since player $B$ learns more from the protocol about $X$ if he knows what the protocol does. Still, I don't see how to prove this.

I'm actually not even sure if the definition purposely doesn't let player $A$ to know his private randomness. Trying to read braverman lecture notes but they're really hard to understand.

  • $\begingroup$ It follows from $I(P; X|Y) \le I(P;X|Y, r)$. The LHS is $H(X|Y) - H(X|Y, P)$ and the RHS is $H(X|Y, r) - H(X|Y, P, r)$. Now note that $H(X|Y, P, r) \le H(X|Y, P)$ and $H(X|Y) = H(X|Y, r)$ (because $(X, Y)$ and $r$ are independent) $\endgroup$ – Sasha Kozachinskiy Dec 16 '18 at 22:29
  • $\begingroup$ @SashaKozachinskiy Thanks, that's great. If I understand correctly then (As I thought initially), the definition of internal information (which is first defined for private randomness) doesn't let either play use his private randomness in the calculation? So the proof you suggest only works when we have public randomness (since then it's a distributation on deterministic and our combined proofs finish it) $\endgroup$ – Andy Dec 17 '18 at 6:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.