# 9 room probability and expected value

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.

## 2 Answers

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.

• @maffh: You're welcome. Note that merely invoking symmetry as in Graham's answer is totally incorrect in certain cases. For an explicit example, consider an infinite tree where each node at level $k$ (the root being at level $1$) has $(k^2-1)$ children. Then a random walk from the root that always takes a random edge from each node will go downwards perpetually with probability $\frac{1}{2}$, and thus never return to the root with probability greater than $\frac{1}{2}$, despite having a positive probability of doing so from every node! Note that it fails the "finitely many states" used above. – user21820 May 24 '15 at 7:05
• @maffh: But if you have only finitely many possible states and there is some $k$ such that taking $k$ steps from each of them has a non-zero probability of reaching a final state, then a final state will be eventually reached with probability 1, and with a finite expected number of steps, and hence the method will give the correct answer. I just want to make clear that the justification is non-trivial. – user21820 May 24 '15 at 7:10
• Why would it not be correct to simply say: The "game" (scenario) continues until either a cat or food is reached; the board has rotational symmetry, therefore $P(A)=\frac 1 2$. For B, the game will still continue until the mouse progresses from the center square to a non-empty edge square, each of which is again symmetrical (the empty square eventually returning the mouse to the center by necessity), so $P(B)=\frac 1 2 \times \frac 1 3=\frac 1 6$. Non-trivial, but quite concise. – Wildcard Jan 12 '17 at 5:14
• @Wildcard: Hmm your answer has the same large hole as the attempt in the question, which my first paragraph addresses. Also, your first line is based on intuition and is true but justification would need to proceed along the lines of my second paragraph. Your second line is again based on intuition and the rigorous explanation is in my third and fourth paragraph. The remainder of my answer is for part (C), though of course one can prove the obvious generalization first, which can then be applied to every discrete Markov process with finite state space. – user21820 Jan 12 '17 at 6:31
• My first comment also gives an example where symmetry alone will not be enough to get the answer. For instance if the mouse starts at the root and at level $2$ there is a cat at one of the nodes and food at another. Then the probability that the mouse reaches the food while avoiding the cat is not $\frac12$, even though there is nonzero probability of reaching the food from any node. – user21820 Jan 12 '17 at 6:53

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}

• Your explanations are not really justified either, because of the issues I mentioned in my answer. – user21820 May 22 '15 at 3:34