THE GEEK-STREAK!

Here we go with a Geeky Story that happened once upon a time on the planet earth.
It is friday night & Bill is totally bored.The geek that he is,his idea of fun was to show off his 'geeky gyaan'.The only person unaffected by this was Steve,another geek!So Bill goes over to Steve's place and shoots a problem over him which would win Steve'The Imaginary Cup'.
The problem is to find the longest Streak of heads when a coin is tossed $n$ times.Take for example we toss a coin 10 times.Say we get the following sequence H,H,T,H,H,T,H,H,H,T.The longest Streak of heads here is 3. Bill asks Steve to toss a coin 10000 times & challenges him that the longest sequence of head he's going to get will be around 10 woah!Now Steve wants to prove him wrong.He quickly types a code in his mac pc to verify & bingo! Bill was right afterall!Bill further says its going to be around 10,11,12,14 for 20000,50000,100000,1000000 tosses respectively.And it turns out that it almost matches every time.Steve will be quick enough to figure out that its following $ln(n)$.
Egoistic that Steve is,he decides to find out all by himself whats happening & how Bill is able to predict the value right each time.He jots down the following points.Since during that time Steve was an intern in MIT,Computer Science Dept., he was much into theoretical computer science which was diametrically opposite to coding. So he thought why shouldnt he apply his theoretical knowledge into this!!
These thoughts came rushing into his mind:
-->when he tosses a coin the probability that he will get a head is $\frac{1}{2}$.
-->He assumes that $k$ is the longest Streak.
-->If the coin is tossed for the second time the probability that he will get a head again is $\frac{1}{2}*\frac{1}{2}$ by the product rule.
-->If this is carried out $\n$ times, then starting from any point in first $n-(k-1)$ tosses the probability that he gets a Streak of heads of length $k$ will be $\frac{1}{2}^k$.
-->But since his aim is to find the maximum Streak,he considers the worst case which would be,not getting the MAX Streak of length $\k$ for all the $\n$ trials that he does.
-->The probability would then be, $(1-\frac{1}{2}^k)^n$
-->For the worst case,the probability of this happening will be greater than half,which means the $k$ which he gets after solving this inequality will be the maximum possible $k$ for $n$ tosses.
-->In notations:
$(1-\frac{1}{2}^k)^n>1/2$
Applying binomial expansion to the above:
$(1-\frac{1}{2}^k )^n= 1- n*(\frac{1}{2})^k + \frac{n*(n-1)}{2!}*(\frac{1}{2^k})^2 - \frac{n*(n-1)*(n-2)}{3!}*(\frac{1}{2^k})^3 + ....$
The above equation is nothing but the expansion of $e^(-\frac{n}{2^k})$
So, now he has the inequality:
$e^(-\frac{n}{2^k})$>$\frac{1}{2}$
Applying logarithm on both sides of the above inequality, we get
$-\frac{n}{2^k} > ln(\frac{1}{2})$
Proceeding further...
$-n > 2^k*ln(\frac{1}{2})$
$n>2^k*ln(2)$
$2^k<\frac{n}{ln(2)}$
$k<ln(\frac{n}{ln(2)})$
$k< ln(n)-\ln(ln(2))$
$k< ln(n)$
The above $k$ is the maximum $k$ he gets for $n$ tosses of a fair coin!.
Steve tells bill "Dude, now thats the power of mathematics, and when combined with coding can win you 'The Imaginary Cup'!".
Not to mention this was to remind Bill of 'The Imaginary Cup'.
So,what is the moral of the story?
Everything in the Universe follows a specific pattern.We need to just figure it out and get great results,just the way Steve figured out that the answer was always around $ln(n)$.Same concept applies to our friends' Birthday paradox and Coupon Collector problems. Always look for a pattern and it can earn you a fortune.Theoretical Computer Science ( thats comp science minus coding)is one of the amazing fields wherein you are actually paid to make such observations. An event like tossing a coin which seems to be completely probabilistic can actually satisfy a mathematical equation (inequality to be more appropriate!).
Sounds dramatic right?
The real moral of the story is : Never ever underestimate Steve!He is one hell of a genius!!

--Nikitha Shenoy K
--Shruti Vinayaka Ranade

Collect them all!

Coupon Collector Problem

Have you ever heard of ads that say "Collect All 27" or "Collect All 50" or "Collect All Whatever"?? I'm pretty sure that almost all of you had a craze to collect all of those 'stuff' in your childhood days. But have you ever wondered how many items that you'd have to buy the item to collect all those 'stuff'? Thats the Coupon Collector Problem.

What is $e$?

Lets start answering this question by a popular joke.

Once $e^x$ and $logx$ were walking down the street. From the other end, they saw a differential walking towards them. $logx$reeched and started running away from the differential. But $e^x$ stood tall and said 'Haha, you are no match for me. No matter what you try to do, you cannot cause me any trouble!'. The differential replied, "I'm $\frac{d}{dy}$!".

But what is this $e$? $e$ is a convergent infinite series. By 'convergent', we mean that the infinite series tends to a particular value. $e$ is given by:

$e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + ...$

Clearly, we can see that this value is greater than 2.

We know that $\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + ... = 1.$ Compare this series with $(\frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + ...)$. The latter must be lesser than the former. Hence $(\frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + ...) < 1$. Therefore, $e$ must be a value between 2 and 3. That is, $2 < e < 3$. By actual computation (upto a certain limit ofcourse), we find the value of $e$ happens to be 2.7182818284590451. Now thats $e$!

What has $e$ got to do with the coupon collector problem?

You'll see.

Consider a group of $n$ people. Lets say you know just 1 among them. If a person is picked randomly, the probability that the chosen one happens to be the person you know is $\frac{1}{n}$. But how many trials should you take until the randomly chosen person is the one you know? Its $n$.

Lets say you know 2 among the group. Now the the probability shifts to $\frac{2}{n}$. In this case, you'll have to take $\frac{n}{2}$ trials. Now we see a connection here, if the probabilty of of an event occuring is $k$, you'll have to perform $\frac{1}{k}$ trials to see the event happen.

Now that we're done with the prerequisites, lets start off with the actual problem.

Lets say you get a coupon for free whenever you buy an item. Let there be $n$ such coupons. You'll have to collect all the coupons.

At the start, you have no coupons with you. Any item bought will add a new coupon to your collection.

The second time you buy an item, the probability of you getting the same old coupon is $\frac{1}{n}$. But you need a new coupon, not the ones already collected. The probability of getting a new coupon is $1 - \frac{1}{n}$, that is $\frac{n-1}{n}$. Hence you'll have to make $\frac{n}{n-1}$ trials.

The third time you buy an item, the probability of you getting a new coupon is $1 - \frac{2}{n}$, that is $\frac{n-2}{n}$. This is because you have already collected 2 different coupons. To get the third coupon, you'll have to buy $\frac{n}{n-2}$ items.

Similarly, to get the $K$th coupon, you'll have to buy $\frac{n}{n-(k-1)}$. Summing this over the range $[1,n]$, we get the following:

Number of items purchased =

$\sum_{k=1}^{n}\frac{n}{n-(k-1)}$

=$1+\frac{n}{n-1}+\frac{n}{n-2}+\frac{n}{n-3}+\frac{n}{n-4}+...$

=$n*(\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+\frac{1}{n-3}+\frac{1}{n-4}+...)$

=$n*\log_e n$

Could find out where $e$ popped into the picture? Its hidden in the last step of the proof. Thats right, $\log_e n$.

Blog Authors:

Vijay

Vijesh

The Birthday Paradox

The Birthday Paradox

BIRTHDAYS!!!! Birthdays make us feel so special...the celebration…the cake…the candles...the balloons... (Of course the Surprise gifts too!!).We had a surprise gift waiting for us a Monday morning. We had Mr. Sudarshan's lecture on Discrete Mathematics and combinatorics. The name of the subject scared us. 'The Pigeon Hole principle', he started. We will try to summarize it for you. Assume there are 6 pigeons and 5 holes. Let us say, each pigeon occupies a hole which means that 5 pigeons occupy the 5 holes and the remaining 1 pigeon has to share a hole with an another one. Hence 2 pigeons share the same hole.

Similarly, consider 365 holes. We need at least 366 pigeons so that one hole is guaranteed to be occupied by 2 pigeons. Let us apply a little transformation to the statement.

Holes : pigeons :: days : people

A simple analogy states that 2 out of 366 people share the same birthday. It seemed clear to us. But he had a different statement to make. He was damn sure that he would find 2 out of 30 randomly chosen people who shared a common birthday. And guess what?? HE WAS RIGHT!! Two of our friends shared a common birthday. While we wondered how this can happen, he was ready with his marker pen to prove his claim. Little did we know that there are mathematical reasons behind it.

Consider there are $N$ number of people around you. What should be the average value of that $N$ so that you can guarantee with more than $50\%$ probability that there at least $2$ people sharing the same birthday?

i.e. Approximately how many people will you choose from a lot, such that you find 2 people with same birthday ?

1. By not considering the leap years

2. Assuming uniform distribution of birthdays throughout the year.

Value of $N$ can be found as follows..

Let us begin by taking a good look at the following equation. Plays an important role u see.. :P

$e=\left(1+\frac{1}{n}\right)^n$

$e^{\frac{1}{n}}=(1+\frac{1}{n})$

$e = \left ( 1-\frac{1}{n} \right )^{-n}$

$e^\frac{-1}{n} = \left ( 1-\frac{1}{n} \right )$

Let us choose one person at a time and compare his birthday with already chosen set of people to see if there is NO match

Select 1^st person out of the $N$ present. Let his name be Mr. Tom. The probability of Mr.Tom

not sharing the same birthday as someone else is 1 i.e. $\frac{365}{365}$. That is obvious isn’t

it?...:) He is the only one selected so far and hence there is no chance of having a match.

Now choose the 2nd person. Let us call him Mr. Jerry. Now there are 2 possibilities.

1. Mr. Jerry sharing the same birthday as Mr. Tom.

2. Mr. Jerry having a different birthday.

Hence the probability of Mr. Jerry NOT having the same birthday as Mr. Tom is product of 2 probabilities

i.e.$\frac{365}{365} \times \left(1 -\frac{1}{365}\right)$

Probability of 1^st person * Probability of 2^nd person

not having same birthday not having the same birthday as the first one

Now choose the 3rd person named Mr. Bluto. With similar reasoning as above, probability of Mr.Bluto not sharing the same birth date is :

$\frac{365}{365} \times \left(1 -\frac{1}{365}\right) \times \left(1 -\frac{2}{365})\right$

Probability of 1^st person * Probability of 2^nd person * Probability of 3^rd person

not having same b'day not having the same b'day not having the same b'day

as the 1^st one as the 1^st one & 2^nd one

The improbability of N person having the same birthday would be:

$\frac{365}{365} \times \left(1 -\frac{1}{365}\right) \times \left(1 -\frac{2}{365}\right) \times \cdots\cdots \times \left(1 -\frac{N-1}{365}\right)$

When the probability of not having the same birthday becomes less than $0.5$, then the probability of having the same birthday becomes dominant..:):)

$\frac{365}{365} \times \left(1 -\frac{1}{365}\right) \times \left(1 -\frac{2}{365}\right) \times \cdots\cdots \times \left(1 -\frac{N-1}{365}\right)\leq 0.5$

The point where this transition occurs gives us our most awaited N...Now now…a little patience there. We still require few more steps to arrive at N…:) Do you remember the equations we asked you to take a good look at? If not please scroll back and check out the equations. We will be using them here…:)

$\frac{365}{365} \times \left(1 -\frac{1}{365}\right) \times \left(1 -\frac{2}{365}\right) \times \cdots\cdots \times \left(1 -\frac{N-1}{365}\right)\leq 0.5$

$1\times e^\frac{-1}{365}\times e^\frac{-2}{365}\times\cdots \times e^\frac{(N-1)}{365}\leq 0.5$

$e^{\frac{-1}{365}\times (1+2+3+\cdots+(N-1))}\leq 0.5$

Apply the following formula to the above equation and let us see what happens.

$1+2+3+\cdots +k = \frac{k(k+1)}{2}$

$e^{\frac{-1}{365} \times {\frac{N(N-1)}{2}}} \leq 0.5$

Applying Logarithms on both sides, we get

$\ln e^{\frac{-1}{365} \times {\frac{N(N-1)}{2}}} \leq \ln 0.5$

$\frac{-1}{365}\frac{N(N-1)}{2} \leq -0.693$

Simplifying it, we get a quadratic equation

$N^2-N-506=0$ (Finding $N$ for $50\%$ probability i.e. considering just the equality )

The roots of this equation are,

$N=23 , -22$

As number of people is a positive quantity, we consider $N=23$.

Voila !!!!!!!!! Here we are…. :) :)

So what’s the moral of the story?? ;)

On an average case, given $23$ members there is $50\%$ probability of you finding $2$ members who share the same birthday…..Amazing isn’t it?..!!!!!!!!!!!!!!!!!!!!!!!

So what are you waiting for??? ;) Go out, make a bet. Tell your friend that you can find $2$ out of $30$ random people(on an average) who share the same birthday. No doubt, you will win it. Get back to us and let us share the money ;)

Three cheers to Math...:) :) :)

By the way, if u reading this today and it happens to be your birthday...Wish you A Very HAPPY BIRTHDAY :)

Shobitha Shetty

Shruthi Nayak