Skip to content

Instantly share code, notes, and snippets.

@RobLewis

RobLewis/WorldSeriesOddsGist_.idea_description.html

Created October 29, 2017 23:50
Show Gist options
  • Save RobLewis/1bf9d3b0ab2ebc7745e4780f9e7769fa to your computer and use it in GitHub Desktop.
Save RobLewis/1bf9d3b0ab2ebc7745e4780f9e7769fa to your computer and use it in GitHub Desktop.
Download ZIP
Recursive coin-flip probability computation
Raw
WorldSeriesOddsGist_.idea_description.html
<html>Simple <b>Java</b> application that includes a class with <code>main()</code> method</html>
Raw
WorldSeriesOddsGist_.idea_misc.xml
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
<component name="EntryPointsManager">
<entry_points version="2.0" />
</component>
<component name="ProjectKey">
<option name="state" value="project://e2804f05-5315-4fc6-a121-c522a6c26470" />
</component>
<component name="ProjectRootManager" version="2" languageLevel="JDK_1_8" project-jdk-name="1.8" project-jdk-type="JavaSDK">
<output url="file://$PROJECT_DIR$/out" />
</component>
</project>
Raw
WorldSeriesOddsGist_.idea_modules.xml
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
<component name="ProjectModuleManager">
<modules>
<module fileurl="file://$PROJECT_DIR$/WorldSeriesOddsGist.iml" filepath="$PROJECT_DIR$/WorldSeriesOddsGist.iml" />
</modules>
</component>
</project>
Raw
WorldSeriesOddsGist_.idea_project-template.xml
<template>
<input-field default="com.company">IJ_BASE_PACKAGE</input-field>
</template>
Raw
WorldSeriesOddsGist_.idea_uiDesigner.xml
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
<component name="Palette2">
<group name="Swing">
<item class="com.intellij.uiDesigner.HSpacer" tooltip-text="Horizontal Spacer" icon="/com/intellij/uiDesigner/icons/hspacer.png" removable="false" auto-create-binding="false" can-attach-label="false">
<default-constraints vsize-policy="1" hsize-policy="6" anchor="0" fill="1" />
</item>
<item class="com.intellij.uiDesigner.VSpacer" tooltip-text="Vertical Spacer" icon="/com/intellij/uiDesigner/icons/vspacer.png" removable="false" auto-create-binding="false" can-attach-label="false">
<default-constraints vsize-policy="6" hsize-policy="1" anchor="0" fill="2" />
</item>
<item class="javax.swing.JPanel" icon="/com/intellij/uiDesigner/icons/panel.png" removable="false" auto-create-binding="false" can-attach-label="false">
<default-constraints vsize-policy="3" hsize-policy="3" anchor="0" fill="3" />
</item>
<item class="javax.swing.JScrollPane" icon="/com/intellij/uiDesigner/icons/scrollPane.png" removable="false" auto-create-binding="false" can-attach-label="true">
<default-constraints vsize-policy="7" hsize-policy="7" anchor="0" fill="3" />
</item>
<item class="javax.swing.JButton" icon="/com/intellij/uiDesigner/icons/button.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="0" hsize-policy="3" anchor="0" fill="1" />
<initial-values>
<property name="text" value="Button" />
</initial-values>
</item>
<item class="javax.swing.JRadioButton" icon="/com/intellij/uiDesigner/icons/radioButton.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="0" hsize-policy="3" anchor="8" fill="0" />
<initial-values>
<property name="text" value="RadioButton" />
</initial-values>
</item>
<item class="javax.swing.JCheckBox" icon="/com/intellij/uiDesigner/icons/checkBox.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="0" hsize-policy="3" anchor="8" fill="0" />
<initial-values>
<property name="text" value="CheckBox" />
</initial-values>
</item>
<item class="javax.swing.JLabel" icon="/com/intellij/uiDesigner/icons/label.png" removable="false" auto-create-binding="false" can-attach-label="false">
<default-constraints vsize-policy="0" hsize-policy="0" anchor="8" fill="0" />
<initial-values>
<property name="text" value="Label" />
</initial-values>
</item>
<item class="javax.swing.JTextField" icon="/com/intellij/uiDesigner/icons/textField.png" removable="false" auto-create-binding="true" can-attach-label="true">
<default-constraints vsize-policy="0" hsize-policy="6" anchor="8" fill="1">
<preferred-size width="150" height="-1" />
</default-constraints>
</item>
<item class="javax.swing.JPasswordField" icon="/com/intellij/uiDesigner/icons/passwordField.png" removable="false" auto-create-binding="true" can-attach-label="true">
<default-constraints vsize-policy="0" hsize-policy="6" anchor="8" fill="1">
<preferred-size width="150" height="-1" />
</default-constraints>
</item>
<item class="javax.swing.JFormattedTextField" icon="/com/intellij/uiDesigner/icons/formattedTextField.png" removable="false" auto-create-binding="true" can-attach-label="true">
<default-constraints vsize-policy="0" hsize-policy="6" anchor="8" fill="1">
<preferred-size width="150" height="-1" />
</default-constraints>
</item>
<item class="javax.swing.JTextArea" icon="/com/intellij/uiDesigner/icons/textArea.png" removable="false" auto-create-binding="true" can-attach-label="true">
<default-constraints vsize-policy="6" hsize-policy="6" anchor="0" fill="3">
<preferred-size width="150" height="50" />
</default-constraints>
</item>
<item class="javax.swing.JTextPane" icon="/com/intellij/uiDesigner/icons/textPane.png" removable="false" auto-create-binding="true" can-attach-label="true">
<default-constraints vsize-policy="6" hsize-policy="6" anchor="0" fill="3">
<preferred-size width="150" height="50" />
</default-constraints>
</item>
<item class="javax.swing.JEditorPane" icon="/com/intellij/uiDesigner/icons/editorPane.png" removable="false" auto-create-binding="true" can-attach-label="true">
<default-constraints vsize-policy="6" hsize-policy="6" anchor="0" fill="3">
<preferred-size width="150" height="50" />
</default-constraints>
</item>
<item class="javax.swing.JComboBox" icon="/com/intellij/uiDesigner/icons/comboBox.png" removable="false" auto-create-binding="true" can-attach-label="true">
<default-constraints vsize-policy="0" hsize-policy="2" anchor="8" fill="1" />
</item>
<item class="javax.swing.JTable" icon="/com/intellij/uiDesigner/icons/table.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="6" hsize-policy="6" anchor="0" fill="3">
<preferred-size width="150" height="50" />
</default-constraints>
</item>
<item class="javax.swing.JList" icon="/com/intellij/uiDesigner/icons/list.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="6" hsize-policy="2" anchor="0" fill="3">
<preferred-size width="150" height="50" />
</default-constraints>
</item>
<item class="javax.swing.JTree" icon="/com/intellij/uiDesigner/icons/tree.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="6" hsize-policy="6" anchor="0" fill="3">
<preferred-size width="150" height="50" />
</default-constraints>
</item>
<item class="javax.swing.JTabbedPane" icon="/com/intellij/uiDesigner/icons/tabbedPane.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="3" hsize-policy="3" anchor="0" fill="3">
<preferred-size width="200" height="200" />
</default-constraints>
</item>
<item class="javax.swing.JSplitPane" icon="/com/intellij/uiDesigner/icons/splitPane.png" removable="false" auto-create-binding="false" can-attach-label="false">
<default-constraints vsize-policy="3" hsize-policy="3" anchor="0" fill="3">
<preferred-size width="200" height="200" />
</default-constraints>
</item>
<item class="javax.swing.JSpinner" icon="/com/intellij/uiDesigner/icons/spinner.png" removable="false" auto-create-binding="true" can-attach-label="true">
<default-constraints vsize-policy="0" hsize-policy="6" anchor="8" fill="1" />
</item>
<item class="javax.swing.JSlider" icon="/com/intellij/uiDesigner/icons/slider.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="0" hsize-policy="6" anchor="8" fill="1" />
</item>
<item class="javax.swing.JSeparator" icon="/com/intellij/uiDesigner/icons/separator.png" removable="false" auto-create-binding="false" can-attach-label="false">
<default-constraints vsize-policy="6" hsize-policy="6" anchor="0" fill="3" />
</item>
<item class="javax.swing.JProgressBar" icon="/com/intellij/uiDesigner/icons/progressbar.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="0" hsize-policy="6" anchor="0" fill="1" />
</item>
<item class="javax.swing.JToolBar" icon="/com/intellij/uiDesigner/icons/toolbar.png" removable="false" auto-create-binding="false" can-attach-label="false">
<default-constraints vsize-policy="0" hsize-policy="6" anchor="0" fill="1">
<preferred-size width="-1" height="20" />
</default-constraints>
</item>
<item class="javax.swing.JToolBar$Separator" icon="/com/intellij/uiDesigner/icons/toolbarSeparator.png" removable="false" auto-create-binding="false" can-attach-label="false">
<default-constraints vsize-policy="0" hsize-policy="0" anchor="0" fill="1" />
</item>
<item class="javax.swing.JScrollBar" icon="/com/intellij/uiDesigner/icons/scrollbar.png" removable="false" auto-create-binding="true" can-attach-label="false">
<default-constraints vsize-policy="6" hsize-policy="0" anchor="0" fill="2" />
</item>
</group>
</component>
</project>
Raw
WorldSeriesOddsGist_.idea_vcs.xml
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
<component name="VcsDirectoryMappings">
<mapping directory="$PROJECT_DIR$" vcs="Git" />
</component>
</project>
Raw
WorldSeriesOddsGist_src_net_grlewis_coinflips_Main.java
package net.grlewis.coinflips;
/*
This was suggested when I heard a sportscaster say "The team that wins Game 1
goes on to win the World Series 68% of the time". I wondered whether that history
reflected team psychology, or whether it was just an outcome of simple probability.
(For those who aren't familiar, the World Series of baseball is won by the first team
(of the 2 finalists) to beat the other team 4 times.)
So I wanted to calculate the odds of a team winning the Series at any point within it,
assuming that both teams had an equal chance of winning each game.
In other words, each game is decided by a coin flip.
So my function is: probability( nHeads, nTails ).
Which is read "The probability of flipping nHeads heads BEFORE you flip nTails tails".
The simplest example is nHeads = nTails = 1. Which is read,
What is the probability of flipping 1 head before you flip 1 tail?" Obviously the answer is 1/2.
What if nHeads = 1 and nTails = 2? We're asking,
What is the probability of flipping 1 head before you flip 2 tails?
Your first flip has a probability of winning of 1/2.
But if your first flip is a tail, your next flip has a 1/2 chance of being a head.
So your total probability of winning is 1/2 + (1/2)*(1/2), or 3/4.
Extend this to a team that has won the first game of the World Series.
They need 3 more wins to win the Series, before the other team wins 4.
The question then is "What is the probability of flipping 3 heads before 4 tails?"
I looked on the Internet, and the closed-form solution of this problem seems quite complex.
I ran Monte Carlo simulations with thousands of runs, and the results closely matched the theoretical answer.
It occurred to me that maybe the way to solve the problem was with recursion.
For each position (h, t) in the sequence, the next coin flip will produce 2 equally likely outcomes:
If a head is flipped, the new state is (h-1, t), while a tail produces the state (h, t-1).
The probability of a win, P(h, t), is thus the average of the two probabilities P(h-1, t) and P(h, t-1).
You may recognize this as the "expectation" for the state P(h, t) where the payoff of the two successor states is equal.
Thus the recursive expression for P(h, t) is
1/2 * (P(h-1, t) + P(h, t-1))
and this is directly computed in the algorithm with recursive calls to the probability method.
This leaves the question of what is the "base case" of the recursive algorithm.
It occurs when either the remaining heads or tails value is equal to 1.
Take, for example, P(1, 3): the probability of flipping 1 head before flipping 3 tails.
The probability of flipping 3 tails in a row without flipping a head is 1/2 * 1/2 * 1/2, or 1/8.
Thus there is a 7/8 probability of failing to do this, that is, of flipping a head before 3 tails.
Similarly for P(3, 1), there is a 1/8 probability of flipping 3 heads before a tail.
Generalizing this, P(n, 1) is just (1/2)^n, and P(1, n) is 1 - (1/2)^n.
These base cases are directly expressed in the algorithm.
(and to answer the question that inspired this, the probability of the team that wins the first game
of the World Series to go on and win the Series is P(3, 4), which equals 65.625%, assuming that both teams
have an equal chance of winning each game. It's left as an exercise for the reader to modify the algorithm
for the case where one team is favored to win over the other one.)
Operational note: define the problem parameters by editing lines 62 and 63, or with command-line arguments.
If you use arguments, they must be exactly 2 positive integers specifying the values for nHeads and nTails.
*/
public class Main {
// following values can be overridden by command-line parameters
private static int noOfHeads = 3; // calculate odds you will flip this many heads, before flipping...
private static int noOfTails = 4; // this many tails
public static class CoinFlipSequence {
private static int recursionDepth = 0;
// version that allows turning off printing
static double probability( int numHeads, int numTails, boolean suppressPrintout ) {
double prob;
if( !suppressPrintout ) System.out.println( "probability called with " + numHeads + " heads " +
"and " + numTails + " tails, " + "at recursion depth " + ++recursionDepth );
// base case is when there is 1 head or 1 tail left
if( numHeads == 1 ) {
prob = 1D - Math.pow( 0.5D, numTails );
}
else if( numTails == 1 ) {
prob = Math.pow( 0.5D, numHeads );
} else { // not base case, recurse
prob = 0.5D * ( probability( numHeads - 1, numTails ) + probability( numHeads, numTails - 1 ) );
}
if( !suppressPrintout ) System.out.println( "Popping out of probability to recursion depth " + --recursionDepth );
return prob;
}
// version that doesn't have the suppressPrintout switch
static double probability( int numHeads, int numTails ) {
return probability( numHeads, numTails, false );
}
}
public static void main(String[] args) {
int nHeads = -1;
int nTails = -1;
if( args.length == 2) { // test for valid command-line parameters (nHeads & nTails)
try {
nHeads = Integer.valueOf( args[0] );
nTails = Integer.valueOf( args[1] );
}
catch( NumberFormatException e ) {
System.out.println( "Bad command-line argument: not an integer" );
System.exit( -1 );
}
if( nHeads <= 0 || nTails <= 0 ) {
throw new IllegalArgumentException( "Command-line arguments must be > 0" );
}
} else if( args.length != 0 ) {
throw new IllegalArgumentException( "Must be exactly 2 command-line arguments" );
}
if( nHeads != -1 ) noOfHeads = nHeads;
if( nTails != -1 ) noOfTails = nTails;
System.out.println( "Probability of " + noOfHeads + " Heads before " + noOfTails + " Tails " +
"is: " + CoinFlipSequence.probability( noOfHeads, noOfTails ) );
}
}
Raw
WorldSeriesOddsGist_WorldSeriesOddsGist.iml
<?xml version="1.0" encoding="UTF-8"?>
<module type="JAVA_MODULE" version="4">
<component name="NewModuleRootManager" inherit-compiler-output="true">
<exclude-output />
<content url="file://$MODULE_DIR$">
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
</content>
<orderEntry type="inheritedJdk" />
<orderEntry type="sourceFolder" forTests="false" />
</component>
</module>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment