0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ If $p$ is uniform then $H(p)=\log_2(n)$. $\endgroup$
    – Stelios
    Commented Nov 3, 2019 at 23:32

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ Thank you for the reference! I will definitely go through the book! $\endgroup$
    – Joe
    Commented Nov 5, 2019 at 2:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .