Question

I'm a teaching assistant in an introductory course of Information Theory. I intend to prove the following well-known fact that easily proven using elementary information theoretic consideration: $\forall t\leq n/2 : \sum _{i=0} ^t \binom {n}{i} \leq 2^{nH\left(\frac t n \right)}$

After this proof, I would like to present simple implications of it. So what I'm looking for is applications of this fact that yield non-trivial results. It is however important that the examples will require very little new definitions and as short introduction as possible. We assume that the students do have a standard undergraduate familiarity with Combinatorics, Graph Theory etc.

Answer 1

How about using this bound to show that the balanced binomial distribution is tightly concentrated around $n/2$? Taking $t=n/2 - \omega(1)\sqrt{n}$, where $\omega(1)$ is a function that goes to infinity with $n$ arbitrarily slowly, your bound together with the Taylor series expansion of $H(1/2 + x)$ gives that the sum of the binomial coefficients up to $t$ is at most $o(2^n)$, and by symmetry the same goes for the sum from $n-t$ to $t$; so the conclusion is that for any such $\omega(1)$, we have that $1-o(1)$ of the mass of ${\rm Bin}(1/2)$ lies in the interval $(n/2-\omega(1)\sqrt{n},n/2+\omega(1)\sqrt{n})$. This is non-trivial, extremely useful, follows quickly from your bound, but isn't something that you would ``see'' instantly.

A quick application of the concentration result could be to the random graph $G(n,1/2)$: for any $\omega(1)$, almost surely the difference between the number of edges and non-edges in $G(n,1/2)$ is at most $\omega(1)n$.

Answer 2

A nice application is showing that every Cayley graph of an Abelian group with a set of generators of logarithmic size has also logarithmic diameter.

More precisely, let $G$ be an Abelian group and let $S$ be a symmetric generating set for $G$ of size $d = c_{0} \log n$ (where $n = |G|$ and $c_{0} > 0$ is a constant. Then for any $c_{1} > 0$ such that: $$ (c_{0} + c_{1})H(\frac{c_{1}}{c_{0} + c_{1}}) < 1 $$

we have $diam(G) \geq c_{1} \log n$, where $diam(G)$ is the diameter of the Cayley graph of $G$ with generating set $S$.

The proof uses a simple observation that the number of distinct pairs of endpoints of paths of length $l$ is at most $\binom{d+l}{l}$, since to determine an element of $G$ as a word in generators we only need to specify which generator appears how many times (because of commutativity the order is unimportant). So we have: $$ \sum\limits_{l=0}^{c_{1} \log n} \binom{c_{0}\log n + l}{l} \leq 2^{(c_{0} + c_{1})H(\frac{c_{1}}{c_{0} + c_{1}}) \log n} < n $$ so the number of vertices reachable from a fixed vertex by a path of length $l \leq c_{1}\log n$ is strictly smaller than $n$. This implies that $diam(G) \geq c_{1}\log n$.

This fact is used by Newman and Rabinovich in "Hard Metrics From Cayley Graphs Of Abelian Groups" to give a simple example of an $n$-point metric space which requires distortion $\Omega(\log n)$ to embed it into $\ell_{2}$.