1
$\begingroup$

There are many variations of this problem but for concreteness I'll stick to one.

I roll a 6 sided die and a 4 sided die, what is the probability the sum is over six?

Very trivially I could make a table with all the outcomes and count 14 out of 24 cases.

However I may be asked this question during an interview, and constructing a table might take a while and is prone to errors. Is there a trick to this problem that I'm missing? Or in other words is there a way to solve this problem that's simpler than constructing a table of outcome?

===Edit===
Distribution methods are nice, but for in an interview this solution might be too cumbersome

$\endgroup$
  • $\begingroup$ A search for "dice", "d6", or even "roll" will provide you with many different, effective answers to this problem and its many generalizations. Code is at stats.stackexchange.com/questions/177163; a difficult example is solved in several ways at stats.stackexchange.com/questions/145621; and many different, general solutions are offered at stats.stackexchange.com/questions/116792. $\endgroup$ – whuber Dec 2 '15 at 18:00
  • $\begingroup$ @whuber As I read it this question is about convolution of two different uniform discrete random variates (which results in a sum which has a discrete trapezoidal pmf) and is amenable to a direct solution. The indicated duplicate does not solve that problem but instead a quite different one. I think it may be more or less a duplicate of some question on site but it seems it's really not a duplicate of that. $\endgroup$ – Glen_b Dec 2 '15 at 21:47
  • $\begingroup$ @whuber it's also not solved at 177163 since the question is asking for a method that could be done in an interview, and explicitly rules out that kind of "counting all the combinations" strategy; it's after a shortcut for a specific sub-class of convolution problems not a general solution to more complicated problems using a program. I have an answer for the shortcut, but it's not suitable to post at any of the linked ones ... the right place to put the shortcut for two different dice is on this question that actually requests it. I wonder if perhaps we read this question quite differently. $\endgroup$ – Glen_b Dec 2 '15 at 21:56
  • $\begingroup$ @glen_b I'm tending to agree with you. I'm looking through the answers and while they do provide good solutions, I had a very specific instance where I had an interview where they asked me a permutation of this question and I essentially ended up just making a huge table. I wasn't sure if there was some clever trick to get this with interview style mental math $\endgroup$ – canyon289 Dec 2 '15 at 22:18
  • $\begingroup$ @canyon For the specific case of two dice, there is an easy shortcut you can do in your head. Of course if you don't know that the result is discrete trapezoidal there'd be an extra step but it's quite simple to do from scratch. $\endgroup$ – Glen_b Dec 2 '15 at 22:22
3
$\begingroup$

How to do this in your head:

Imagine you have a die with $a$ sides and one with $b$ sides ($b>a$), so the $a\times b$ combinations all have probability $\frac{1}{ab}$. If you wrote them out, they'd make an $a\times b$ table. You want the upper tail probabilities.

So if you wrote out your $a\times b$ table the largest outcome would be the bottom right entry, it would have value $a+b$ and probability $\frac{1}{ab}$. The second largest outcomes would be the two entries above and to the left of that one, with value one smaller, each with probability $\frac{1}{ab}$.

![![schematic illustration of table of outcomes

Each next smaller outcome would be on a diagonal above and to the left of the larger outcomes we considered before it. The count would increase until the top right corner of our table, where the outcome was $b+1$, which has $a$ entries at that value. (After we round the corner, the probabilities stay at $\frac{a}{a+b}$ until we get to a total of $a+1$, and then if we go back any earlier, we are going down the left arm of the trapezoid in the distribution as we head to the top left corner of the table.

The probabilities of the totals then look like this:

       |     |
       |     | 
       |     |          |     
       |     |          |     |   
       |     |  . . .   |     |     |
   ... b    b+1             a+b-1  a+b

So if your desired value is b+1 or more, you add 1,2,3, etc lots of the probabilities $\frac{1}{ab}$ until you have the right number of values that at least make your total.

If it's below $b+1$ you need to add $\frac{a}{a+b}$ for each earlier value (moving back through the shaded part until you run into the white parts in the other corner). This sounds complicated because I'm speaking generally, but for any specific instance it's dead simple.

So for your specific case $a=4$ (outcomes in red) and $b=6$ (in blue). You have 24 combinations in your table, each with prob $\frac{1}{24}$, the highest is 10 and you want "7 or more" (more than 6 in your question). This takes you exactly to the "b+1" top right corner:

enter image description here

 total combinations
  10       1
   9       2
   8       3
   7       4


       :     | 
       :     |     |     
       :     |     |     |   
       :     |     |     |     |

   ... 6     7     8     9    10

For a total of 10 (out of 24) combinations. So the final probability is 10/24.

If it was 8 or more, you'd have 6/24, then 9+ would be 3/24 and so on.

If you had say "5 or more" it would be 10+4+4 combinations or a probability of 18/24 (going back from the corner case of 7 to include exactly 6 and exactly 5). If you go back further still (say "4 or more") you start going down the left arm of the trapezoid and then it's easier to work out the complementary probability ("3 or less") and then subtract from 1.

You can solve quite large problems quickly this way if you know the triangular numbers (1,3,6,10,15,21), but they're also easy to compute if needed.

So say it was d100 + d20, and we wanted a total of 110 or more. That is we want the totals at 110, 111, 112, ... 120, ... that's 11 terms, but they are all after the corner so we want the 11th triangular number ($\frac{11\times 12}{2}=66$) divided by $100\times 20$ so the probability is 66/2000). That's a very rapid calculation!

[It's not much harder even if you go around the corner (below 101); for each one under 101 you just add another 20 combinations; if you get down to small numbers (say below 30 at worst) then just work with the complement.]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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