Nathan's thief of Baghdad problem

thief.py

#--------------------------------------------------------------------------
# Nathan's thief of Baghdad problem.
#
#   Expected time to reach exit = 4.03 +/- 0.02 days ; based on 1e5 trials
#--------------------------------------------------------------------------

import numpy as np
from scipy.stats.mstats import sem

def solve(time_sum):
    choice = np.random.randint(3)
    if choice == 0:
        return solve(time_sum + 1)
    elif choice == 1:
        return solve(time_sum + 3)
    elif choice == 2:
        return time_sum
        
def main():
    successes = np.array([], dtype='i4')
    for n in np.arange(1e5):
        successes = np.append(successes, solve(0))
    print "Mean of %d attempts = %g +/- %g" % (successes.size, successes.mean(), sem(successes)) 

if __name__ == '__main__':
    main()

1.9 thief of baghdad problem.

A thief in jail has 3 doors to choose from. Door A takes him on a 1 day trip then falls and knocks his head, door B same thing, but 3 days. Door C is freedom. Every time he knocks his head he loses memory of his past door choices. Assuming he picks a door as soon as he can, what's his expected time to freedom?

http://books.google.com/books?id=mwW-iODttSQC&pg=PA50&lpg=PA50&dq=thief+of+baghdad+problem&source=bl&ots=KyMMxNwktw&sig=WEjLJ0BXS6zASEf1M572G_FJ4LU&hl=en&sa=X&ei=UTHqUNTUNNPHqAH184E4&ved=0CDEQ6AEwAQ#v=onepage&q=thief%20of%20baghdad%20problem&f=false

You can solve this numerically, or with calculus, or you can come up with a couple of lines of conditional expectation and come out with an answer.