Average Time for a Mouse to Find CheeseDate: 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. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/