Running Shoes

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/