Problem: You toss a fair coin times. What is the expected number of occurrences of HH pattern?
Math solution.
Let to denote the expectation we are looking for. Let to denote the conditional expectation given that the first toss is Head. Conditioning on the first toss, we get
Conditioning on the outcome of the second toss:
Plugging this equation into previous one, we get
We can use the first equation to express in terms of and to get recursion:
It has solution:
We could have arrived to this solution in a much easier way.
Physics solution.
It is very reasonable to conjecture that should be a linear function in . If the assumption is correct, we can write two boundary conditions which are easy to compute: . From this we get the same solution as above.
Why must be linear? This can be shown as follows:
Let if th toss begins the HH pattern; otherwise. The number of HH patterns is .
Here we used that , and that is constant for . This shows that is a linear function in . We can see that linearity directly arises from the linearity of expectation, and from the fact that can be represented as a sum of indicator random variables with expectations that do not depend on the position (except for the last one).
Advertisements

Recent Posts
 cvxpy, cvxopt and convex optimization July 2, 2013
 Merging in mercurial with vimdiff June 24, 2013
 Running script in background on linux June 5, 2013
 Installing Scipy on Linux Red Hat May 29, 2013
 Resolving import errors in Python May 15, 2013
 Switching back and forth between tabs and spaces for Python indentation May 10, 2013
 Problems with character encoding when piping output from a python script to a file May 6, 2013
 Installing extensions for Mercurial May 1, 2013
 Running unit tests in Python April 25, 2013
 Great unix one liner to join two tables keys in the first columns April 23, 2013
 Add a new host to known_hosts April 15, 2013
 Python things April 13, 2013
 Interview brainteaser asked at Google February 15, 2013
 Popular computer science interview question: thieves locking treasure in cryptographic way :) February 15, 2013
 C++: some simple pointer arithmetic February 12, 2013
 Things I was never aware of: C++. Comma operator. February 12, 2013
 Binary Search Trees February 12, 2013
 Mounting memory card on Ubuntu February 9, 2013
 Interview questions on Perl February 7, 2013
 Get a notebook! :) February 7, 2013
 Interview question: what is the expected number of occurrences of a “HH” pattern in n tosses of an unbiased coin? February 7, 2013
 Pulling info about running processes on Ubuntu February 4, 2013
 Opening files in Python using “with” block to type less February 4, 2013
 Executing JavaScript and getting returned value back to Python, when using Selenium webdriver February 4, 2013
 Note on a differencing and lag operators in time series modeling February 2, 2013
 Running Selenium Server on Ubuntu 10.04 February 2, 2013
 Using Selenium with Python for Web Crawling February 1, 2013
 Reversing linked list January 24, 2013
 Sorting Algorithms January 24, 2013
 Interview questions on UNIX January 24, 2013
Categories
Archives