Combinatorics approach for player $A$ and $B$ rolling a 20-sided die

Question

Problem: Consider players $A$ and $B$ rolling a 20-sided die. Player $B$ is allowed to re-roll. Assume that player $B$ will re-roll a single time if his first dice roll is $\leq 10$, and will not re roll if their first dice roll is $> 10$. The comparison is conducted between the last roll of $B$ (not the max roll of player $B$) with $A$. Let $RR$ and $NR$ denote the event of player $B$ rerolling and not rerolling. I want to find the probability of $NR$ occuring given that the first player rolls a higher number than the second player using a combinatorics approach.

Denote $A$ and $B$ as the random variables for the outcome of $A$ and $B$'s tosses. First, I computed the case where player $B$ isn't allowed to reroll. The result of this case is used later. For this case where $B$ can't re-roll, consider the possibilities in which $A > B$ is satisfied:

For $B = 1$, there are 19 possibilities for $A$.

For $B = 2$, there are 18 possibilities for $A$.

... For $B = 19$, there is 1 possibility for $A$.

So the number of possibilities for $A > B$ is $\frac{19 \cdot 20}{2} = 190$ when $B$ isn't allowed to re-roll. .

As stated previously in words, I want to find $$ P(NR | A > B) $$

combinatorically. From a pure probability approach, I found that the probability is $\frac{9}{28}$ and confirmed this via monte carlo using 10 million trials.

At first, I sought the number of cases such that $A > B$. To do this, I considered the disjoint events $NR$ and $RR$. For the event $NR$, i.e., where player $B$ rolls once and his outcome is $> 10$, there are 45 cases where $A > B$. For $B = 11$, we have $9$ cases, ...., for $B = 19$, we have 1 case. So we have $\frac{9 \cdot 10}{2} = 45$ cases.

Then I considered the event $RR$, i.e., where player $B$ rolls a $\leq 10$ on the first toss and rolls again. This is effectively the same problem as the first problem I did in this post. Here, player $B's$ outcome can be $\in \{1, \ldots, 20\}$. As we saw at the beginning of this post, there are $190$ cases in which $A > B$.

So my first inclination was that $$ P(NR | A > B) = \frac{45}{45 + 190} = \frac{45}{235} $$

where the denominator is the sum of the number of $A > B$ cases in the two disjoint events $RR$ and $NR$.

But this probability is smaller than $\frac{9}{28}$, so it seems I may have overcounted or possibly undercounted somewhere.

It seems it is the the $RR$ case in which I overcounted the number of cases with $A > B$. In particularly, it seems that I may be duplicately counting the cases where $A > B \cap B \in \{11, \ldots, 19\}$, since I already counted this in the event $NR$. But it's not clear to me why this is overcounting when I defined $RR$ and $NR$ to be disjoint. Nevertheless, if we operate on this assumption that this did in fact overcount the cases where $B \in \{11, \ldots, 19\}$, then that means the number of cases where $A > B$ should be reduced by 45.

So now our result is

$$ P(NR | A > B) = \frac{45}{45 + 190} = \frac{45}{190} $$

But this result is still not correct, and does not match the pure probability approach and monte carlo. Originally, I thought this problem would be simple from a combinatorics perspective, but now I am confused why my thought process doesn't work.

What is wrong with my approach?

Answer 1

First, I will provide the way I would go about computing the desired probability without regard to the method of solution. The key is to use Bayes' theorem: $$\Pr[NR \mid A > B] = \frac{\Pr[A > B \mid NR]\Pr[NR]}{\Pr[A > B]}.$$ Given that no reroll occurred, the set of outcomes for $B$ is $\{11, 12, \ldots, 20\}$, each with probability $1/10$. If $B = b$, then $\Pr[A > B \mid B = b] = \frac{20 - b}{20}$, hence $$\Pr[A > B \mid NR] = \sum_{b=11}^{20} \Pr[A > b]\Pr[B = b \mid NR] = \sum_{b=11}^{20} \frac{20 - b}{20}\cdot \frac{1}{10} = \frac{9}{40}.$$ The probability of the event $NR$ is simply $\Pr[B > 10] = \frac{1}{2}$.

The denominator, which is the marginal probability of $A > B$, is not $19/40$, which was the calculation when $B$ was not allowed to reroll. By the law of total probability, $$\Pr[A > B] = \Pr[A > B \mid NR]\Pr[NR] + \Pr[A > B \mid RR]\Pr[RR].$$ The first term is the same as the numerator we calculated earlier. For the second term, the probability $$\Pr[A > B \mid RR] = \sum_{b=1}^{20} \Pr[A > b]\Pr[B = b \mid RR] = \sum_{b=1}^{20} \frac{20 - b}{20} \cdot \frac{1}{20} = \frac{19}{40},$$ which is the original calculation--this is because if $B$ did reroll, then the outcomes and their probabilities are the same as if $B$ was never allowed to reroll in the first place. But now we have to also take into account $\Pr[RR] = \frac{1}{2}$. So our desired probability is $$\Pr[NR \mid A > B] = \frac{\frac{9}{40} \cdot \frac{1}{2}}{\frac{9}{40} \cdot \frac{1}{2} + \frac{19}{40} \cdot \frac{1}{2}} = \frac{9}{28}.$$

---

The problem with your approach is that your outcomes are not equiprobable, so you cannot simply add the number of outcomes as you did. You have $45$ outcomes in which $A > B$ given $NR$, but these outcomes are out of a total conditional set of outcomes of size $20 \cdot 10 = 200$, whereas in the case that event $RR$ occurred, the total number of outcomes is $20 \cdot 20 = 400$. Therefore, your calculation must be modified to weight the outcomes accordingly: $$\frac{\frac{45}{200}}{\frac{45}{200} + \frac{190}{400}} = \frac{9}{28}.$$ In essence, you have intuitively applied Bayes' theorem in your reasoning but you applied it incorrectly.

---

To see how you would do this calculation if $\Pr[NR] \ne \Pr[RR]$, it is immediately obvious with Bayes' theorem. But your "combinatorial" or enumerative approach requires more subtlety. The reason your approach could even be adjusted/weighted at all was because it so happened that the criterion for $B$ to reroll is such that the probability of a reroll is equal to the probability of no reroll. So we give an example where this is not the case by modifying the criterion.

Suppose $B$ decides instead to reroll if the first roll is less than or equal to $7$. Then in the case where there is no reroll, there are $13(12)/2 = 78$ desired outcomes where $A$ outrolls $B$, out of a possible $13(20) = 260$ outcomes. If there is a reroll, then as before, there are $190$ desired outcomes where $A$ outrolls $B$ out of a possible $20(20) = 400$ outcomes. But because the probability of reroll is $7/20$ and no longer the same as the probability of no reroll which is $13/20$, the probability of no reroll given $A$ outrolled $B$ is now $$\frac{\frac{78}{260} \frac{13}{20}}{\frac{78}{260} \frac{13}{20} + \frac{190}{400} \frac{7}{20}} = \frac{156}{289}.$$

Answer 2

I think, but I am not sure, that the problem concerns the following game:

"$A,B$ are tossing a fair $20$ sided die. $A$ takes whatever value comes up but $B$ must toss again if the first value was $≤10$ at which point only the second value $B$ gets counts. Given that $A$ got a higher roll than $B$, what is the conditional probability that $B$ did not roll twice?"

If so, this is a routine application of Bayes' Theorem.

Note that if $B$ gets $>10$ on the first roll then the probability that $A$ wins is given by $$\frac 1{10}\times \frac 9{20}+\frac 1{10}\times \frac 8{20}+\cdots +\frac 1{10}\times \frac 0{20}$$ which sums to $\frac 9{40}$.

If $≤10$ then $B$ rolls again and, of course, this is then just a fair match between $A,B$, since the initial toss does not signify. In that case, the probability that $A$ wins is $\frac 12\times \left(1-\frac 1{20}\right)=\frac {19}{40}$

Thus the probability that $A$ wins this unfair game is $$\frac 12\times \frac 9{40}+\frac 12\times \frac {19}{40}$$

Of that, the portion explained by $B$ only rolling once is $\frac 12\times \frac 9{40}$ so Bayes' tells us that the desired answer is $$\frac 12\times \frac 9{40}\Bigg/ \left(\frac 12\times \frac 9{40}+\frac 12\times \frac {19}{40}\right)=\frac 9{28}$$ as desired.

Answer 3

To make it easier to think about, assume that $A$ doesn’t roll until you have either re-rolled or decided not to do so. There are $10$ equally likely outcomes of the first roll in which you do not re-roll, so there are $200$ equally likely outcomes in which you do not re-roll and $A$ wins in $45$ of them.

There are also $10$ equally likely outcomes of the first roll in which you do re-roll, and for each of them there are $400$ equally likely final outcomes, in $190$ of which $A$ wins. If you were really counting outcomes, that would be $1900$ wins for $A$ in $4000$ possible outcomes. However, since the result of the first roll doesn’t affect the result of the game, it does no harm to think of this as $190$ wins for $A$ in $400$ possible equally likely outcomes.

But you still have different numbers of outcomes making up the $NR$ and $RR$ events: the former is divided into $200$ equally likely outcomes and the latter into $400$. Thus, since the $NR$ and $RR$ events are equally likely, each of the $200$ outcomes that you’re considering in the $NR$ case is twice as likely as each of the outcomes that you’re considering in the $RR$, and the calculation therefore cannot be a simple matter of counting total outcomes. In order to do that, you have to put them on the same basis, e.g., by noting that $190$ wins for $A$ out of $400$ outcomes is the same ratio as $95$ wins out of $200$ outcomes. Then you can calculate the desired probability as

$$\frac{45}{45+95}=\frac{45}{140}=\frac9{28}\,.$$

In effect this is halving the weight of each outcome in the $RR$ case. Alternatively, you could double the weight of each outcome in the $NR$ case and compute

$$\frac{90}{90+190}=\frac{90}{280}=\frac9{28}\,.$$