Created
January 8, 2013 22:04
-
-
Save kenthorvath/4488414 to your computer and use it in GitHub Desktop.
Nathan's thief of Baghdad problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#-------------------------------------------------------------------------- | |
# 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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.