Thursday, February 11, 2010

Math challenge

I'm proud to say I came up with this one myself:

Consider an experiment where I continuously flip a coin until I get ten heads in a row, after which I terminate the experiment. Let X be the number of times I end up flipping the coin before this sequence of ten heads begins. What is the most likely value of X?


  1. Nice challenge, it took me a couple of minutes to think about this in the right way.

    Answer is 0.

    P(X=0) is just the probability of ten heads or 0.5^10.

    For X = 1-10 you'd need the last 11 flips to be a tail followed by ten heads in a row so 0.5^11.

    The probabilities for X>10 would be similar to the probabilities for x = 1-10 except you'd also need to exclude the possibility of ten heads in a row having already come up earlier in the coin tossing sequence so they would be less than 0.5^11.

  2. For 11<=X<=20, I think the odds are 0.5^11*q(X-1), where q(x) is the probability of x flips with at least one tail. I figure q(x) = 1 - r(x), where r(x) is the probability of every single flip being a heads, i.e 0.5^x. So I think for 11<=X<=20, the odds would be:

    p(x) = (1 - 0.5^(x-1))*0.5^11

    Heh, which is interesting, because the probability actually climbs slightly in that region as X increases, if I haven't made an error...

    For X>20, I am totally lost. :/

  3. Not sure that formula for 11<=X<=20 works. For example for X=15 the formula would allow the following set of flips:
    13 heads followed by a tail (this satisfies q(X-1) followed by a tail and then 10 heads.

    I think P(X=11) is 0.5^11 * (1-probability that the first ten coin flips were all heads) so:

    0.5^11*(1-P(X=0)) = 0.5^11*(1-0.5^10).

    P(X=12) is 0.5^11 * (1 - the probability taht the first ten coin flips were all heads or that the first 11 flips were a tail followed by 10 heads.) so:

    0.5^11*(1-P(X=0) - P(X=1))
    = 0.5^11*(1-0.5^10-0.5^11).

    In general for x>10 I think

    P(X=x) = 0.5^11*(1 - r(x-10))

    Where r(x) is P(X=0)+P(X=1)...+..P(X=x).

    (If I could work out how to put in proper maths notation with a sigma symbol this expression might have been more compact :))

    Im pretty sure that probability always decreases as X increases.

  4. Bah, you're right, I was thinking that a single tails was all it took, but the placement of the tails is key too..

    Your formula sounds right... I'll have to think about it some more...

  5. Slight correction.

    Formula should have been:

    P(X=x) = 0.5^11*(1 - r(x-11))

    Or more succinctly :

    P(X=x) = 0.5^11*(1 - P(X<=x-11))

  6. For super bonus challenge, compute the expected value of X. If I could remember how to take the limit of an infinite series...