

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
just curiosity, what is $H?$ – Will Jagy Mar 13 '12 at 0:38
I assumed at first that it was Shannon entropy, but then it doesn't type-check: t/n is a number, not a probability distribution. – Tom Leinster Mar 13 '12 at 0:49
I think its the binary entropy function. $H(x) = -x\log x - (1-x)\log (1-x)$. – VSJ Mar 13 '12 at 0:52
Ah, that makes sense. Thanks, VSJ. – Tom Leinster Mar 13 '12 at 0:59
The lower bound of Gilbert and Varshamov for binary codes is the first example that comes to mind. For a maximal code of length $n$ and distance at least $t+1$, the Hamming $t$-balls cover Hamming space, so there are at least $2^n / A$ of them where $A$ is the number of points in each ball. Now use your formula to obtain the asymptotic behavior of this bound. – Noam D. Elkies Mar 13 '12 at 5:10

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$.

share|cite|improve this answer

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}$.

share|cite|improve this answer

Your Answer


