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
$
\begin{eqnarray*}
F_{M_n}(m)&=&P(M_n<m)\\
&=&P(\max\{S_{n},S_{n-1},…,S_1\}<m)\\
&=&P(S_{n}<m,S_{n-1}<m,…,S_1<m)\\
&=&\int\limits_{-\infty}^m … \int\limits_{-\infty}^m f_{S_n,S_{n-1},…,S_1}(s_n,s_{n-1},…,s_1)\mathrm ds_n \mathrm ds_{n-1} … \mathrm ds_1 \\
&=&\int\limits_{-\infty}^m … \int\limits_{-\infty}^m
f_{S_n \mid S_{n-1},…,S_1}(s_n \mid s_{n-1},…,s_1)…
f_{S_2 \mid S_1}(s_2 \mid s_1)f_{S_1}(s_1)
\mathrm ds_n \mathrm ds_{n-1} … \mathrm ds_1 \\
&=&\int\limits_{-\infty}^m … \int\limits_{-\infty}^m
f_{S_n \mid S_{n-1}}(s_n \mid s_{n-1})…
f_{S_2 \mid S_1}(s_2 \mid s_1)f_{S_1}(s_1)
\mathrm ds_n \mathrm ds_{n-1} … \mathrm ds_1 \\
&=&\int\limits_{-\infty}^m … \int\limits_{-\infty}^m
f_X(s_n – s_{n-1})…
f_X(s_2 – s_1)f_X(s_1)
\mathrm ds_n \mathrm ds_{n-1} … \mathrm ds_1 \\
&=& \prod_{i=1}^n \int\limits_{-\infty}^m f_X(s_i – s_{i-1}) \mathrm ds_i
\end{eqnarray*}
$$
where $s_0 \equiv 0$. I hope the above notation is clear enough. Now
$$
\begin{eqnarray*}
F_{M_n}(m) = \mathbb E[\mathbb I_{ M_n \leq m}] = \prod_{i=1}^n \int\limits_{-\infty}^{-\infty} f_X(s_i – s_{i-1}) \mathbb I_{s_i \leq m} \mathrm ds_i.
\end{eqnarray*}
$$
The characteristic function $\varphi_{M_n}(t) = \mathbb E[\mathbb e^{i t M_n}]$ is then
$$
\begin{eqnarray*}
\varphi_{M_n}(t) = \prod_{i=1}^n \int\limits_{-\infty}^{-\infty} f_X(s_i – s_{i-1}) \mathbb e^{i t s_i} \mathrm ds_i
\end{eqnarray*}
$$
Best Answer
The step where you assert that $$ \mathrm P(S_n<m\mid M_{n-1}<m)=\mathrm P(S_n<m\mid S_{n-1}<m) $$ because $(S_n)_{n\ge0}$ is a Markov chain, is a beautiful example of the subtle errors one can make when using the Markov property.
To see that this equality is false in general, consider an inhomogenous random walk $(S_n)$, exactly like in your post. Fix a time $n\ge2$, and assume that $X_{n-1}=-1$ or $-2$ but that $X_k=\pm1$ or $0$ for every $0\le k\le n$ such that $k\ne n-1$.
Then, $X_{n-1}\le0$ almost surely hence $[M_{n-1}<1]=[M_{n-2}<1]$. And $X_{n-1}\le-1$ almost surely hence $[M_{n-2}<1]\subseteq[S_{n-2}<1]\subseteq[S_{n-1}<0]$. And $X_n\le1$ almost surely hence, conditionally on $[S_{n-1}<0]$, $S_n<1$ almost surely. This shows that $$ \mathrm P[S_n<1\mid M_{n-1}<1]=1. $$ On the other hand, $[S_{n-1}=0]$ has positive probability because $n\ge2$, and $[S_{n}=1]$ contains $[S_{n-1}=0]\cap[X_{n}=1]$, hence $$ \mathrm P[S_n<1\mid S_{n-1}<1]<1. $$ Added in note The key properties of the random walk in this counterexample are that $X_{n-1}\le-x$ and $X_n\le x$ almost surely, for a given positive $x$, and that both events $[S_{n-1}=0]$ and $[X_n\ge1]$ have positive probability.