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):=r∑i=0(nr)(q−1)i
We define the Hilbert entropy function as Hq(x):={0, x= 0xlogq(q−1)−xlogqx−(1−x)logq(1−x), 0<x≤1−1q
There is a lemma that states if 0≤λ≤1−1q 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