# Random walk and its expectation

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.

-
Is $q=1-p$? If not, what are the other possibilities for $X_i$? – Ross Millikan Aug 6 '12 at 4:55
@RossMillikan Yes, q=1-p – user30795 Aug 6 '12 at 7:11

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

-
Oh, I haven't studied the strong or weak Markov property yet and I don't know what is the hitting time. So, I mean, uh, I can't understand it. – user30795 Aug 7 '12 at 2:31
Oh, you might have mentioned what you know and what you do not know in the context of this question, especially the extraordinary fact that you ask nontrivial questions about random walks without knowing what the Markov property or a hitting time are. So, I mean, uh, too bad. – Did Aug 7 '12 at 7:12

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}$$
-
Sum $\neq$ sup. – Did Aug 6 '12 at 17:49
@did Thanks, that is a typo. I meant to say $\sup$. – Sasha Aug 6 '12 at 17:52
Then $S^*\geqslant0$ almost surely since $S^*$ is a supremum over $k\geqslant0$ (and not over $k\geqslant1$ as, seemingly, in your computations). – Did Aug 6 '12 at 17:59
@did Yes, indeed! I was using $1 \leqslant k \leqslant n$. The results are neat, I found. I will try to repeat them with $0 \leqslant k \leqslant n$ to see if similar recurrence relation holds for the expectations. – Sasha Aug 6 '12 at 18:01
@did I have redone the computations with $0 \leqslant k \leqslant n$. – Sasha Aug 6 '12 at 18:30