Limit of $\sum_{j=0}^n (1-j){n\choose j} \frac{1}{(n-1)^j}\left( \frac{n-j}{n} \right)^k$ as $n\to \infty$ (and $k=n$)

Question

Question

Find $\lim_{n\to \infty} P(n,n)$ where $$ P(n,k) = \sum_{j=0}^n (1-j){n\choose j} \frac{1}{(n-1)^j}\left( \frac{n-j}{n} \right)^k. $$

The origin of this sum is from this question. The probability that a box is empty after $k$ iterations is given by $\left( \frac{n-1}{n} \right)^n P(n,k)$. Verifications of this are also welcome, I just managed to guess it with numerical evidence. But that got me thinking about the limiting behavior.

Obviously for any particular $n$, if $k \to \infty$, only the term $j=0$ survives and we're left with just $P(n, \infty) = 1$. This means the probability is $\left( \frac{n-1}{n} \right)^n$ and that goes to $e^{-1}$. But what if $n$ goes to infinity with $k$? Let's consider the case $k=n$. More general approaches would be interesting too.

---

If we approximate (but are these allowed?)

$$ {n\choose j} \frac{1}{(n-1)^j} \approx \frac{1}{j!} $$

and (remember now $k=n$)

$$ \left( \frac{n-j}{n} \right)^n \approx e^{-j} $$

we get

$$ P(n,n) \approx \sum_{j=0}^n {\frac{1-j}{j!}}e^{-j} $$

and hence the limit would be

$$ \lim_{n\to \infty} P(n,n) = {\huge e^{\frac{1}{e}} \left(1-\frac{1}{e} \right)}. $$

And the probability would be

$$ e^{\frac{1}{e}-1} \left(1-\frac{1}{e} \right) = 0.335949071234. $$

Answer 1

I just realised: doesn't this follow from the Dominated Convergence Theorem? We can put the indicator $\mathbb{1}_{j<n}$ in there and let the sum go all the way to infinity (or actually the binomial coefficient already is $0$ when $j>n$). And for each $j$

$$ \left( \frac{n-j}{n} \right)^n \leq e^{-n} $$

and

$$ {n\choose j} \frac{1}{(n-1)^j}\ \leq \frac{1}{j!} \space \space \text{ (when n large, or put some constant there) } $$

And the sum with these converges, so by DOM we can take the limit inside and point-wise those limits are clear.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{{\displaystyle #1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\on}[1]{\operatorname{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\sr}[2]{\,\,\,\stackrel{{#1}}{{#2}}\,\,\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#44f}{\on{P}\pars{n,k}} & \equiv \color{#44f}{% \sum_{j\ =\ 0}^{n}\pars{1 - j}{n \choose j} {1 \over \pars{n - 1}^{\,j}} \pars{n - j \over n}^{k}} \\[5mm] & \sr{j\ \mapsto\ n\, -\, j}{=} \sum_{j\ =\ 0}^{n}{n \choose n - j} {1 - \pars{n - j} \over \pars{n - 1}^{\,n - j}} \bracks{n - \pars{n - j} \over n}^{k} \\[5mm] & = {1 \over \pars{n - 1}^{n}\,n^{k}\,} \sum_{j\ =\ 0}^{n} {n \choose j}\bracks{j\pars{n - 1}^{\,j} - \pars{n - 1}^{\,j - 1}}j^{k} \\[5mm] & = \left.{1 \over m^{n}\,n^{k}\,} \sum_{j\ =\ 0}^{n}{n \choose j} \pars{jm^{\,j} - m^{j - 1}}\,\,\, \overbrace{\braces{k!\bracks{z^{k}}\expo{jz}}} ^{\ds{j^{k}}}\right\vert_{\,m\ \equiv\ n - 1} \\[5mm] & = {k! \over m^{n}\,n^{k}\,}\bracks{z^{k}} \sum_{j\ =\ 0}^{n}{n \choose j} \bracks{j\pars{m\expo{z}}^{\,j} - {\pars{m\expo{z}}^{\,j} \over m}} \\[5mm] & = {k! \over \pars{n - 1}^{n + 1}\,\,n^{k}}\ \times \\[2mm] & \quad\bracks{z^{k}} \bracks{1 + \pars{n - 1}\expo{z}}^{n - 1}\ \bracks{\pars{n^{3} -2n^{2} - 1}\expo{z} - 1} \end{align}