9
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ I do not know how to mathematically solve the 100+ move question either but I would guess it is extremely unlikely, but possible. The mouse would have to "tennis ball" between doors 2 and 6 (inclusive) for a long time before getting to doors 1 or 7. I'll take a guess and say 1 out of 1 billion that this will happen. $\endgroup$ Commented Sep 21, 2018 at 4:12
  • 3
    $\begingroup$ You may take a look at those markov chain / random walk / gambler ruins problem for a more generalized set up. For your particular problem it is possible to do with law of total probability and solving a recurrence relation. en.wikipedia.org/wiki/Absorbing_Markov_chain If you can understand those math behind, the wiki site has provided you the tools to analysis the problem. $\endgroup$ Commented Sep 21, 2018 at 5:17
  • $\begingroup$ The mouse will, on average, move twice to the left for every move to the right. So let's look at a few examples (starting at door 4). 5 moves : 3,2,3,2,1 (pattern is L,L,R...) 7 moves : 3,4,3,2,3,2,1 (pattern is L,R,L...) 9 moves : 5,4,3,4,3,2,3,2,1 (pattern is R,L,L) Assuming each of those 3 patterns is equally likely, I just took the average and it comes out to 7 moves. The other possible scenarios of moves are less likely so maybe those are not so significant and will not change the answer much or at all. $\endgroup$ Commented Sep 21, 2018 at 5:37
  • 1
    $\begingroup$ Your unscientific intuition is right. The expected number of moves starting from 4 to reach the absorbing states of 0 or 7 is indeed "7". $\endgroup$ Commented Sep 21, 2018 at 6:25
  • $\begingroup$ Wow, I wouldn't say unscientific since I got the patterns correct. I just don't have good math skills to run the Markov chain or whatever else is needed. I expected the answer to be 7 or something close to 7. As far as the 100+ move probability, I am working on it but still do not have an answer. I am hoping my guess of 1 out of a billion is at least in the right order of magnitude, but since it is just a guess, I don't expect it to be very accurate. $\endgroup$ Commented Sep 21, 2018 at 6:38

3 Answers 3

Reset to default
10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This seems to be the most liked answer by your peers and I appreciate your effort. I haven't heard the terms eigenvalue and eigenvector since my college days. $\endgroup$ Commented Sep 23, 2018 at 17:36
  • $\begingroup$ @David: Since I didn't calculate them myself and just posted a link to how I let Wolfram|Alpha calculate them, you don't have to know all the theory of how to find them -- basically you just need to verify that applying the matrix to the two vectors in the decomposition does indeed multiply them by the factors $\frac23$ and $0$, respectively -- that's all I'm using to derive the probability distribution. $\endgroup$ Commented Sep 23, 2018 at 18:15
3
$\begingroup$

The first matrix is the transition matrix with seven states. States 1 and 7 are absorbing states. The one shaded baige is the matrix Q. The next matrix below is (I-Q) and the one below it is its inverse giving you the fundamental matrix. Take this fundamental matrix and multiply by (5X1) unit vector. As you can see, the entry near 4 is the expected number of moves before it reaches either of the absorbing states. It works out to be 7. Had the starting state been 2, the expected number of moves before it is eaten is 2.714.

enter image description here

$\endgroup$
2
  • $\begingroup$ I ran a computer simulation of 1 million deaths from each starting position (2,3,4,5,6) and all of your results match mine. Nice work. With computer simulation it is easy. Between runs, I just changed one number in the code, namely the starting position of the mouse. 1 million simulated deaths from each starting position only took a few seconds each using an interpreted language and an old slow laptop. Math and computer simulation seem to work great as a pair for probability problems like this one. If the answers match (which they did), then that is extra assurance they are both correct. $\endgroup$ Commented Sep 21, 2018 at 15:32
  • $\begingroup$ You are welcome!! $\endgroup$ Commented Sep 21, 2018 at 15:40
2
$\begingroup$

I'll take a shot at this........

1) The eventual fateful outcome occurs when the total number of moves, lower versus higher, differs by 3.

So, a way to look at this as an $E(x) = n\cdot p$ type problem is to sum the $(n\cdot p)$s for all possible outcomes.

This will be:

$3(\frac{1}{3})+5(\frac{2}{9})+7(\frac{4}{27})+9(\frac{8}{81})+ .....\text{etc}$ which is an infinite arethmetico-geometric series whose infinite sum is: $$S = \frac{dg_2}{(1-r)^2} + \frac{a}{1-r} = \frac{2\cdot (\frac{1}{3}\cdot \frac{2}{3})}{\frac{1}{3}^2} + \frac{3\cdot \frac{1}{3}}{\frac{1}{3}} = 2\cdot 2 + 3 = 7$$

2) $$P(n\ge 100) = 1 - P(n<100)$$

$$P(n<100) = S_n = \frac{1}{3}+\frac{2}{9}+\frac{4}{27}+ .......+\frac{2^{n-1}}{3^n}$$

This turns out to be a geometric series, where $a_1 = \frac{1}{3}, r = \frac{2}{3}$ and $n = 49$ (odd from $3$ to $99$) a different n from the n moves.

Example calculation for $3$rd term is: $9(\frac{2}{3})^5(\frac{1}{3})^2 + 9(\frac{1}{3})^5(\frac{2}{3})^2 = \frac{4}{27}$

$$P(n\ge 100) = 1 - \frac{\frac{1}{3}(1-(\frac{2}{3})^{49})}{1-(\frac{2}{3})}$$

$$P(n\ge 100) = 1 - .9999999976 = 2.4\cdot 10^{-9}$$

$\endgroup$
6
  • $\begingroup$ If the probability of getting to states (doors) 1 or 7 in exactly 7 moves is slightly less than 1/2, then that actually seems like it could be the peak of the likely # of moves to be "absorbed" (eaten). My simplistic analysis also agrees that using the LLR, LRL, and RLL movements of the mouse in equal proportions, will result in 7 moves before death. I am not sure where you are getting 9 from. I think if the probability of moving either left or right was the same (50%), then the average number of moves would then be 9, but since there is a bias to move left, the 9 answer seems wrong to me. $\endgroup$ Commented Sep 21, 2018 at 7:01
  • 2
    $\begingroup$ Note that your result for $\mathsf P(n\ge100)$ simplifies to $\left(\frac23\right)^{49}$. $\endgroup$ Commented Sep 21, 2018 at 7:06
  • 1
    $\begingroup$ At the end of your geometric sum (it's not a series), it should be $100$ instead of $n$; $n$ isn't a free variable on the left. Note also that you could obtain the life expectancy from your death probabilities as $$ \sum_{k=0}^\infty(2k+3)\cdot\frac13\cdot\left(\frac23\right)^k=2\cdot2+3=7\;. $$ $\endgroup$ Commented Sep 21, 2018 at 10:52
  • $\begingroup$ @joriki I can see algebraically how it simplifies to $(\frac{2}{3})^{49}$ but I'm missing how that works conceptually, same as the life expectancy. I'll need to study these a little further to "see" how they work. $\endgroup$ Commented Sep 21, 2018 at 16:39
  • $\begingroup$ @David My life expectancy calculation is based on an expected value being the number of trials times the probability of an outcome. In $10$ tosses of a fair coin we expect $n\cdot p = 10\cdot 0.5 = 5$ heads. I don't think my method considered all possible outcomes especially those with fewer moves. I'll need to study joriki's equation a little more. $\endgroup$ Commented Sep 21, 2018 at 16:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.