<p>Suppose $|\Pi|&lt;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)&lt;\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.</p>

CC BY-SA 3.0
2018-05-01T07:00:44.273Z
2018-05-01T07:00:44.273Z
Ariel
<p>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). </p>

<p>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 <em>worst case</em> length of $\Pi$, over all inputs and random bits. </p>

<p>In the paper <a href="https://pdfs.semanticscholar.org/c822/76f525ab37cda42025714134b496cdad9988.pdf" rel="nofollow noreferrer">An information statistics approach to data stream and
communication complexity</a>, the following fact is used in the proof of Proposition 4.3: </p>

<p>$$
|\Pi| \ge H[ \Pi ],
$$
where $H$ denotes the binary entropy. </p>

<p>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? </p>

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

CC BY-SA 4.0
2018-05-05T03:33:11.683Z
Apologies, I was abusing the notation $E[|\Pi|]$ to denote the expected transcript length.
JohnDoe
CC BY-SA 4.0
2018-05-05T09:38:02.013Z
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]$.
Ariel
CC BY-SA 4.0
2018-05-05T10:30:03.780Z
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$.
Ariel
<it.information-theory><communication-complexity>
Relationship between worst case length of transcript and entropy of transcript
JohnDoe
# Relationship between worst case length of transcript and entropy of transcript

(Asked by: username_0 on 2018-05-01)

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](https://pdfs.semanticscholar.org/c822/76f525ab37cda42025714134b496cdad9988.pdf), 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]?
$$

**Tags:** it.information-theory, communication-complexity
> **Comments:**
> **username_0**: Apologies, I was abusing the notation $E[|\Pi|]$ to denote the expected transcript length.  
> **username_1**: 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]$.  
> **username_1**: 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$.  

---

## 1 answers

### Answer by username_1 on 2018-05-01. Score: 1

Suppose $|\Pi|


---

