$$\int_{[0,1]^n} \max(x_1,\ldots,x_n) \, dx_1\cdots dx_n$$

My work:

I know that because all $x_k$ are symmetrical I can assume that $1\geq x_1 \geq \cdots \geq x_n\geq 0$ and multiply the answer by $n!$ so we get that $\max(x_1\ldots,x_n)=x_1$ and the integral that we want to calculate is $n!\int_0^1 x_1 \, dx_1 \int_0^{x_1}dx_2\cdots\int_0^{x_{n-1}} \, dx_n$ and now it should be easier but I'm stuck..

Can anyone help?

  • 2
    $\begingroup$ Try the case $n=2$ first. $\endgroup$ – Jean Marie Jul 28 '16 at 21:21

One can see by induction that:

$$\int_0^1 x_1 dx_1 \int_0^{x_2 } dx_2 \cdots = \int_0^1 x_1 \frac{x_{n - (n-1)}^{n-1}}{(n-1)!} dx_1 =\frac{1}{(n+1) \times (n-1)!}$$

Therefore, the original integral is:

$$n! \times \frac1{(n+1) \times (n-1)!} = \frac{n}{n+1}$$


This is an alternative approach.

Let $X_i$ ($i=1,\cdots , n$) be independent uniform random variable in $[0,1]$.

What is the PDF of $M=\max (X_1, \cdots, X_n)$?

Then what is $\mathbf{E}[M]$?

  • 2
    $\begingroup$ Ah, a probabilistic approach. Nice. $\endgroup$ – Brevan Ellefsen Jul 28 '16 at 22:33
  • $\begingroup$ @BrevanEllefsen: knowing the properties of Beta distributions make this rather easy $\endgroup$ – Henry Jul 29 '16 at 8:22

Note that $\max(x_1,x_2,\dots,x_n)=\max(x_1,\max(x_2,\dots,x_n))$. In addition, note that

$$\begin{align} \int_0^1\int_0^1\max(x,y)\,dx\,dy&=\int_0^1\left(\int_0^y y\,dx+\int_y^1 x\,dx\right)\,dy\\\\ &=\int_0^1 \left(\frac12+\frac12 y^2\right)\,dy \end{align}$$

Now, we can write

$$\begin{align} \int_0^1 \max(x_1,x_2,\dots,x_n)\,dx_1&=\int_0^1 \max(x_1,\max(x_2,\dots,x_n))\,dx_1\\\\ &=\int_0^{\max(x_2,\dots,x_n)}\max(x_2,\dots,x_n)\,dx_1+\int_{\max(x_2,\dots,x_n)}^1x_1\,dx_1\\\\ &=\frac12 +\frac12\left(\max(x_2,\dots,x_n)\right)^2 \end{align}$$

Then, observe that

$$\begin{align} \frac{1}{k}\int_0^1 \left(\max(x_k,\dots ,x_n)\right)^{k}\,dx_k&=\int_0^{\max(x_{k+1},\dots ,x_n)}\left(\max(x_{k+1},\dots ,x_n)\right)^k\,dx_k+\int_{\max(x_{k+1},\dots ,x_n)}^1 x_k^k\,dx_k\\\\ &=\frac{1}{k}\left(\frac{k}{k+1}\left(\max(x_{k+1},\dots,x_n)\right)^{k+1}+\frac{1}{k+1}\right)\\\\ &=\frac{1}{k(k+1)}+\frac{1}{k+1}\left(\max(x_{k+1},\dots,x_n)\right)^{k+1} \end{align}$$

Proceeding inductively, we find that

$$\begin{align} \int_0^1\cdots \int_0^1 \max(x_1,x_2,\dots,x_n)\,dx_1\cdots dx_n&=\frac1{(2)(1)}+\frac{1}{(3)(2)}+\frac{1}{(4)(3)}+\cdots +\frac{1}{(n+1)(n)}\\\\ &=\sum_{k=1}^n \frac{1}{k(k+1)}\\\\ &=\sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right)\\\\ &=\frac{n}{n+1} \end{align}$$

  • 2
    $\begingroup$ +1. It's an elegant proof. Given the quite simple and unexpected result, we always think it must be some simple or, lets say, 'direct procedure'. This 'theorem' doesn't seem to be true, anyway. $\endgroup$ – Felix Marin Jul 29 '16 at 1:43
  • $\begingroup$ @felixmarin Thank you! And very much appreciated as always. -Mark $\endgroup$ – Mark Viola Jul 29 '16 at 12:18

This is pretty straightforward using probabilistic methods: What you're looking for is

$$E[\max_{1 \le i \le n} X_i] = \int_{[0,1]^n} \max x_i \ \ dx_1\dots dx_n$$

where $X_i$ are iid uniformly distribuited on $[0,1]$.

Now call $Y = \max_i X_i$; its distirbution function is given by

$$F_Y(x) = P(\max X_i \le x) = \prod_i P(X_i \le x) = x^n \ \ \ \text{ $x \in [0,1]$}$$

Hence $Y$ is absolutely continuos and its density is given by $$f_Y(x) = nx^{n-1}1_{[0,1]}(x)$$

Hence we find that

$$E[\max X_i] = E[Y] = \int_\mathbb R xf_Y(x) dx = \int_0^1 nx^n dx = \frac n{n+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.