# Problem about partial sum of exponential random variable

Let $X_1, X_2, \dots,X_n, X_{n+1}$ be independent random variable of exponential distribution, and the mean is 1.

Let $S_i = X_1 + \dots + X_i$

I want to know $\mathbb{E}\left[\max_{k=1}^n\left(\frac{S_k}{S_{n+1}} - \mathbb{E}\left(\frac{S_k}{S_{n+1}}\right)\right)\right]$. Approximated solution is OK.

Here, $\left(\frac{S_1}{S_{n+1}}, \frac{S_2}{S_{n+1}}, \dots, \frac{S_n}{S_{n+1}}\right)$ has the same distribution with the order statistics of $n$ uniform $U(0,1)$ random variables. Please see Didier's answer to Question about order statistics.

-
Do you really mean $S_{n+1}$ (is $X_{n+1}$ also defined then)? –  bgins Jan 26 '12 at 15:38
Yes, please see my update. –  Fan Zhang Jan 26 '12 at 15:42
What have you tried so far? Do you know that $S_k\sim\Gamma(k,1)$ (the sum of $k$ exponential iid RVs is Gamma -- en.wikipedia.org/wiki/Gamma_distribution) and that the ratios are therefore Beta (en.wikipedia.org/wiki/Beta_distribution)? –  bgins Jan 26 '12 at 15:50
Thank you for your hint, it seems still a bit hard to get the expectation of the maximum. –  Fan Zhang Jan 26 '12 at 15:59

By exchangeability, $\mathrm E\left(\frac{S_k}{S_n}\right)=\frac{k}n$ for every $0\leqslant k\leqslant n$.

Heuristics based on the functional central limit theorem suggest that, for every $0\leqslant t\leqslant 1$, when $k\approx tn$, $S_k\approx nt+\sqrt{n}\cdot B_t$ for a standard Brownian motion $(B_t)_{0\leqslant t\leqslant 1}$. Thus, $$\frac{S_k}{S_n}-\mathrm E\left(\frac{S_k}{S_n}\right)\approx\frac{nt+\sqrt{n}\cdot B_t}{n+\sqrt{n}\cdot B_1}-t\approx\frac1{\sqrt{n}}(B_t-tB_1).$$ The process $(B_t-tB_1)_{0\leqslant t\leqslant 1}$ is a standard Brownian bridge. This suggests that the expectation $\mathfrak e_n$ you are asking for behaves like $\mathrm E(M)/\sqrt{n}$, where $$M=\max\limits_{0\leqslant t\leqslant 1}(B_t-tB_1).$$ Finally, since $\mathrm P(M\geqslant x)=\mathrm e^{-2x^2}$ for every $x\geqslant0$, $\mathrm E(M)=\sqrt{\pi/8}$ and all this would yield the asymptotics $$\lim\limits_{n\to\infty}\sqrt{n}\cdot\mathfrak e_n=\sqrt{\pi/8}=0.626657\ldots$$ Edit The Brownian bridge is distributed like $(B_t)_{0\leqslant t\leqslant 1}$ conditioned on $B_1=0$, hence, for every $x\gt0$, $$\mathrm P(M\geqslant x)=\mathrm P(M_1\geqslant x\mid B_1=0),\qquad M_1=\max\limits_{0\leqslant t\leqslant 1}B_t.$$ Informally, intyroducing $T_x=\inf\{t\geqslant0\mid B_t\geqslant x\}$, $[M_1\geqslant x]=[T_x\leqslant1]$, hence $$\mathrm P(M_1\geqslant x\mid B_1=0)\approx\left.\frac{Q(\mathrm dz)}{\mathrm P(B_1\in\mathrm dz)}\right|_{z=0}$$ where $$Q(\mathrm dz)=\mathrm P(T_x\leqslant1,B_1\in\mathrm dz)=\mathrm P(T_x\leqslant1)\mathrm P(B_1\in\mathrm dz\mid T_x\leqslant1).$$ By the reflection principle, for $z\lt x$, $$\mathrm P(B_1\in\mathrm dz\mid T_x\leqslant1)=\mathrm P(B_1\in\mathrm 2x-dz\mid T_x\leqslant1),$$ hence $Q(\mathrm dz)=\mathrm P(B_1\in\mathrm 2x-dz, T_x\leqslant1)=\mathrm P(B_1\in\mathrm 2x-dz)$. Introducing the density $\varphi$ of the distribution of $B_1$ and applying this to $z=0$, this yields $\mathrm P(M\geqslant x)=\varphi(2x)/\varphi(0)$, which is the formula used above.

-
Hi Didier, is your result the same with $S_k/S_{n+1}$ in my question? –  Fan Zhang Jan 28 '12 at 15:20
Another question, how to get M's distribution as stated in your answer? –  Fan Zhang Jan 28 '12 at 15:23
??? The result is the same with $S_{n+1}$, obviously, since one looks at the asymptotics $n\to\infty$. –  Did Jan 28 '12 at 15:36
About $M$ distribution, this is textbook stuff (see Edit). –  Did Jan 28 '12 at 15:59
Hi Didier, sorry for another question, hope it is the last. How you get $\frac{1}{\sqrt{n}}(B_t - tB_1)$ from $\frac{nt+\sqrt{n}\cdot B_t}{n+\sqrt{n}\cdot B_1}-t$, what's the approximation did you take? –  Fan Zhang Jan 28 '12 at 17:50

Let $U_{k:n}$ be $k$-th order statistics in a uniform sample of size $n$. $U_{k:n}$ is equal in distribution to a beta random variables with parameters $\alpha = k$ and $\beta=n+1-k$, so that $$\mathbb{E}\left( \frac{S_k}{S_{n+1}} \right) = \mathbb{E}(U_{k:n}) = \frac{k}{n+1}$$ Thus we need to find the expectation of random variable $V_n = \max_{k=1}^n \left(U_{k:n} - \frac{k}{n+1} \right)$. Clearly $\mathbb{P}\left(-\frac{1}{n+1} \leqslant V_n \leqslant \frac{n}{n+1} \right) = 1$.

Let $-\frac{1}{n+1} <z<\frac{n}{n+1}$, and consider $$\begin{eqnarray} \mathbb{P}(V_n \leqslant z) &=& \mathbb{P}\left(\land_{k=1}^n \left(U_{k:n} \leqslant z+\frac{k}{n+1}\right)\right) = F_{U_{1:n}, \ldots, U_{n:n}}\left(z + \frac{1}{n+1},\ldots,z + \frac{n}{n+1} \right) \\ &=& \sum_{\begin{array}{c} s_1 \leqslant s_2 \leqslant \cdots \leqslant s_n \\ s_1+s_2 + \cdots+s_n+s_{n+1} = n \\ s_i \geqslant i \end{array}} \binom{n}{s_1,s_2,\ldots,s_{n+1}}\prod_{k=1}^{n+1} \left(F_U(z_k) - F_U(z_{k-1})\right)^{s_k} \end{eqnarray}$$ where $z_i = z + \frac{i}{n+1}$ and $z_0 = 0$ and $z_{n+1} = 1$. This gives an exact law for variable $V_n$.

Computation of the mean can be done as $$\mathbb{E}(V_n) = -\frac{1}{n+1} + \int\limits_{-\frac{1}{n+1}}^{\frac{n}{n+1}} \left( 1- \mathbb{P}(V_n \leqslant z) \right) \mathrm{d} z = \frac{n}{n+1} - \int\limits_{-\frac{1}{n+1}}^{\frac{n}{n+1}} \mathbb{P}(V_n \leqslant z) \mathrm{d} z$$

With this it is easy to evaluate moments for low values of $n$:

In[76]:= Table[n/(n + 1) -
Integrate[(
CDF[OrderDistribution[{UniformDistribution[], n}, Range[n]],
z + Range[n]/(n + 1)]) // Simplify, {z, -1/(n+1), n/(
n+1)}], {n, 1, 10}]

Out[76]= {0, 8/81, 129/1024, 2104/15625, 38275/279936, 784356/5764801,
18009033/134217728, 459423728/3486784401, 12913657911/100000000000,
396907517500/3138428376721}


Denominators of the expectation $\mathbb{E}(V_n)$ equal to $(n+1)^{n+2}$. Exact computations of $\mathbb{E}(V_n)$ for $n$ much higher than $n=10$ is difficult due to bad complexity.

However, simulation is always at hand.

-