Average Time for a Mouse to Find Cheese

Date: 11/05/97 at 03:48:24
From: Nadav Shalit
Subject: Average time for a mouse to find cheese

A mouse has 3 rooms to go into.

     If it goes into room 1 it will find the cheese after 3 minutes.

     If it goes into room 2 it will look for cheese for 4 minutes, 
     won't find it, and will go out.

     If it goes into room 3 it will look for cheese for 5 minutes, 
     won't find it, and will go out.

The mouse will not remember that it was in rooms 2 and 3 after it 
goes out of them, and it will continue going in and out until it 
finds the cheese. (It can go into the same room again and again.)

What is the average time for the mouse to find cheese?

Date: 11/05/97 at 10:14:10
From: Doctor Anthony
Subject: Re: Average time for a mouse to find cheese

There is a constant probability 1/3 that the mouse will go into any of 
the three rooms. 

If we call the rooms a, b, c representing rooms 1, 2, 3 respectively, 
then the possible sequences will always end with an 'a' when 
the mouse enters room 1.

                          Time (mins)        Probability
                           -------          --------------
So we could have   a          3                 1/3       
                   ba         7                 (1/3)^2 
                   ca         8                 (1/3)^2 
                   bba       11                 (1/3)^3 
                   bca       12                 (1/3)^3
                   cba       12                 (1/3)^3
                   cca       13                 (1/3)^3
                   bbba      15                 (1/3)^4

as you can see, calculating the expected time would be very difficult 
if we keep the b and c rooms separate. However, we can combine them by 
having a time of 4.5 minutes and probability 2/3.

     i.e.  (1/3)(4) + (1/3)(5) = (1/3)(9)  =  (2/3)(4.5)  

The table now looks like this, combining b and c into f (for failure).

     Sequence         Time (mins)          Probability 
     --------         -----------          -----------
        a                  3                1/3
       fa                  7.5             (2/3)(1/3)
       f^2.a              12               (2/3)^2 (1/3)   
       f^3.a              16.5             (2/3)^3 (1/3)
       f^4.a              21               (2/3)^4 (1/3)

and so on to infinity.

Expected time = 3*(1/3) + 7.5(2/3)(1/3) + 12(2/3)^2 (1/3) + ...

              = (1/3)[3 + 7.5(2/3) + 12(2/3)^2 + 16.5(2/3)^3 + ...]

Now to sum the series in brackets we represent (2/3) by x and we have:

          S = 3 + 7.5x +  12x^2 + 16.5x^3 +   21x^4   + ...
         xS =       3x + 7.5x^2 +   12x^3 + 16.5x^4   + ...
     --------------------------------------------------------
     (1-x)S = 3 + 4.5x + 4.5x^2  + 4.5x^3 +  4.5x^4   + ...

     (1-x)S = 3 + 4.5x(1 + x + x^2 + x^3 + ...)

     (1-x)S = 3 + 4.5x(1/(1-x))

          S = 3/(1-x) +  4.5x/(1-x)^2

and putting x = 2/3,  1-x = 1/3

Expected time  = (1/3)[3/(1/3) + 4.5(2/3)/(1/3)^2]

               = (1/3)[ 9 + 27 ]

               =  12 minutes


-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 03/02/2000 at 14:23:27
From: Rob Pratt
Subject: Re: Average time for a mouse to find cheese

There is a better method and a better solution than the one 
presented. The better method is as follows. Let m(i) be the expected 
time until finding the cheese if the mouse has just arrived at room i. 
(Let room 0 correspond to the starting position.) Then we have:

     m(0) =     (1/3) m(1) + (1/3) m(2) + (1/3) m(3)
     m(1) = 3
     m(2) = 4 + (1/3) m(1) + (1/3) m(2) + (1/3) m(3)
     m(3) = 5 + (1/3) m(1) + (1/3) m(2) + (1/3) m(3).

Solving this system yields m(0) = 12, the same answer given by Doctor 
Anthony.

But it doesn't seem reasonable to allow the mouse to visit the same 
room twice without visiting some other room in between (otherwise, 
the mouse doesn't really "leave the room"). Under this assumption, 
the equations become

     m(0) =     (1/3) m(1) + (1/3) m(2) + (1/3) m(3)
     m(1) = 3
     m(2) = 4 + (1/2) m(1)              + (1/2) m(3)
     m(3) = 5 + (1/2) m(1) + (1/2) m(2).

Solving this system yields m(0) = 9.

Date: 04/11/2000 at 04:17:02
From: Mikael Jansson
Subject: Re: Average time for a mouse to find cheese

The mouse problem above has a very, very, VERY long solution by 
Dr. Anthony. Here's a quick solution:

Call the expected time (in minutes) to find cheese, E. The mouse will 
have three choices each chosen with a 1/3 probability: use 3 minutes 
to find the cheese, use 4 minutes and try again (4 + E minutes), or 
use 5 minutes and try again (5 + E minutes). The equation would be:

     E = 1/3 * ((3) + (4 + E) + (5 + E))

which yields

     E = 12

Problem solved. 12 minutes.