3

I got stuck with the following problem which seemed not to be very complicated at the beginning!

I would like to compute the CDF of a Binomial distribution, \begin{equation*} F(\ell;n,q) = \sum_{k=0}^{\ell} \binom{n}{k} q^k (1-q)^{n-k} \end{equation*} where $\ell$ is the solution of \begin{equation*} \sum_{k=0}^{\ell} \binom{n}{k} = 2^{\alpha n}. \tag{*} \end{equation*} for some fixed $0 < \alpha \le 1$.

Of course the exact value of $F(\ell;n,q)$ is not important (and I guess it is not possible to compute). I would like to know whether $F(\ell;n,q)$ goes to $0$ as $n \to \infty$ or not?

One way to see this is to check whether $\ell > n q$ or not. However, I cannot see how one can know this given (*). More precisely, I guess there should be a relatively simple criterion that tells us whether the CDF goes to $0$ or not (as $n$ gets large) by comparing $\alpha$ and $q$ (or perhaps $h_2(q)$, ...)

Any ideas?

Thanks in advance!

MikeL
  • 627

2 Answers2

0

If $\alpha = 1$ then $\ell(n) = n$ so $F$ is constant and equal to $1$.

Otherwise, let $\eta$ be the unique real number such that $h_2(\eta) = \alpha$ and $0 < \eta < \frac{1}{2}$. One can show that $\ell(n) \sim \eta n $ by using the Stirling formula and the very crude bounds $$ \log \binom{n}{\ell} \leq \log \sum_{k=0}^\ell \binom{n}{k} \leq \log n + \log \binom{n}{\ell}, \qquad \ell \leq \frac{n}{2}. $$ By the weak law of large numbers, we now deduce that $$ \lim_{n\to\infty}F(\ell(n);n,q) = \begin{cases}0 & \text{if } \eta < q\\1 & \text{if } \eta > q\end{cases}. $$ The case $\eta = q$ requires to know the second term of the asymptotic expansion of $\ell(n)$.

Siméon
  • 10,664
  • 1
  • 21
  • 54
  • Thanks a lot for your help. The problem in my case is that we know $q > 1/2$. So this will not help (i.e. this technique would always suggest that $\lim_{n\to\infty} F(\ell(n);n,q) = 0$. While for reasonably large $\alpha$ the answer should be $1$ (e.g. take $\alpha \approx 1$. Then $\ell(n) \approx n$ and $F(\ell(n); n,q) \approx 1$.) – MikeL Jul 09 '14 at 14:26
  • @MBP: Given your question, I assumed that $\alpha$ was fixed and bounded away from $1$. Can you edit it to make it more accurate? – Siméon Jul 09 '14 at 14:32
  • Sure! Done! :-) – MikeL Jul 09 '14 at 14:35
  • Great. So what you are suggesting is that when $q > \frac12$, as long as $\alpha < 1$ the limit is always zero. Which now makes sense to me. Thanks again! – MikeL Jul 09 '14 at 14:43
  • Yes. Actually it is much easier to prove under the assumption $q > \frac{1}{2}$, because $2^{\alpha n} < \frac{1}{2} 2^n$, which implies that $\ell \leq \frac{n}{2}$. – Siméon Jul 09 '14 at 14:46
0

Let $\gamma = (1 - \alpha)\log 2$ and $x = x(n) = \frac{n - 2l}{\sqrt{n}}$.

Approximating the binomial distribution with a normal one, we get $$ \Phi(-x) \approx e^{-\gamma n}$$ and we wish to compute the limit of

$$ \Phi\left(\frac{l - qn}{\sqrt{nq(1-q)}}\right) = \Phi\left(\frac{(1 - 2q)\sqrt{n} - x}{2\sqrt{q(1-q)}}\right). $$

So, it all amounts to the limit of $$A = (1-2q)\sqrt{n} - x.$$

From section 5 of Dominici, we get an approximation for $x \approx -\Phi^{-1}(e^{-\gamma n})$: $$ x \approx \sqrt{LW\left(\frac{1}{2\pi}e^{2\gamma n}\right)} $$ where $LW(y)$ is the Lambert W with asymptotic behaviour $LW(y) \approx \log(y) - \log(\log(y))$.

Now we just need to organise the computations.

To get rid of the square roots, we rewrite $$ A = \frac{(1-2q)^2 n - x^2}{(1-2q)\sqrt{n} + x}$$ ($q < 1/2$).

The numerator is then approximated by

$$ ((1-2q)^2 - 2\gamma)n + o(n)$$

while the denominator is $\sim \sqrt{n}$. We thus conclude:

  • If $q < \frac{1}{2}(1 - \sqrt{2\gamma})$, then $A \rightarrow +\infty$ and the limit is 1.
  • If $q > \frac{1}{2}(1 - \sqrt{2\gamma})$, then $A \rightarrow -\infty$ and the limit is 0 (the case $q \geq \frac{1}{2}$ is easy).

For the case $q = \frac{1}{2}(1 - \sqrt{2\gamma})$, the numerator is $\sim\log(n)$, $A \rightarrow 0$ and the limit is $1/2$.

filipos
  • 1,523