# Combinatorial proof that the maximum of an i.i.d. sample of size $n$ uniform on $(0,1)$ has expectation $\frac{n}{n+1}$?

Let $X_i \sim U(0,1)$ for $i = 1,\dots,n$, and let $X = \max(X_1,\dots,X_n)$. Is there a combinatorial way of seeing that $$\mathbb E(X) = \frac{n}{n+1}$$ and likewise for the minimum? Intuitively this is my guess for the expectation since, "on average," the experiment results will be distributed evenly on $[0,1]$. This may of course be verified by $$\int_0^1 x[P(X < x)]' \mathrm dx = \int_0^1 nx^n \mathrm dx = \frac{n}{n+1}.$$

• Could you make more precise what a "combinatorial" proof is to you?
– Did
Aug 30, 2016 at 22:27
• A technique that would avoid integration by turning it into some counting problem. For instance, one can compute the probability that $X_1 < X_2$ via integration, but it's easier to note that there is a $1/2$ probability that any two numbers chosen from $[0,1]$ are in order. Aug 30, 2016 at 22:31
• I see. Thanks. 
– Did
Aug 30, 2016 at 22:34

Let $(Y_1,Y_2, \cdots, Y_n)=(X_{(1)},X_{(2)}, \cdots, X_{(n)})$ be the ranked (ordered) variables. Let $(Z_0,Z_1, \cdots Z_n)$ be the differences : $Z_i=Y_{i+1}-Y_i$ (with $Y_0=0$ and $Y_{n+1}=1$); hence $Z_i\ge 0$ and $\sum\limits_{i=0}^n Z_i=1$.
It can be shown that the $Z_i$ have the same distribution as $n+1$ i.i.d. exponential variables $W_i$ conditioned on $V_n=1$, where $V_n=\sum\limits_{i=0}^n W_i=1$.
Once we accept this, then we get $$E(Z_i)=E(W_i\mid V_n=1)=\frac{1}{n+1}$$
So $$E(Y_1)=E(Z_1)=\frac{1}{n+1}$$ and, for every $1\le k\le n$, $$E(Y_k)=E(Z_0 + \cdots + Z_{k-1})= \frac{k}{n+1}$$ in particular, $$E(Y_{n})=E(Z_0 + \cdots + Z_{n-1})= \frac{n}{n+1}$$