Date: 04/03/2001 at 12:21:25 From: Detti Rattay Subject: Probability Dear Dr. Math, This is a fascinating little problem, and I have been struggling with it for a long time. Please help, if you can. Each morning an individual leaves his house and goes for a run. He is equally likely to leave either from the front or the back door. Upon leaving the house, he chooses a pair of running shoes (or goes running barefoot it there are no shoes at the door from which he departs). On his return he is equally likely to enter and to leave his running shoes either at the front or the back door. If he owns a total of k pairs of running shoes, what proportion of the time does he run barefoot? I think this is like a gambler's ruin problem, but in a way it is more general, because we don't even know exactly with how many shoes he starts out with. Also, when he is out of shoes, the problem is not finished. I would really appreciate your help in setting this problem up properly. Thank you for your help in advance. Sincerely, D. Rattay
Date: 04/04/2001 at 05:35:14 From: Doctor Anthony Subject: Re: Probability We can see what is happening by giving k a specific value and working from that. I will use the notation (x,y) where x = the number of pairs of shoes at the front door, and y = the number of pairs at the back door, and x+y = k. Take a simple situation where k = 4. We then have 5 possible states: (4,0), (3,1), (2,2), (1,3), (0,4). This is a problem where we can use a Markov chain to give the probabilities of moving from one state to the next, and also investigate long-term behaviour. The transition matrix will be as shown below. Note that the columns always sum to 1. If we start in state (4,0) then there is probability 1/2 that he leaves from the front door and then returns to state (4,0) or (3,1), and there is probability 1/2 that he leaves by the back door and then MUST return to state (4,0). These possibilities mean that in total there is probability 3/4 of returning to state (4,0) and probability 1/4 of returning to state (3,1). The transition probabilities in the other columns of the matrix are calculated in the same way, in each case considering what happens if he leaves by the front door and what happens if he leaves by the back door. FROM ------- (4,0) (3,1) (2,2) (1,3) (0,4) |--------------------------------------- (4,0)| 3/4 1/4 0 0 0 (3,1)| 1/4 1/2 1/4 0 0 TO (2,2)| 0 1/4 1/2 1/4 0 ---(1,3)| 0 0 1/4 1/2 1/4 (0,4)| 0 0 0 1/4 3/4 If you take the higher and higher powers of this matrix it reduces to [0.2 0.2 0.2 0.2 0.2] |0.2 0.2 0.2 0.2 0.2| |0.2 0.2 0.2 0.2 0.2| |0.2 0.2 0.2 0.2 0.2| [0.2 0.2 0.2 0.2 0.2] which means that you are equally likely to be in any one of the 5 possible states. The two states where he runs barefoot are (4,0) and (0,4) If in state (4,0) and he leaves by back door, or in state (0,4) and he leaves by front door, the probability is 0.2 x 1/2 + 0.2 x 1/2 = 0.2 = 1/5 If we extend this to the general situation with k pairs of shoes there are k+1 possible states and he runs barefoot on 1/(k+1) of all occasions. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.