Analogy of binary systems in probability

Probability is a tricky subject. Often we confuse the sub-branch of counting, which is concerned with the number of ways to perform a certain task with the science of probability. We often forget that each number of ways to perform a certain task does not necessarily share the same probability, or in math-speak, they do not share a symmetric event space.

For example, if you are tasked to find the number of ways to arrange 5 identical balls in 2 urns. The formula for such a scenario is given as below:






As an aside, an ingenious way (unfortunately not mine) of interpreting the formula goes as follows:
I line up all 5 balls in a row. There are 2 urns, so I utilise an imaginary stick and place it between the 5 balls, creating effectively 2 partitions (one left of the stick, and one right). Each partition denotes an urn, so 1 stick is enough to denote 2 partitions. If there are 3 urns, 2 sticks are needed...and so on, giving:

No of sticks needed = No of urns - 1.

Then I simply find the number of ways to order all the sticks and balls, giving me:






(since the balls are themselves indistinguishable and the stick is indistinguishable, so we divide by 5! and 1! respectively.)


What if you are now told that each urn must now contain at least 1 ball each?
Simple. Using the same values, 1 ball is first distributed to each urn to ensure that each urn must now contain at least 1 ball each. That leaves us with 5-2=3 balls left to arrange with the same number of sticks (r-1), giving:







Now comes THE question:
Let the no. of ways of arranging 5 balls in 2 urns given each urn must have at least 1 ball = P1(5,2).
Let the no. of ways of arranging 5 balls in 2 urns given each urn has no restrictions on the number of balls = P0(5,2).

Is the probability of having each urn containing at least 1 ball ( which can be rephrased as the probability of having no empty urn) equal to:





No!
The number of ways to arrange 5 balls in 2 urns is not all equal in probability.

A better way to view the problem uses the analogy of states (like binary states, tri-states that electrical engineers are comfortable with).
The 2 urns represent 2 states, giving us the familiar binary system. Each ball represent one bit. Hence there are a total of:

2^5=32 possible states.

(Of course, we are now simply viewing the problem as putting n distinguishable balls into r distinguishable urns, which is also the number of ways to draw n balls from r unique types(each unique type is an urn!) with replacement, where order counts. Just like a mountaineer who always tries to find new ways to climb the same mountain, mathematicians are always trying to view the same problem from different angles, hoping to gain further insights or discover something which was previously hidden. Back to the problem:)

Breaking up the problem:









The probability of distribution of balls such that we end up with no empty urns becomes relatively clear. It is simply:






Note that 00000 and 11111 all denote 1 empty urn.



The analogy of binary system helps bring probability problem into sharp focus. Another question illustrates its power.

Cards were dealt face down from a deck of 52. What is the probability that the 1st ace encounterd occurs on the nth draw?

We now imagine a binary system of 1 (Ace) and 0 (no ace) with a total of 52 bits.
Picture the table with headers as below:







The meaning of the curly braces, which divide up the table into 2 groups, will be apparent later. But first, we define the sample space, noting that each way has equal probability of occurence.There are a total of 4 aces, to be scattered among all 52 bits. So for every row, there are 4 1s, and 48 0s. So how many rows are there?
Total number of rows possible:






Now, we introduce the restrictions. The 1st ace must occur on the nth draw.
We divide up the group into A1 to An, and An+1 to A52.
In the first group, only 1 ace resides in it, specifically in the An position.
In the second group, 3 aces are distributed among An+1 to A52.

The problem is now reduced to a matter of throwing out unwanted rows and retaining those that we want. So which are the rows that we have to throw out?
1) All those with more than 1 Ace in the group A1 to An.
2) All those with only 1 Ace in the group A1 to An, but whose 1 Ace does not reside in the nth position.

There are quite a lot of rows to throw out here. Instead of throwing out rows, we can think of the rows that we must keep. There is only one group we must keep, which is:
1) All those with 1 Ace in the group A1 to An, and whose 1 Ace resides in the nth position.

For this group, how many ways are there to arrange them? The answer lies in the other group An+1 to A52. Considering that 3 aces are to be found among An+1 to A52, and that there are 52 - n bits from An+1 to A52, we get the final answer:








Now what is the significance of multiplying the answer found above by n? Essentially it gives us the probability of finding 3 Aces in the group An+1 to A52. Without the binary system, these angles may not be so readily apparent.



Lastly, the binary system has made light of an unnecessarily complicated problem: The issue of drawing 4 Venn circle diagrams. I believe most of us were introduced to the Venn diagrams from young, first with 2 circles, then 3 circles. It is a very elegant and simple solution to many probability questions involving many intersections. Put it simply, without John Venn and his marvellous invention, my head would spin like a gyroscope everytime I encounter probability. So if 3 circle Venns have been useful, then 4 circle Venns must be even more useful. I chanced upon this diagram at Wikipedia:

http://en.wikipedia.org/wiki/Image:Inclusion_exclusion_diagram.JPG














The diagram is flawed as soon as I counted the number of states in it. Using the binary system, for each circle we denote it as ONE bit. There are 4 circles, hence 4 bits. In a 4 bit system, there are supposed to be 2^4 = 16 mutually exclusive regions marked out by the intersections of the 4 circles. (The last region is 0000, representing the area outside of all 4 circles.) But I counted only 13.

So I present my own model in which care was taken to include all 15 different regions as spelt out by the binary system.














A brief explanation:
The 4 events are depicted by their colours:
Red, Blue, Black and Green.
While Red, Blue and Black are the usual 3 circle Venn,
I added Green...modified to resemble a doughnut with a hole in the middle and an extension outside of the 3 circles.







This model is useful for anyone who wishes to understand the inclusion-exclusion theories and other theories based on this, e.g. Waring's Theorem, and also to visualise the De Montmort's Problem of Coincidences better. Now I wonder how did the Wikipedia poster manage to get inclusion-exclusion theory correct with a flawed model.

An alternative model was offered by my brother. (See below). Basically all you have to do is to make sure the new region(Green)splits every other existing region into two...a truly intuitive illustration of the Binary Model indeed! Maybe not too symmetrical though...

















Now the problem comes alive when you try to add more and more regions. In adding the regions, we are supposed to cross the boundaries of each existing region one and only one time. Now, is this problem vaguely similar to the famous Bridge of Konigsberg Problem as proposed by Euler?