Concentration property of entropy

Question

Let $X$ be a random variable taking its values in $A = \{a_1,\ldots,a_n\}$ such that $Pr[X = a_i] = p_i$ for all $1 \leq i \leq n.$

The entropy of $X$ is defined as $$H(X) = -\sum_{i=1}^n p_i \log_2{p_i}.$$

I would like to show that

If $H(X) \leq t$ then there is an element $a \in A$ such that $$Pr[X = a] \geq 2^{-t}.$$

My intuition was to use Jensen's inequality which seems to give that $$ 2^{-t} \le 2^{\sum_{i=1}^n p_i \log_2{p_i}} \le \sum_{i=1}^n p_i^2.$$ From here it follows that at least one term say $p_i^2$ is larger than $2^{-t}$ and hence implies $p_i \geq 2^{-t/2}.$

Unfortunately this is not the stated bound hence I am wondering what am I missing in the above reasoning? Is it the wrong approach or is there some mistake in the presented reasoning?

Answer 1

If for all $i$ we have $p_i<2^{-t}$ then $\log_2\frac{1}{p_i}> t$ for all $i$ hence \begin{equation} H(X) = \sum_{i=1}^{n}p_i\log_2\frac{1}{p_i}> t\sum_{i=1}^{n}p_i = t. \end{equation} This implies contradiction.

Answer 2

Suppose that for all $1\le i\le n$ you have $p_i < \frac{1}{2^t}$.

$-H(x) = \sum\limits_{i=1}^{n}p_i\log_2p_i < \sum\limits_{i=1}^{n}p_i\log_2\frac{1}{2^t} = \log_2\frac{1}{2^t}=-t$, hence $H(x)>t$ contradiction.

The first inequality follows from the simple fact that logarithm is increasing.

note that your use of Jensens inequality is wrong. Take the random variable $X$ accepting values $p_i$ with probabilities $p_i$ and the convex transformation $\log_2X$, then it follows that:

$\log_2\sum\limits_{i=1}^np_i^2\le\sum\limits_{i=1}^{n}p_i\log_2p_i$ (you used it in the opposite direction).

p.s. i know its answered, i just posted this an hour ago with a mistake, so i corrected and undeleted.