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.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ 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? $\endgroup$– Michael LugoCommented May 19, 2010 at 18:23
-
1$\begingroup$ Can you illustrate why you are interested in this, and what preliminary calculations you've done? $\endgroup$– Andrew StaceyCommented May 19, 2010 at 18:23
-
1$\begingroup$ @Michael: I'd guess that 1111 doesn't have a "sum of subset" being 5. $\endgroup$– Andrew StaceyCommented May 19, 2010 at 18:28
-
$\begingroup$ So we're looking at the sums of all the sub(multi)sets? $\endgroup$– Michael LugoCommented May 19, 2010 at 18:31
-
$\begingroup$ 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. $\endgroup$– BingerCommented May 19, 2010 at 18:56
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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
answered May 19, 2010 at 18:44
$\begingroup$
$\endgroup$
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.
