Untitled — Python Coding — Nerchuko Academy

First to Roll a Six

MEDIUM

Amy and Brad take turns rolling a fair six-sided die. Whoever rolls a "6" first wins the game. Amy starts by rolling first.

What is the theoretical probability that Amy wins? (Conceptual/Mathematical)
Implement a simulation in Python to estimate this probability empirically.

Simulation Goal:

Your Python simulation should run a large number of game rounds (e.g., 10,000 or 100,000) and calculate the proportion of rounds won by Amy. This estimated probability should be close to the theoretical probability.

Function Signature for Simulation (Python):

import random

class Solution:
    def simulate_dice_game(self, num_simulations: int) -> float:
        # Your simulation code here
        pass
    
    # Optional: helper function for a single game round
    # def play_one_round(self) -> bool: # Returns True if Amy wins, False otherwise
    #     pass

Solution: Dice Game Probability & Simulation

The Game: Amy and Brad take turns rolling a standard six-sided die. The first person to roll a "6" wins. Amy goes first.

The Question: We want to figure out Amy's chances of winning. We'll do this in two ways: by calculating the exact mathematical probability and by running many simulated games in Python to see how often she wins.

Part 1: Theoretical Probability that Amy Wins

Let P(A wins) be the probability Amy wins. Let P(roll 6) = p = 1/6. Let P(not roll 6) = q = 5/6.

Amy can win on her first roll. Probability = p.

Or, Amy fails (q), Brad fails (q), then Amy wins on her second turn (which is the 3rd roll of the game). Probability = q * q * p = q²p.

Or, Amy fails (q), Brad fails (q), Amy fails (q), Brad fails (q), then Amy wins on her third turn (5th roll). Probability = q⁴p.

And so on. The probability Amy wins is the sum of these probabilities:

P(Amy wins) = p + q²p + q⁴p + q⁶p + ...

This is a geometric series: p * (1 + q² + (q²)² + (q²)³ + ...)

The sum of an infinite geometric series a + ar + ar² + ... is a / (1 - r), where |r| < 1. Here, the first term 'a' (of the series in parentheses) is 1, and the common ratio 'r' is q². So, the sum of (1 + q² + (q²)² + ...) = 1 / (1 - q²).

Therefore, P(Amy wins) = p * [1 / (1 - q²)] = p / (1 - q²).

Substitute p = 1/6 and q = 5/6:

P(Amy wins) = (1/6) / (1 - (5/6)²)
= (1/6) / (1 - 25/36)
= (1/6) / ((36-25)/36)
= (1/6) / (11/36)
= (1/6) * (36/11)
= 36 / (6 * 11)
= 6 / 11

So, the theoretical probability that Amy wins is 6/11 (approximately 0.54545...).

Part 2: Python Simulation to Estimate Probability

We'll simulate the game many times and count how often Amy wins.

import random

class Solution:
    def _roll_die(self) -> int:
        """Simulates rolling a fair six-sided die."""
        return random.randint(1, 6)

    def _play_one_round(self) -> bool:
        """
        Simulates one round of the game.
        Returns True if Amy wins, False if Brad wins.
        """
        while True:
            # Amy's turn
            if self._roll_die() == 6:
                return True  # Amy wins
            
            # Brad's turn
            if self._roll_die() == 6:
                return False # Brad wins (Amy loses)

    def simulate_dice_game(self, num_simulations: int) -> float:
        """
        Simulates the dice game for a given number of rounds
        and returns the estimated probability of Amy winning.
        """
        if num_simulations <= 0:
            raise ValueError("Number of simulations must be positive.")

        amy_wins_count = 0
        for _ in range(num_simulations):
            if self._play_one_round():
                amy_wins_count += 1
        
        return amy_wins_count / num_simulations

# Example Usage of Simulation:
# sol = Solution()
# num_trials = 100000
# estimated_prob_amy_wins = sol.simulate_dice_game(num_trials)
# print(f"After {num_trials} simulations:")
# print(f"Estimated probability Amy wins: {estimated_prob_amy_wins:.5f}")
# print(f"Theoretical probability Amy wins: {6/11:.5f} (which is {6/11})")

Complexity Analysis (Simulation):

Let K be num_simulations.

Time Complexity: O(K) on average. Each game round takes a constant number of rolls on average (related to the geometric distribution for waiting for a 6). Since the probability of rolling a 6 is 1/6, the expected number of rolls until a 6 is 6. The game ends much quicker than that because there are two players. The average number of turns per game is small and constant. So, K simulations take K * (avg_rolls_per_game) which is O(K).

Space Complexity: O(1), as we only use a few variables to keep track of counts and simulate rolls.

Key Takeaways for Interviews:

Theoretical First (If Possible): If you can derive the theoretical probability quickly (as with this geometric series), it's impressive to do so. It shows strong analytical skills.
Simulation Logic:
- Clearly define how a single round of the game is played, especially the turn-based nature.
- Use random.randint(1, 6) or random.choice([1,2,3,4,5,6]) for die rolls.
- Structure the simulation with a loop for many trials.
Clarity and Modularity: Breaking the simulation into a helper function for a single round (like _play_one_round) makes the code cleaner and easier to understand.
Law of Large Numbers: Mention that the accuracy of the simulation improves with a larger number of trials.
Seed for Reproducibility (Optional): For testing or debugging, you might mention setting random.seed(), but for a pure estimation, it's not strictly needed in the final function.