9 room probability and expected value

Solution 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.