Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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}. $$

share|cite|improve this answer
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$:enter image description here

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:
    enter image description here 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}$$
share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.