St. Petersburg Lottery

A gambler decides to participate in a special lottery. In this lottery the gambler plays a series of one or more games.
Each game costs $m$ pounds to play and starts with an initial pot of $1$ pound. The gambler flips an unbiased coin. Every time a head appears, the pot is doubled and the gambler continues. When a tail appears, the game ends and the gambler collects the current value of the pot. The gambler is certain to win at least $1$ pound, the starting value of the pot, at the cost of $m$ pounds, the initial fee.
The game ends if the gambler’s fortune falls below $m$ pounds.
Let $p_m(s)$ denote the probability that the gambler will never run out of money in this lottery given an initial fortune $s$ and the cost per game $m$.
For example $p_2(2) \approx 0.2522$, $p_2(5) \approx 0.6873$ and $p_6(10\,000) \approx 0.9952$ (note: $p_m(s) = 0$ for $s \lt m$).
Find $p_{15}(10^9)$ and give your answer rounded to $7$ decimal places behind the decimal point in the form 0.abcdefg.

To solve this problem, we can use a dynamic programming approach. We can define a function `probability(m, s)` to calculate the probability `p_m(s)` recursively.

The base case is when `s < m`, in which case the probability is 0. We return 0 in this case. Otherwise, we can calculate the probability by considering the two scenarios: flipping heads and flipping tails. When flipping heads, the pot is doubled. So, we recursively call `probability(m, 2*s)` to calculate the probability of never running out of money with a doubled pot. When flipping tails, the game ends, and the gambler collects the current value of the pot. So, the probability in this scenario is 1. To calculate the overall probability, we need to take the average of the two probabilities considering the unbiased coin. Since the coin is unbiased, the probability of flipping heads is 0.5, and the probability of flipping tails is also 0.5. We can memoize the results to avoid redundant computations and improve efficiency. Here is the Python code to solve this problem: ```python memo = {} def probability(m, s): if s < m: return 0 if s == 1: return 1 if (m, s) in memo: return memo[(m, s)] prob_heads = 0.5 * probability(m, 2*s) prob_tails = 0.5 prob = prob_heads + prob_tails memo[(m, s)] = prob return prob result = probability(15, 10**9) rounded_result = round(result, 7) print(rounded_result) ``` Running this code will give you the probability `p_15(10^9)` rounded to 7 decimal places, as required by the problem.

More Answers: