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.

Let's say we have a discrete random variable $X$ uniform distributes on $[1, n]$. Not we make $n$ experiments to get $X$ and record the minimal value of $X$ as $X_\min$. My question is, what is the expected value of $X_\min$?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

For clarity, I prefer to segregate the sample size from the support of the distribution. That is, I will assume that $X$ is uniform over $\{ 1, 2, \ldots, U \}$. The special case that the question is concerned with is not much simpler anyway. $\newcommand{\e}{\mathrm{e}} \newcommand{\Xmin}{X_\min}$

For $1 \leqslant r \leqslant U$, the probability that the minimum $\Xmin$ is at least $r$ is equal to $$ \Pr(\Xmin \geqslant r) = \frac{(U-r+1)^n}{U^n}. $$ This is because the event $\Xmin \geqslant r$ happens iff $X_i \geqslant r$ for all $i \in \{ 1, 2, \ldots, n \}$. For any fixed $i$, the probability of the latter event occurring is $\frac{U-(r-1)}{U}$. And as usual, by independence, the probability of all the $n$ events occurring simultaneously is just the product of the individual probabilities.

Therefore (e.g., see this wikipedia page for the formula used), $$ \mathbf{E}(\Xmin) = \sum_{r \geqslant 1} \Pr(\Xmin \geqslant r) = \sum_{1 \leqslant r \leqslant U} \frac{(U-r+1)^n}{U^n} = \frac{1}{U^n} \sum_{s = 1}^{U} s^n, \tag{$\ast$} $$ by re-indexing the sum.

The final expression $(\ast)$ is essentially the sum of the $n^{th}$ powers of the first $U$ natural numbers. I don't think this be simplified much further. :-)


Some asymptotics. We can say a bit more about the original question assuming $n \to \infty$.

In this case, for constant $r$, the probability that $\Xmin \geqslant r$ is equal to $$ \Big( 1 + \frac{1-r}{n} \Big)^n \to \e^{1-r}. $$ Of course, if $r$ is not a constant but grows with $n$ (i.e., $r \to \infty$ as $n \to \infty$), then this probability goes to $0$. Thus the probability that the minimum is exactly $r$ is $$ \e^{1-r} - \e^{-r} = (\e-1) \cdot \e^{-r}, $$ which is a geometric distribution (starting at $1$). The expected value of the distribution approaches $$ \sum_{r \geqslant 1} \e^{1-r} = \frac{1}{1 - \frac{1}{\e}} = \frac{\e}{\e - 1}. $$

share|improve this answer

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.