3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Equation $E(\hat N) = \frac{n}{n=1}N$ is exact for sampling from (continuous population) $\mathsf{Unif}(0,N).$ $\endgroup$
    – BruceET
    Jul 15, 2021 at 0:19
  • $\begingroup$ @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? $\endgroup$ Jul 15, 2021 at 14:03
  • 1
    $\begingroup$ Won't be exact, of course, but OK as approximation. I simulated it both ways. $\endgroup$
    – BruceET
    Jul 15, 2021 at 16:27
  • $\begingroup$ 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} $. $\endgroup$
    – JimB
    Aug 6, 2021 at 17:34

1 Answer 1

2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.