14
$\begingroup$

I got this question from an interview.

A and B are playing a game of dice as follows. A throws two dice and B throws a single die. A wins if the maximum of the two numbers is greater than the throw of B. What is the probability for A to win the game?

My solution.

If $(X,Y)$ are the two random throws of A and $Z$ is the random throw of B, then the problem asks (if I guessed correctly) to compute $P(\max(X,Y)>Z)$. But how to do it? I highly appreciate your help.

$\endgroup$
2
  • $\begingroup$ Hello Sir, yes you are right. $\endgroup$
    – darda
    Commented Dec 28, 2022 at 21:32
  • 6
    $\begingroup$ Enumeration of cases, though there are some natural shortcuts that save literally going 'one, two, three...'. In short just 'fancy counting' as common with a lot of discrete problems. $\endgroup$
    – Glen_b
    Commented Dec 28, 2022 at 23:10

9 Answers 9

13
$\begingroup$

Let $V =\max(X,Y)$ and note that $V$ takes values in $\{1,2,\ldots,6\}$. We see that $V=1$ if A realises $(1,1)$, $V=2$ if it realises $(1,2), (2,2), (1,2)$ and so on. Because the dice are uniformly distributed, you can check that $P(V=1) = \frac{1}{36}$, $P(V=2) = \frac{3}{36}$, and so on, $P(V=6) = \frac{11}{36}$. To compute $P(V>Z)$ use conditional probability $$ P(V>Z) = \sum_{z=1}^6 P(V>z, Z=x) = \sum_{z=1}^6 P(V>z| Z=z)P(Z=z) = \cdots = \frac{125}{216}. $$ Note: $P(V>z | Z=z) = P(V>z)$ for all $z$, since $V$ is independent of $Z$.

$\endgroup$
0
21
$\begingroup$

Because the point to an interview question is to demonstrate your thinking, I want to emphasize two things:

  1. Finding a simple, clear, analysis using minimal calculation and straightforward notation.

  2. Explicitly identifying the rules of probability that justify the solution.

Thus, in the following, you will see repeated references to simplicity and to key concepts of probability: independence, additivity, and complementation. The hope is that following such a principled, efficient analysis and explaining it well will help get you the job in addition to merely finding the answer.


Focus first on the simplest part of the situation: B's throw. To win, A has to beat B's value and A has two independent tries to do so.

This framing of the question suggests we break down the analysis according to B's possibilities. Again, in pursuit of the simplest approach, consider the chance that $A$ loses after B throws some value $b.$ To lose, A must throw two values between $1$ and $b$ inclusive. Since each of those events has a chance of $b/6$ and because the events are independent, A loses with probability $(b/6)^2$ in such a case.

Because the chance of throwing $b$ was $1/6$ and A's throws are independent of B's throw,

the event "B throws $b$ and A loses" has a probability of $1/6\times (b/6)^2 = b^2/6^3.$

This is why computing the chance of a loss is simpler than the chance of a win: all we need do is multiply.

All that remains to do is sum these probabilities, because these events exhaust all the possible outcomes and are non-overlapping. The answer therefore can be expressed as

$$\Pr(\text{A loses}) = \frac{1}{6^3}\left(1^2+2^2+3^2+4^2+5^2+6^2\right) = \frac{91}{216}.$$

Do not lose sight of the question: it asks for the chance that A wins. That, of course, is the complement of the chance of losing,

$$\Pr(\text{A wins}) = 1 - \frac{91}{216} \approx 57.87\%.$$

$\endgroup$
9
$\begingroup$

Consider the probability of its complementary event $\{\max(X, Y) \leq Z\}$:
\begin{align} P(\max(X, Y) > Z) = 1 - P(\max(X, Y) \leq Z) = 1 - P(X \leq Z, Y \leq Z). \tag{$*$} \end{align} The term $P(X \leq Z, Y \leq Z)$ can be evaluated by the law of total probability and the independence assumption: \begin{align} & P(X \leq Z, Y \leq Z) = \sum_{i = 1}^6P(X \leq Z, Y \leq Z, Z = i) \\ =& \sum_{i = 1}^6 P(X \leq i, Y \leq i, Z = i) \\ =& \sum_{i = 1}^6 P(X \leq i)P(Y \leq i)P(Z = i) \\ =& \sum_{i = 1}^6 \frac{i}{6} \times \frac{i}{6} \times \frac{1}{6} = \frac{1}{216} \times \frac{1}{6} \times 6 \times 7 \times 13 = \frac{91}{216}. \\ \end{align}

Plugging this back to $(*)$ to get \begin{align} P(\max(X, Y) > Z) = 1 - \frac{91}{216} = \frac{125}{216}. \end{align}

$\endgroup$
0
4
$\begingroup$

I will take a less formal approach, in order to illustrate my thinking.

My first instinct was to visualize the usual $6 \times 6$ array of outcomes $(X,Y)$ of $A$'s dice rolls, and looking at when the larger of the two values is less than or equal to some value:

$$\begin{array}{cccccc} (1,1) & (2,1) & (3,1) & (4,1) & (5,1) & (6,1) \\ (1,2) & (2,2) & (3,2) & (4,2) & (5,2) & (6,2) \\ (1,3) & (2,3) & (3,3) & (4,3) & (5,3) & (6,3) \\ (1,4) & (2,4) & (3,4) & (4,4) & (5,4) & (6,4) \\ (1,5) & (2,5) & (3,5) & (4,5) & (5,5) & (6,5) \\ (1,6) & (2,6) & (3,6) & (4,6) & (5,6) & (6,6) \\ \end{array}$$ It's intuitively clear from this diagram that the number of ordered pairs whose maximum is at most $k$ is $k^2$, for $k \in \{1, 2, 3, 4, 5, 6\}$. This is because geometrically, the set of such outcomes are arranged in a series of nested squares in the array. So it follows that for each of the six equiprobable outcomes for $B$'s die roll $Z \in \{1, 2, 3, 4, 5, 6\}$, $A$ will lose with probability $z^2/6^2$, hence the total probability of $A$ losing to $B$ is simply $$\frac{1^2 + \cdots + 6^2}{6^2(6)} = \frac{6(7)(13)}{6} \cdot \frac{1}{6^3} = \frac{7(13)}{6^3}.$$ Hence $A$ wins with probability $1 - \frac{7(13)}{6^3} = \frac{125}{216}$.

This line of reasoning is what I would use if I had no access to pencil or paper and had to answer the question mentally, reserving the computational part to the very end.

$\endgroup$
4
$\begingroup$

We need to know two things to calculate Player A's overall chances of winning: 1) his odds of rolling each score and 2) his odds of winning with that score.

If you visualize player A's possible outcomes on a 6x6 grid, it is easy to see that they form a series of bands (for lack of a better word), and we can count them and divide by the total number of outcomes to get the probabilities for each.

enter image description here

It's also fairly easy to see that the number of occurrences of each outcome can be represented as 2n-1 (because it's two sides of a square of size n with the overlapping corner being -1), and the total number of outcomes is 6 squared, so the probability of each of A's possible outcomes is

enter image description here

Player B's outcomes are evenly distributed: 1/6 (or 16.7%) for each number 1 through 6. Since Player A has to BEAT Player B's roll, we can find his chance of winning by summing the probabilities of each of B's possible outcomes that are less than his outcome. That is, if he scores 1, none of B's outcomes are less, meaning that he can beat 0% of B's possible scores. A score of 2 can beat just one of B's possible scores, or 16.7%, and a score of 3 wins in two out of six scenarios (33.3%). This can be represented as

enter image description here enter image description here

We can multiply these probabilities together (A's chance of rolling a specific number vs his chance of winning with that number) to obtain his overall chances of winning:

enter image description here

57.9%, or 125/216.

The formula for the overall chance of winning can be derived by multiplying the two previously given formulae:

enter image description here or enter image description here

giving the same table of values:

enter image description here

We can represent the summation like this:

enter image description here

and this does yield the expected 125/216. Just a slightly different way to think about it, and the demonstration of it can quickly be setup in a spreadsheet in just a minute or two, if they were letting you use a computer, or sketched out just as quickly.

$\endgroup$
3
$\begingroup$

Let's first code up a simulation to see where we should head, and then let's come at this theoretically. In R...

sims <- replicate(1000000, {
  
  A <- max(sample(1:6, replace=T, size=2))
  B <- sample(1:6, size=1)
  
  ifelse(A>B, 'A WINS', 'B WINS')
})

prop.table(table(sims))
sims
  A WINS   B WINS 
0.578675 0.421325 

We can be confident in these results up to the second decimal place, so A wins about 57% of the time. For an interview, I think this is a sufficiently good answer. Let's analyze

Let $B$ be the roll form player B and let $A = \max(A_1, A_2)$ be the number rolled for player A which, which is the maximum of the two rolls. Luckily, we don't have to do any math to get the distribution of $A$, we can just do some logcial thinking.

$A=1$ when both $(A_1 = 1, A_2=1)$. So out of a possible 36 outcomes, $A=1$ can only happen 1 way. So $P(A=1)=1/36$. Similarly, $A=1$ when either $(A_1=1, A_2)=2$ or $(A_1=2, A_2=1)$ or $(A_1=2, A_2=2)$. That's 3 outcomes out of 36 so $P(A=2) = 3/36$. We can continue on like this to get the entire distribution. Using R for some help...

library(tidyverse)

crossing(
  A1 = 1:6,
  A2 = 1:6
) %>% 
  mutate(A = pmax(A1, A2)) %>% 
  count(A)

# A tibble: 6 × 3
      A     n      p
  <int> <int>  <dbl>
1     1     1 0.0278
2     2     3 0.0833
3     3     5 0.139 
4     4     7 0.194 
5     5     9 0.25  
6     6    11 0.306 

Do you think you can take it from here?

To compute $P(A>B)$ we need to know the joint distribution of $(A=a, B=b)$. Because the two random variables are independent, $P(A=a, B=b) = P(A=a)P(B=b)$. A can only win when their roll exceeds $B$ so we need to compute $P(\text{A Wins}) = \sum_{b=1}^{b=5} \sum_{a=b+1}^{6} P(A=a, B=b)$. The sum turns out to be approximately 0.579, so $P(\text{A Wins}) = 57.9\%$. If you wanted this as an exact answer, simply do the arithmetic.

$\endgroup$
0
3
$\begingroup$

Here's a fairly simple way — based on a symmetry argument — to get the solution for dice with $n$ sides, for arbitrarily large $n$, without having to consider up to $n$ different cases. Instead, the number of cases we need to consider is only proportional to the number of dice involved (i.e. three, in your example).

First note that, if we knew (and thus conditioned the problem on) that no two dice were tied for the highest roll, then the answer would clearly be $\frac23$. This is because each of the three dice rolled is equally likely to be the one that rolls the highest number, and player A, with two dice for B's one, is twice as likely to own this highest rolling die as B.

However, to get the correct answer for your problem, we do need to consider the possibility of ties. So let's break up the problem into cases based on how many dice are tied for the highest roll:

  • The probability that all three dice are tied for highest is clearly $p_3 = \frac1{n^2}$ (where, again, $n = 6$ is the number of sides on the dice).

  • The probability that exactly two of the three dice are tied for highest is a bit harder to calculate, but a moment's thought shows that it must equal the probability that there is a two-way tie (but not a three-way one) divided by two (since half the time the two dice that are tied will roll lower than the third one that isn't). By applying the inclusion-exclusion principle we can see* that the probability of getting a two-way tie is $\frac{3n - 3}{n^2}$, and thus the probability of a two-way tie for the highest roll is half of that, i.e. $p_2 = \frac{3n - 3}{2n^2}$.

  • Finally, the probability that there is no tie for the highest roll, i.e. that a single die rolls the unique highest result, is of course $p_1 = 1 - p_2 - p_3 = 1 - \frac{3n - 3}{2n^2} - \frac1{n^2} = \frac{2n^2 - 3n + 1}{2n^2}$.

Now, by the rules of your game:

  • If all three dice are tied, player B always wins.
  • If two dice are tied for highest, player A wins if they have both of these dice, i.e. with probability $\frac13$.
  • If there is a single highest die, player A wins if they have it, i.e. with probability $\frac23$.

Thus, the overall probability of player A winning your game is $$p = \frac13 p_2 + \frac23 p_1 = \frac{3n - 3}{6n^2} + \frac{4n^2 - 6n + 2}{6n^2} = \frac{4n^2 - 3n - 1}{6n^2}.$$

In particular, for $n = 6$, $p = \frac{4\cdot36 - 3\cdot6 - 1}{6\cdot36} = \frac{144 - 18 - 1}{216} = \frac{125}{216} ≈ 0.5787.$


*) Specifically, label the dice as $a$, $b$ and $c$, and note that there are three pairs of dice — $(a,b)$, $(a,c)$ and $(b,c)$ — that can be tied. Let $T_{a,b}$, $T_{a,c}$ and $T_{b,c}$ be the events where each of these pairs is tied, and note that $$P(T_{a,b}) = P(T_{a,c}) = P(T_{b,c}) = \tfrac1n,$$ while $$P(T_{a,b} \cap T_{a,c}) = P(T_{a,b} \cap T_{b,c}) = P(T_{a,c} \cap T_{b,c}) = P(T_{a,b} \cap T_{a,c} \cap T_{b,c}) = \tfrac1{n^2},$$ as any two pairs being tied implies that all three are. Thus, by the inclusion–exclusion principle, the probability of getting at least a two-way tie is $$\begin{aligned} P(T_{a,b} \cup T_{a,c} \cup T_{b,c}) &= P(T_{a,b}) + P(T_{a,c}) + P(T_{b,c}) \\ &\qquad - P(T_{a,b} \cap T_{a,c}) - P(T_{a,b} \cap T_{b,c}) - P(T_{a,c} \cap T_{b,c}) \\ &\qquad + P(T_{a,b} \cap T_{a,c} \cap T_{b,c}) \\ &= 3 \tfrac1n - 3 \tfrac1{n^2} + \tfrac1{n^2} = \tfrac{3n-2}{n^2}. \end{aligned}$$ But the number we actually want is the probability of getting an exactly two-way tie, i.e. $$P(T_{a,b} \cup T_{a,c} \cup T_{b,c}) - P(T_{a,b} \cap T_{a,c} \cap T_{b,c}) = \tfrac{3n-3}{n^2}.$$

$\endgroup$
2
$\begingroup$

To add to the other answers, while this isn't what you were exactly asking for, this is a good place to highlight that this type of problem is the exact type where numerical simulation is a powerful tool. A challenging mathematical problem is reduced to a very simple numerical problem. Here is some python code which simulates this game 1000 times and estimates the probability of A winning as the proportion of games A wins out of these 1000.

from numpy import random

def play_game(): 
    dieA_1 = random.choice([1,2,3,4,5,6])
    dieA_2 = random.choice([1,2,3,4,5,6])
    A_num = max(dieA_1, dieA_2)
    B_num = random.choice([1,2,3,4,5,6])
    
    A_wins = A_num > B_num 
    return A_wins

num_A_wins = 0 
for iter in range(1000): 
    A_wins = play_game()
    num_A_wins += A_wins  

print(f"probability of A winning is {num_A_wins/1000}")

Output:

probability of A winning is 0.582
$\endgroup$
2
  • 3
    $\begingroup$ In this case, the simulation takes more computation and isn't appreciably simpler than a direct calculation of all possible cases. It's a stretch to characterize this as an "extremely challenging mathematical problem." Thus, to succeed in proposing a simulation-based solution in an interview, it would be important to reframe the question in greater generality, perhaps positing dice with more sides or using more dice for each player. $\endgroup$
    – whuber
    Commented Dec 31, 2022 at 14:16
  • 2
    $\begingroup$ (1) The amount of computation is pretty trivial on a decent computer -- you can run this in less than a second (2) Looking at the math above, it's quite a lot simpler (3) I didn't suggest it from the perspective of an interview, just from the perspective of getting the answer. $\endgroup$
    – gtoques
    Commented Dec 31, 2022 at 17:13
0
$\begingroup$

Since this is an interview question, simple thinking and an approximate answer is best. Three dice are thrown, the biggest number wins. The probability to win is $1/3$ for each of the die. Player A has two dice, and so wins in $2/3$ of the cases. Done.

This is a slight over-estimate since whenever player B throws a 6, player B automatically wins. Other answers give ideas on how to calculate more accurately. But somehow that's not so much fun, is it.

$\endgroup$
3
  • 4
    $\begingroup$ Approximate seat-of-the-pants estimation and quick, "good enough" answers are valuable. However, over the centuries, we have learned the hard way that "simple thinking" about probability questions often leads to the wrong answer. Google "probability paradox" for many examples. Thus, this reasoning serves as a quick reality check, but does not suffice. $\endgroup$
    – whuber
    Commented Dec 30, 2022 at 14:18
  • 1
    $\begingroup$ @whuber whether it suffices or not depends on the desired accuracy. Unless of course you think my reasoning is wrong (which it is not, I am sure). I am a physicists, stumbling across this question from the physics stackexchange. Rest assured this answer is perfectly adequate in any interview of a physicists' position... $\endgroup$
    – rfl
    Commented Dec 30, 2022 at 14:29
  • 3
    $\begingroup$ That's fine. But I suspect such an answer would not get one hired into any kind of data analysis position. One difference between the two professions is that most physical problems involve such large numbers that such approximations can be extremely accurate. Some -- a minority, but an important minority -- of problems in probability and statistics involve relatively small numbers where those approximations can be erroneous. From this perspective, it comes down to whether you view (or can demonstrate) 6 as being large or not. $\endgroup$
    – whuber
    Commented Dec 30, 2022 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.