Solution to Problem 178

Correct solutions were received from Scott Hoffmeyer and Jeremy Light.  Further correct solutions were received from Ahmed AboAdham, Lou Cairoli, Lorenzo Pozzoli, Iñigo Picaza, Bill Webb, Jérôme Lefebvre, Jens Voß, Ron Welch, Al Zimmermann, Brian Laughlin, and Johann Moll. Special mention goes to Nancy Schwarzkopf for having two correct solutions.

The probability is , which is very close to, but not equal to the popular answer of 1/4.

Let's call the starting node, node O.  Let an be the probability of being at O after n minutes, and bn be the probability of not being at O after n minutes.

Note that if you are not at O at time n-1 you move to O be at time n with probability 1/3.  On the other hand, there are two ways in which you can fail to be at O at time n, namely, you could have been at O at time n-1, in which case you definitely moved to a node different from O, or you could have been and then stayed at a node different from O, which occurs with probability 2/3.  These observations yield the following equations.

an =1/3·bn-1,     bn = an-1 + 2/3 ·bn-1.

After some algebraic manipulation, these formulas combine to reveal that an+1 = 1/3· an-1 + 2/3·an , for n > 1, and a0 = 1, a1 = 0.  Working out the first few cases, you see that a2 = 1/3, a3 = 2/9, a4 = 7/27, a5 = 20/81. Let's write the general term as the fraction an = dn/3n-1.  A moment's thought reveals that the numerators appear to follow the pattern dn = 3dn-1 + (-1)n; this can be proven by an easy induction.  Another easy induction verifies that  dn =  3n-2 - 3n-3 + ... + (-1)n = (3n-1 + (-1)n) /4. Substituting dn back into an and 10080 (the number of minutes in a week) for n yields the stated solution.

You are visitor number 3485 to this page.
ã2003 Alberto L. Delgado