4
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ just curiosity, what is $H?$ $\endgroup$
    – Will Jagy
    Mar 13, 2012 at 0:38
  • $\begingroup$ 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. $\endgroup$ Mar 13, 2012 at 0:49
  • 3
    $\begingroup$ I think its the binary entropy function. $H(x) = -x\log x - (1-x)\log (1-x)$. $\endgroup$
    – VSJ
    Mar 13, 2012 at 0:52
  • $\begingroup$ Ah, that makes sense. Thanks, VSJ. $\endgroup$ Mar 13, 2012 at 0:59
  • 3
    $\begingroup$ 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. $\endgroup$ Mar 13, 2012 at 5:10

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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