Markov Chain and Random Walks

243 Views Asked by At

I am having difficulty understanding the question here. It says that $\{X_n\mid n=0,1,2,...\}$ is a simple random walk on the integers $S=\{\dots,-2,1,0,1,2,\dots\}$,starting at $X_0=3$. The probabilities of jumping left and right are $1/2$.

Let $T=\min{n\mid X_n=-3\text{ or }Xn=7}$.

(a) Find $E[X(T-2)]$.

(b) Find $E[X(T+2)]$.

I was wondering if I should put $T=4$ here since the minimum no of transitions to reach $-3$ or $7$ from $3$ is $4$. But then it would be straightforward as $E[X(2)]$ and $E[X(4)]$ which I believe should be $3$ in both cases. I think I am missing something [I was thinking whether I should try $\sum_xP(X>x)$]. Any help here would be appreciated.

1

There are 1 best solutions below

0
On

It is a very nice exercise to show that $\mathbb P(X_T=7)=\frac{3}{5}$ and $\mathbb P(X_T=-3)=\frac{2}{5}$. As a hint:

Let $h_n$ be the probability of hitting $7$ before $-3$ when you start out at $X_0=n$, and set up a system for $h_n$, which you can solve with the boundary conditions $h_7=1$ and $h_{-3}=0$.

As a consequence, we have $$\mathbb E[X_T]=\frac{3}{5}\times7+\frac{2}{5}\times(-3)=3.$$ Now note that if $S_1, S_2$ are the two steps you take after $X_T$, then $$\mathbb E[X_{T+2}]=\mathbb E[X_T+S_1+S_2]=\mathbb E[X_T]+\mathbb E[S_1]+\mathbb E[S_2]=\mathbb E[X_T]+0+0=\mathbb E[X_T]=3.$$ The case for $T-2$ is a bit trickier -- we can't immediately apply a similar argument as above, because, conditional on the fact that we hit $-3$ or $7$ two steps later, the increments may no longer distributed uniformly over $\pm1$.

We do have the following work around though. Note that $X_{T-2}$ is either $-1$ or $5$. Further, $X_{T-2}=-1$ iff $X_T=-3$ and $X_{T-2}=5$ iff $X_T=7$. So $$\mathbb E[X_{T-2}]=\frac35\times5+\frac25\times(-1)=2.6.$$


What's going on under the hood here is that the simple random walk $X_n$ is an example of what is called a martingale, that is $X_n$ has the property $$\mathbb E[X_{n+1}\mid X_n,\dots,X_1]=X_n.$$ For the random walk, this is obvious -- at each step, we are equally likely to move one space left or right. Martingales also have the property that $$\mathbb E[X_n]=\mathbb E[X_{n-1}]=\dots=\mathbb E[X_0],$$ which again is especially obvious in the case of a simple random walk. For general martingales, you can prove this via the law of total expectation.

In general, if $\tau$ is a stopping time, and $M_n$ is a martingale, then the optional stopping theorem tells us that, so long as $\tau$ and $M_n$ satisfy some certain "finiteness" properties, then it is in fact true that $\mathbb E[M_\tau]=\mathbb E[M_0]$. This applies in the case of the simple random walk $X_n$ and our stopping time $T$, so we instantly know that $\mathbb E[X_T]=\mathbb E[X_0]$.

The fact that $\mathbb E[X_{T-2}]\neq\mathbb E[X_0]$ is because, as noted in the comments, $T-2$ is not a valid stopping time.