4

I'm having trouble deriving the return time for a Markov chain. The graph has $n$ vertices and is connected by $n - 1$ edges. So we can draw this as a horizontal line of nodes with node $1$ all the way to the left and node $n$ all the way to the right. At each intermediate node $i$ there is a $1/2$ probability that it moves to node $i - 1$ and a $1/2$ probability it moves to $i + 1$ and at node $1$ and $n$ there is a probability of $1$ that it moves to node $2$ and $n-1$ respectively.

I have to derive an equation for the expected return time that I return to node $1$ starting from node $1$.

I'm just having trouble starting so any hints toward the right direction will be very helpful.

Thanks!

Artem
  • 14,414
Ricky
  • 53

1 Answers1

3

Let $T = \min\{t \ge 0 : X_t = 1\}$ be the first time that you reach state 1, and let $h(i) = E_i T$ be the expected amount of time to reach state 1 when starting from state $i$. (As we've defined it, $h(1) = 0$; don't worry about this for now.)

By conditioning on $X_1$ (i.e. using the fact that $E_i T = \sum_j E_i[T \mid X_1 = j] P_i(X_1 = j)$) together with the Markov property, find a relationship between $h(i)$ and $h(i \pm 1)$. (Be careful to note the special cases when $i=1$ or $i=n$.) This will give you a system of $n$ linear equations which you can solve to find the $h(i)$.

Finally, when starting from state 1, the first step must be to state 2. So the expected return time is simply $h(2) + 1$.

Nate Eldredge
  • 97,710
  • Is there a way to do this by relating it to hitting time of node 1 and node 2 and using recurrent equations? We haven't actually learned about first step analysis and what we've been doing so far is using recurrent equations to solve these types of questions. Also I have a question about the last equation written. Is $P_{1}(X_{1} = n)$ equal to 0 because you can't go from state 1 to state n in one step or am I misunderstanding you? – Ricky Mar 16 '13 at 03:39
  • @Ricky: The "system of $n$ linear equations" I mentioned will be recurrent. You are right about $P_1(X_1 = n)$; I misread the statement of the problem. That simplifies the last step and I edited my answer accordingly. – Nate Eldredge Mar 16 '13 at 03:44
  • Thanks, I understand it now! – Ricky Mar 16 '13 at 03:47
  • Just to confirm, if n = 3, would h(3) = 1 + .5(h(3) + 1)? – Ricky Mar 16 '13 at 04:29
  • @Ricky: Yes, that's what I get also. – Nate Eldredge Mar 16 '13 at 05:45