# Distribution of maximum of partial sums of independent random variables

I have been looking all over the net to find a way to work out a probability distribution of a maximum of partial sums of independent random variables, but to no avail. So I have decided to try to work it out for myself. Here are the results of this endeavour and I would appreciate if people with better understanding of probability than me would give it a look over to see if I’ve made a mess of it somewhere. Many thanks. Here it goes.

Given a set $\{X_i:i=0,1,\ldots,n \}$ of independent random variables with $X_0 = 0$ and with given p.d.f.'s $f_{X_i}(x)$ and corresponding c.d.f's $F_{X_i}(x)$, define $S_k=\Sigma_{i=0}^k\,X_i$, and $M_k=\max\{S_0,S_1,\ldots,S_k \}$, and we want to find a distrinution of $M_n$. We have

$$\begin{eqnarray*} P(M_n<m)&=&P(\max\{M_{n-1},S_n\}<m)\\ &=&P(M_{n-1}<m,S_n<m)\\ &=&P(S_n<m|M_{n-1}<m)P(M_{n-1}<m),\\ \end{eqnarray*}$$

where

$$\begin{eqnarray*} P(S_n<m|M_{n-1}<m) &=&P(S_n<m|\max\{M_{n-2},S_{n-1}\}<m)\\ &=&P(S_n<m|S_{n-1}<m)\\ &=&P(S_n<m,S_{n-1}<m)/P(S_{n-1}<m), \end{eqnarray*}$$

where

$$\begin{eqnarray*} P(S_n<m,S_{n-1}<m) &=&P(S_{n-1}+X_n<m,S_{n-1}<m)\\ &=&\int\limits_{-\infty}^m f_{S_{n-1}}(s)\int\limits_{-\infty}^{m-s}f_{X_n}(x)\mathrm dx\,\mathrm ds\\ &=&\int\limits_{-\infty}^m f_{S_{n-1}}(s)F_{X_n}(m-s)\mathrm ds, \end{eqnarray*}$$

where

$$\begin{eqnarray*} f_{S_k}(s)&=&\int\limits_{-\infty}^{\infty} f_{X_k}(x)\,f_{S_{k-1}}(s-x)\mathrm dx, \end{eqnarray*}$$

with

$$\begin{eqnarray*} f_{S_0}(s)=\delta (s), \end{eqnarray*}$$

so that putting it all together gives a recursion formula

$$\begin{eqnarray*} F_{M_n}(m) = \frac{F_{M_{n-1}}(m)}{F_{S_{n-1}}(m)} \int\limits_{-\infty}^m f_{S_{n-1}}(s)F_{X_n}(m-s)\mathrm ds \end{eqnarray*}$$

with

$$\begin{eqnarray*} F_{M_0}(m) = H(m) \end{eqnarray*}$$

the Heaviside step function.

Added 1: Using another approach, I have obtained the following result $$f_{M_n}(m) = f_{M_{n-1}}(m)F_{X_n}(0) + \int\limits_0^m f_{X_n}(m-x)f_{M_{n-1}}(x)\mathrm dx$$

which for 2 normal r.v. seems to give a result that agrees with the one put forward in one of the answers by Sasha.

Added 2: Finally I got some free time to look at this problem again and here are my thought on it. Once again, I would appreciate any comments on it.

We begin by considering a joint distribution of $f_{S_1,S_2}(s_1,s_2)$ where $S_1 = X_1$, $S_2 = S_1 + X_2$, $X_1 \sim X_2 \sim X$, and $X_1$ and $X_2$ are independent. We have

$$f_{S_1,S_2}(s_1,s_2) = f_{S_2 \mid S_1}(s_2 \mid s_1)f_{S_1}(s_1) = f_{X_2}(s_2 - s_1)f_{X_1}(s_1) = f_{X}(s_2 - s_1)f_{X}(s_1)$$

Next, we have

-