Problem: You toss a fair coin times. What is the expected number of occurrences of HH pattern?
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.
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).
- 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
- 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