Binary Model and Inclusion-Exclusion Theory

A dice is rolled t times. What is the probability that all sides appear at least 2 times?

Sounds like a simple question. We have to be cautious though, for "what is the meaning of life?" is too a simple question that has stumped humanity.

First up, we search for an opening to the problem that is at once accessible to us.
Consider this: if all sides were to appear at least 2 times, the smallest value for t has to be 12. One possible set for t=12 would be {1,1,2,2,3,3,4,4,5,5,6,6}. In fact, this is the only set possible.

We see that for t<12, P = 0. And we can calculate the probability for t=12 by means of simple combinatorics:






This approach may not be useful, but the answer comes in handy to allow us to verify whatever complicated equations we may derive later.

(Or we can build from this approach, evaluating 13 throws as having 1 extra throw to distribute among the 6 sides. 6 choose 1 = 6. Hence, ans = 6*P12.
For t=14, we have extra 2 throws to distribute among 6 sides = 2 balls to distribute among 6 urns. 7 choose 5 = 21. But it is not so simple to evaluate now, as the number of ways is not all the same probablity.)

Where do we go from here? Introduce the binary system! And one that is symmetric in event space. Let each bit represent one side of the dice: A1 A2 A3 A4 A5 A6.

Now, how shall we define 1 and 0?
Consider that we want to find probability of "at least 2 times". In other words, we can find 1 - P(0) - P(1). With this in mind, we define bit 1 as occurence of 1 or 0 times, and bit 0 as occurence of 2 and above times, so that we can do something like 1 - P(...).

Now we can construct the Binary Table!













Let us inspect the meaning of each row.






The first row means all the numbers must appear at least 2 times. Hey! This is the case we want to find! Now things becomes apparent. To find the probability of this row, all we have to do is to sum up the probability of the rest of the rows, and do a 1 - P(prob of the rest of all the rows). Note that all the rows of the Binary Table are mutually exclusive.





The second row. It would mean Number 1 appears once or 0 times, and the rest all appear at least 2 times.








The last row. It means that all sides appear at most 1 time, hence giving a maximum of t=6 (or a minumim of 0). As earlier established, t has to be >=12, so the probability of this happening is 0. We shall not consider this case.
So there are a total of 2^6= 64 cases for us to sweat on.
(actually 63, as we discount 111111....)

Let's start evaluating the probability of Row 2. (Row 1 is 000000. There is very little information we can get from that.)






How can we find the probability that the Number 1 appears only once or none WHILE ensuring that the rest appear at least 2 times? Unfortunately it is too difficult.


Imagine t=12.
For 1 to appear 0 times(NONE): we need to find the number of ways to solve A2+A3+A4+A5+A6 = 12...a case of 12 balls distributed among 6 urns.
For 1 to appear 1 time: we need to solve for the number of ways to solve
A2+A3+A4+A5+A6 = 11...

Mind boggling stuff. And that's only for the 1 out of 62 cases we need to establish.

Instead, for that row, I am forced to consider a variation of it:






Here, I introduce a 3rd state x to mean Don't Care. I do not care what happens to the rest of the number as long as Number 1 appears 0 or 1 time in t throws. The probability of the case I just mentioned is actually humanely possible:











Why the term




Because we still need to account for the fact that this appearance of Dice Number 1 can occur at the first throw, or at the second throw,...up till the t throw. For lack of a better term, let's call this the t Loop.

The formula can now be combined:






Now we shall generate the full table, which I shall call the Don't Care Table.













One very important point to note is that the table is a truncated form. I left out the rows xxxx1x, xxx1xx, xx1xxx, x1xxxx, 1xxxxx, whose calculation is similar to the one we did for xxxxx1. Please bear this in mind! Also note that the rows of this table aren't mutually exclusive!

But how does the Don't Care table help when all we want is to sum up all the 62 rows of the Binary table. Ah....Poincare has this figured out. He found that to calculate the probability of the whole table minus the case of 000000 (we cannot include 000000, else the Probabilty is unity), for example, we must do:





As mentioned, the rows are not mutually exclusive. xxxxx1 and its 5 cousins (xxxx1x, xxx1xx,xx1xxx,x1xxxx,1xxxxx) contain all of what we want from the Binary Table...and more. We have some subtraction on our hands.

Consider the last row 111111. This row is exactly the same whether in the Don't Care or Binary Table. It is the simplest element in a recursive algorithm.
Now consider the second last row x111111. It can either be 0111111 or 1111111.
Hence, to get 0111111, all we have to do is to compute x111111 - 111111.
Therein lies the recursive algorithm, which we use to work back all the way to the top.

If you are not convinced, work out the next row 001111 (which is going to be a bit more tedious.) First we evaluate xx1111:
xx1111=001111+011111+101111+111111
Hence, 001111 = xx1111-(011111+111111)-101111
Knowing x111111=011111+111111, the equation becomes 001111 = xx1111-x11111-101111

We now need to break down 101111 into its elements.
We consider 1x1111 = 111111 + 101111
101111 is then equal to 1x1111 - 111111.
Since 1x1111 = x11111 in absolute value, we get 101111 = x11111 - 111111

We get 001111 = xx1111 - x11111 - 101111 = xx1111 - x11111 - x11111 + 111111
= (2C0)xx1111 - (2C1)x11111 + (2C2)111111

Finally, we can set up this equation:
(6C1)000001 + (6C2)000011 + (6C3)000111 + (6C4)001111 + (6C5)011111 + (6C6)111111
= (6C1)xxxxx1 - (6C2)xxxx11 + (6C3)xxx111 - (6C4)xx1111 + (6C5)x11111 - (6C6)111111

This is basically the inclusion-exclusion theory, now cast in a different light with my binary model. Bear in mind that it is EXACTLY of the form:





Let's take a look at the next row.






If you realise here, we are going to introduce another binary system. Take stock for a moment what is happening: A binary system and a t Loop inside another binary system which has been modified to a Don't Care system. That's rhetoric you can ignore.

The internal binary arises from having 2 Numbers now combining to give 00, 01, 10 and 11. The equation is now:







Why the term





The t Loop that was mentioned a while earlier has gotten a bit sticky. When there was only 1 event, now there are 2 events A1 and A2 to account for, resulting in a total of 3 distinct groups to arrange: A1,A2 and the rest (t-2). Rearranging the term, we get:






We now revise the Row 2 equation:





We do the same for all rows, and come to a general ROW equation:




Now comes the defining moment.
We are going to loop through all the rows, executing
xxxxx1 - xxxx11 + xxx111-xx1111+x11111
(ignoring 111111 of course),
which is equal to the summation of the probability of all the rows in the Binary Table except 000000.

Summation of the probability of all the rows in Binary Table except 000000=
Alternating inclusion exclusion of Dun Care Table =





Hence, our answer to the question posed right at the beginning is:






I have not verified the answers yet. Remember at the beginning, we solved for t=12. This is a good start to verify the formula.

Note that the internal binary loop would become Trinary (0,1,2) if the question is rephrased:
A dice is rolled t times. What is the probability that all sides appear at least 3 times?