# Markov Chain (Simple Random Walk) distribution

Let $\{X_n\}_{n = 0,1,\ldots}$ be the Markov Chain with state space $\mathbb{Z}$ and the transition probability

$P_{n,n+1} = p \qquad P_{n,n-1} = 1-p$

where $p \gt \frac{1}{2}$. Assume $X_0 = 0$

Let $Y = min\{X_0,X_1,\ldots\}$. What is the distribution of $Y$?

I can only get that for all $k \in \mathbb{Z}_{> 1}, P(Y=k) = 0$ since the chain is already in state $0$. And I think the meaning of event $Y = -k$ means that this chain have across state $-1,-2,\ldots,-k$ but never reach state $-k-1$. However I still cannot solve this problem, can some one help me? Thanks!

• – Guy Fsone Oct 7 '17 at 14:30
• @GuyFsone Sorry I cant see the relation between this two questions, could you give me more details? – user370220 Oct 7 '17 at 14:36
• are younot looking for the distribution of Y? – Guy Fsone Oct 7 '17 at 14:43

Let the chance for $\{X_n\}$ to ever reach a negative integer $-k\,$ from $\,0\,$ be $P_{-k}$. Then we have

$$P_{-1}=P_0\,(1-p)+P_0\,p\,P_{-1}^2.$$

Since $P_0=1$, because the particle was initially at $X_0=0$, we have

$$P_{-1}=\frac{1-p}{p}\mbox{ or }\,1.$$

For $\,p>1/2$, the random walk drifts to the positive side. So the chances to reach negative numbers are less than $1$. The random walk no longer returns to the origin infinitely often because of the drift. So we take the first root $P_{-1}=(1-p)/p$. Then the chance to reach $-k\,$ is

$$P_{-k}=(P_{-1})^k=\left(\frac{1-p}{p}\right)^k.$$

This is because to reach $-k$, the walker has to first reach $-1$, which happens with probability $P_{-1}$, and then it has to reach $-2\,$ from $-1$, which also happens with probability $P_{-1}$ independently of its history, and so on. Finally, notice that

$$\mathrm{Pr}(Y\equiv\mbox{minimum}\leq-k)=P_{-k}.$$

The expected value of the minimum $Y$ is given by

$$\langle Y\rangle=-\sum_{k=1}^\infty\,\mathrm{Pr}(Y\leq-k)=-\frac{1-p}{2p-1}.$$

• Hi I understood the first part but the support for Y is discrete. why Y has an exponential distribution？ – user370220 Oct 7 '17 at 18:04
• Oh, sorry. I meant geometric distribution (the discrete version). – Zhuoran He Oct 7 '17 at 18:06
• Oh thanks, but I still don't understand why $Pr(Y \le -k) = P_{-k}$ and why we can derive the distribution of $Y$ based on this probability? Could you involve more details? Thanks! – user370220 Oct 7 '17 at 18:12
• $\mathrm{Pr}(\mbox{minimum}\leq -k)=\mathrm{Pr}(\exists\,n, X_n=-k)$. So if it reaches $-k$, the minimum is $\leq-k$. – Zhuoran He Oct 7 '17 at 18:14
• Oh your explanation is great, and I think you also solved a problem I posted before: math.stackexchange.com/questions/2455249/… – vita nova Oct 7 '17 at 20:49