Expected value of visits state in finite markov chain

markov chainsprobability

I have 4 states {human, dog, cat, floor). Flea can move between each state (always with same probability). In state human flea is dying (end game), in state {cat, dog} flea eats, and on floor flea is starving. Count expected values of meals{dog, cat}, starting from floor and before dying in human.

This is my transition matrix (3 states – Hungry, Meal, Dead)
$$ A = \left( \begin{matrix} 0 & \frac{2}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & 1 \end{matrix} \right) $$

I think about counting expected values of visit of state Meal (starting from Hungry and before die in Dead), but I don't have any idea, how to start

Best Answer

The answer is either $1.5$ or $2$, depending on the interpretation of the problem.

Let $e_f$ be the expected number of future meals if the flea is currently on the floor, $e_c$ the number of future meals if the flea is on the cat, and $e_d$ the number of future meals if it is on the dog. Clearly $e_c=e_d$.

Under the assumption that the flea always changes state, we have $$\begin{align} e_f&=\frac23(e_c+1)\\ e_c&=\frac13e_f+\frac13(e_d+1) \end{align}$$ Solving we get $e_c=\frac54,\ e_f=\frac32$.

Under the assumption that the flea may stay in the same state, we have $$\begin{align} e_f&=\frac14e_f+\frac12(e_c+1)\\ e_c&=\frac14+\frac12(e_c+1) \end{align}$$ and we get $e_c=e_f=2$

I've done two simulations, one for each case In the first case, and the results agree with these. In an earlier version of this post, I said that the simulation in the first case gave $1.7$, but there must have been some error in the code. I've rewritten it, and it gives $1.5$.

Here's my python script for the first simulation:

from random import random

floor, cat, dog, human = range(4)

def test(trials):
    meals  = 0
    for _ in range(trials):
        state = floor
        while state != human:
            r = random()
            if state == floor:
                if r <= 1/3:
                    state = cat
                elif r <= 2/3:
                    state = dog
                else:
                    state = human
            elif state == cat:
                if r <= 1/3:
                    state = floor
                elif r <= 2/3:
                    state = dog
                else:
                    state = human
            elif state == dog:
                if r <= 1/3:
                    state = floor
                elif r <=2/3:
                    state = cat
                else:
                    state = human
            if state in (cat,dog):
                meals += 1
    return meals/trials

Here's my python script for the second case:

from random import random

floor, cat, dog, human = range(4)

def test(trials):
    meals  = 0
    for _ in range(trials):
        state = floor
        while state != human:
            r = random()
            if state == floor:
                if r <= 1/4:
                    state = cat
                elif r <= 1/2:
                    state = dog
                elif r <= 3/4:
                    state = floor
                else:
                    state = human
            elif state == cat:
                if r <= 1/4:
                    state = floor
                elif r <= 1/2:
                    state = dog
                elif r <= 3/4:
                    state = cat
                else:
                    state = human
            elif state == dog:
                if r <= 1/4:
                    state = floor
                elif r <=1/2:
                    state = cat
                elif r <= 3/4:
                    state = dog
                else:
                    state = human
            if state in (cat,dog):
                meals += 1
    return meals/trials

Surely we should be able to state this in term of the transition matrix.

EDIT

I haven't had a chance to read it yet, but section 9.2 of these lecture notes addresses the question.

Related Question