Expectation for the MLE for a Uniform Discrete Random Variable

Question

$\newcommand{\szdp}[1]{\!\left(#1\right)} \newcommand{\szdb}[1]{\!\left[#1\right]}$ Problem Statement: Suppose that $n$ integers are drawn at random and with replacement from the integers $1,2,\dots,N.$ Find the maximum-likelihood estimator $\hat{N}$ of $N,$ and show that $E\!\left(\hat{N}\right)$ is approximately $[n/(n+1)]N.$

Note: This is essentially Exercise 9.88a,b from Mathematical Statistics with Applications, 5th. Ed., by Wackerly, Mendenhall, and Sheaffer.

My Work So Far: Let $Y_1, Y_2,\dots,Y_n$ be the random sample. The distribution function is $$p(y)= \begin{cases} 1/N,&y\in\{1,2,\dots,N\}\\ 0,&\text{otherwise.} \end{cases} $$ Hence, the likelihood function is $$L=\frac{1}{N^n}.$$ It is clear that the logarithmic differentiation approach will not work, here. Instead, we need to choose the smallest value of $N$ that is still greater than all the $Y_i.$ That means $\hat{N}=Y_{(n)}=\max(Y_1, Y_2,\dots,Y_n),$ the maximum order statistic.

The cumulative distribution is just $$F(y_i)=P(Y_i\le y_i)=y_i/N.$$ Following the wikipedia page on order statistics based on discrete distributions, we construct the three probabilities: \begin{align*} p_1 &=P(Y_i<x)\\ &=F(x)-p(x)\\ &=x/N-1/N\\ &=(x-1)/N\\ p_2 &=P(Y_i=x)\\ &=p(x)\\ &=1/N\\ p_3 &=P(Y_i>x)\\ &=1-F(x)\\ &=1-x/N. \end{align*} It follows, then, that \begin{align*} P(Y_{(n)}\le x) &=(p_1+p_2)^n\\ &=\szdp{\frac{x-1}{N}+\frac1N}^{\!\!n}\\ &=\szdp{\frac{x}{N}}^{\!n}\\ P(Y_{(n)}<x) &=p_1^n\\ &=\szdp{\frac{x-1}{N}}^{\!\!n}\\ P(Y_{(n)}=x) &=P(Y_{(n)}\le x)-P(Y_{(n)}<x)\\ &=\szdp{\frac{x}{N}}^{\!n}-\szdp{\frac{x-1}{N}}^{\!\!n}\\ &=\frac{x^n-(x-1)^n}{N^n}\\ E\szdp{\hat{N}_2} &=\frac{1}{N^n}\sum_{x=1}^N x\szdb{x^n-(x-1)^n} \end{align*}

My Question: It's not the least bit obvious where to go from here. The exact sum is intractable unless I want to write it in terms of harmonic numbers (I think $N^{n+1}-H_{N-1}^{(-n)}$ is correct). The problem did say to find an approximate expectation, but there are usually dozens of ways to approximate things. Which approximation method would get me towards the stated goal?

Answer 1

I can replicate your result by computing the mean as

$$E[Y_{n}] = \sum_{y=1}^N P(Y_n \geq y) = \sum_{y=1}^N 1-\left( \frac{y-1}{N}\right)^n = N - \frac{1}{N^n} \sum_{y=0}^{N-1} y^n = N - \frac{H^{(-n)}_{N-1}}{N^n}$$

Then, if you approximate the generalized harmonic number with an integral $$\sum_{y=0}^{N-1}y^n \approx \int_0^{N-1}y^n dy = \frac{1}{n+1}(N-1)^{n+1}$$

You get $$\begin{array}{} E[Y_n]&\approx& N - \frac{1}{n+1} \frac{(N-1)^{n+1}}{N^n} \\ &\approx& \frac{N^{n+1}}{N^n} - \frac{\frac{1}{n+1}\sum_{k=0}^{n+1} {{n+1}\choose{k}}(-1)^{k}N^{n+1-k}}{N^n}\\ &\approx& \frac{N^{n+1}}{N^n} - \frac{\frac{1}{n+1}N^{n+1}+\sum_{k=1}^{n+1} {{n+1}\choose{k}}(-1)^{k}N^{n+1-k}}{N^n}\\ &\approx& N \frac{n}{n+1} - N \frac{1}{n+1} \sum_{k=1}^n {{n+1}\choose{k}}\frac{1}{(-N)^{-k}} &\approx& N \frac{n}{n+1} \end{array}$$

You would get to this more direct when you integrate till $N$ in which case the integral is $\frac{1}{n+1}N^{n+1}$

---

Alternative

The draw from a discrete uniform distribution is like the draw from a continuous uniform distribution but rounding the figure up. So you can use the order distribution for a sample drawn from a continuous uniform distribution as an estimate.

The order distribution for a sample drawn from a continuous uniform distribution is a beta distribution, $Beta(n,1)$, which has the mean $\frac{n}{n+1}$. Scaling the range from $(0,1)$ to $(0,N)$ adds another factor $N$ giving you $E[Y_n] \approx N \frac{n}{n+1}$

---

Lower estimate

So the estimate $E[Y_n] \approx N \frac{n}{n+1}$ stems from either one of the following:

• using the estimate of the generalized harmonic number $$\sum_{y=0}^{N}y^n \approx \int_0^{N}y^n dy = \frac{1}{n+1}(N)^{n+1}$$ which overestimates the generalized harmonic number and underestimates the expectation $E[Y_n]$

• estimating the uniform discrete distribution with the uniform continuous distribution but rounding the figures up to achieve the discrete distribution. (this means that the continuous distribution has a lower value than the discrete distribution) So, also from this point of view we can see that the estimate underestimates the expectation $E[Y_n]$.

If we would use a uniform continuous distribution, but round down, then this will be like using the uniform distribution from $1$ to $N+1$ instead of from $0$ to $N$ and the upper estimate is $N \frac{n}{n+1} + 1$