# Please give me a more thorough explanation: Computing the first return time for a Markov Chain

This is not a wikipedia question, because I cannot find it there. How does one compute the first return time of a time-homogeneous Markov chain. There are a lot of neat notions such as recurrence and expected return time, but I am not sure how one can calculate the first return time.

For simple example, if we have $p_{11} =1/3$, $p_{12}=2/3$, $p_{22}=1/6$ and $p_{21}=5/6$, then what is the first return time to state 1?

-
It looks like you have "$p_11$" where you want $p_{11}$. If so, write "p_{11} instead of "p_11". –  Quinn Culver Jan 26 '12 at 11:52
@Brian You have two different values for $p_{12}$. –  Byron Schmuland Jan 26 '12 at 12:46
@Bryon / Brian: corrected so $p_{22}+p_{21}=1$ –  Henry Jan 26 '12 at 12:50
The first return time is a random variable. In what sense do you want to "calculate" it? –  Nate Eldredge Jan 26 '12 at 13:06
expectation of the random variable i mean –  Brian Jan 26 '12 at 13:28

The expected time to return to a given state $i$ is $1/\pi(i)$, where $\pi$ is the invariant probability vector. In your problem, the transition matrix is $P=\pmatrix{1/3&2/3\cr 5/6&1/6}$ and the invariant probabilities are the solution to $\pi =\pi P$. This works out to $\pi=(5/9,4/9)$, so the answer is $9/5$.

-

Personally, I think there is ambiguity in the term "first return time," from a natural language point of view. We can look at the first time (after 0) that we are in our starting state, we can look at the first time after we leave the starting state that we are back in the starting state, or we can look at the first time after we leave that we are back at the starting state but we don't start the clock until after we leave the starting state. In your class, you've picked one of these three perspectives, but it's worth looking at all 3. Note that if $p_{ii}=0$, then the first return to state $i$ is necessarily the same in all three cases, and so this ambiguity doesn't always exist.

Consider the following sequence of states: $1;1,1,1,2,2,2,1.$ We are starting at $1$ (and we will call our starting time $0$). The first time after time zero we are back at $1$ is time $1$. The first time we are back at $1$ after actually having left the initial state is time $7$. However, once we finally left $1$ it only took $4$ steps before we returned. What should the first return time be in this case?

Instead of looking at first return time, it is easier to look at the more general first hitting time. Suppose we have a finite Markov chain with a collection of states $S$, and we want to know the expected amount of time before we hit some collection of absorbing state(s), $A$. Let $p_{ij}$ be the probability that we go from state $i$ to state $j$, and let $h_i$ be the expected amount of time it takes to go from state $i$ to some state in $A$.

If $i\in A$, we have $h_i=0$. Otherwise, from state $i$, we take one time period to travel to a new state, at which point we can re-evaluate the amount of time it will take us to hit $A$. Thus, we have that

$$h_i=1+\sum p_{ij} h_j.$$

This gives us a system of linear equations to solve, and we have reduced the problem to linear algebra. Once we have $h_j$, if we have an initial distribution $\pi$, then our first hitting time is $\sum h_i \pi_i$.

For first return time, we are just calculating the first hitting time for a state $i$, starting from state $i$, but assuming that we at least try to move first. If you allow moving from state $i$ back to state $i$ on your first move to count as a return, this means that the formula for expected time till first return is $$1+\sum_j p_{ij}h_j.$$

If we don't want to count a stationary move as a first return, then we have two options. Either we can ask for (a) the first return time conditional on the first move not being a self return, which is the expected amount of time to return when the clock starts only after leaving, or (b) expected first return time where a return means leaving and then coming back.

We can calculate both (a) and (b) in terms of the $h_i$. For (1), it is easy to determine that the formula is

$$1+\frac{1}{1-p_{ii}}\sum_{j\neq i}p_{ij}h_j$$

because $\frac{p_{ij}}{1-p_{ii}}$ is the probability of moving from state $i$ to state $j$ conditional on not going from state $i$ back to state $i$.

For (b), if we let $r$ be the expected time to return, then we have

$$r=1+p_{ii}r+\sum_{j\neq i} p_{ij}h_j$$

because after one move, either we are back where we started and expect to have to wait $r$, or we have moved to state $j$ and expect to have to wait $h_j$.

Perhaps the best way to view the difference between our original approach and our alternatives (a) and (b) is by modifying our Markov chain by adding one new state $i'$. We want to think of $i'$ being a clone of $i$ which cannot be reached from any outside state. There are three reasonable ways to do the cloning.

• Set $p_{i'j}=p_{ij}$ for all $j$, and $p_{i'i'}=0$.
• Set $p_{i'j}=\frac{p_{ij}}{1-p_{ii}}$ if $i\neq j$, and $p_{i'i}=p_{ii}=0$.
• Set $p_{i'j}=p_{ij}$ for $i\neq j$, but set $p_{i'i'}=p_{ii}$ and $p_{i'i}=0$.

Our three cases are then just the expected first hitting time starting from $i'$ and ending in $i$.

-

The expected time to travel from $2$ to $1$ is $6/5$ so the expected time starting from $1$ to the next appearance at $1$ is $$\frac{1}{3} \times 1 + \frac{2}{3} \times \left(1 + \frac{6}{5}\right) = \frac{9}{5} =1.8$$

-
I dont understand at all. please explain more thoroughly...I dont understand the +2/3 (1+6/5) term –  Brian Jan 26 '12 at 13:02
There is a probabilit $1/3$ that you are at $1$ at time $t=0$ and also at $1$ at time $t=1$, so so your first return happens in one step. If you do not regard that as a first return then the answer would be $3/2 + 6/5$ as the expected time to go from $1$ to $2$ and then return. –  Henry Jan 26 '12 at 13:09
But where are we using the Markov property? –  Brian Jan 26 '12 at 13:12
How did u calculate the expectation for going form 2 to 1 –  Brian Jan 26 '12 at 13:33