What is the state space of this markov chain?

Question

Consider a system where two persons sit at a table and share three books. At any point in time both are reading a book, and one book is left on the table. When a person finishes reading his/her current book, he/she swaps it with the book on the table and starts reading. Reading times are exponentially distributed, denote by bi,j the average time for person i to read book j.

Let b = [1 2 4]
        [5 1 2]

What is the state space of this markov chain and how can i construct the rate matrix Q ?

I got this exercise from my lecture notes and somehow find the state space confusing since it is a continuous time markov chain.

These are the possible states i could think of :

Person i1 and i2, Book A,B,C

i1,A
i1,B
i1,C
i2,A
i2,B
i2,C

But how can i represent this graphically ? I tried but each user has a separate markov chain(reducible) which i doubt is correct. I think from there constructing the rate matrix based on the rates on matrix b should be ok.

Answer 1

This is one of those questions which probably fit better on http://stats.stackexchange.com, even if you plan to write a code to solve this problem. One of the reasons is that there you have an easily usable math mode whereas on SO you don't. But anyways, I'll give an answer here.

When you want to construct your Markov Chain, it doesn't matter whether it is a continuous-time or a discrete chain, as these are based on the same concept and are related by a formally simple transition (just as the difference quotient becomes the derivative when the length becomes infinitesimal). Rather it matters that you correctly get the information content of the state. So, one needs to evaluate what is required here in order to make a transition.

For this, the state variable you proposed is not enough: it contains only a single reader and it lacks the time. Obviously, you need both readers plus their books in the state variable. But also the time when they started is needed, otherwise you would not know when they finish the book.

So, one ends up with a state variable

S = ({book_reader_1, start_time_1}, {book_reader_2, start_time_2})

The transition function can then be evaluated by integrating the exponential distribution from the start_time to the current time t, which gives the probability that the reader has finished at time t. You need to do that for both readers, but you can do it separately as they do not influence their reading times.