Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
2  
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
3  
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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.