Waiting, again II

[bonanova]

I find probability questions interesting, because they often defy intuition. Particularly for me are those that involve waiting times. Other than the basic idea of an event of probability p needing on average 1/p trials to occur. But here's one not that trivial, yet still fairly easy to solve -- with the right approach.

On average, how many times do you need to flip a fair coin before you have seen a (continuous) run of an odd number of heads followed by a tail?

For example, T T H H H H T H H H T took 11 flips.

Edited January 17, 2018 by bonanova
clarification

[CaptainEd]

Spoiler

As you said, it IS easy, after a while of thinking I’m clueless.

My solution is a recursive evaluation, based on a two/state machine.
The two states are based on parity of H seen so far, “Even” and “odd”

In even state

H -> 1/2 (1+ odd)
T -> 1/2 (1+ even)

To summarise: 

Even = 1/2(1+odd) + 1/2(1+even)

Similarly, 

Odd = 1/2(1+even) + 1/2 = 1 + even /2

Substitute odd into even

Even = 1/2 + 1/2(1+even/2) + 1/2 +even/2
        = 3/2  + 3even/4

Solve for even

1/4 even = 3/2
Even =6

 

Edited January 17, 2018 by bonanova
Add spoiler

[bonanova]

6 hours ago, CaptainEd said:

  Hide contents

... based on parity of H seen so far  ...

 

Not sure if it was clear that the run of odd number of heads are contiguous, as in the example, or if I'm misunderstanding your algorithm. Can you add some words here and there?

[CaptainEd]

Spoiler

 

Before any coin is flipped, there are an even number of heads. This is the Even state; if a Head is flipped, we go to the Odd state. Whenever we flip a Tail in Even state, we are back to zero which is Even state. If we get a Tail in Odd state, we win!

If we get a Head in Odd state, we go to Even state. If we get a tail in Even state, we go to Odd state.

 

 

Edited January 18, 2018 by bonanova
Added spoiler / reduced type size

[CaptainEd]

Transition diagram

In Even State: H->Odd, T-> Even

in Odd state: H-> Even, T->Terminate(win)

i believe this is sufficient to keep track of parity of Heads.

each transition adds 1 to Flip count

Edited January 17, 2018 by CaptainEd

[bonanova]

@CaptainEd - Nice solve.

Here is a solution i was aware of.
I think the two are similar or equivalent, parsed out into a different set of states.
 

Spoiler

Let e be the expected number of flips.
There are three early states that are easy to analyze and cover all the possibilities:

1. T consumes 1 flip and, because it cannot be part of the solution, requires e more flips.
2. HH consumes 2 flips and, even tho it could be part of a solution, it also requires e more flips.
3. HT consumes 2 flips and, because it is a solution, requires no more flips.

That allows us to write an expression for x as the sum of these terms, weighted by their respective probabilities: 1/2, 1/4, 1/4.

   e = 1/2{1+e} + 1/4{2+e} + 1/4{2}.

4e = 2+2e + 2+e + 2.

   e = 6

 

[CaptainEd]

much more clearly stated than my babbling. I’m tickled that I’ve shown that it can be evaluated one flip at a time, based merely on the parity of contiguous Hs.

here is my argument, expressed by plagiarizing your expression:

Let e be the expected number of flips from the initial (even) state
There are two states that are easy to analyze and cover all the possibilities: 

1. E is the initial state, it also represents the state of having seen an even number of H (including zero), since the beginning or the most recent T.
2. O is the odd state, representing the fact of having seen an odd contiguous run of H.
3. State E  requires e more flips. In this state, H changes to state O, while T remains in state E
4. State O requires o more flips. In this state, H changes to state E, while T terminates with a win.

That allows us to write an expression for x as the sum of these terms, weighted by their respective probabilities, all 1/2.

   e = 1/2{1+e} + 1/2{1+o}

   o = 1/2{1+e} + 1/2

substitute o into e

e = 1/2{1+e} + 1/2{1+1/2{1+e} + 1/2}

= 1/2{1+e} + 1/2+1/4+e/4 + 1/4

= 3/2 + 3e/4

e/4 = 3/2

e = 6