4
$\begingroup$

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!

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Commented Mar 16, 2013 at 3:39
  • $\begingroup$ @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. $\endgroup$ Commented Mar 16, 2013 at 3:44
  • $\begingroup$ Thanks, I understand it now! $\endgroup$ Commented Mar 16, 2013 at 3:47
  • $\begingroup$ Just to confirm, if n = 3, would h(3) = 1 + .5(h(3) + 1)? $\endgroup$ Commented Mar 16, 2013 at 4:29
  • $\begingroup$ @Ricky: Yes, that's what I get also. $\endgroup$ Commented Mar 16, 2013 at 5:45

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.