MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If we roll 4 dices (fair), what is the probability of "sum of subset" being 5. e.g. 1432,1121, 2344, 2354 have a subset sum of 5. Can you illustrate how to calculate this.

share|cite|improve this question

closed as too localized by Michael Lugo, Loop Space, Steve Huntsman, Robin Chapman, Gjergji Zaimi May 19 '10 at 21:19

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

This question does not appear to be advanced enough for mathoverflow, so I'm voting to close. There may be a kernel of interest here, though. What do you mean by "sum of subset"? In particular, can you give an example of an outcome from four dice that does not have a subset sum of 5? – Michael Lugo May 19 '10 at 18:23
Can you illustrate why you are interested in this, and what preliminary calculations you've done? – Loop Space May 19 '10 at 18:23
@Michael: I'd guess that 1111 doesn't have a "sum of subset" being 5. – Loop Space May 19 '10 at 18:28
So we're looking at the sums of all the sub(multi)sets? – Michael Lugo May 19 '10 at 18:31
I agree it may be too simple for this group. I started approaching the problem by find the prob of 1 dice having 5, then 2 summing to 5 etc., but got caught in eliminating the double countings. Any advice on better way of approaching this problem would be helpful. As Michael illustrates, 1111, 4366, 2244 would not be the positive outcomes. on the other hand 2354 has two subsets, {(2,3),5} summing to 5. – Binger May 19 '10 at 18:56
up vote 1 down vote accepted

The most straightforward way is also the most tedious: list all die rolls (1296 of them, I assume), and count which ones have a subset sum of 5. You can save on some work by looking at all rolls which have at least one 5 in them, and then all rolls which have no 5 but at least one 1 and one 4 or one 2 and one 3, and then enumerate the remaining cases.

A possibly quicker but still involved approach involves calculating the probabilities that a sum appear on the kth roll but not the (k-1)th roll. Then one gets 1/6 of a probability of a sum on the first roll and 1/6 + 1/4 = 5/12 of a probability of such a sum on the first or the second roll. The calculation for the third roll assumes that no subset sum has occurred on the scone roll, and breaks down into 21 cases, starting with 6 6 and going down to 1 1, if you like, but many of the cases can be treated the same way, so that there are fewer types of cases to consider.

You can also try looking at rolls which miss having a subset sum of 5. Taking all even die gets you a lower bound of 1/16 for not having a subset sum of 5, while looking at all combinations of 3, 4, and 6, and removing the even combinations gives you (81-16) more rolls which do not have a subset sum of 5, giving a lower bound of (1/8 -1/81) for missing a subset sum of 5. There are still the extra cases to handle.

I do not see a simple characterization that allows a quick calculation of the probability.

Gerhard "Ask Me About System Design" Paseman, 2010.05.19

share|cite|improve this answer

Since this (perhaps oddly) hasn't been closed, let me offer a more general method: you have a Markov chain on the seventeen states $\mathcal{P}(\{1,2,3,4\}) \cup \{5\}$ (here $\mathcal{P}$ represents powerset) with initial state $\varnothing$ and final (absorbing) state 5. At any given moment, your current state tracks which sums you can make with the numbers you've rolled so far. Thus, from the initial state you move to one of {1}, {2}, {3}, {4}, 5, or $\varnothing$, if you respectively roll 1, 2, 3, 4, 5, or 6, and each step has probability $\frac{1}{6}$. Similarly, from state {1, 2} you move to state 5 with probability $\frac{1}{2}$ (if you roll a 3, 4, or 5), and to states {1, 2}, {1, 2, 3}, {1, 2, 3, 4} with probability $\frac{1}{6}$ each (if you roll a 6, 1, or 2, respectively).

It turns out that you get to make some simplifications because some states (e.g., {1, 3}) are unreachable, so you don't have to work with all 17 at once.

share|cite|improve this answer

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