0
$\begingroup$

How can I verify that

$\lim_{N,M,K \to \infty, \frac{M}{N} \to 0, \frac{KM}{N} \to \lambda} \frac{\binom{M}{x}\binom{N-M}{K-x}}{\binom{N}{K}} = \frac{\lambda^x}{x!}e^{-\lambda}$,

without using Stirling's formula or the Poisson approximation to the Binomial?

I have been stuck on this problem for a while, because I don't know how to divide up the terms and factorials without using the help of prior results!

Any help would be appreciated. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ Just out of curiosity, why are you constrained not to use Stirling's formula? $\endgroup$ – jbowman Oct 18 '13 at 17:30
  • $\begingroup$ I am not constrained - I know how to use it, but I would like to see if there is a simpler solution. $\endgroup$ – user30602 Oct 18 '13 at 17:33
  • $\begingroup$ Stirling's approximation follows easily from taking the logarithms of the binomial coefficients and so is perhaps one of the simplest and most natural solutions possible. $\endgroup$ – whuber Oct 18 '13 at 21:03
  • $\begingroup$ Ok. I used Stirling's formula, but not by taking the logarithms of the binomial coefficients. Could you show me how? $\endgroup$ – user30602 Oct 18 '13 at 23:07
1
$\begingroup$

This is the simplest proof I've been able to find.

Just by rearranging factorials, we can rewrite the hypergeometric probability function as
$$ \mathrm{Prob}(X=x) = \frac{1}{x!} \cdot \dfrac{M^{(x)} \, K^{(x)}}{N^{(x)}} \cdot \dfrac{(N-K)^{(M-x)}}{(N-x)^{(M-x)}}, $$ where $a^{(b)}$ is the falling power $a(a-1)\cdots(a-b+1)$. Since $x$ is fixed, \begin{align*} \dfrac{M^{(x)} \, K^{(x)}}{N^{(x)}} &= \prod_{j=0}^{x-1} \dfrac{(M-j) \cdot (K-j)}{(N-j)} \\ &= \prod_{j=0}^{x-1} \left( \dfrac{MK}{n} \right) \cdot \dfrac{(1-j/M) \cdot (1-j/K)}{(1-j/N)} \\ &= \left( \dfrac{MK}{N} \right) ^x \; \prod_{j=0}^{x-1} \dfrac{(1-j/M) \cdot (1-j/K)}{(1-j/N)}, \end{align*} which $\to \lambda^x$ as $N$, $K$ and $M$ $\to \infty$ with $\frac{MK}{N} = \lambda$.

Lets replace $N-x$, $K-x$ and $M-x$ by new variables $n$, $k$ and $m$ for simplicity. Since $x$ is fixed, as $N,K,M \to \infty$ with $KM/N \to \lambda$, so too $n,k,m \to \infty$ with $nk/m \to \lambda$. Next we write $$ A = \dfrac{(N-K)^{(M-x)}}{(N-x)^{(M-x)}} = \dfrac{(n-k)^{(m)} }{(n)^{(m)}} = \prod_{j=0}^{m-1} \left( \dfrac{n-j-k}{n-j} \right)= \prod_{j=0}^{m-1} \left( 1 - \dfrac{k}{n-j} \right)$$ and take logs: $$ \ln \, A = \sum_{j=0}^{m-1} \ln \left( 1 - \dfrac{k}{n-j} \right). $$ Since the bracketed quantity is an increasing function of $j$ we have $$ \sum_{j=0}^{m-1} \ln \left( 1 - \dfrac{k}{n} \right) \le \ln \, A \le \sum_{j=0}^{m-1} \ln \left( 1 - \dfrac{k}{n-m+1} \right), $$ or $$ m \, \ln \left( 1 - \dfrac{k}{n} \right) \le \ln \, A \le m \, \ln \left( 1 - \dfrac{k}{n-m+1} \right). $$ But $\ln (1-x) < -x$ for $0 < x < 1$, so $$ m \, \ln \left( 1 - \dfrac{k}{n} \right) \le \ln \, A < -m \, \left( \dfrac{k}{n-m+1} \right), $$ and dividing through by $km/n$ gives $$ \frac{n}{k} \, \ln \left( 1 - \dfrac{k}{n} \right) \le \dfrac{\ln \, A}{km/n} < - \, \left( \dfrac{n}{n-m+1} \right) = - \, \left( \dfrac{1}{1-m/n+1/n} \right). $$ Finally, we let $k$, $m$ and $n$ tend to infinity in such a way that $km/n \to \lambda$. Since both $k/n \to 0$ and $m/n \to 0$, both the left and right bounds $\to -1$. (The left bound follows from $\lim_{n \to \infty} (1-1/n)^n = e^{-1}$, which is a famous limit in calculus.) So by the Squeeze Theorem we have $\ln \, A \to -\lambda$, and thus $A \to e^{-\lambda}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy