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).

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: Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s