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


The $25.2\%$ given in the problem is the success rate, not the failure rate, which should be $74.8\%$.

Your code contains a bug in case $2$: The comment correctly says "if there is money in pot", but the code incorrectly requires possibility[0] < price_to_play.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.