Interview question: what is the expected number of occurrences of a “HH” pattern in n tosses of an unbiased coin?

Problem: You toss a fair coin n times. What is the expected number of occurrences of HH pattern?
Math solution.
Let E_{n} to denote the expectation we are looking for. Let E_n^H to denote the conditional expectation given that the first toss is Head. Conditioning on the first toss, we get
E_n = \frac{1}{2} E_{n-1} + \frac{1}{2} E_n^H
Conditioning on the outcome of the second toss:
E_n^H =  \frac{1}{2}E_{n-2} + \frac{1}{2}(1 + E_{n-1}^H)
Plugging this equation into previous one, we get
E_n = \frac{1}{2} E_{n-1} + \frac{1}{2} (\frac{1}{2}E_{n-2} + \frac{1}{2}(1 + E_{n-1}^H))
We can use the first equation to express E_{n-1}^H in terms of E_{n-1} and E_{n-2} to get recursion:
E_n = \frac{1}{4} + E_{n-1}
It has solution:
E_n = \frac{(n - 1)}{4}
We could have arrived to this solution in a much easier way.
Physics solution.
It is very reasonable to conjecture that E_n should be a linear function in n. If the assumption is correct, we can write two boundary conditions which are easy to compute: E_1 = 0,\; E_2 = \frac{1}{4}. From this we get the same solution as above.
Why E_n must be linear? This can be shown as follows:
Let X_i = 1 if i-th toss begins the HH pattern; X_i = 0 otherwise. The number of HH patterns is N = \sum\limits_{i=1}^n X_i.
E[N]= \sum\limits_{i=1}^n E[X_i] = \sum\limits_{i=1}^{n-1} E[X_i] = \sum\limits_{i=1}^{n-1} P(X_i = 1) = p(n - 1)
Here we used that P(X_n = 1) = 0, and that P(X_i = 1) is constant for i < n. This shows that E_n is a linear function in n. We can see that linearity directly arises from the linearity of expectation, and from the fact that N 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
This entry was posted in Interview, Math, Probability Theory and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s