# 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$$

1. 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.

1. 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}$ ?

• Well known cases: 1. $S_n$ is simple random walk with $S_0=0$: $P(M_n\ge t)=P(S_n\ge t)+P(S_n\ge t+1)$ 2. $S_t$ is a driftless Brownian motion: $P(M_t\ge l)=2P(S_t\ge l)$ – A.S. Feb 2 '16 at 23:28
• Also see en.wikipedia.org/wiki/Kolmogorov%27s_inequality for Chebyshev like bounds. – A.S. Feb 2 '16 at 23:42
• @A.S. Thanks. I know the classical inequalities (Kolmogorov, Doob when it's a martingale, Azuma, Hoeffding, etc.) but I was really interested for equality. How do you prove the case 1. ? – Basj Feb 2 '16 at 23:45
• Azuma and Hoeffding don't address running maximum. 1&2 follow immediately from reflection principle and could be adapted (approximately asymptotically) to $X_n$ that aren't too spread out. – A.S. Feb 2 '16 at 23:51

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^+$.

• You seem to be computing $E(e^{-\lambda S_n}\mathbf 1_{S_n>0})$ instead of $E(e^{-\lambda S_n^+})$. The correction to be made is easy. – Did Feb 5 '16 at 12:24
• @Did, thanks, you're right. Is it ok now? – zhoraster Feb 5 '16 at 13:31
• Seems very much so. +1 from me. – Did Feb 5 '16 at 15:08

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.

• How do you know any of those densities exist? – user198044 Feb 3 '16 at 1:53
• @JackBauer: What do you mean by whether those densities exist? Density is just a positive function integrating to $1$. – Hans Feb 4 '16 at 1:22
• If the joint distribution of $X_1$ and $X_2$ is absolutely continuous with respect to $2$-dimensional Lebesgue measure, then it's not hard to prove that the distribution of $\max(X_1, X_1 + X_2)$ is absolutely continuous. Thus it has a density in the $L^1$ sense, which is almost everywhere the derivative of the CDF. There may be a set of measure $0$ where the CDF is not differentiable. – Robert Israel Feb 4 '16 at 1:50
• @Hans Not all continuous random variables have densities, no? books.google.com.ph/… – user198044 Feb 4 '16 at 3:54
• There are singular continuous random distributions, where the mass is concentrated on a set of Lebesgue measure $0$ (such as a Cantor set), although every single points still have measure $0$. That's not what's happening here. – Robert Israel Feb 4 '16 at 4:10

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$.

• This is wrong as the probability p in your first formula should be an indicator (i.e. a random variable) and not a constant. Furthermore we should expect the process $S_n$ to have an increase in expected value. Indeed the process is increasing, therefore if it has constant mean the process will be constant. – Kolmo Feb 4 '16 at 17:04
• @Kolmo Yes, you are right. – Jimmy R. Feb 4 '16 at 17:43
• @JimmyR. The first comment (on the question) by A.S. shows that we have explicitely $P(M_n≥t)=P(S_n≥t)+P(S_n≥t +1)$ so we do have a closed form expression for the distribution of $M_n$ ? – Basj Feb 5 '16 at 7:56
• Indeed the distributional identity is $$M_{n+1}\stackrel{d}{=}X+(M_n)^+,\qquad M_0=0,$$ where $X$ is distributed like every $X_i$ and independent of $M_n$. No explicit general solution can be expected but queuing theory textbooks are full of studies of this model. – Did Feb 5 '16 at 7:58
• @Did don't you think A.S.'s comment (ie a closed form expression for $P(M_n \geq t) = ...$ gives the answer? I'm currently trying to study this. – Basj Feb 5 '16 at 8:00

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: $$\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)$$ 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}

• Thanks Przemo! As I posted the question 1 year ago, I don't have these notations fresh in my mind, can you add details about the notations (what is $\rho_X$, $F_<(x)$). Thanks! – Basj Mar 1 '17 at 23:03