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