2
$\begingroup$

In the middle of page 3 of this lecture on coding theory (linked), the following lower bound for ${n \choose pn}$ is derived, with $n$ and $q$ integers satisfying $n > 0$, $q \geq 2$, and $p \in [0, 1-1/q]$. Quoting:

By Stirling's formula, $m! = \sqrt{2\pi m}(m/e)^m(1 + o(1))$, [so] it follows that

${n \choose pn} \geq \left(\frac{1}{p}\right)^{pn} \left( \frac{1}{1-p} \right)^{(1-p)n} \exp(-o(n))$

My question is how exactly was this lower bound derived? In particular how does the first RHS factor $\left(\frac{1}{p}\right)^{pn}$ relate to ${n \choose pn}$; how does the second RHS factor $\left( \frac{1}{1-p} \right)^{(1-p)n}$ relate to ${n \choose pn}$; and finally how does $\exp(-o(n))$ relate to ${n \choose pn}$? I'm guessing that $\exp(-o(n))$ is a lower bound on $n!$ derived from the given Stirling formula, but I'm not entirely sure how it's obtained.

$\endgroup$

1 Answer 1

1
$\begingroup$

\begin{align} \binom{n}{pn} &= \frac{n!}{(pn)!(n-pn)!}\\ &= \frac{\sqrt{2\pi n}(n/e)^n (1+o(1))}{\sqrt{2\pi np}(np/e)^{np} (1+o(1))\cdot\sqrt{2\pi n(1-p)}(n(1-p)/e)^{n(1-p)} (1+o(1))}\\ % &= \frac{1}{\sqrt{2\pi n p(1-p)}\;(1+o(1))} \left(\frac{1}{p}\right)^{np} \left( \frac{1}{1-p}\right)^{n(1-p)}\\ &= \exp\big( -\tfrac12\ln (2\pi p(1-p)) - \tfrac12\ln(n) - \ln(1+o(1))\big)\left(\frac{1}{p}\right)^{np} \left( \frac{1}{1-p}\right)^{n(1-p)} \end{align}

Note that for any $t > 0$ $$\frac{-\tfrac12\ln (2\pi p(1-p)) - \tfrac12\ln(n) - \ln(1+o(1))}{n^t} \to 0$$ so the exponential expression satisfies $\exp(-o(n^t))$. So

$$\binom{n}{pn}\geq \exp(-o(n))\left(\frac{1}{p}\right)^{np} \left( \frac{1}{1-p}\right)^{n(1-p)}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .