Maximum of dependent random variables

Question

Consider the following process: Pick $N$ numbers uniformly at random from $U[0,1]$. Suppose that they are numbered such that $w_1 \geq w_2 \geq \cdots \geq w_N$. Denote $X_i=w_i-w_{i+1}$. Find $\mathbb{E}\left[ \max_i X_i \right]$.

Here's what I tried: \begin{aligned} \mathbb{E}\left( \max_i X_i \right) = & \int_{1/N}^1 1 - \mathbb{P}(\max_i X_i \leq x) dx \\ = & \int_{1/N}^1 \int_{1/N}^1 \cdots \int_{1/N}^1 \mathbb{P} \left( X_1\leq x ∧ X_2\leq x ∧ \cdots X_N\leq x \right) \end{aligned}

Well, things got quickly out of hand here. I am aware that integral limits above are not correct since $\sum_i X_i = 1$.

Is there a different way around for dependent random variables?

Answer 1

One way to think about this is to define the joint pdf: $$f(w_1,w_2,...,w_N)=f(w_1)f(w_2|w_1)f(w_3|w_2,w_1)...f(w_N|w_N-1,...w_1)$$ which I believe can be written as: $$f(w_1,w_2,...,w_N)=f_N(w_1|1)f_{N-1}(w_2|w_1)f_{N-2}(w_3|w_2)...f_1(w_N|w_N-1)$$ such that $f_{N-2}(w_3|w_2)$ is the pdf for $w_3$ which represents the maximum of $N-2$ uniform random variables over the range $[0,w_2]$. Using: https://stats.stackexchange.com/questions/18433/how-do-you-calculate-the-probability-density-function-of-the-maximum-of-a-sample $$f_n(w|b)={n w^{n-1}\over b^n}$$ Interestingly enough, many terms cancel, leaving: $$f(w_1,w_2,...,w_N) = N!$$ provided $w_1>w_2>...>w_N$ and zero otherwise. This supports the symmetry comment - it is uniform within the slice of space in which the ordering holds. Maybe this should have been obvious.

As a first attempt, with the erroneous assumption that the $X_i$ could be treated as independent. The next step is to consider $X_i=W_i-W_{i+1}$. Its pdf can be constructed as a convolution. Doing this by hand for $i=1$ and for $N=2$ and $N=3$ (work not shown here), suggests again a very simple form: $$h_N(x_1) = N(1-x_1)^{N-1}$$ As stated in the comment the pdf for $X_i$ is the same for all $i$. The cdf for each is therefore, $$H_N(x_i) = 1-(1-x_i)^N$$ Finally consider $Z_N=\max(X_i)$. Its cdf can be constructed through the product of the $(N-1)$ cdf's for $X_i$: $$P_N(Z_N<z)=\left(H_N(z)\right)^{N-1}$$ So the pdf is: $$g_N(z)=N(N-1)(1-z)^{N-1}\left[1-(1-z)^N\right]^{N-2}$$ and the expectation value is: $$E[Z_N]=\int_0^1 z\,g_N(z)\,dz$$ If we consider $U_N=1-Z_N$, the expectation works out easily (using WolframALPHA): $$E[U_N] = {N-1\over N}{\Gamma(N-1)\Gamma({1\over N})\over\Gamma(N+{1\over N})}$$ so finally, $$E[Z_N] = 1 - E[U_N] = 1 - {N-1\over N}{\Gamma(N-1)\Gamma({1\over N})\over\Gamma(N+{1\over N})}$$ A plot of $E[Z_N]$ vs $N$ is below (also Wolfram Alpha)

A correct approach treats the joint pdf for $x_i$, without the mistaken assumption above that the $X_i$ are independent. Transform from $w_i, i=1...n$ to $x_i = w_i - w_{i+1}, i = 1...N-1$ by the relations: $$w_2 = w_1 - x_1, w_3 = w_2 - x_2 = w_1 - x_1 - x_2, ...$$ so $$h(x_1,...,x_{N-1}) = \int_s^1 f(w_1, w_1-x_1, w_1 - x_1 - x_2, ...) \,dw_1$$ where the integral is over all possible $w_1$, from $s=\sum_{i=1}^{N-1}x_i$ to 1. This integral is easy, since the integrand is constant: $$h(x_1,...,x_{N-1}) = N! (1-s)$$ provided $s<1$ and 0 otherwise. To find the pdf for $Z_N=\max(X_i)$, evaluate: $$g_N(z) = \int h(z,x_2,x_3,...)\,dx_2\,dx_3... + \int h(x_1,z,x_2,...)\,dx_1\,dx_3... + ...$$ over the space $x_i<z$. Given the symmetry of $h()$, each integral is the same, so $$g_N(z) = (N-1)N!\int \left(1-z-\sum_{i=2}^{N-1}x_i\right)\,dx_2\,dx_3...\,dx_{N-1}$$ where the boundaries for integration are given by the conditions: $$0<x_i<z \mathrm{\ \ and\ \ } z+\sum_{i=2}^{N-1}x_i<1$$ I don't have tools to do this analytically for general N, so evaluated these for $N=2,3,4$. The pdfs are not simple forms (piecewise polynomials). The expectations for $Z_N$ turn out to be simple fractions: $$\begin{align} E[Z_2] & = 1/3 \\ E[Z_3] & = 3/8 \\ E[Z_4] & = 11/30 \end{align} $$ A numerical approach was used to find that, $$\begin{align} E[Z_5] & = 25/72 \\ E[Z_6] & = 137/420 \end{align} $$ With these values it became apparent that there is a very simple relation $$E[Z_N] = {1\over N+1}\sum_{i=1}^{N-1}{1\over i}$$ which correctly predicted the numerical result for $E[Z_7]$. No doubt there is a way to solve this problem analytically, since the result has such a simple form. Can anyone explain the approach to take?