An exercise about Markov Chains

Lately  I have stopped reading “Probability and computing”, since I found some gaps in the exposition of the text, especially at chapter 7 “Markov Chains and Random Walks”-the authors left undefined some terminologies such as absorption. Certainly this is not the text for anybody who has little background of probability and want to learn it rigorously (though it is a good introductory text for randomized algorithm). So I bought “Markov Chains” of James Norris.
Exercises in “Markov Chains” are easy (at least for the first chapter ), though there are some problems that I am not quite sure. Here is one of them:

A particle moves on the eight vertices of a cube in the following way: at each step the particle is equally likely to move to each of the three adjacent vertices, independently of it past motion. Let i be the initial vertex occupied by the particle, o the vertex oppostite i. Calculate each of the following quantities:
(i)
the expected number of steps until the particle returns to i;
(ii) the expected number of visits to o until the first return to i;
(iii) the expected number of steps until the first visit to o.

This exercise is placed under “Invariant distribution” section. My answer is (i) 8, (ii) 1, (iii) 16 (?). I did not use anything from this section to solve (iii) and the answer also is suspicious, at least counter-intuitive to me. So I would like to know if there is any connection between the expected number of steps until the first visit to o, E_{i}[T_{o}], and the invariant distribution \pi.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: