0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I don't get it. Number of steps could count Hungry state as well $\endgroup$ – cvzx Feb 23 at 12:21
  • $\begingroup$ starting from floor, flea has prob(2/3) to eat and 1/3 to die $\endgroup$ – cvzx Feb 23 at 12:54
  • $\begingroup$ from my calculation T is equal to 3 so 2/3(3-1) is equal to 4/3, but the answer in book is 4. $\endgroup$ – cvzx Feb 23 at 13:16
  • $\begingroup$ so maybe my matrix is wrong? $\endgroup$ – cvzx Feb 23 at 13:41
  • $\begingroup$ i was wandering the same, but i assumed that is not possible $\endgroup$ – cvzx Feb 23 at 14:25
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I have the same result in both cases, but this exercise has a second subtask(?), calculate the probability that flea dies hungry(without eating meal) and the answer in the book is 1/3. So i think that flea should always change state $\endgroup$ – cvzx Feb 23 at 14:38
  • $\begingroup$ @cvzx Yes, that would make sense. $\endgroup$ – saulspatz Feb 23 at 15:46
  • $\begingroup$ OK I found an answer on the internet that expected values of number of steps flea makes before death is 3, so the number of meals should be less than 3. So the answer in the book is not correct. $\endgroup$ – cvzx 2 days ago
  • $\begingroup$ If you look at the lecture notes I referred to at the end, you'll find that the answers you get by using its formula agree with the answers I've computed here. $\endgroup$ – saulspatz 2 days ago
  • $\begingroup$ Yeah, i got 3/2 as well $\endgroup$ – cvzx 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.