# Entropy and Joint Probabilty Distributions for iid random variables

The question is the following:

Given two discrete iid random variables $$X_1$$ and $$X_2$$ with a probability distribution $$p$$, Show that: $$P(X_1=X_2) \geq \frac{1}{2^{H(p)}}$$. Also show that this is an equality iff $$p$$ is uniform.

Using these lecture notes, I was able to reach this (trivial) step:

$$P(X_1 = X_2) \geq 2^{-H(p)}$$ $$P(X_1 = X_2) \geq 2^{\mathbb{E}[\log(p)]}$$

I really don't know where to go from here, How do I get rid of the $$\log (p)$$? Is this related to Conditional Entropy or Relative Entropy at all? I've seen lots of resources on that online but couldn't relate that information to this question.

I don't even understand this on a basic level. Intuitively, if $$p$$ is discrete and uniform with $$n$$ possible values, then $$P(X_1=X_2) = \frac{1}{n}$$. I see no way in which the formula can be manipulated to transform $$2^{\mathbb{E}[\log(p)]}$$ into $$\frac{1}{n}$$.

Feeling like an idiot and I'd love some guidance.

• If $p$ is uniform then $H(p)=\log_2(n)$. – Stelios Nov 3 at 23:32

Below is an expanded version of the proof given in Elements Of Information Theory by T.M Cover (2nd Edition, pg 40 - Lemma 2.10.1) for the inequality in question.

If $$X_1$$ and $$X_2$$ are iid (i.e. $$X_1 \sim p(x)$$ and $$X_2 \sim p(x)$$ )

\begin{align} P(X_1 = X_2) &= \sum_{x \in \mathcal{X}} P(X_1 = x , X_2 = x) \\ &= \sum_{x \in \mathcal{X}} P(X_1 = x) P(X_2 = x) \\ &= \sum_{x \in \mathcal{X}} p(x) p(x) \\ &= \sum_{x \in \mathcal{X}} p^2(x) \end{align}

Using Jenson's Inequality we know that if a function, $$f(y)$$, is convex then $$\mathbb{E}_{p(x)} \left[ f(y) \right] \geq f\left( \mathbb{E}_{p(x)}[y] \right)$$, with equality if and only if $$\textbf{y}$$ is a constant.

The function $$f(y) = 2^{y}$$ is convex and so if $$z = \mathbb{E}_{p(x)} \left[\phi \right]$$, then

$$f(z) = f(\mathbb{E}_{p(x)} \left[\phi \right]) \leq \mathbb{E}_{p(x)} [f (\phi) ]$$

Where

$$\mathbb{E}_{p(x)} [f (\phi) ] = \sum _{x \in \mathcal {X}} p(x) f(\phi)$$

Let $$\phi = \log_2 p(x)$$. Note that

\begin{align} 2^{-H(X)} &= 2^{\mathbb{E}_{p(x)}[\log _2 p(x)]} \\ &= f(y) |_{y = \mathbb{E}_{p(x)}[\log _2 p(x)]} \\ &= f(y) |_{y = \mathbb{E}_{p(x)}[\phi]} \\ &= f(\mathbb{E}_{p(x)}[\phi]) \\ &\leq \mathbb{E}_{p(x)} [f (\phi) ] \\ &= \mathbb{E}_{p(x)} 2^{\phi} \\ &= \mathbb{E}_{p(x)} 2^{\log _2 p(x)} \\ &= \mathbb{E}_{p(x)} p(x) \\ &= \textstyle{\sum} p(x)p(x)\\ &= \textstyle{\sum} p^2 (x) \\ &= P(X_1 = X_2) \end{align}

What this means is $$P(X_1 = X_2) \geq 2^{-H(X)}$$, with equality if and only if $$\log p(x)$$ is a constant. If $$\log p(x)$$ is constant then $$p(x)$$ is also constant and so the distribution in that case is uniform. $$\square$$

• Thank you for the reference! I will definitely go through the book! – QuantumHoneybees Nov 5 at 2:07