ML Interview Q Series: Estimating True Coin Flip Winners Using Conditional Probability
Browse all the Probability Interview Questions here.
There are 100 players, each tossing a coin once for a chance to win. If they get heads on the first flip, they genuinely win. If they get tails and then flip heads on the second try, they will falsely claim a win. If both flips are tails, they admit to losing. By the end, 30 people say they have won. How many of those are likely to be true winners?
Comprehensive Explanation
The problem deals with probability and conditional reasoning. Each student has a fair coin. The first flip determines whether they truly win (if it is heads). If that first flip is tails, they take a second flip, and if that second flip is heads, they lie about winning even though they really lost the main game condition. If the second flip is tails, they truthfully admit they lost. We want to figure out, from the 30 who claim victory, how many are expected to have actually won on their first flip.
Mathematical Setup
A single student either genuinely wins by flipping heads initially or pretends to win by getting tails on the first flip and heads on the second. We define these probabilities:
P(first flip heads) = 1/2, which is the probability of genuinely winning. P(first flip tails, second flip heads) = 1/2 * 1/2 = 1/4, which corresponds to losing the main chance but then lying about the outcome. P(says they have won) = 1/2 + 1/4 = 3/4, which is the total probability that a student ends up saying "I won."
When 30 students out of 100 claim a win, we consider how many of those claimed wins correspond to true winners.
Detailed Probability Reasoning
To find the expected count of genuine winners among those who say they won, we use Bayes’ theorem in essence. The central formula is:
Where:
P(Winner) is the probability of actually winning on the first flip, which is 1/2.
P(Claimed Winner | Winner) is the probability that a true winner (heads on first flip) would claim they won, which is 1.
P(Claimed Winner) is the total probability of anyone who ends up saying they won, which is 1/2 (true winners) plus 1/4 (those who got tails first but heads second and lie), giving 3/4.
Substituting values:
P(Winner | Claimed Winner) = (1 * 1/2) / (3/4) = (1/2) / (3/4) = 2/3.
This means two-thirds of those who claim to have won are in fact legitimate winners from the first flip. Out of the 30 who report a win, 2/3 of 30 is 20. So we expect 20 genuine winners.
Potential Implementation Example in Python
import numpy as np
np.random.seed(42)
num_students = 1000000
first_flip = np.random.randint(0, 2, size=num_students) # 0 for tails, 1 for heads
second_flip = np.random.randint(0, 2, size=num_students)
# True winners: first_flip == 1
# Liars: first_flip == 0 and second_flip == 1
says_win = (first_flip == 1) | ((first_flip == 0) & (second_flip == 1))
true_win = (first_flip == 1) # Only first flip heads
# Among those who claimed win, check proportion of true winners
claimed_win_indices = np.where(says_win)[0]
true_winners_among_claimed = np.sum(true_win[claimed_win_indices])
proportion = true_winners_among_claimed / len(claimed_win_indices)
print("Proportion of genuine winners among those who claim a win:", proportion)
This simulation would yield a result close to 0.666..., confirming our analytical reasoning.
Potential Pitfalls
A common mistake is to assume everyone who claimed "I won" truly won, ignoring the second-flip lie scenario. Another pitfall is to neglect the role of conditional probability when analyzing how many real winners exist among those who claim to have won.
Follow-up Questions
If the coin were biased, how would the analysis change?
The essential structure remains the same, but the probabilities would shift based on the coin’s bias. Suppose the probability of heads is p. Then the probability of a true win on the first flip becomes p. The probability of losing the first flip but lying by flipping heads on the second is (1 - p)*p. Hence the total probability of claiming “I won” would be p + (1 - p)*p = p + p - p^2 = 2p - p^2. Bayes’ theorem would then adjust accordingly.
What if the second heads outcome did not cause a lie but something else?
If a different behavior occurred on the second heads instead of lying, we would redefine the events. For instance, if a second heads indicated a different type of response, the proportion of those claiming they won would change. The crux is always to carefully identify how each flip outcome translates to a reported result and then apply the same Bayesian reasoning.
How would results be affected if students continued flipping until heads appeared?
In that scenario, the probability of eventually hitting heads is 1 if the coin is fair, which complicates the definition of “true win” unless a specific rule is stated about which flip counts for the genuine win. The structure of the question would need to define at which flip the game is truly decided. Probability analyses would become more elaborate but the fundamental conditional probability approach remains the same.
Could we solve this without explicitly using Bayes’ theorem?
Yes. One can reason directly with proportions: For every 100 students, on average 50 truly win on the first flip, 25 lose the first flip but get heads on the second (thus lying about a win), and 25 lose both flips. Among those who say they won, 50 + 25 = 75 total claim a win, of which 50 are genuine. That ratio is 50 out of 75, or 2/3, which matches the Bayesian calculation. This direct reasoning helps corroborate the final estimate.
Below are additional follow-up questions
How would the result change if students were allowed to flip the coin three or more times under similar rules?
In a scenario with multiple flips, we need to carefully define the victory and lying conditions for each additional flip. For instance:
True Win could still be defined as obtaining heads on the first flip only.
A subsequent heads (on the second, third, or further flips) might trigger a lie.
Multiple consecutive tails might lead to a truthful loss.
When more flips are introduced, each student can have multiple “paths” to eventually claiming or not claiming a win. This enlarges the probability tree. The core principle of analyzing who is telling the truth about their win remains the same: we enumerate all possible ways in which students can end up claiming victory (some of which are legitimate and some not), compute their corresponding probabilities, and then condition on the claim.
A potential pitfall is to lose track of the probabilities associated with each additional coin toss or to incorrectly assume outcomes are mutually exclusive when they are not. In real-life application, the complexity grows exponentially with each additional flip, so carefully enumerating states (such as the Markov chain approach) or systematically applying total probability rules would be essential.
What if, instead of lying on the second flip only, students always lied whenever they eventually encountered a heads after the first tails?
This variation means that once the student fails the first flip, any subsequent flip that lands heads leads them to claim a win. In other words, some students are determined to claim a win as soon as they see a head at any point after losing the first flip.
From a probability perspective, a student who loses the first flip has an ongoing chance each subsequent flip to get a head and then lie. The chance of eventually flipping heads in repeated independent attempts is 1 if the coin is fair (or approaches 1 for a biased coin if p > 0). This would mean almost everyone who fails their first flip but keeps flipping would eventually produce a heads and thus lie about the win.
A subtlety arises if there is a finite upper limit on the number of flips allowed. If it is infinite (or extremely large), eventually each student with an initial tails is almost certain to see at least one head and thereby lie. This drastically inflates the proportion of people claiming a win, making the fraction of genuine winners among claimants smaller. In practice, if we observe a certain fraction of declared winners, we would again apply conditional probability but note that the total probability of “claimed win” might be significantly higher than in the original two-flip scenario.
Could we have a scenario where some fraction of students do not follow the instructions strictly (e.g., they randomly claim win or loss)?
Real-world settings might have participants who do not perfectly comply with the rules. A fraction of them might randomly report outcomes or become confused about instructions. This noncompliance introduces noise into the data and causes any straightforward probability-based calculation to deviate from the ideal.
One approach to handle this is to model a compliance parameter c (ranging from 0 to 1) that indicates the probability a student follows the prescribed rule. Then, with probability 1 - c, the outcome is random or otherwise unaligned with the instructions. The resulting analysis would weight the claims by c to represent the portion of participants who truly follow the coin toss logic. However, identifying the true value of c might require additional data or assumptions, leading to potentially large uncertainty intervals in the final estimates of genuine winners.
What if the group size was not 100 but very large or very small?
Very Large Group (e.g., millions of students): The law of large numbers tells us that the observed proportion of claimants will likely be close to the expected theoretical probability (3/4 in the simple two-flip scenario). The ratio of true winners among the claimants will also approach 2/3. In large samples, the variance decreases, and the estimated count of genuine winners stabilizes around the theoretical expectation.
Very Small Group (e.g., only 5 students): Random fluctuations become significant. The theoretical ratio might still be 2/3, but due to high variance in such small samples, we could see scenarios where almost everyone claims a win or almost nobody does. In that case, the expectation formula still holds on average, but any single instance might deviate substantially.
Is there a possibility that students could coordinate among themselves to trick the observer about how many wins occurred?
If students collude, they might decide on a predetermined fraction to claim a win, regardless of coin toss outcomes. This group-level strategy breaks the individual independence assumption. The analysis that each student’s probability of claiming a win is 3/4 relies on them flipping fairly and lying or telling the truth based on the outcome alone.
When coordination occurs, the reported fraction of winners might no longer reflect the independent probabilities we derived. To detect such collusion, one might track more data (like the distribution of flips, or repeated experiments, or cross-checking self-reported outcomes with additional tests). Another pitfall is to assume that just because the overall data matches an expected ratio, there was no collusion—coordinated lying can still coincidentally match the theoretical average in some cases, though that is less likely without careful planning.
How would the analysis be affected if students had different motivations or utilities associated with lying vs. telling the truth?
In the standard formulation, we assume students automatically lie on the second flip if it is heads. But in more realistic behavioral models, there could be a cost or benefit to lying, and each student’s decision might differ depending on their perceived payoff. If a student’s payoff or penalty for lying is greater than that for truth-telling, they might not lie even if they see a head on the second flip. Conversely, if lying is heavily rewarded or has minimal consequences, more students might falsely report a win.
In such utility-based models, we must incorporate each student’s utility function. The probabilities of lying or telling the truth become functionally dependent on how individuals weigh the potential gains or losses. This transforms the analysis into a game-theoretic or decision-theoretic problem, requiring additional assumptions on rational behavior, risk preferences, or extrinsic motivations. The final ratio of genuine winners among claimants would be determined by equilibrium strategies rather than simple coin probabilities, and one must carefully solve for that equilibrium given the known payoffs.
Could a real-world measurement error affect how we interpret the final result?
Measurement or recording errors could lead to miscounting how many said they won. For example, if some individuals who said “lost” were incorrectly tallied as “won” or vice versa, the final tally might deviate from the true fraction. In practice:
The fraction who claim “win” might be systematically inflated or deflated by a certain bias factor.
A random error in counting might introduce noise around the observed fraction.
To mitigate these issues, one would use classical measurement error models, possibly employing repeated audits, double-checking recorded outcomes, or building confidence intervals around the expected fraction of genuine winners. Failing to account for even small systematic error can lead to incorrect estimates, especially if the sample size is not large enough to average out random miscounts.
Could the lying condition occur in other ways, for instance, lying only if the second flip is tails?
That variation would invert the logic: maybe a student who fails the first flip but sees a second flip that is tails decides to lie (saying they won out of frustration or other reasons), while a second-heads leads them to truthfully admit some different outcome. The main idea is that each flip outcome modifies the student’s claim according to a predefined but distinct rule.
Regardless of the exact rule, you would calculate:
The probability distribution of each first and second flip result.
The student’s final claim (win or lose) in each scenario.
The probability of each final claim, thus obtaining the fraction who claim “win.”
The subset of that fraction who genuinely meet the “true winner” condition.
The pattern of lying might be less intuitive or more complex, but the core process of enumerating probabilities and applying conditional probability remains the same. The biggest pitfall is incorrectly tracking each scenario or forgetting one branch of the decision tree, leading to erroneous estimates of the final fraction of true winners.