Consider the two party model of communication complexity where Alice and Bob are given inputs $X$ and $Y$ sampled from some distribution $\mu$, and their goal is to solve some problem $P$ (the details of which don't really matter for this question).

Let $\mathcal{P}$ be the best (i.e. smallest amount of bits) 2-party protocol for solving $P$ and let random variable $\Pi$ denote the transcript of messages between Alice and Bob when executing $\mathcal{P}$ for inputs sampled from $\mu$. We use $|\Pi|$ to denote the worst case length of $\Pi$, over all inputs and random bits.

In the paper An information statistics approach to data stream and communication complexity, the following fact is used in the proof of Proposition 4.3:

$$ |\Pi| \ge H[ \Pi ], $$ where $H$ denotes the binary entropy.

I can see that this is true intuitively, since the worst case length of $\Pi$ shouldn't be smaller than the expected amount of uncertainty in $\Pi$, but how can this be proven formally?

Also, does it even hold that $$E[|\Pi|] \ge H[\Pi]? $$

  • $\begingroup$ This question is better suited for cs.se $\endgroup$
    – Ariel
    May 1 '18 at 7:00
  • $\begingroup$ Apologies, I was abusing the notation $E[|\Pi|]$ to denote the expected transcript length. $\endgroup$
    – JohnDoe
    May 5 '18 at 3:33
  • $\begingroup$ It also holds for the expectation, you can prove by induction on $n$ that for every random variable $X$ taking values in $\{1,...,n\}$ it holds that $\mathbb{E}[X]\ge H[X]$. $\endgroup$
    – Ariel
    May 5 '18 at 9:38
  • $\begingroup$ My previous comment refers to $\mathbb{E}[|\Pi|]\ge H[|\Pi|]$, where $|\Pi|$ denotes the length of the transcript (and not the maximum). The inequality mentioned in your question doesn't hold, suppose for example that the transcript is uniform over $\{0,1\}^n$, then $E[|\Pi|]=\frac{n+1}{2}$ and $H[\Pi]=n$. $\endgroup$
    – Ariel
    May 5 '18 at 10:30

Suppose $|\Pi|<H(\Pi)$, then there are less than $2^{H(\Pi)}$ values $\Pi$ can take. The maximum entropy distribution on a collection of $n$ elements is the uniform distribution, whose entropy equals to $\log n$, thus $H(\Pi)<\log 2^{H(\Pi)}=H(\Pi)$, contradiction. Note that $|\Pi|$ is constant and not a random variable, so it doesn't make much sense to talk about its expectation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.