## Interview Question

## Interview Answer

4 Answers

I think the answer should be this:

Since the probability of getting two heads in a row and getting two tails in a row is the same, we only need to figure out the probability of the total. The remaining event is:

1 head 1 tail......due to different order, events should be 2

Therefore the probability=0.5(1-2(1/2)^N)=0.5(1-(1/2)^(N-1))

Only solution I could think of, which took quite some time, was to actually start by drawing a tree of possible outcomes. From there, I could see only three different states at each node. Either I am in a state similar to my initial state (when I toss a tail), I can also be in tilt state (I have just flipped heads after flipping a tail) or I am in the done state (I have just flipped heads after having flipped heads before).

I consider that someone would only continue flipping if he/she has not flipped two heads in a row. That is, is not in the done state.

That is, for any toss level N, it wrong to assume that number of nodes is equal to 2^N. It will be strictly smaller as of level N = 3.

Anyway, after 3-4 levels drawn, one should see a pattern, that is, the number of tails, or initial state nodes (is), at a level N is equal to the number of is's I had at level N-1 + the number of is's I had at level N-2. We can thus write:

is(N) = is(N-1) + is(N-2).

we then realize that at every level N, the number of tilt nodes (t) is equal to the number of initial states from the previous level. That is:

t(N) = is(N-1)

That makes sense, because on the level N-1, all initial states output one tail (becoming a new initial state at level N) and a heads (becoming a tilt state at level N). the other states of level N-1 are either done (so no continuation) or tilt. The possible outcomes of a tilt state are either done or initial state (if I flip heads again, I am done, so I can't go from tilt to tilt.)

One then realize that following the same logic, the number of done (d) nodes for a level N is given by:

d(N) = t(N-1) = is(N-2)

that is, at every level (as of the second level, or two tosses), I will have a number of done outcomes equal to the number of initial states to levels (or tosses) ago. So the general recursive formula to get the number of done nodes for a certain level really is:

d(N) = is(N-2) = is(N-3) + is(N-4)

We note, by definition:

is(N) = 0, is N<0

is(N) = 1, if N = 0, or 1

is(N) = is(N-1) + is(N-2) otherwise.

Furthermore, the probability of being at any node of a level N is simply (1/2)^N. So if I want to find the probability that I observed at least one occurrence of 2 heads in a row. I simply add the number of done nodes from level 1 to N multiplying them by the probability of them occurring at each level. That is:

P(hh after N tosses) = sum(from i = 1 to N) (d(i).(1/2)^i).

E.g. for N = 2, I get:

d(1).1/2 + d(2).(1/4) = s(-1).1/2 + s(0).(1/4) = 0 + 1/4.

We know that this is true. you can test it for a larger number of tosses and see it is true. as N goes to infinity, the sum will converge to 1, as I have theoretically no chance of never tossing 2 heads in a row if I throw a coin an infinity number of times.

I haven't found a solution that didn't use recursions. There probably is one, I'd be interested in seeing one.

sorry for all the typos, the solution should be understandable in spite of that.

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

Do you mean Prob(at least 1 observation of 2 consecutive heads appears) ??

Then since the subsets can be:

1. all tails

2. 1 head 1 tail 1 head 1 tail ....

3. at least 2 heads consecutively appear once

So Pr(3) = 1- Pr(1) - Pr(2) = 1- (1/2)^N - (1/2)^N

= 1 - power(1/2,N-1)