# Expectation of maximum of arithmetic means of i.i.d. exponential random variables

Given the sequence $(X_n), n=1,2,...$, of iid exponential random variables with parameter $1$, define:

$$M_n := \max \left\{ X_1, \frac{X_1+X_2}{2}, ...,\frac{X_1+\dots+X_n}{n} \right\}$$ I want to calculate $\mathbb{E}(M_n)$. Running a simulation leads me to believe that $$\mathbb{E}(M_n)=1+\frac{1}{2^2}+\cdots+\frac{1}{n^2} = H_n^{(2)}.$$ Is this correct? If yes, how would one go proving it? I tried using induction and the fact that $M_{n+1}=\max \{M_n, \frac{1}{n}(X_1+\cdots+X_{n+1}) \}$ along with the equality $E(X_1|X_1+\cdots+X_{n+1})=\frac{1}{n}(X_1+\cdots+X_{n+1})$ but didn't manage to accomplish anything.

• Cute problem. I doubt your conjecture is true as $$E(M_{n}-M_{n-1})=\frac 1{n}P(M_{n}=\frac {S_{n}}n)$$ But for $n\ge 3$, $P(M_n=S_1)>P(X_1=\max_{i\le n} X_i)=\frac 1 n$ and heuristically $P(M_n=\frac {S_i}i)$ is a non-increasing function of $i\le n$, so $P(M_n=\frac {S_n}n)<\frac 1 n$, so your conjecture is an upper bound only. – A.S. Dec 16 '15 at 23:31
• @A.S. The correct formula should be the 2nd order $n^{\rm th}$ harmonic number , rather than the first order $n^2-{\rm th}$ harmonic number. – heropup Dec 17 '15 at 1:28
• My heuristic was wrong. $P(M_3=\frac {S_3}3)=\frac 1 3$ in alignment with conjecture. – A.S. Dec 17 '15 at 3:24
• that looks very much like that the $E[\cdot]$ here. Possibly relevant links: 1 2 – BCLC Dec 17 '15 at 14:28
• @A.S. Really 1/3 and not $H_3^{(2)}$ ? – BCLC Dec 17 '15 at 15:35

For any $x>0$ and $n>1$, the following relation holds (with $\mathbb P(M_1\leqslant x)=1-e^{-x}$):

$$\mathbb P(M_n \leqslant x)=\mathbb P(M_{n-1} \leqslant x) - e^{-nx}\frac{x^{n-1}n^{n-2}}{(n-1)!}\tag{1}$$

Consequently, $\mathbb P(M_n \leqslant x) = 1 - \sum\limits_{r=1}^{n} e^{-rx} \frac{x^{r-1}r^{r-2}}{(r-1)!}$. Therefore,

$$\mathbb E[M_n]=\int\limits_{0}^{\infty} \mathbb P(M_n>x) \mathrm dx = \sum\limits_{r=1}^{n}\int\limits_{0}^{\infty}e^{-rx}\frac{x^{r-1}r^{r-2}}{(r-1)!}\mathrm dx = \sum\limits_{r=1}^{n}\frac{1}{r^2}\,.$$

Proof of $(1)$:

$$\mathbb P(M_{n-1} \leqslant x) - \mathbb P(M_n \leqslant x) = e^{-nx}\int\limits_{0}^{x}\int\limits_{0}^{2x-x_1}\ldots\int\limits_{0}^{(n-1)x-\sum_{i=1}^{n-2}x_i}\mathrm dx_{n-1} \ldots \mathrm dx_1 \\= e^{-nx}\frac{x^{n-1}n^{n-2}}{(n-1)!}\,,$$ where the volume integral may be evaluated by successive application of Leibniz's integral rule .

• Can you explain a bit how Leibniz's integral rule can be used to prove $(1)$? – mr.stealyourgirl Dec 21 '15 at 15:54

One way to calculate $EM_n$ is to first calculate $P(M_n>m)$, for $m\in \mathbb R$, then use $EM_n=\int_0^\infty P(M_n>m)\,dm$.

Note that, in order for the event $\{M_n\le m\}$ to occur, it must be true that $X_1\le m$ and $X_2\le 2m-X_1$, and $X_3\le 3m-X_2-X_1$, and so on. Thus,

$$P(M_n\le m) = \int_0^m\int_0^{2m-x_1}\int_0^{3m-x_1-x_2}\cdots \int_0^{nm-x_1-\dots-x_{n-1}}e^{-(x_1+x_2+\cdots x_n)}dx_n\,dx_{n-1}\,\cdots dx_1\tag{*}$$

You can now use this expression to calculate $EM_n$. For example,

$$P(M_2\le m) = \int_0^me^{-x_1}\int_0^{2m-x_1}e^{-x_2}\,dx_2\,dx_1=\int_0^me^{-x_1}-e^{-2m}\,dx_1=1-me^{-2m}-e^{-m}$$ so, $$EM_2=\int_0^\infty P(M_2>m)\,dm=\int_0^\infty me^{-2m}+e^{-m}\,dm=\frac14+1$$ This does seem to suggest that $EM_n=\sum_1^n \frac1{k^2}$.

It might get messy, but perhaps you deduce a formula for $P(M_n\le m)$ by looking at more small cases, then prove it is correct by induction.