Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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

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/
```
Associated Topics:
College Probability
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search