# Segment 5, Group 2

**Part 1:** You are given a unique investment opportunity. Starting with £1 of capital, you can choose a fixed proportion, f, of your capital to bet on a fair coin toss repeatedly for 1000 tosses. Your return is double your bet for heads and you lose your bet for tails. For example, if f = 1/4, for the first toss you bet £0.25, and if heads comes up you win £0.5 and so then have £1.5. You then bet £0.375 and if the second toss is tails, you have £1.125. Choosing f to maximize your chances of having at least £1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire? All computations are assumed to be exact (no rounding), but give your answer rounded to 12 digits behind the decimal point in the form 0.abcdefghijkl.

For this problem, the total capital you have is updated by a multiplicative factor after each coin flip. If the flip is heads, then the total capital is multiplied by (1+2f). If the flip is tails, then the total capital is multiplied by (1-f). This means that the order of the heads and tails doesn't matter, only the number of heads and tails. Also, the probability of flipping **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_H}**
heads is independent of the choice of f. Therefore, we only need to determine the number of heads required to reach £1,000,000,000 after 1,000 flips for a given f and find the f that minimizes this. Based on this minimum number of heads required to reach £1,000,000,000 after 1,000 flips, the probability can be determined by evaluating the CDF of the binomial distribution.

For a given f, the required number of heads to reach £1,000,000,000 after 1,000 flips can be determined through the following relation

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+2f)^{N_H}(1-f)^{1000-N_H} = \left(\frac{1+2f}{1-f}\right)^{N_H}(1-f)^{1000} \geq 10^9}Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{1+2f}{1-f}\right)^{N_H} \geq \frac{10^9}{(1-f)^{1000}}}Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_H = ceil\left(\frac{\log\left(\frac{10^9}{(1-f)^{1000}}\right)}{\log\left(\frac{1+2f}{1-f}\right)}\right) = ceil\left(\frac{9 - 1000\log\left(1-f\right)}{\log\left(1+2f\right) - \log\left(1-f\right)}\right)}

A MATLAB script that determines this maximum probability of reaching £1,000,000,000 after 1,000 flips for any given f is shown below. This script divides the range of possible f into 1,000,000 evenly spaced points, computes the required **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_H}**
to reach £1,000,000,000 after 1,000 flips for each value of f, finds the minimum number of heads required, and determines the probability that you will have at least £1,000,000,000 after 1,000 flips.

NH_f = @(f) ceil((9 - 1000*log10(1-f))./log10((1+2*f)./(1-f))); minf = 0.0001; maxf = 0.9999; f = linspace(minf,maxf,10^6); NH = NH_f(f); [NHmin ind] = min(NH); P = 1 - cdf('bino',NHmin-1,1000,.5)

Running this script results in the output

P = 0.999992836186714

**Part 2:** The problem as stated multiplies your wager by 2 on a win. What is the smallest this factor can be while still leaving the probability of ending up above one billion greater than 0.5, assuming that you play with an optimal f given the value of the factor?

We can update the script from above to include an additional outer loop that optimizes over possible winning factor **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M}**
. In order for the probability of ending up above one billion to be greater than 0.5, the required number of heads for the optimal f must be at least 500. Therefore, the goal is to find the minimal **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M}**
for which the optimal f requires only 500 heads to reach one billion. The following updated MATLAB code performs this optimization where each iteration of the outer loop fixes one digit of **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M}**
. This is far from the most efficient way to perform this optimization over

digits = 15; Mlow = 1; Mhigh = 2; minf = 0.0001; maxf = 0.9999; f = linspace(minf,maxf,10^6); for(d = 1:digits) M = linspace(Mlow,Mhigh,11); for(i = 1:length(M)) Mi = M(i); NH_f = @(f) ceil((9 - 1000*log10(1-f))./log10((1+2*f)./(1-f))); NH = NH_f(f); [NHmin ind] = min(NH); if(NHmin <= 500) break end end Mhigh = Mi; Mlow = Mi - 10^(-d); end Mi P = 1 - cdf('bino',NHmin-1,1000,.5)

Running this script results in the output

Mi = 1.504673877089423 P = 0.512612509089180

Note that this answer is lower than that reported in Jeff's solution because the range of f was divided into 1,000,000 points instead of 1,000. This resulted in a more accurate and, thus, lower answer.

- This is great stuff! You are absolutely right that this would have won the prize over my answer and about the mechanism why. But I have responded to your challenge with an even smaller factor - check my (updated) solution. I don't think you can beat this one, but I would be happy to be wrong! Jeff Hussmann (talk) 22:06, 29 January 2014 (CST)

- Jeff, your updated solution is exactly correct and is the best approach to solving the problem. Daniel Shepard 13:18, 30 January 2014 (CST)

- Here's an updated version of the MATLAB script that uses fminbnd from MATLAB's optimization toolbox for the calculation

digits = 16; Mlow = 1; Mhigh = 2; minf = 0.0001; maxf = 0.9999; options = optimset('TolX',1e-16); for(d = 1:digits) M = linspace(Mlow,Mhigh,11); for(i = 1:length(M)) Mi = M(i); NH_f = @(f) (9 - 1000*log10(1-f))./log10((1+Mi*f)./(1-f)); [f NHmin] = fminbnd(NH_f,minf,maxf,options); NHmin = ceil(NHmin); if(NHmin <= 500) break end end Mhigh = Mi; Mlow = Mi - 10^(-d); end fprintf('M = %17.16f\n',Mi) P = 1 - cdf('bino',NHmin-1,1000,.5)

- The result from this script is shown below and is accurate to machine precision.

M = 1.5046738770873433 P = 0.512612509089180

- This falls within the bounds Jeff prescribed in his updated solution. Daniel Shepard 14:23, 30 January 2014 (CST)