Expected time to absorption - Random Walk

322 Views Asked by At

I am trying to solve part (b).(i) of the attached question. Note that there is a typo and the equations should read

$$k_2 = 1 + \frac{1}{2}k_1 + \frac{1}{2}k_3$$ $$k_3 = 1 + \frac{1}{2}k_2 + \frac{1}{2}k_4$$

enter image description here

I tried writing down the expectation from its definition:

$$k_2 = 0 * P(0 | X_0 = 2) + 1 * P(1 | X_0 = 2) + 2 * P(2 | X_0 = 2) + ...$$ $$=$$ $$k_2 = 0 + 1 * \frac{1}{2} + 2 * (\frac{1}{2})^2 + ...$$

Which didn't lead to the answer, but I was able to deduce that $$k_2 = k_3$$ I also observed that if you start from state 2 you'll only go to state 1 in odd number of steps and to state 4 in even number of steps. Intuitively, I understand the result. You'll have to step once, to get to state 1 or state 3 (from state 2), but it seems as if the expectation is broken down into 2 disjoint sets (like the probability in part (a)) and I don't seem to follow that.

2

There are 2 best solutions below

0
On

$k_i$ is the expected number of (future) steps to absorption, given that you are now in state $i$. In general, $$k_i=1+\sum_jp_{ij}k_j\tag1$$

We have to take $1$ step, and if we end up in state $j$, we'll have to take an addition $k_j$ steps on average. Another way of looking at it is that if we transition to state $j$ we'll need to take $1+k_j$ steps on average, including the transition step. This gives $$k_i=\sum_jp_{ij}(1+k_j)$$ which immediately reduces to $(1).$

0
On

We are to compute the expected number of steps to reach our goal (get absorbed) that is why in the equations, we are adding $1$ each time we move from one state to another.

A recent question involving moving from one floor to another here on this forum may help you cement the concept.