Maximum of a sum of random variables
Let $X_1, \dots, X_n$ be independent and identically distributed random variables with $E(X_i) = 0$ and $$S_k = \sum_{i \leq k} X_i$$
- What is the probability distribution of $M_2 = \max \{ X_1, X_1+X_2 \}$?
We can suppose $X_i$ have normal distribution ; we have to note that $X_1$ and $X_1 + X_2$ are not independent, that's why all my attempts of computing $P(S \leq t)$ failed.
- What is the probability distribution of $M_3 =\max \{ X_1, X_1+X_2, X_1+X_2+X_3 \}$, and, more generally, of $M_n = \max\limits_{k \le n} {S_k}$ ?
Solution 1:
Through the Spitzer identity, it is possible to find some kind of transform of the distribution of $M_n$. Well, not exactly. The Spitzer identity involves the expressions $M^+_n = \max_{0\le k\le n} S_k$, where $S_0 = 0$, $S_k = X_1 + \dots + X_k$, $k\ge 1$. So this translates to the positive part of expression you are interested in. But it is possible to reduce the original question to this one, since, as it was already mentioned in the previous answers, $M_n$ has the same distribution as $X + M_{n-1}^+$, and $X$ is independent of $M_{n-1}^+$.
Going back to the Spitzer identity, it reads $$ \sum_{n=0}^\infty s_n \mathsf E[e^{-\lambda M_n^+}] = \exp\left\{\sum_{n=1}^\infty \frac{s^n}n \mathsf E[e^{-\lambda S_n^+}] \right\}, $$ where $S_n^+ = \max\{S_n,0\}$.
The right-hand side can be calculated more or less explicitly in some cases. For example, if $X\simeq N(0,\sigma^2)$, then $S_n \simeq N(0,\sigma^2 n)$, so $$ \mathsf E[e^{-\lambda S_n}\mathbf{1}_{S_n\ge 0}] = \int_0^\infty e^{-\lambda \sigma x\sqrt{n}} e^{-x^2/2}\frac{dx}{\sqrt{2\pi}} = \sqrt{n} \int_0^\infty e^{-\lambda \sigma y n} e^{-y^2n/2}\frac{dy}{\sqrt{2\pi}}. $$ Therefore, $$ \sum_{n=1}^\infty \frac{s^n}n \mathsf E[e^{-\lambda S_n}\mathbf{1}_{S_n\ge 0}] = \sum_{n=1}^\infty \int_0^\infty \frac{s^n e^{-\lambda\sigma yn} e^{-y^2n/2}}{\sqrt{2\pi n}} dy = \int_0^\infty \operatorname{Li}_{1/2}(s e^{-\lambda\sigma y}e^{-y^2})\frac{dy}{\sqrt{2\pi}}, $$ where $\operatorname{Li}_{s}(x) = \sum_{n=1}^\infty{x^n}n^{-s}$ denotes the polylogarithm. Hence, $$ \sum_{n=1}^\infty \frac{s^n}n \mathsf E[e^{-\lambda S_n^+}] = \sum_{n=1}^\infty \frac{s^n}n \mathsf E[e^{-\lambda S_n}\mathbf{1}_{S_n\ge 0}] + \frac12 \sum_{n=1}^\infty \frac{s^n}{n}\\= \int_0^\infty \operatorname{Li}_{1/2}(s e^{-\lambda\sigma y}e^{-y^2})\frac{dy}{\sqrt{2\pi}} - \frac12\log(1-s). $$
This does not look too neat, but it is not hopeless as it might seem. From here you can calculate expectations (quite easily), variances (not so easily) and get some expressions for higher order moments of $M_n^+$.
Solution 2:
1) $\max(x_1, x_1 + x_2) \le t$ if either $x_1 \le t$ and $x_2 \le 0$, or $x_1 + x_2 \le t$ and $x_2 \ge 0$. It may help to sketch this in the $x_1-x_2$ plane. Thus if $(X_1, X_2)$ has joint density $f(x_1,x_2)$, $$P(\max(X_1, X_1 + X_2) \le t) = \int_{-\infty}^t dx_1 \int_{-\infty}^{t-x_1} dx_2 f(x_1,x_2)$$
If $X_1$ and $X_2$ are iid with density $f$ and cdf $F$, this can be written as $$ \int_{-\infty}^t dx_1 \; f(x_1) F(t-x_1) $$ The density for $\max(X_1,X_1+X_2)$ is then the derivative of that with respect to $t$, namely
$$ f(t) F(0) + \int_{-\infty}^t dx_1 \; f(x_1) f(t-x_1) $$
In the case of the normal distribution $\mathscr N(\mu, \sigma^2)$, if I haven't made a mistake that density is
$$ \dfrac{\exp(-(t-\mu)^2/(2\sigma^2))}{\sqrt{2\pi} \sigma} + \dfrac{\exp(-(t/2 - \mu)^2/\sigma^2)}{2\sqrt{\pi}\sigma} \Phi\left(\frac{t}{\sqrt{2}\sigma}\right) - \dfrac{\exp(-(t-\mu)^2/(2\sigma^2))}{\sqrt{2\pi} \sigma} \Phi\left(\frac{\mu}{\sigma}\right)$$
where $\Phi$ is the standard normal CDF.
Solution 3:
An observation (to replace a previous wrong answer). Note that $$M_2=X_1+X_2^+$$ where $X_2^+=\max\{0,X_2\}$. So, $$E[M_2]=E[X_1]+E[X_2^+]=0+\frac{1}{σ\sqrt{2\pi}}$$ Similarly $$M_3=X_1+\max\{0,X_2,X_2+X_3\}=X_1+\left(X_2+\max\{0,X_3\}\right)^+=X_1+\left(X_2+X_3^+\right)^+$$ with $E[M_3]>E[X_2^+]=E[M_1]$.
And two links here and here that might indicate(?) that there is not a nice (easily tractable) closed form expression for the distribution of $M_n$.
Solution 4:
Let $\rho$ be the probability density function(PDF) and let $F_<(x) := P(X<x)$ by the cumulative density function(CDF) of $X$. Fix $n\ge 2$. Define $M_n := max(X_1,X_1+X_2,\cdots,\sum\limits_{j=1}^n X_j)$. Take $1\le i\le n$. Clearly $M_n = \sum\limits_{j=1}^i X_j$ if and only if $X_1 \in {\mathbb R}$ and $(X_j)_{j=2}^n \in \Delta_i$ where: \begin{equation} \Delta_i := \left( \begin{array}{rrrr} X_n+X_{n-1}+\cdots+X_{i+1}& &<& 0\\ X_{n-1}+\cdots+X_{i+1}& &< & 0\\ \vdots & & & \\ X_i+X_{i+1}& &<& 0\\ X_{i+1}& &<& 0\\ &X_i &>& 0\\ &X_i+X_{i-1} &>& 0\\ \vdots \\ &X_i+X_{i-1}+\cdots+X_2 &>& 0 \end{array} \right) \end{equation} Therefore the density of $M_n$ reads: \begin{eqnarray} \rho_{M_n}(\xi) &=& \sum\limits_{i=1}^n\int\limits_{{\mathbb R} \times \Delta_i}\delta\left(\xi - \sum\limits_{j=1}^i x_j \right) \cdot \prod\limits_{j=1}^n \rho(x_j)d x_j \\ &=& \sum\limits_{i=1}^n \int\limits_{\Delta_i} \rho(\xi-(\sum\limits_{j=2}^i x_j)1_{i\ge 2}) \cdot \prod\limits_{j=2}^n \rho(x_j) d x_j \end{eqnarray} where in the bottom line we integrated over $x_1$. Now we substitute for the partial sums in the matrix above. Here we proceed from the top downwards all the way to the bottom. \begin{eqnarray} u_j &:=& -\sum\limits_{\xi=i+1}^{n-j+1} x_\xi & \mbox{for $j=1,\cdots,n-i$} \\ u_{j+n-i}&:=& \sum\limits_{\xi=i-j+1}^i x_\xi & \mbox{for $j=1,\cdots,i-1$} \end{eqnarray} Since the modulus of Jacobian of the transformation $(x_2,\cdots,x_n) \rightarrow (u_1,\cdots,u_{n-1})$ is equal to unity we get: \begin{eqnarray} \rho_{M_n}(\xi) = \sum\limits_{i=1}^n \int\limits_{{\mathbb R}_+^{n-1}} \rho(\xi-u_{n-1} 1_{i\ge 2}) \cdot \prod\limits_{j=n-i}^{n-2} \rho(u_{j+1}-u_j 1_{j> n-i}) \cdot \prod\limits_{j=1}^{n-i} \rho( u_{j+1} 1_{j< n-i} - u_j) \cdot d^{n-1} u \end{eqnarray} In the particular cases $n=2$ and $n=3$ we get : \begin{eqnarray} \rho_{M_2}(\xi) &=& \rho(\xi) \cdot F_{<}(0) + \int\limits_{-\infty}^\xi \rho(\xi-u_1) \rho(u_1) d u_1 \\ \rho_{M_3}(\xi) &=& \rho(\xi) \cdot \int\limits_0^\infty \rho(-u) F_{<}(u) d u + F_{<}(0) \cdot \int\limits_{-\infty}^\xi \rho(u) \rho(\xi-u) du \\ &&+\int\limits_0^\infty \int\limits_{-\infty}^\xi \rho(\xi-u_1-u_2) \rho(u_1)\rho(u_2) d u_2 d u_1 \end{eqnarray}