18
$\begingroup$

Let us roll a fair die $4$ independent times, and denote the outcomes as $X_1, X_2, X_3$ and $X_4$.

What is the probability of $X_1+X_2+ X_3+X_4 > X_1X_2 X_3X_4$?

My try: I could get the answer for $2$ rolling case by enumerating possibilities, but couldn't get this larger problem. Can someone help me with this?

Thanks in advance for any help!

$\endgroup$
  • 3
    $\begingroup$ When you say you "couldn't get this larger problem": where did you get stuck? $\endgroup$ – Aaron Montgomery May 8 '18 at 18:23
  • $\begingroup$ @AaronMontgomery I meant to say that I couldn't approach the problem without able to enumerating or writing a simple python script. Sorry for not being clear. $\endgroup$ – Random-generator May 8 '18 at 18:32
  • 1
    $\begingroup$ Ah, I see -- so you're saying that you were able to solve the problem with one of those methods? (For the record, I currently think those may be the only reasonable ways to do it.) $\endgroup$ – Aaron Montgomery May 8 '18 at 18:34
  • 1
    $\begingroup$ The generating function for $X_1$ is $P(s)\frac16\sum_{j=1}^6 s^j$ so the generating function for $S_n:=\sum_{i=1}^n X_i$ is $$P_n(s):=P(s)^n=6^{-n}\left(\sum_{j=1}^6 s^j\right).$$ Then $\mathbb P(S_n=k)$ is the coefficient of $s^k$ in $P_n(s)$. The distribution of the product of the $X_i$ is a bit more problematic. $\endgroup$ – Math1000 May 8 '18 at 18:35
  • 2
    $\begingroup$ Numerically from excel you get $39/1296 \approx 3\%$... $\endgroup$ – gt6989b May 8 '18 at 18:42
23
$\begingroup$

Case work:

  • If 3 or 4 of the rolls come up 1, it's straightforward to see that the desired inequality holds.
  • If 0 or 1 of the rolls come up 1, then we can show that the inequality never holds. (The product of three integers, all $>1$, is always at least 2 greater than their sum.)
  • The remaining case is when exactly 2 of the rolls come up 1. Empirically, you can find that the only case when the inequality is satisfied is when the rolls are some permutation of $3,2,1,1$ or $2,2,1,1$.

There is only 1 combination of all 1's, $5\times 4=20$ combinations with three 1's, $4\times 3=12$ permutations of $3,2,1,1$, and $\binom{4}{2}=6$ permutations of $2,2,1,1$. This adds up to a total of 39 rolls that satisfy the inequality. There are $6^4=1296$ total rolls, so the probability that the inequality holds is $39/1296 \approx .03009$.

$\endgroup$
  • 1
    $\begingroup$ I was thinking of the problem e.g. $X_1+X_2+X_3+X_4>Y_1Y_2Y_3Y_4$, which is a bit more complicated. No wonder I didn't see this elegant solution ;) $\endgroup$ – Math1000 May 8 '18 at 19:44
15
$\begingroup$

A solution to the equation has at least one $1$.

When you roll all 2s, the equation is false.

$2 + 2 + 2 + 2 > 2 \times 2 \times 2 \times 2$

$8 > 16 \implies false$

Adding one to any of the numbers always maintains the falsehood of this equation, or the truth of the reverse. Assuming the opposite equation:

$x_1 + x_2 + x_3 + x_4 \le x_1x_2x_3x_4$

Adding $1$ to one of the die results in the product results in a value that is $x_2x_3x_4$ higher.

$(x_1 + 1)x_2x_3x_4 = x_1x_2x_3x_4 + x_2x_3x_4$

Adding $1$ to one of the die results in the sum makes the sum $1$ higher, and $x_2x_3x_4 >= 1$, so we can say:

  • If $x_1 + x_2 + x_3 + x_4 \le x_1x_2x_3x_4$, then $(x_1 + 1) + x_2 + x_3 + x_4 \le (x_1 + 1)x_2x_3x_4$.

Therefore, any solution to $x_1 + x_2 + x_3 + x_4 > x_1x_2x_3x_4$ must have at least one $1$.

The lowest possible dice roll with exactly one $1$ goes like this:

$1 + 2 + 2 + 2 > 1 \times 2 \times 2 \times 2$

$7 > 8 \implies false$

Therefore, the solution must require at least two $1$s.

Three or more $1$s.

If there are at least 3 $1$s, the equation is always true. Note this includes the case of all four $1$s.

$1 + 1 + 1 + x > 1 \times 1 \times 1 \times x$

$x + 3 > x \implies true$

Exactly two $1$s.

With exactly two $1$s, let's explore the other two values.

If one of the other values is a $2$, then that restricts the other value to $3$ or less.

$1 + 1 + 2 + 2 > 1 \times 1 \times 2 \times 2$

$6 > 4 \implies true$

$1 + 1 + 2 + 3 > 1 \times 1 \times 2 \times 3$

$7 > 6 \implies true$

$1 + 1 + 2 + 4 > 1 \times 1 \times 2 \times 4$

$8 > 8 \implies false$

If both the other values are at least $3$, then we don't have a solution.

$1 + 1 + 3 + 3 > 1 \times 1 \times 3 \times 3$

$8 > 9 \implies false$

All solutions

  • All four $1$s. 1 solution.
  • Three $1$s and we don't care what the last value is (this excludes the four $1$s case): 5 possible choices for the last value, 4 choices as to on which die it occurs: 20 solutions
  • Exactly two $1$s: The other two values are both $2$. There are $4\choose2$ or 6 choices to distribute the two $2$s.
  • Exactly two $1$s: The other two values are $2$ and $3$. There are four choices for the $2$, leaving three choices for the $3$, for a total of 12 solutions here.

I count 39 possible solutions, out of $6^4$ possibilities.

$39\div1296 = 13\div432 \approx0.0301 $

$\endgroup$
4
$\begingroup$

Of course we can quickly simulate this, e.g. in R:

rolls = expand.grid(1:6, 1:6, 1:6, 1:6)
sum(apply(rolls, 1L, sum) > apply(rolls, 1L, prod))
# [1] 39

So there are 39 cases which fit the criterium out of $6^4$ in the sample space.

This approach allows us to easily generalize to $n$ rolls as long as $6^n * n * b$ fits in memory (where $b$ is the storage space for an integer), e.g. (*I've made some small adjustments to make it run more efficiently for large $n$):

p = sapply(2:10, function(n) {
  print(n)
  rolls = 
    as.matrix(do.call(expand.grid, lapply(integer(n), function(...) 1:6)))
  mean(rowSums(rolls) > apply(rolls, 1L, prod))
})
plot(2:10, p, type = 'o', lwd = 3L, xaxt = 'n', las = 1,
     xlab = '# of Dice', ylab = 'Pr[sum > product]',
     main = 'Extension of Dice Problem')
axis(side = 1L, at = 2:10)

extension

To be clear, there's no inherent need to store all $n 6 ^ n$ dice rolls in memory, and this problem is trivial to stream so that the only RAM needed is $n * b+2 * b = O(n)$ storage; I only eschew the more memory-efficient approach for simplicity (the 2-line code here would be hard to match with explicitly arbitrarily nested loops)

$\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.