[Math] Cat / mouse probability question

probability

There exist 7 doors numbered in order from 1 to 7 (going from left to right). A mouse is initially placed at center door 4. The mouse can only move 1 door at a time to either adjacent door and does so, but is twice as likely to move to a lower numbered door than to a higher numbered door each time it moves 1 door. There are cats waiting at doors 1 and 7 that will eat the mouse immediately after the mouse moves to either of those 2 doors.

So for example, the mouse starts at door 4. He could then move to door 3, then to door 2, then back to 3, then back to 2, then to door 1 where he gets eaten. That counts as 5 moves total. Skipping doors is not allowed.

So there are 2 questions I have regarding this:

1) What is the expected average number of moves before the mouse gets eaten? (do not count the initial start at door 4 as a move but count any final move to doors 1 or 7 and any "intermediate" moves between those 2 states).

2) What is the probability that the mouse will survive for 100 or more moves?

Best Answer

I'll renumber the doors $0$ to $6$ to simplify the calculations.

For the first question, we can set up a recurrence for the expected number $a_n$ of moves the mouse will make starting at door $n$:

$$ a_n=1+(1-p)a_{n-1}+pa_{n+1}\;, $$

with $p=\frac13$. A particular solution of the inhomogeneous equation is $a_n=3n$, and the homogeneous equation can be solved using the ansatz $a_n=\lambda^n$, leading to the charateristic equation

$$ p\lambda^2-\lambda+1-p=0 $$

with solutions $\lambda=1$ and $\lambda=\frac1p-1=2$. Altogether,

$$ a_n=c_1+c_22^n+3n\;. $$

The boundary values are $a_0=a_6=0$, which yields

\begin{eqnarray*} c_1+c_2&=&0\;,\\ c_1+64c_2+18&=&0\;, \end{eqnarray*}

with solution $c_1=-c_2=\frac27$. Thus the life expectancy in the middle is

$$ a_3=\frac27-\frac27\cdot2^3+3\cdot3=7\;. $$

For the second question, you can group the $100$ steps into $50$ pairs, reducing the process to doors $1$, $3$ and $5$. The transition matrix for each pair of steps is

$$ \frac19\pmatrix{2&4&0\\1&4&4\\0&1&2}\;, $$

which conveniently happens to have a nice eigensystem. The initial state decomposes as

$$ \pmatrix{0\\1\\0}=\frac16\left(\pmatrix{4\\4\\1}-\pmatrix{4\\-2\\1}\right)\;, $$

where the first vector is an eigenvector with eigenvalue $\frac23$ and the second vector is an eigenvector with eigenvalue $0$. Thus after $50$ pairs of steps the distribution on doors $1$, $3$ and $5$ is

$$ \frac16\left(\frac23\right)^{50}\pmatrix{4\\4\\1}\;, $$

and the sum of these probabilities is

$$ \left(\frac23\right)^{49}\approx2.4\cdot10^{-9}\;, $$

so your guess had the right order of magnitude.

We can also use this eigenanalysis to derive the life expectancy another way. After the first pair of steps, the distribution is

$$ \frac19\pmatrix{4\\4\\1}\;. $$

From then on, the mouse gets eaten with probability $\frac13$ in each pair of steps, so the expected number of pairs after the first one is $3$. Since death occurs on the first step of a pair, that translates to $7$ steps.