# 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 '15 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\ ?$$ – yohbs Sep 2 '15 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. – chrisoutwright Sep 2 '15 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. – chrisoutwright Sep 2 '15 at 13:48
• Did you know that Multinomial[] is built-in? – J. M. will be back soon Sep 2 '15 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. – chrisoutwright Sep 3 '15 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. – chrisoutwright Sep 3 '15 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! – chrisoutwright Sep 3 '15 at 15:46
• @chrisoutwright: the range provides the inclusion/exclusion. Could do same using Sum, I like direct math... – ciao Sep 3 '15 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 '15 at 23:09