2D random walk - first hits

123 Views Asked by At

A 2D symmetric random walk $(X_k,Y_k)$ $k\ge 0$ (Markov chain) where $(X_{k+1},Y_{k+1})$ takes one value of the next ones: $(X_k,Y_k+1),(X_k,Y_k-1),(X_k+1,Y_k),(X_k-1,Y_k)$, all have the same probability and the initial values of X and Y are zero.

a) Find the value of $P(X_T=3,Y_T=0)$ and $E[T]$ if $T=inf(k\ge 0:\left| X_k \right|+\left| Y_k \right|=3)$

b) Find the value of $P(X_T=-2,Y_T=0)$ and $E[T]$ if $T=inf(k\ge 0:max(-X_k,\left| Y_k \right|=2))$

Any help is greatly appreciated!

1

There are 1 best solutions below

2
On

I am not sure my answer for part a) is right, just for your reference.

a) First, it is important to observe that the point $(X_{T-2}, Y_{T-2})$ must be one of the four: \begin{align} (1,0),\,(-1,0),\,(0,1),\,(0,-1).\tag{1} \end{align} Now, if $(X_T, Y_T)=(3,0)$, then $(X_{T-2}, Y_{T-2})=(1,0)$. Consider (1), and by symmetry, \begin{align} P((X_{t-2}, Y_{T-2})=(1,0))=\frac{1}{4}. \end{align} On the other hand, if we start the random walk at $(X_{T-2}, Y_{T-2})=(1,0)$, then the point $(X_T,Y_T)$ must be one of the following five: \begin{align} \begin{array}{ll} (1,2)&\mbox{with $1$ path},\\ (2,1)&\mbox{with $2$ paths},\\ (3,0)&\mbox{with $\color{red}{1}$ path},\\ (2,-1)&\mbox{with $2$ paths},\\ (1,-2)&\mbox{with $1$ path}. \end{array}\tag{2} \end{align} Since each path has equal probability, we get that \begin{align} P(X_T=3, Y_T=0)=P((X_{t-2}, Y_{T-2})=(1,0))\cdot\frac{\color{red}{1}}{1+2+1+2+1}=\frac{1}{28}. \end{align}

To calculate $E[T]$, we omit the detail, just note that $T\ge 3$, $T$ must be odd, and moreover, $(X_3,Y_3), (X_5,Y_5),\ldots,(X_{T-2},Y_{T-2})$ are one of the following four: \begin{align} (1,0),\,(-1,0),\,(0,1),\,(0,-1).\tag{3} \end{align} From the above observations, we may obtain \begin{align} P(T=3)&=\frac{28}{4^3}=\frac{7}{16},\\ P(T=5)&=\frac{9}{16}\cdot\frac{7}{16},\\ P(T=7)&=\left(\frac{9}{16}\right)^2\cdot\frac{7}{16},\\ &\vdots \end{align} and therefore, \begin{align} E[T]&=\sum_{n=3,5,7,\ldots} nP(T=n)\\ &=\frac{7}{16}\left(3+5\cdot\frac{9}{16}+7\cdot\left(\frac{9}{16}\right)^2+\cdots\right)\\ &=\frac{39}{7}. \end{align}