# Relationship between worst case length of transcript and entropy of transcript

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]?$$

• This question is better suited for cs.se May 1 '18 at 7:00
• Apologies, I was abusing the notation $E[|\Pi|]$ to denote the expected transcript length. May 5 '18 at 3:33
• 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]$. May 5 '18 at 9:38
• 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$. 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.