Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a friend who has a list of n numbers from [0, x). They are integers (though x is so large that doesn't really matter), and are uniformly randomly distributed. My friend figures out the smallest member from this set, and calls it y.

I know x and y, but not the original list of numbers or n. How can I estimate n? How accurate will my estimate be?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The bias of any estimator will go to $\infty$ as $n\to\infty$. This is because as $n\to\infty$, the probability that $y=0$ goes to $1$. You have to assign some arbitrary estimate $n_0$ to $y=0$, and then no matter what estimates you assign to the other values of $y$, as $n\to\infty$ the expected value of your estimate will go to $n_0$ as $n\to\infty$, whereas it should be going to $\infty$ along with $n$.

However, you can estimate $1/(n+1)$. This is messy and approximate for a discrete distribution, so I'll derive it for a uniform continuous distribution on $[0,1]$ and you can use it as an approximation for your discrete case.

The cumulative distribution function for $y$ in this case is $1-(1-y)^n$, the density is $n(1-y)^{n-1}$, and the expected value of $y$ is

$$ \int_0^1n(1-y)^{n-1}y\,\mathrm dy=\frac1{n+1}\;. $$

Thus $y$ is a unbiased estimator for $1/(n+1)$. Its variance is

$$ \begin{align} \langle y^2\rangle-\langle y\rangle^2 &= \int_0^1n(1-y)^{n-1}y^2\,\mathrm dy-\frac1{(n+1)^2} \\ &= \frac2{(n+1)(n+2)}-\frac1{(n+1)^2} \\ &= \frac n{(n+1)^2(n+2)} \\ &\sim\frac1{(n+1)^2}\;. \end{align} $$

Thus for large $n$ the standard deviation is also approximately $1/(n+1)$.

In the continuous case, you could use $n=y^{-1}-1$ to estimate $n$. The expected value of this estimator is infinite, but at least you'd have the right expected value for $1/(n+1)$. In the discrete case, you can't do this, since typically $y=0$ and then $y^{-1}$ isn't defined.

share|improve this answer
    
What do the angle brackets around y mean? By y^-1, you mean 1/y, right? –  Nick ODell Nov 1 '12 at 1:11
1  
@Nick: The angled brackets denote the expected value, otherwise also denoted by $E(y^2)$ or $\overline{y^2}$. Yes, $y^{-1}$ is standard notation for $1/y$. –  joriki Nov 1 '12 at 22:59
    
I'm not sure I totally understand your answer, but thank you. –  Nick ODell Nov 4 '12 at 7:25
    
@Nick: Feel free to ask about any parts you're not sure about. –  joriki Nov 4 '12 at 10:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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