36
$\begingroup$

What is the expected value of the maximum of 500 IID random variables with uniform distribution between 0 and 1?

I'm not quite sure of the technique to go about solving something like this. Could anyone point me the right direction?

Thanks

$\endgroup$

5 Answers 5

46
$\begingroup$

Suppose the maximum is $X_{500}$, then $$P(X_{500}\le x)=P(X_i \le x ,i=1,2,...,500)$$ Note that this is so because if the maximum is less than $x$ , then every other order statistic is less than $x$. Now since the $X_i's$ are IID, it follows that; $$P(X_{500}\le x)=\prod_{i=1}^{500} P(X_i\le x)=x^{500}$$ which is the CDF and so the PDF is $500x^{499}$ (which is obtained by differentiation). Now the expected value of the maximum is found as follows; $$E[X]=\int _0^1 x (500x^{499})dx=\int _0^1 500x^{500}dx=\frac {500}{501}$$

$\endgroup$
1
  • $\begingroup$ X500 is max implies every order statistic is less than X500 , X500 < x => X(1, 2 .. 499) <= X500 and X500 <= x , so i am confused why is this equivalent to what you have written as first equation ? $\endgroup$
    – user179156
    Commented Feb 5, 2018 at 7:18
28
$\begingroup$

There is one trick useful for uniform distribution.

The trick: If you have 500 independent uniform random variables on $[0;1]$ then you may think that you have 501 independent uniform random variables on a circumference with unit length. You just consider the first random variable as a cut-point, which transforms the circumference into a unit segment $[0;1]$.

The average distance between points on the circumference is $1/501$ and ...

the average length of 500 intervals is equal to $500/501$.

$\endgroup$
3
  • 2
    $\begingroup$ Could you provide more elucidation-- I don't understand the intuition for this way of thinking about the problem, and it seems interesting $\endgroup$
    – Tina
    Commented Jun 21, 2018 at 20:55
  • 2
    $\begingroup$ @Tinatim You just replace the experiment by an equivalent one. Choose 501 points on a circumference instead of 500 points on a segment. The average distance between points is 1/501 by symmetry. One point is considered as a cut, that transforms circumference into the segment. The distance between the maximum point and the end of the segment is the distance between cut-point and the point to the right (or to the left, does not matter). And this distance is 1/501 on average. So the remaining distance is 500/501 on average. $\endgroup$
    – Roah
    Commented Jun 23, 2018 at 7:24
  • $\begingroup$ @Tinatim: the 500 points will (on "average") divide the $[0,1]$ segment into 501 segments of length $1/501$. The maximum will sit at the end of the 500th segment, at position $500\times1/501$. $\endgroup$
    – roygbiv
    Commented Oct 18, 2022 at 10:11
2
$\begingroup$

George Pólya says "Is there a simpler problem of the same type that you do know how to solve?"

The way to go about solving something like this is to look at simpler cases first. What's the expected value of the maximum of one IID uniform random variable? What is the expected value of the maximum of two?

Mouse over if you want the actual answer.

I believe the answer is $\frac{500}{501}$.

$\endgroup$
1
$\begingroup$

Let $Y$ be the maximum. Then $P(Y\le y)=y^{500}$ (if $0\le y\le 1$). So now we know the cumulative distribution function of $Y$, and therefore the density, and therefore the mean.

$\endgroup$
0
$\begingroup$

This can be solved by taking repeated expectations. Fix $n$ (500 in your example), and let $Y_k = \mathrm{max}\,\left\{X_1, \ldots, X_k\right\}$ for $1 \leq k \leq n$. Set $R_k = \mathbb E\left(Y_k^{n + 1 - k}\right)$.

Then $R_1 = \int_0^1 x^n\,dx = \frac{1}{n + 1}$, and for $k > 1$, $$R_k = \mathbb E\left(\mathbb E Y_k^{n+1-k}\right|Y_{k-1}).$$

Now, $Y_k$ is $X_k$ if $X_k \geq Y_{k-1}$, and $Y_{k-1}$ otherwise. Thus

$$ R_k = \mathbb E \left(\int_0^{Y_{k1}}Y_{k-1}^{n+1-k}\,dx + \int_{Y_{k-1}}^1x^{n+1-k}\,dx\right) = \mathbb E\left(Y_{k-1}^{n+2-k} + \frac{1 - Y_{k-1}^{n+2-k}}{n+2-k}\right),$$ which in turn gives $$R_k = \frac{1}{n+2-k}+\frac{n+1-k}{n+2-k}R_{k-1}.$$

Using this expression for $R_k$ in terms of $R_{k-1}$, it is a matter of basic algebra to prove via induction that

$$R_k = \frac{1}{n+2 - k} + (n+1 -k)\sum_{i=n+2-k}^n \frac{1}{i(i+1)}.$$

Then $$\mathbb E Y_n = R_n = \frac{1}{2} + \sum_{i=2}^n \frac{1}{i(i+1)} = \sum_{i=1}^n \frac{1}{i(i+1)},$$ and it is again easy to prove by induction that the sum on the right equals $\frac{n}{n+1}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .