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.
closed as too localized by Michael Lugo, Loop Space, Steve Huntsman, Robin Chapman, Gjergji Zaimi May 19 '10 at 21:19This 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. 


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 (k1)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 (8116) 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 


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. 

