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$?
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$– LuciaCommented 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$– James MartinCommented Oct 25, 2015 at 0:06
-
3$\begingroup$ Crossposted from math.stackexchange.com/questions/1493006/… $\endgroup$– user6096Commented Oct 25, 2015 at 14:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
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.
