Thursday, November 16, 2006 - 08:26 PM

Clay's article was an excellent, and a very well explained one too. I'd just like to add the bit about the probability of the odds of finding a person with the same birthday as you. Hopefully mine will be as descriptive as his.

In this article, we shall explore some techniques of probability, and 'permutations and combinations'. This is going to be a slightly long article, but is very much educative, and I'll try to cover the entire thing from front to back. You can skip bits if you know them, but for the benefit of those who don't I've included them. I've finally posted a way of doing the question without any of this knowledge, but I still think you should read and understand what I'm trying to explain.

Now let's look a bit closer a probability first. Let's find the probability of getting 3 heads only out of 5 flips. The probability of getting a head is just 1/2, but lets consider a 'biased' coin where the probability is 'p' instead. Then the probability of getting a tail is (1-p) (which is generally 1/2 for an unbiased coin). We can get two heads in the following manner:

1) HHTTT
2) HTHTT
3) HTTHT
4) HTTTH
5) THHTT
6) THTHT
7) THTTH
8) TTHHT
9) TTHTH
10) TTTHH

You can see that I've listed all the cases by the systematic manner in which I've done so. This is an important part of maths. The way in which you get a result is often worth more than the answer.

If we wanted to do the same with 30 coins... well lets say that you'll probably have to snuff out your lights. But I'll tell you the answer: 435. And it gets worse for finding atleast 3,4 coins and so on. Finding the number of such pairs belongs to the topic 'permutations and combinations' (lovingly abbreviated as PC).

PERMUTATIONS

Another diversion here, we shall study permutations. Permutations is the number of ways a 'string' of characters can be rearranged. For example lets consider abc to be a string. Then we can re arrange them like: abc, acb, bac, bca, cab, cba. There are 6 permutations. Lets try and generalise this result. Suppose we have 'n' characters a1,a2,a3...an forming the string, then for the first position, we can place ANY one of the n characters. The next position can take any of the remaining 'n-1' characters. Thus we can write that the number of ways we can arrange or permute the string is n*(n-1)*(n-2)...*2*1. This can be written more compactly as n! (read as n factorial).

COMBINATIONS

Let's move on to 'combinations', where we simply compute the ways of SELECTING 'r' objects from a set of 'n' objects. This means suppose you have a,b,c, the number of ways of selecting 1 object is 3, 2 objects is 3 also. But in the case of 4 objects, we have 4,6,4 ways for choosing 1 object, 2 objects, 3 objects respectively. There is a lot more to it, but we won't need it here.

Now, lets visualise a row of 'n' boxes, each containing a unique ball. The keyword here is that these boxes are unique or contain something unique. Now if you are to choose just 2 boxes and take the containing ball, then you can do so by choosing any of the 'n' boxes first. Then, you can choose another ball from the 'n-1' that remain. We can do so by (n)*(n-1) ways. BUT, suppose we select a particular ball (say a red one) first, then we select a blue one. We could have done this by selecting the blue ball first, then the red ball. But both would give the same result. We can easily see that this is true for every set of two balls (green and pink or pink and green). So we can see that this number is repeats each cases twice, and thus the true result is: n*(n-1)/2.
Lets look at the case for choosing 3 balls. We can choose the first ball in 'n' ways, the second in 'n-1' and the third in 'n-2' ways. But the number of repeated cases is much larger now. lets take the balls a,b,c (they've got letters on them now), and look at the order of choosing them:
abc
acb
bac
bca
cab
cba.
Now many of you readers will immediately see that the this is the EXACT same sequence as we saw in the permutations section. Well, lets reason this out. These balls can be removed in any PERMUTATION of order, and still give the same result. Thus this number is infact the number of permutations of 3.

Let's generalise for choosing r (obviously r<=n) objects from 'n'. We can write this as:
n*(n-1)*(n-2)...(n-r) / r!. Note that n*(n-1)*(n-2)...(n-r) can also be written as:
n!/(n-r)!. This is written compactly as ⁿC_r. Infact this is read as n chose r. Thus,
ⁿC_r. = n!/(n-r)!r!

Permutations and combinations is a lovely topic, and though challenging, is very enjoyable. It is highly logical, and if any of you have an option to learn it, don't let it pass.

BACK TO THE PROBLEM

Let's apply what we've just learnt to this problem. Now we can see the coin sequence in a different light. The number of ways of getting 'r' heads is just the number of ways of choosing 'r' coins from the 'n' that you flip and making the heads, and all the rest tails. It definitely doesn't matter if you flip one coin 'n' times, or if you flip 'n' coins once. Thus the number of ways is:
ⁿC_r.
The probability of such an event occuring is equal to p^r * (1-p) ^n-r , because you have 'r' heads and 'n-r' tails. The nCr term is just the 'frequency' wit which the event occurs. Thus we can write the probability as:
ⁿC_r * p^r * (1-p) ^n-r

This is the probability of getting exactly 'r' heads.

Now lets look at our class (finally). The probability of a person to have the same birthday as me is 1/365. This is 'p'. Now the case is satisfied if there is atleast 1 person, i.e 1,2,3.... persons will do too. Thus it is

nC1 (1/365)^1 * (364/365)^n-1 + nC2 (1/365)^2 * (364/365)^n-2 ....

summation ( ⁿC_r * p^r * (1-p) ^n-r ) from r = 1 to r = n
Here 'n' is the number of people exculding your self.

BINOMIAL EXPANSIONS

Now, we can solve this summation using a concept called 'binomial' expansions, which deals with the polynomial expansions of (x+y)^n. For example:
(x+y)^2 = x^2 + 2xy + y^2.
(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3.
...

Lets see if we can reason out a general formula.
(x+y)*(x+y)*(x+y)...(n times). Then we get the term x^r y^(n-r) (we have to get the sum of their powers to be equal to n btw.) if we choose any r terms and take their 'x's and take the 'y's from the rest of the terms. This is a logical operation. Thus this is just nCr as we saw in the above sections. Then, we have the coefficient of x^r y^(n-r) is nCr!

Our summation is the same thing, with x = p, y = 1-p, except for the term of nC0 p^0 (1-p)^n (i.e. when none of the people share your birthday). So lets just add and subtract this term and get

RESULT

P = (p + 1-p)^n - (1-p)^n. = 1 - (1-p)^n
Such an awfully simple result isn't it. For our case it gives 7.9% with n = 30, and 15.1% with 60 students.

SUPER SIMPLE WAY OF GETTING THE SAME RESULT

Now, you are going to get angry at me, for this can be solved so easily, and without any of this extra stuff, but I still feel that this was a good place to introduce all of this. We can simply take the complementary set of the probabilty when nobody shares your birthday, similar to how we did in clays' post. and get the same result. I just wanted to introduce all these topics.