Wednesday, April 18, 2007

Something To Think About. Topic: Probability. Level: AMC/AIME.

Problem: A coin is repeatedly flipped. What is the expected number of flips to get two heads in a row? $ n $ heads in a row?


I will be out of town for the next four days, so have fun with the problem!


  1. four times for the two heads in a row
    and... 2n for n heads in a row


    so ur at stanford?? u miss out on concessions... MOOO

  2. Yeah, I'm at Stanford right now. And both of your answers are wrong =P.

  3. Xuan, those answers are correct for n heads total, but it takes a lot more effort to get them all in a row.

    Anyway, the recursion for n looks really ugly...

  4. Another Day, Another Post

    [...] I highly recommend that you check out this blog, I found it quite fascinating [...]

  5. Getting n heads in a row requires 2^(n+1)-2 flips, as follows:
    First, you will need to get n-1 consecutive heads: this will take f(n-1) flips.
    Then, there is a 1/2 chance that your next flip will end the sequence
    There is also a 1/2 chance the next flip will "restart" the sequence, meaning you will have to flip another f(n) times. Putting this together,
    f(n)=f(n-1) + 1/2(1) + 1/2(1+f(n))
    and f(1)=2 so f(n)=2^(n+1)-2

    In general, for a random outcome generator with mutually exclusive outcomes {O1, O2, ..., On} and assigned probabilities {P1, P2, ... Pn} to flip a sequence constructed out of a string of outcomes will be equal to the product of the reciprocals of each of the individual probabilities in the string, plus the expected number of times that it takes to obtain the "overlapping portion" of the string - that is, the proper substring that occurs at both the beginnin of end of the original string. I haven't proven that yet, but I think it's true ._.