3
$\begingroup$

I'm reading Fan Chung's Spectral Graph Theory. There's a pair of inequalities I don't know how to justify. Chung doesn't attempt to explain them, so maybe they're very obvious. Example 1.19 on page 20 reads, in part:

$ \frac{1}{2} \bigg( \sum_{k=1}^n \binom{n}{k} (1 - \frac{2k}{n+1})^{2s} \bigg)^{1/2} \leq \frac{1}{2} \bigg( \sum_{k=1}^n e^{k\log n - \frac{4ks}{n+1}} \bigg)^{1/2} \leq e^{-c} $ if $s \geq \frac{1}{4}n\log n +cn$

($n$ and $s$ are arbitrary positive integers, representing the number of vertices in a graph and the number of steps in a random walk, respectively.)

The first inequality seems to suggest that

$ \binom{n}{k}(1-\frac{2k}{n+1})^{2s} \leq e^{k\log n - \frac{4ks}{n+1}} $

I do know that $(1 + x/n)^n \approx e^x$ for large $n$, and there's a faint resemblance to the inequality above. Could that be part of the answer?

(An excerpt of the book which contains the part I'm talking about is available here: http://www.math.ucsd.edu/~fan/research/cbms.pdf )

  • 0
    A partial answer: Multiply by 2 and square both sides and you get.. $\sum\limits_{k=1}^n {n \choose k}\left(1-\frac{2k}{n+1}\right)^{2s} \leq \sum\limits_{k=1}^n e^{k\ln(n)-\frac{4ks}{n+1}} = \sum\limits_{k=1}^n n^k(e^{-2k/(n+1)})^{2s}$. Next, note that $1-2k/(n+1)$ is the first two terms in the Taylor series for $e^{-2k/(n+1)}$2011-11-23

1 Answers 1

1

For the first inequality, use $\binom{n}{k} \leq n^k$ and $1 - \epsilon \leq \exp(-\epsilon)$. The first follows since $\binom{n}{k} = n(n-1)\cdots(n-k+1)/k!$, the second is true for all $\epsilon \geq 0$ by elementary calculus.

For the second inequality, think of the expression as a geometric series in $ a = \exp(\log n - 4ks/(n+1)) \leq \exp(\log n - 4ks/n) \leq \exp(-4c). $ The expression is at most $ \tfrac{1}{2} \sqrt{\frac{1}{1-a} - 1} \leq \tfrac{1}{2} \exp(-2c) \sqrt{\frac{1}{1-\exp(-4c)}}. $ Since $\exp(-2c) \leq \exp(-c)$, the required inequality is true if $ \tfrac{1}{2} \leq \sqrt{1-\exp(-4c)}. $ Squaring and rearranging, we get $c \geq -\ln(3/4)/4 \approx 0.072$; this bound is not best possible, though the inequality does fail for small $c$.