Monday 23 September 2013

combinatorics - Asymptotic Gilbert-Varshamov Bound Using Hilbert's Entropy Formula

I am reading Walker's book Codes and Curves and am having trouble proving this Lemma regarding the Asymptotic Gilbert-Varshamov bound.



Suppose that $q$ is a prime power and we define \begin{align*}
V_q(n,r) &:= \sum\limits_{i=0}^r {n\choose r}(q-1)^i
\end{align*}



We define the Hilbert entropy function as \begin{align*}
H_q(x) &:= \cases{0, & x= 0\\
x\log_q(q-1)-x\log_q x - (1-x)log_q(1-x), & $0 < x \leq 1-\frac{1}{q}$}

\end{align*}



There is a lemma that states if $0\leq\lambda\leq 1-\frac{1}{q}$ then \begin{align*}
\lim\limits_{n\to\infty}\frac{1}{n} \log_q V_q(n,\lfloor \lambda n\rfloor) &= H_q(\lambda)
\end{align*}



Walker suggests using Stirling's approximation to get this limit. Here is what I have so far: First, I find that if $0<\lambda \leq 1-\frac{1}{q}$ then \begin{align*}
H_q(\lambda) &= \lambda\log_q(q-1)-\lambda\log_q \lambda - (1-\lambda)log_q(1-\lambda)\\
&= \log_q\left(\frac{(q-1)^\lambda}{\lambda^\lambda(1-\lambda)^{1-\lambda}}\right)
\end{align*}




Then, try to calculate $\lim\limits_{n\to\infty} \frac{1}{n}\log_q V_q(n,\lfloor \lambda n\rfloor)$.
\begin{align*}
\lim\limits_{n\to\infty} \frac{1}{n}\log_q V_q(n,\lfloor \lambda n\rfloor) &= \lim\limits_{n\to\infty} \log_q\left(\left(\sum\limits_{i=0}^{\lfloor \lambda n\rfloor} {n\choose i}(q-1)^i\right)^\frac{1}{n}\right)\\
&= \log_q\left(\lim\limits_{n\to\infty} \left(\sum\limits_{i=0}^{\lfloor \lambda n\rfloor} {n\choose i}(q-1)^i\right)^\frac{1}{n} \right)
\end{align*}



Looking only at the terms inside the logarithm, I would like to show that \begin{align*}
\lim\limits_{n\to\infty} \left(\sum\limits_{i=0}^{\lfloor \lambda n\rfloor} {n\choose i}(q-1)^i\right)^\frac{1}{n} &= \frac{(q-1)^\lambda}{\lambda^\lambda(1-\lambda)^{1-\lambda}}
\end{align*}




Unfortunately, I get stuck here. This stackexchange post pointed me to this resource which essentially shows the case for $q=2$ in exercise 9.42. It looks easy to generalize to this problem using the provided method. However, I do not quite understand this crucial step:



If we let $m = \lfloor\lambda n\rfloor$, then we get that \begin{align*}
{n\choose m}\sum\limits_{i=0}^m \left(\frac{\alpha}{1-\alpha}\right)^i = {n\choose m}\frac{1-\alpha}{1-2\alpha}
\end{align*}

This step seems so simple based off of geometric series, but I cannot get my calculations into the provided form.

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...