I'm current working on the following question from Chapter 1 of Theory of Probability and Random Processes by Koralov and Sinai:
For integers $n$ and $r$, find the number of solutions of the equation $$x_1 + \ldots + x_r = n,$$
where $x_i \geq 0$ are integers.
Assuming the uniform distribution on the space of the solutions, find $P(x_1=a)$ and its limit as $r\to \infty$, $n\to\infty$, $n/r\to\rho > 0$.
So, the first part is just a simple stars and bars and we get $\binom{n+r-1}{r-1}$. However, it's the second part, taking the limit, that I'm struggling with. Essentially, I'm trying to evaluate the following limit $$\lim_{n\to\infty\,r\to\infty\\n/r\to\rho} \binom{n-a+r-2}{r-2}\big/\binom{n+r-1}{r-1}.$$
Intuitively, I expect the limit to converge to some Poisson Distribution parameterized by $\rho$ and evaluated at $a$. I've attempted this by applying Stirling's Approximation, but have no idea how to proceed:
\begin{align}P(x_1=a)&=\binom{n-a+r-2}{r-2}\big/\binom{n+r-1}{r-1} \\ &= \frac{(n-a+r-2)!(r-1)!n!}{(r-2)!(n-a)!(n+r-1)!} \\
&= \frac{(r-1)n!(n-a+r-2)!}{(n+r-1)!(n-a)!} \\
&\approx \frac{(r-1)\sqrt{2\pi n}(n/e)^n\sqrt{2\pi (n-a+r-2)}\left(\frac{n-a+r-2}{e}\right)^{n-a+r-2}}{\sqrt{2\pi(n+r-1)}\left(\frac{n+r-1}{e}\right)^{n+r-1}\sqrt{2\pi (n-a)}\left(\frac{n-a}{e}\right)^{n-a}} \\
&\,\,\vdots \\
&= (r-1)n^n (e^{r-1})(n-a+r-2)^{n-a+r-2}(e^{2-r})\left(\frac{1}{n-a}\right)^{n-a}\left(\frac{1}{n+r-1}\right)^{n+r-1} \\
&\,\,\vdots \\
&= (r-1)e\left(\frac{n}{n+r}\right)^a \\
P(x_1=a)&= (r-1)e\left(\frac{n/r}{n/r+1}\right)^a.
\end{align}
Then, taking the limit of the last expression we get $(r-1)e(\rho/(\rho+1))^a$, which then goes to infinity. But this result makes no sense…
Best Answer
I think you can get a reasonable result without Stirling...
$${n-a+r-2\choose r-2}\big/{n+r-1 \choose r-1}$$
$$=\frac{(n-a+r-2)!}{(n-a)!(r-2)!}\cdot{\frac{n!(r-1)!}{(n+r-1)!}}$$
$$={\frac{n(n-1)\cdots(n-a+1)(r-1)}{(n+r-1)(n+r-2)\cdots(n+r-(a+1))}}$$ So in our limit, as $\{n,r\}\rightarrow \infty$, we have;
$$\approx\frac{(n)^{a}r}{(n+r)^{a+1}}=\frac{(r\rho)^{a}r}{(r\rho+r)^{a+1}}=\frac{(\rho)^{a}}{(1+\rho)^{a+1}}$$