# Expectation for the MLE for a Uniform Discrete Random Variable

$$\newcommand{\szdp}{\!\left(#1\right)} \newcommand{\szdb}{\!\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_ix)\\ &=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)}

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?

• Equation $E(\hat N) = \frac{n}{n=1}N$ is exact for sampling from (continuous population) $\mathsf{Unif}(0,N).$ Jul 15, 2021 at 0:19
• @BruceET Thanks for your comment. How can I convince myself that going from the continuous uniform to the discrete uniform will preserve the expected value? Jul 15, 2021 at 14:03
• Won't be exact, of course, but OK as approximation. I simulated it both ways. Jul 15, 2021 at 16:27
• Nothing wrong with harmonic numbers. The expectation is $N-\frac{H_{N-1}^{(-n)}}{N^n}$. So if an approximation is desired, get an approximation for the harmonic number. One such approximation is $\frac{1}{12} N^n \left(\frac{12 N}{n+1}-\frac{n}{N}+6\right)+\zeta (-N)$ from math.stackexchange.com/questions/1583452/…. This results in the approximation for the expectation as $N^{-n} (-\zeta (-N))+\frac{N n}{n+1}+\frac{n}{12 N}-\frac{1}{2}$.
– JimB
Aug 6, 2021 at 17:34

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$$