6
$\begingroup$

Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the left is $q = 1-p$. Let $S_n$ be such a random walk started at $0$ for some $p \in (0, {1\over2})$. Let $M = \max_{n \ge 0} S_n$. What is the distribution of $M$?

$\endgroup$
3
  • 3
    $\begingroup$ This must be well known, since someone voted to close it. But it wasn't well known to me. If $P(n)$ denotes the probability that the random walk gets to $n$, then clearly $P(0)=1$ and $P(n)$ must tend to zero as $n\to \infty$. Further for $n\ge 1$ we have the recurrence $P(n)=pP(n-1)+(1-p)P(n+1)$, by just seeing what the first move does. Solving the recurrence, one gets that $P(n)$ must be $(p/(1-p))^n$. Now the probability that the maximum is $M$ is just $P(M)-P(M+1)$. $\endgroup$
    – Lucia
    Oct 24, 2015 at 22:01
  • $\begingroup$ Bjørn, did you paste the wrong url? It doesn't seem to be a duplicate of that question. I don't have strong feelings about whether it belongs here or on math.stackexchange. Since it's here I felt like I might as well answer it. $\endgroup$ Oct 25, 2015 at 0:06
  • 3
    $\begingroup$ Crossposted from math.stackexchange.com/questions/1493006/… $\endgroup$
    – user6096
    Oct 25, 2015 at 14:49

2 Answers 2

9
$\begingroup$

As Lucia pointed out in a comment, by solving the hitting probability recursions for the Markov chain, you get that the distribution of the maximum is geometric; for $k=0,1,2,\dots$, $$ \mathbb{P}(M=k)=\left(\frac{p}{1-p}\right)^k\left(1-\frac{p}{1-p}\right), $$ or equivalently $$ \mathbb{P}(M\geq k)=\left(\frac{p}{1-p}\right)^k. $$

There's actually a simple intuition for why the answer must be geometric. The only way to reach site $k>0$ is by passing through sites $1,2,\dots,k-1$ on the way. So to hit $k$ starting from $0$, you first have to hit $1$ starting from $0$, then you have to hit $2$ starting from $1$, then $3$ starting from $2$, .... , and finally $k$ starting from $k-1$. Now use the Markov property (formally the strong Markov property) and the fact that the process is translation invariant (so that the probability of hitting $j+1$ starting from $j$ doesn't depend on $j$), to get that the probability of hitting $k$ from $0$ is just the $k$th power of the probability of hitting $1$ from $0$.

$\endgroup$
3
$\begingroup$

More generally, for any upward skip–free random walk on the integers (such that $P(X>1)=0$), the distribution of $M$ is geometric (when finite): $P(M=n)= (1-\theta) \cdot \theta^n$, where $\theta$ is the unique solution in $(0,1)$ of $1=E[\theta^{-X}]$.

The distribution of $M$ can also be calculated inductively for downward skip free random walk (such that $P(X<-1)=0$).

See e.g. Corollary 5.5 and Corollary 5.6 in Asmussen, S. (2003). Applied probability and queues, 2nd ed. New York: Springer, and http://people.bu.edu/pekoz/skipfree.pdf for other interesting information concerning skip free random walks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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