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.

  • $\begingroup$ Do you really mean $S_{n+1}$ (is $X_{n+1}$ also defined then)? $\endgroup$ – bgins Jan 26 '12 at 15:38
  • $\begingroup$ Yes, please see my update. $\endgroup$ – Fan Zhang Jan 26 '12 at 15:42
  • $\begingroup$ 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)? $\endgroup$ – bgins Jan 26 '12 at 15:50
  • $\begingroup$ Thank you for your hint, it seems still a bit hard to get the expectation of the maximum. $\endgroup$ – 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.

  • $\begingroup$ Hi Didier, is your result the same with $S_k/S_{n+1}$ in my question? $\endgroup$ – Fan Zhang Jan 28 '12 at 15:20
  • $\begingroup$ Another question, how to get M's distribution as stated in your answer? $\endgroup$ – Fan Zhang Jan 28 '12 at 15:23
  • $\begingroup$ ??? The result is the same with $S_{n+1}$, obviously, since one looks at the asymptotics $n\to\infty$. $\endgroup$ – Did Jan 28 '12 at 15:36
  • $\begingroup$ About $M$ distribution, this is textbook stuff (see Edit). $\endgroup$ – Did Jan 28 '12 at 15:59
  • $\begingroup$ 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? $\endgroup$ – 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) - 
      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, 

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. enter image description here


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.