3
$\begingroup$

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.

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.

  • 0
    @RossMillikan Yes, q=1-$p$2012-08-06

2 Answers 2

3

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

  • 0
    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.2012-08-07
1

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}$
  • 0
    Yep. I saw that.2012-08-12