Problem
Alice wants to join her school’s Probability Student Club. Membership dues are computed via one of two simple probabilistic games.
The first game: roll a die repeatedly. Stop rolling once you get a five followed by a six. Your number of rolls is the amount you pay, in dollars.
The second game: same, except that the stopping condition is a five followed by a five.
Which of the two games should Alice elect to play? Does it even matter? Write a program to simulate the two games and calculate their expected value.
Examples
Example 1
Input: Simulate 100,000 iterations
Output: First game expected value: 42.32, Second game expected value: 36.50
Explanation: After 100,000 simulations, these are the average number of rolls (costs) for each game.
Example 2
Input: Simulate 1,000,000 iterations
Output: First game expected value: 42.56, Second game expected value: 36.47
Explanation: After 1,000,000 simulations, these are the average number of rolls (costs) for each game.
Solution
Method 1 - Run the simulation
To find out which game Alice should play, we can simulate both games multiple times (e.g., 100,000 iterations) and compute the average number of rolls required to reach the stopping condition. The game with the lower average number of rolls is the better choice.
Approach
- Simulation:
- For each game, simulate rolling a die until the stopping condition is met.
- Record the number of rolls for each simulation.
- Repeat for a large number of iterations to obtain a reliable average.
- Compute Expected Value:
- Calculate the average number of rolls needed for each game over multiple iterations.
- Compare the averages to determine the better game.
Code
Java
public class Solution {
public static void main(String[] args) {
int numIterations = 100000;
Solution solution = new Solution();
double firstGameExpectedValue = solution.simulateFirstGame(numIterations);
double secondGameExpectedValue = solution.simulateSecondGame(numIterations);
System.out.println("First game expected value: " + firstGameExpectedValue);
System.out.println("Second game expected value: " + secondGameExpectedValue);
}
public double simulateFirstGame(int numIterations) {
double totalRolls = 0;
Random random = new Random();
for (int i = 0; i < numIterations; i++) {
int rolls = 0;
boolean gotFive = false;
while (true) {
int roll = random.nextInt(6) + 1;
rolls++;
if (gotFive && roll == 6) {
break;
}
gotFive = (roll == 5);
}
totalRolls += rolls;
}
return totalRolls / numIterations;
}
public double simulateSecondGame(int numIterations) {
double totalRolls = 0;
Random random = new Random();
for (int i = 0; i < numIterations; i++) {
int rolls = 0;
boolean gotFive = false;
while (true) {
int roll = random.nextInt(6) + 1;
rolls++;
if (gotFive && roll == 5) {
break;
}
gotFive = (roll == 5);
}
totalRolls += rolls;
}
return totalRolls / numIterations;
}
}
Python
import random
class Solution:
def simulate_first_game(self, num_iterations: int) -> float:
total_rolls = 0
for _ in range(num_iterations):
rolls = 0
got_five = False
while True:
roll = random.randint(1, 6)
rolls += 1
if got_five and roll == 6:
break
got_five = (roll == 5)
total_rolls += rolls
return total_rolls / num_iterations
def simulate_second_game(self, num_iterations: int) -> float:
total_rolls = 0
for _ in range(num_iterations):
rolls = 0
got_five = False
while True:
roll = random.randint(1, 6)
rolls += 1
if got_five and roll == 5:
break
got_five = (roll == 5)
total_rolls += rolls
return total_rolls / num_iterations
# Example usage
num_iterations = 100000
sol = Solution()
first_game_expected_value = sol.simulate_first_game(num_iterations)
second_game_expected_value = sol.simulate_second_game(num_iterations)
print(f"First game expected value: {first_game_expected_value}")
print(f"Second game expected value: {second_game_expected_value}")
Complexity
- ⏰ Time complexity:
O(n)
wheren
is the number of iterations. - 🧺 Space complexity:
O(1)
because we’re only storing the number of rolls and the averages.