import random
import pandas as pd
from datetime import datetime
If you flip a coin until you decide to stop and you want to maximize the ratio of heads to total flips, what is the expected ratio?
Coin Flip Game
This is a program I made to simulate a game I came across preparing for job interviews. The idea of the game is this:
If you flip a coin until you decide to stop and you want to maximize the ratio of heads to total flips, what is the expected ratio?
My strategy
At first glace the problem seems easy, but as you start modeling you realize it is quite complicated. Initially I came up with a maximum ratio .75 as my estimate. This comes from the idea that there is a 50% chance we get heads on our first flip (a ratio of 1 heads / 1 total flips = 100%) and stop, or a 50% chance we get tails then keep flipping till in the long run we get a ratio of .5 (since we expect to get 1 heads for every 2 flips we do).
This will give us \(.5*1 + .5*.5 = .75\)
Now lets go and try to model this idea and see if we can improve on it at all:
if we have greater than some stopRatio X of heads/totalFlips (my intuition tells me this should be .50 since that is the long run ev) we will stop
- if we do not hit this threshold we just keep flipping till we do
Model out which number works best as a stopRatio X to set as a threshold for achieving the best results possible
To avoid recursive depth problems with python if we have flipped more than 1000 times in a single simulation I will equate this to a ratio of max(currentRatio, .5) since if we keep flipping till infinity we approach a ratio of .5 heads to total flips.
def runFlipSimulation(numRuns:int, stopRatio:float) -> float:
= 0
averageSimulationOutcome for i in range(numRuns):
+= (runSingleSimulation(0,0,stopRatio)/numRuns)
averageSimulationOutcome
return round(averageSimulationOutcome,4)
def runSingleSimulation(numPreviousFlips:int,numHeads:int,stopRatio:float) -> float:
# here we are calling 0 tails and 1 heads
= random.randint(0,1)
coin_flip +=1
numPreviousFlips
if coin_flip == 1:
+=1
numHeads
= numHeads/numPreviousFlips
currentRatio
if currentRatio > stopRatio:
return currentRatio
# if depth >1000 then lets call it .5 as the ratio (long run result anyway)
# this depth limit stops us from bricking python
if numPreviousFlips>=1000:
# Either return current ratio or long run ratio of .5
return max(.5,currentRatio)
return runSingleSimulation(numPreviousFlips,numHeads,stopRatio)
# This method will run tests with stopRatio being between 50% and 60% inclusive steping by 1% with every new test
def run_ten_stopNumber_tests() -> pd.DataFrame:
# Test run with 100K flips
= 100000
numRuns
# get a unique identifier for our run
= datetime.now()
now = str(int(now.timestamp() * 1000))
unique_string = pd.DataFrame()
df # run test
for i in range(0,11):
= round(i/100+.5,2)
stopRatio = round(runFlipSimulation(numRuns,stopRatio),5)
simResult
= df._append(pd.DataFrame({ f'Expected Value Test_ID:{unique_string}':simResult }, index=[stopRatio]))
df
return df
# gather an array of dataframes that we generate through testing
= []
dfStorageArr = 10
numTests for i in range(numTests):
dfStorageArr.append(run_ten_stopNumber_tests())
Results
# concat all results into one dataframe joining on the index(stopRatio)
= pd.concat(dfStorageArr,axis=1)
df_all_results
df_all_results.head()
Expected Value Test_ID:1723830103687 | Expected Value Test_ID:1723830403945 | Expected Value Test_ID:1723830705809 | Expected Value Test_ID:1723831009492 | Expected Value Test_ID:1723831309161 | Expected Value Test_ID:1723831624928 | Expected Value Test_ID:1723831945790 | Expected Value Test_ID:1723832266780 | Expected Value Test_ID:1723832589264 | Expected Value Test_ID:1723832901556 | |
---|---|---|---|---|---|---|---|---|---|---|
0.50 | 0.7859 | 0.7860 | 0.7842 | 0.7851 | 0.7839 | 0.7859 | 0.7862 | 0.7856 | 0.7858 | 0.7862 |
0.51 | 0.7850 | 0.7864 | 0.7863 | 0.7854 | 0.7876 | 0.7853 | 0.7869 | 0.7861 | 0.7869 | 0.7859 |
0.52 | 0.7880 | 0.7879 | 0.7873 | 0.7865 | 0.7868 | 0.7869 | 0.7878 | 0.7878 | 0.7868 | 0.7869 |
0.53 | 0.7871 | 0.7875 | 0.7877 | 0.7885 | 0.7875 | 0.7864 | 0.7871 | 0.7878 | 0.7876 | 0.7889 |
0.54 | 0.7883 | 0.7888 | 0.7889 | 0.7896 | 0.7884 | 0.7881 | 0.7867 | 0.7880 | 0.7877 | 0.7888 |
='line',figsize=(10,6),title='Heads to Total Flips ratio of 10 seperate 100k samples across each stopRatio',xlabel='Stop Ratio',ylabel = 'Heads / Total Flips') df_all_results.plot(kind
'Row_Average'] = df_all_results.mean(axis=1)
df_all_results[
# Step 2: Plot the averages
'Row_Average'].plot(kind='line', figsize=(10, 6), marker='o', title='Heads to Total Flips ratio of 1M samples across each stopRatio',xlabel='Stop Ratio',ylabel = 'Heads / Total Flips') df_all_results[
Findings
It appears that we can find a new optimal strategy for this game that I find surprising:
- We only accept a ratio of better than 56% heads/total flips to stop
- The best long run result I was able to achieve was 78.9% heads/total flips ratio across 1M simulations!
Future Work
This was a naive method only considering that there has to be some constant ratio of heads/total flips at which we accept it. I also however could forsee a situation where our heads/total flips ratio might want to be lower or higher.
An example of this might be:
we are 1M flips out and our current ratio is 52% this might be considered good since our variance per flip is extremely low and our long run expectancy is 50%. Versus if we are currently in the start and have only flipped 25 times so far and our ratio is 52% (13 heads/25 flips) we might be more inclined to want a higher number since our variance per flip is much higher.
This is just some initial thoughts by me and am open to discussion! Feel free to reach out to me if you have any comments or ideas on the idea of a constant/variable stopRatio or any other improvements!