Nov 11 2011

Happy HDLC Day!

011.11.110

Today is the HDLC day!

For those of you who doesn’t know, the frame delimiter in HDLC is the bit sequence 01111110.

(Thanks to Yoni Ho)

no comments   |  tags: , | posted in Computers

Nov 7 2011

Birthday Paradox

The Birthday Paradox is not real paradox, you will not find any logical contradiction in the next few paragraphs. It is called a paradox because it is very counter-intuitive, and you will soon find out why.

The paradox is demonstrated in the following way: Choose $latex n$ people randomly. What is the probability that two of them were born on the same date? (only day and month, discarding the year. and assuming there are 365 days every year)

Lets say that $latex n=40$, what do you think that chances are?
Most people will think the probability is very low, but is it?

First lets define our sample space:

$latex \Omega=\left\{ \left(d_{1},\ldots,d_{n}\right)\, d_{i}\in\left\{ 1,\ldots,365\right\} \right\}$

The vector $latex \left(d_{1},\ldots,d_{n}\right)$ defines a series of dates for every person. Meaning $latex d_1$ is the birthday of the first person, $latex d_2$ of the second and so on…

The event we are interested in is the following:

$latex A=\left\{ d_{i}=d_{j},\text{ for any } i\neq j \right\}$

Apparently, Doing the direct calculation to solve this problem is hard, too hard. So we’ll attack the problem from a different angle.

Lets take a look at the complement of A (meaning, that every person in the group was born on a unique date):

$latex A^{c}=\left\{ \left(d_{1},\ldots,d_{n}\right)\in\Omega:\, d_{i}\neq d_{j},\,\forall i\neq j\right\}$

It is easily calculated that the number of elements in $latex A^{c}$ is:

$latex \left|A^{c}\right|=365\cdot364\cdot\ldots\cdot\left(365-n+1\right)$

And of course the number of elements in our sample space (meaning the number of options for birthdays for $latex n$ people) is:

$latex \left|\Omega\right|=365^{n}$

Assuming uniform probability, the probability that every person was born on a unique date is:

$latex P\left(A^{c}\right)=\frac{\left|A^{c}\right|}{\left|\Omega\right|}=\frac{365}{365}\cdot\frac{364}{365}\cdot\ldots\cdot\frac{365-n+1}{365}=\prod_{k=0}^{n-1}\left(1-\frac{k}{365}\right)$

Therefore, the probability that at least two people were born on the same day is:

$latex P\left(A\right)=1-P\left(A^{c}\right)=1-\prod_{k=0}^{n-1}\left(1-\frac{k}{365}\right)$

So, said $latex n=40$ right? lets calculate! (Don’t worry, you can let WolframAlpha do the calculations for you)

$latex P\left(A_{40}\right)=1-\prod_{k=0}^{39}\left(1-\frac{k}{365}\right)\approx 0.891232$

So it seems the probability is more than 89%! Amazing, isn’t it?

If you want, you can checkout and find that after 23 people, the probability pass the 50% barrier, and that after only 57 people the probability is more than 99%!

1 comment   |  tags: , | posted in Math