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


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


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.