# Calculate sum of probabilities in multinomial model

The question at hand:

On average in every 7th chocoloate egg there is a figure to be drawn from a known list of special figures (e.g 15 distinct pieces) the other draws are on average fails.

With what probability in a given sample size (n) can you at least get 1/2/3/4/5 distinct specific figures out of these 15 figures (duplicates do not matter, though I could ask for it as well)?

The case with at least one distinct specific figure is: $$\small 1-\left(\frac{104}{105}\right)^n$$

For two I get:

$$\small -2^{3 n+1} \left(\frac{13}{105}\right)^n+\left(\frac{103}{105}\right)^n+1$$

For three I get: $$\small 105^{-n} \left(-102^n+3\dot\ 103^n-3\dot\ 104^n+105^n\right)$$

Which looks kind of nice.

For four I used again the modified code:

p1[a_, b_, n_] :=
n - Sum[Subscript[k, a - i + 1], {i, 1, b}] - ((a - b))

bubu[a_, n_] :=
Flatten[Append[
Reverse[Table[{Subscript[k, i - 1], 1, p1[a - 1, a - i, n]}, {i, 1,
a}]], {l, 0, p1[a - 1, a - 1, n] - Subscript[k, 0]}], 0]

(*Get at least 4 distinct special figures in your sample n, add up \
probability of all applicable possible series*)

calc22[n_] :=
Sum[(n!/((k0)!*(k1)!*(k2)!*(k3)!*
l!*(n - l - k0 - k1 - k2 -
k3)!))*(1/(105))^(k0)*(1/(105))^(k1)*(1/(105))^(k2)*(1/(105)\
)^(k3)*((11/105)^l)*((90/105)^(n - l - k0 - k1 - k2 - k3)), {k3, 1,
n - 3}, {k2, 1, n - k3 - 2}, {k1, 1, n - k2 - k3 - 1}, {k0, 1,
n - k1 - k2 - k3}, {l, 0, n - k0 - k1 - k2 - k3}]


For more I have written the general code:

p1[a_, b_, n_] :=
n - Sum[Subscript[k, a - i + 1], {i, 1, b}] - ((a - b))

bubu[a_, n_] :=
Flatten[Append[
Reverse[Table[{Subscript[k, i - 1], 1, p1[a - 1, a - i, n]}, {i, 1,
a}]], {l, 0, p1[a - 1, a - 1, n] - Subscript[k, 0]}], 0]

(*Get at least #(A+1) distinct special figures in your sample n, add \
up probability of all applicable possible series*)
(*Choose low sample size <30*)

calc24[n_, A_] :=
Sum[(n!/(Product[(Subscript[k, A - i])!, {i, 0, A}]*
l!*((n - l -
Sum[Subscript[k, A - i], {i, 0, A}])!)))*(1/(105))^(Sum[
Subscript[k, A - i], {i, 0, A}])*(((15 - (A + 1))/105)^
l)*((90/105)^(n - l - (Sum[Subscript[k, A - i], {i, 0, A}]))),
Evaluate[Sequence @@ bubu[A + 1, n]]]


Using the Multinomial function you can substitute the last block beneath the comment with these two:

buba[A_, n_] :=
Flatten[Append[
Table[(Subscript[k, A - i]), {i, 0, A}], {l,
n - l - Sum[Subscript[k, A - i], {i, 0, A}]}], 1]

calc24[n_, A_] :=
Sum[(Multinomial[
Evaluate[Sequence @@ buba[A, n]]])*(1/(105))^(Sum[Subscript[k,
A - i], {i, 0, A}])*(((15 - (A + 1))/105)^
l)*((90/105)^(n - l - (Sum[Subscript[k, A - i], {i, 0, A}]))),
Evaluate[Sequence @@ bubu[A + 1, n]]]


Somehow it takes too long to solve for larger values of A (number of distinct figures -1) or n (Sample size).

On this site [crossreference] the probability can be calculated but without stating the mechanics.

My number is slightly off after about 10 digits, I am still astonished that the code actually works to some precision.

Am I doing it overly complicated or is there a way to work with probability in complements for this kind of question?

Thank you.

• There is an English version of the site that you refer to: verklagekasper.de/ueei-en.html
– demm
Sep 2, 2015 at 13:28
• First, please define everything properly (e.g. what is $n$?). Second: I don't understand the problem. Why isn't the answer for $n=1$ simply $$1-\left(\frac{6}{7}\right)^n\ ?$$ Sep 2, 2015 at 13:30
• You would like to get at least one specific special figure out of 15, these 15 only appear on average once in every 7th egg, but you don't know which of course. So therefore $$\frac{104}{105}$$ chance of not getting this special figure in the first draw. n is the sample size, so the number of eggs you buy for your observation. The Problem I have is the solving time, so I would appreciate help in this. Sep 2, 2015 at 13:35
• The code is nothing else than all the applicable summation of the Probability mass function of the Multinomial distribution, when looking at the possible series in question (e.g. sample n=10, two distinct special figures and all other 8 are duplicates of them). This is one series but there are more where I get these two figures (2 special out of 15) actually! So therefore I have to sum. The mathematics shouldn't be the difficult part in it. So I can't ramify over every detail when the topic is actually mainstream. Sep 2, 2015 at 13:48
• Did you know that Multinomial[] is built-in? Sep 2, 2015 at 13:54

setp[eggs_, pPerEgg_, setSize_, wanted_] :=
With[{r = Range[1, wanted]},
1 - Tr[Binomial[wanted, r]*(1 - r*pPerEgg/setSize)^eggs*(-1)^(r - 1)]];


Example: 500 eggs collected, 1/10 chance of egg having item, 50 items available, you want 20 particular:

setp[500, 1/10, 50, 20]


For huge arguments, you can use inexact arguments (machine precision, e.g.) to speed further if you don't require exact result.

As an aside,

setMeanTo[pPerEgg_, setSize_, wanted_] := (setSize*HarmonicNumber[wanted])/pPerEgg


will give you the mean eggs to collect to reach your goal.

Do note the web site ref'd is not accurate past about the tenth digit shown there...

• Thank you very much for this less formidable looking code! How exactly does the argument of list of numbers (Range) exactly play into the formula? In the end you also do a trace: Could you explain the maths behind this a little bit? The numbers of both code do math up exactly, so both are legit. Sep 3, 2015 at 13:15
• So essentially the formula without coding would be: For 5 wanted figures (s=series number, p=prop per egg, and n=eggs): $$-5 \left(1-\frac{p}{s}\right)^n+10 \left(1-\frac{2 p}{s}\right)^n-10 \left(1-\frac{3 p}{s}\right)^n+5 \left(1-\frac{4 p}{s}\right)^n-\left(1-\frac{5 p}{s}\right)^n+1$$ For 6 wanted figures: $$-6 \left(1-\frac{p}{s}\right)^n+15 \left(1-\frac{2 p}{s}\right)^n-20 \left(1-\frac{3 p}{s}\right)^n+15 \left(1-\frac{4 p}{s}\right)^n-6 \left(1-\frac{5 p}{s}\right)^n+\left(1-\frac{6 p}{s}\right)^n+1$$ And so on (rearranging expressions), so expanding with pascal's triangle. Sep 3, 2015 at 15:36
• I wonder what would happen if we would additionally ask for a specific duplicate number of wanted figures or even specific duplicate number of non-wanted figures. Surely then we would see Pascal's pyramid appearing in the coefficients. This would be another great addition! Sep 3, 2015 at 15:46
• @chrisoutwright: the range provides the inclusion/exclusion. Could do same using Sum, I like direct math...
– ciao
Sep 3, 2015 at 18:25
• @chrisoutwright: Opps, sorry, neglected to answer second part - this is just a Coupon Collectors problem. See. e.g. Wikipedia or any decent combinatorics text for the math. I added a related function to the answer (I'm sure you knew this beforehand) that gives the mean eggs to collect to reach goal.
– ciao
Sep 3, 2015 at 23:09