Random walk and its expectation

Question

Let $S_n=X_1+X_2+...+X_n$, where $X_i=1$ with probability $p$ and $X_i=-1$ with probability $q=1-p$, for all $i$ and independently of each other. Assume that $S_0=0$ and $0<p<\frac{1}{2}$.

Show $$E\left(\sup\limits_{0\le k\le n}S_k\right) \le \frac{p}{q-p}$$

I would like to know how to prove it.

Answer 1

Let $S^*=\sup\limits_{n\geqslant0}S_n$.

• For every $i\geqslant0$, the strong Markov property at the first hitting time of $i\geqslant0$ yields $\mathrm P(S^*\geqslant i+1\,\mid\,S^*\geqslant i)=\mathrm P(S^*\geqslant 1)$ hence $\mathrm P(S^*\geqslant i)=r^i$ with $r=\mathrm P(S^*\geqslant 1)$.
• Let $s=\mathrm P(\text{hit $+1$ starting from $-1$})$ hence $s=\mathrm P(S^*\geqslant 2)=r^2$. The weak Markov property at time $1$ yields $r=p\cdot1+q\cdot s=p+q\cdot r^2$ hence $r=1$ or $r=p/q$.
• The random walk has a drift to $-\infty$ because $p\lt\frac12$, hence $r\lt1$, that is, $r=p/q$.

Thus, for every $n\geqslant0$, $$ \mathrm E\left(\sup\limits_{0\leqslant k\leqslant n}S_k\right)\leqslant\mathrm E(S^*)=\sum_{i=1}^{+\infty}\mathrm P(S^*\geqslant i)=\sum_{i=1}^{+\infty}r^i=\frac{r}{1-r}=\frac{p}{q-p}, $$ and, furthermore, $$ \lim\limits_{n\to\infty}\mathrm E\left(\sup\limits_{0\leqslant k\leqslant n}S_k\right)=\mathrm E(S^*)=\frac{p}{q-p}. $$

Answer 2

This post does not answer the OP's question, but provides certain experimental findings, which might be of interest to the OP, but which need to be established rigorously.

Representing each $X_i$ as an affine transform of the Bernoulli random variable, Mathematica can be summoned to evaluate the expectation for low values of $n$, here is the result for $0\leqslant n \leqslant 16$:

Few observations are in order:

• Expectations $\mathbb{E}\left(\sup\limits_{0 \leqslant k \leqslant n}S_k\right)$ appear to follow a pattern $\frac{p}{1-2p} + \mathcal{o}\left(p^{\lfloor n/2 \rfloor}\right)$, which is in agreement with the result of @did that $\mathbb{E}(S^\ast) = \frac{p}{1-2p}$.
• Expectations appear (as suggested by Mathematica's FindSequenceFunction) to be solutions of rank $3$ linear inhomogeneous recurrence equation:
  That is $(n+3) S_{n+3}^\ast - (n-4) S_{n+2}^\ast - 4 n p (1-p) S_{n+1}^\ast + 4(n+1) p(1-p) S^\ast_n = -p(1-2p)$
• The generating function for the sequence of expectations $S_n^\ast$, i.e. $$g(x) = \sum\limits_{n=0}^\infty x^{n} S_n^\ast = \frac{\sqrt{4 p^2 x^2-4 p x^2+1}+2 p x-1}{2 (1-x)^2}$$