9 room probability and expected value

Question

I got the following question:

In a house with 9 rooms. There is 1 mouse that is looking for some food. This can be found in 2 rooms, but there are also 2 cats, these are in different rooms. When the mouse enters a room with a cat, he will be eaten right away, but they are quite lazy and always stay in the same room. The mouse is very forgetful, so he immediately forgets that he has entered a room. And the probability to enter a room will always have the same probability of the time before.

The following picture shows how everything is arranged:

I have numbered the rooms to calculate the expected value.

A) What is the probability that the mouse takes one of the food before it is eaten by a cat?

B) What is the probability that the mouse eats both food before it is eaten by a cat?

C) What is the expected value? The expected value means in this case the total amount steps the mouse walks before he will be in the room with the cat.

A) $$ {1\over2} * {2\over3} = {1\over3}$$ B) $$ {1\over2} * {1\over3} = {1\over6}$$

My answer of A & B are not correct, because my teacher told me if I used this on my exam I will not get all the points. And I am really sure how to do it the right way.

I tried the following to calculate the expected value:

Define X= #Total steps of mouse

Pi(X=k) = Chance that X=k if you start in room i.

I know that if the mouse is in the room with the cat I will not walk anymore. So I gave the rooms with the cat 1.

$$ P1 = P5= 1 $$

$$ P4(X=k) = {1\over2}P5(X=k-1) + {1\over2}P3(X=k-1) $$ $$ P5(X=k) = {1\over4}P8(X=k-1) + {1\over4}P2(X=k-1) + {1\over4}P7(X=k-1) + {1\over4}P4(X=k-1) $$ $$ P2(X=k) = {1\over2}P1(X=k-1) + {1\over2}P3(X=k-1) $$ $$ P6(X=k) = {1\over2}P7(X=k-1) $$ $$ P7(X=k) = {1\over2}P6(X=k-1) + {1\over2}P3(X=k-1) $$ $$ P8(X=k) = {1\over2}P7(X=k-1) + {1\over2}P8(X=k-1) $$ $$ P9(X=k) = {1\over2}P8(X=k-1) $$

I'm not sure if this is correct and how to continue from here. I hope that someone could show me how to do this the correct way or give me some tips.

Answer 1

Your answers to (A) and (B) are numerically correct, but a lot of non-trivial justification is missing, which is why your teacher's grading would be fair.

Solution

First you must prove that the mouse will almost surely (with probability 1) get to an end room (with a cat or with food). To do so, the easiest way is to check that for the mouse not to do so, it will have to continually turn back to the centre room every time it gets to a side room (right next to the centre room). The probability of turning back is less than 1 and so the probability of continually turning back is 0.

Next you need to show that the symmetry makes getting to each end room equally likely. To do so, check that we can rotate any path to an end room to get an equally likely path that goes to any other end room we want. Only then can you conclude that the first end room reached by the mouse has food with probability $\frac{1}{2}$.

Whenever the mouse leaves the centre room, it must with probability 1 get to the centre room again, because it will continually turn away from the centre room with probability 0.

Thus after getting to a food room, the mouse will almost surely get back to the centre, and from there the first end room that the mouse gets to will have food with probability $\frac{1}{4}$ and a cat with probability $\frac{2}{4}$ and be empty (the first food room) with probability $\frac{1}{4}$. But since the mouse will almost surely return to the centre whenever it gets to the empty end room, the probability that it will never get to a non-empty end room is 0. Therefore you can now conclude that the first non-empty end room that the mouse gets to the second time will have food with probability $\frac{1}{3}$ and a cat with probability $\frac{2}{3}$.

This is the simplest complete justification of the answers to (A) and (B).

Now for (C) your definition of expected number of steps from a certain room is incongruent with assigning 1 for the cat rooms. It should be 0. Also, all your equations are wrong because from each room you take 1 step before you get to an adjacent room from which you know the expected number of subsequent steps. Each should thus have a "1+". I didn't check the other details, but you should try using your corrected equations and see if you get the same answer as I do. My method below takes advantage of the symmetry.

Note that both methods are only valid after you verify that the expected number of steps is finite, because $\infty$ will always satisfy the equations. To do so, let $v$ be the vector of the probabilities of being in the rooms, and let $s$ be the sum of its entries. Since the mouse will from any room get to a cat with non-zero probability after 4 steps, which can be taken to be at least $c$ for some $c > 0$ independent of room, because there are finitely many rooms. There is always a room with probability at least $\frac{s}{n}$, so after every 4 steps $s$ will decrease by at least $\frac{s}{n}c$. Therefore $s$ is bounded above by a geometric series with ratio $r = 1-\frac{c}{n} < 1$, and hence the expected number of steps is bounded above by $\sum_{k=0}^\infty r^k$ which is finite. (Note that this expectation is only under the condition that the mouse does reach the cat, which is almost sure but not absolutely certain. There is a possibility with probability 0 that the mouse takes $\infty$ steps without reaching any cat, so we cannot count that in unless we adopt $0 \infty = 0$.)

Let $x,y,z$ be the expected number of steps to a cat from centre room, side room towards food, and side room towards cat, respectively. Then we get:

  $x = \frac{1}{2} (1+y) + \frac{1}{2} (1+z)$

  $y = \frac{1}{2} (1+x) + \frac{1}{2} (2+y)$

  $z = \frac{1}{2} (1+x) + \frac{1}{2} (1)$

Solving would give the answer, because $x,y,z$ are all finite.

Answer 2

Your answers to A and B are numerically correct, but what you are missing is justification.   In an exam you are required to explain why you do what you do, not just jot down magic numbers.

Something like: The mouse begins equidistant from two food and two cats, so it is equally probable that it will random walk to any particular one of these four rooms before any other.   The room with each food is also equidistant from the two cats and the one other food, so the same reasoning would apply again.   Let $F$ be the number of food taken before meeting a cat, so then:

$$\mathsf P(F=0) = \tfrac 2 4 \\ \mathsf P(F=1) = \tfrac 2 4\tfrac 2 3 = \tfrac 1 3\\\mathsf P(F=2) = \tfrac 2 4\tfrac 1 3 = \tfrac 1 6$$

---

For part $C$: Let $e_k$ be the expected number of steps until cat starting from room k.

Except for the rooms with cats, this will be $1$ plus the sum of the product of expected number of steps in each adjacent room and the probability of entering that room.   This gives nine simultaneous linear equations in nine unknowns.   Solve them to find $e_3$.

$$\begin{align} e_1 & = 0 \\ e_2 & = 1+ \tfrac 1 2(e_1+e_3) \\ e_3 & = 1 + \tfrac 1 4(e_2+e_4+e_7+e_8) \\ e_4 & = 1 +\tfrac 1 2(e_3+e_5) \\ e_5 & = 0 \\ e_6 & = 1 + e_7 \\ e_7 & = 1 + \tfrac 12(e_6+e_3) \\ e_8 & = 1 + \tfrac 12(e_3+e_9) \\ e_9 & = 1 + e_8 \end{align}$$

---

You can, of course, simplifying it by noting that it does not matter which cat the mouse meets, or whether or not their is food in the room. The arrangement of rooms is symmetric: so $e_6=e_9, e_7=e_8, e_1=e_5=0, e_2=e_4$

$$\begin{align} e_2 & = 1+ \tfrac 1 2(e_3) \\ e_3 & = 1 + \tfrac 1 2(e_2+e_8) \\ e_8 & = 1 + \tfrac 12(e_3+e_9) \\ e_9 & = 1 + e_8 \end{align} $$