$E[1/(M+1)]$ where $M$ is the number of unique items from sampling with replacement Let $M$ be the number of unique items from sampling $n$ items with replacement from a set of $n$ unique items. Compute the expectation:
$$E\left[\frac{1}{M+1}\right]$$
What I've tried
It's straightforward to compute the expectation of $M$ by representing $M$ as the sum of indicator functions (whether the $i$th element appears in the sample) and applying linearity of expectation.
However, as far as I can tell, computing the expectation of interest requires that I compute the marginal distribution of $M$ which I know is nontrivial (involving stirling numbers, see https://arxiv.org/abs/1602.05822)
Maybe there is some trick that makes the above expectation simpler to compute. I would also be happy with strong upper and lower bounds.
 A: There is a relatively explicit form. Fix $n$ and, for $0\leq k\leq n$, define
$$s_k=\frac{1}{\binom nk(n+1)}.$$
Claim. Let $0\leq m\leq n$ be a positive integer. Then
$$\sum_{k=0}^m\binom mk s_k=\frac1{n-m+1}.$$
Proof. Write
$$\sum_{k=0}^m\binom mks_k=\frac{m!(n-m)!}{(n+1)!}\sum_{k=0}^m\binom{n-k}{n-m}$$
and use the hockey stick identity. $\square$
Now, let $X$ be a random variable denoting the number of items we fail to select in any of the $n$ trials, i.e. $X=n-M$. For $S\subset\{1,\dots,n\}$, let $X_S$ denote the event that we select no element of $S$ in $n$ trials. We have
$$\mathbb E[X_S]=\frac{(n-|S|)^n}{n^n}.$$
Now, consider
$$Y=\sum_{S\subset\{1,\dots,n\}}X_Ss_{|S|}.$$
If $T$ is the exactly the set of items we fail to select, then
$$Y=\sum_{S\subset T}s_{|S|}=\sum_{k=0}^{|T|}\binom{|T|}ks_k=\frac{1}{n-|T|+1}=\frac1{n-X+1}=\frac1{M+1}.$$
So,
\begin{align*}
\mathbb E\left[\frac1{M+1}\right]
&=\sum_{S\subset\{1,\dots,n\}}X_Ss_{|S|}\\
&=\sum_{k=0}^n\frac{(n-k)^n}{n^n}\binom nks_k\\
&=\frac1{n+1}\sum_{k=0}^n\frac{(n-k)^n}{n^n}=\frac{\sum_{j=1}^n j^n}{n^n(n+1)}.
\end{align*}

Letting this expectation be $v_n$, we can also compute
$$\mu:=\lim_{n\to\infty}\frac{v_n}{\frac1{n+1}}=\lim_{n\to\infty}\sum_{j=1}^n\left(\frac jn\right)^n.$$
On one hand, this is at least, for any $\ell\geq 0$,
$$\lim_{n\to\infty}\sum_{j=n-\ell}^n\left(\frac jn\right)^n=\lim_{n\to\infty}\sum_{k=0}^\ell\left(1-\frac kn\right)^n=1+e^{-1}+\cdots+e^{-\ell},$$
so
$$\mu\geq \frac1{1-e^{-1}}=\frac{e}{e-1}.$$
On the other hand, using $1+x\leq e^x$ on $x=-k/n$,
$$\sum_{k=0}^n\left(1-\frac kn\right)^n\leq \sum_{k=0}^n e^{-k}<\frac e{e-1}.$$
So $\mu\leq \frac e{e-1}$. This means that $\mu=\frac e{e-1}$, and so your expectation given $n$ is $\frac e{e-1}n^{-1}+o(n^{-1})$.
A: This answer only identifies the limit of the ratio in question.
By writing $M_n$ as a sum of indicators, it is straightforward to show that:
$$\mathbb E \left [M_n\right] = n\left(1-\left (1- \frac{1}{n}\right)^n\right) = n\left (1-e^{-1} +o(1)\right)$$
where the second equality follows by definition of the exponential function.
Next it is also straightforward to show that $\left |M_n - \mathbb E [M_n]\right| \rightarrow 0$ in probability since the variance of $M_n$ goes to $0$ as $n \rightarrow \infty$.
So now we have that:
$$\mathbb E \left[\frac{\frac{1}{M_n + 1}}{\frac{1}{n+1}}\right] = \mathbb E \left[\frac{\frac{1}{\mathbb E[M_n] + 1 + o_p(1)}}{\frac{1}{n+1}}\right]$$
The expression inside the expectation:
$$\frac{\frac{1}{\mathbb E[M_n] + 1 + o_p(1)}}{\frac{1}{n+1}} = \frac{n+1}{\mathbb E[M_n] + 1 + o_p(1)} = \frac{n+1}{n\left (1-e^{-1} +o(1)\right) + 1 + o_p(1)}$$
Applying the expectation again we have:
$$\mathbb E \left [ \frac{n+1}{n\left (1-e^{-1} +o(1)\right) + 1 + o_p(1)}\right] = \frac{n+1}{n\left (1-e^{-1} +o(1)\right) + 1} + o(1)$$
Taking the limit and applying l'Hopital's rule we have that the limit is $(1-e^{-1})^{-1}$.
