Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
bonanova

Waiting, again II

Question

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 by bonanova
clarification

Share this post


Link to post
Share on other sites

6 answers to this question

  • 0
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 by bonanova
Add spoiler

Share this post


Link to post
Share on other sites
  • 0
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?

Share this post


Link to post
Share on other sites
  • 0
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 by bonanova
Added spoiler / reduced type size

Share this post


Link to post
Share on other sites
  • 0

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 by CaptainEd

Share this post


Link to post
Share on other sites
  • 0

@CaptainEd - Nice solve. bona_gold_star.gif

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

 

Share this post


Link to post
Share on other sites
  • 0

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

 

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×