The following question references Project Euler Problem 499, which can be found here. Here is the problem in a nutshell: a gambler starts with s dollars, and he can gamble in a that costs m dollars to play. Once he starts to play, he pays the m dollars to the dealer, and he gets a 1 dollar pot. He then flips a fair coin. If the coin lands on heads, his pot is doubled, and he plays again. If the coin lands on tails, the gambler takes the entirety of the pot, and he has to pay the m dollar starting fee again to the dealer to get his pot back. What is the probability he never runs out of money for m = 2 dollars and s = 2 dollars?
My strategy was to create a python script with a branching probability tree that would tell me all possible outcomes on a certain branch down the line (for example, all possibilities after 25 coin tosses). Here is the script, though the code is secondary; the important thing for me is the mathematical, statistical theory behind it.
def play_game(initial_funds, price_to_play, iterations):
prob_tree = {}
for iteration in range(1, iterations + 1):
prob_tree[iteration] = []
# first number always represents money in hand, second represents money in pot.
prob_tree[1].append([initial_funds - price_to_play, 1])
for iteration in range(2, iterations + 1):
# for each possible outcome listed in the line above in the probability tree
for possibility in prob_tree[iteration - 1]:
# if there isn't any money in the pot AND not enough current funds, just repeat it twice in the next line for counting purposes.
if possibility[0] < price_to_play and possibility[1] == 0:
prob_tree[iteration].append(possibility)
prob_tree[iteration].append(possibility)
# maybe add the current possibility combo twice to the current iteration.
# if there is money in pot, append a heads and tails possibility to the current row
elif possibility[0] < price_to_play and possibility[1] > 0:
case2_old_pot = possibility[1]
case2_win_new_pot = possibility[1] * 2
case2_lose_new_pot = 0
case2_player_funds = possibility[0]
# if successful, the money in the pot will double, and the player's money will remain constant
prob_tree[iteration].append([case2_player_funds, case2_win_new_pot])
# if not successful, the money in the pot will be added into the player's money, and the pot will return to 0
prob_tree[iteration].append([case2_player_funds + case2_old_pot, case2_lose_new_pot])
# if there is no money in the pot but there is sufficient money in the player's pocket to play again1
elif possibility[0] >= price_to_play and possibility[1] == 0:
# first, the money in the player's pocket goes down by the amount price_to_play, and the pot amount goes up to one.
case3_funds_after_buyin = possibility[0] - price_to_play
case3_pot_after_buyin = 1
case3_pot_if_successful = 2
case3_pot_if_unsuccessful = 0
case3_funds_if_successful = case3_funds_after_buyin
case3_funds_if_unsuccessful = case3_funds_after_buyin + case3_pot_after_buyin
# then, either the player gets back the pot and it goes to 0
prob_tree[iteration].append([case3_funds_if_unsuccessful, case3_pot_if_unsuccessful])
prob_tree[iteration].append([case3_funds_if_successful, case3_pot_if_successful])
counter = 0
for outcome in prob_tree[iterations]:
if outcome[0] < price_to_play and outcome[1] == 0:
counter += 1
print float(counter)/(2**iterations)
play_game(2, 2, 25)
I figured as the number of layers on the tree grew larger, the answer would be increasingly accurate. When testing this theory, I was surprised to see that the failure rate for a 2 pound cost and a 2 pound initial amount was stabilizing around 35.4%, instead of the expected 25.2% that the problem gives me.
Some possible reasons for this could be that I am assuming that all non-failures at a given line will go on forever, but I don't know how to account for this without adding another branch and thus repeating the problem. Any insights would be greatly appreciated.
