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 Vq(n,r):=ri=0(nr)(q1)i



We define the Hilbert entropy function as Hq(x):={0, x= 0xlogq(q1)xlogqx(1x)logq(1x), 0<x11q



There is a lemma that states if 0λ11q then lim



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