coin toss

Discussion in 'Recreational Math' started by Fakename, Sep 4, 2005.

  1. Fakename

    Fakename Guest

    If you toss a coin 100 times, what's the probability of getting 5 (either
    heads or
    tails in a row)? 6 in a row?
    How do you figure it out?
     
    Fakename, Sep 4, 2005
    #1
    1. Advertisements

  2. Fakename

    sjherschko Guest

    The answer to the last question is, "Recursively, by a Markov
    conditioning argument."

    Let a coin have probability p of coming up heads, 1-p of coming up
    tails. If we flip the coin n times, what is the probability that
    there is at least one instance of k consecutive identical toss
    outcomes? We assume k>1.

    In the following, the third argument i=1 indicates the event of a run
    of k in the n tosses; i=0 indicates the complement of this event.

    For 0 < x < k, let q(n,x,i) be the joint probability that tosses
    n-x+1 through n come up heads and, if x < k-1, toss n-x comes up
    tails.
    For -k < x < 0, let q(n,x,i) be the joint probability of this event
    given that tosses n+x-1 through n come up tails and, if x > 1-k,
    toss n+x comes up heads.

    We want
    sum(x=1..k-2, p^x (1-p) q(n,x,1) + (1-p)^x p q(n,-x,1)) + p^(k-1)
    q(n,k-1,1)
    + (1-p)^(k-1) q(n,1-k,1).


    q(n,x,i) = 0 if n<k.

    In the sequel, assume n>=k-1.

    q(n+1,k-1,1) = p [q(n,k-1,0) + q(n,k-1,1) + q(n,k-2,1)]
    q(n+1,1-k,1) = (1-p) [q(n,1-k,0) + q(n,1-k,1) + q(n,2-k,1)]
    (If k=2, omit the terms with k-2 or 2-k.)

    For x>1 and (i=0 or x<k-1),
    q(n+1,x,i) = p q(n,x-1,i)
    q(n+1,-x,i) = (1-p) q(n,1-x,i)

    q(n+1,1,i) = p sum(j=1..k-1, q(n,-j,i))
    q(n+1,-1,i) = (1-p) sum(j=1..k-1, q(n,j,i))


    -S.J. Herschkorn
    Math Tutor in Central New Jersey and Manhattan
     
    sjherschko, Sep 5, 2005
    #2
    1. Advertisements

  3. Fakename

    Fakename Guest

    Thankyou. ....now if someone will just explain to me what he just said.

     
    Fakename, Sep 5, 2005
    #3
  4. Here's an easier way...

    Let n be the number of tosses, and let x be the run length. We want the
    probability that within the n tosses there is at least one run of at
    least x consecutive heads or tails.

    For i = 1,2,3 ... x-1, write down the numbers 2^(i-1). You have x-1
    numbers written down. Calculate the next number as the sum of the
    previous x-1 numbers, and repeat this until you have n numbers. Denote
    the n'th (and last) number by y. The desired probability is 1 -
    2*y/2^n. I THINK!!!

    For x=2 and x=3 there will be a closed form solution for this
    probability, but I'm not sure if there is for larger x, or how
    complicated it gets. I might have a look at it...

    Example. What is the probability of getting a run of at least 4 in 10
    tosses (n = 10, x = 4)?

    First write down the numbers:

    1,2,4

    The next number is 1+2+4 = 7, so now you have

    1,2,4,7

    The next number is 2+4+7 = 13, so now you have

    1,2,4,7,13

    Continue until you have 10 numbers:

    1,2,4,7,13,24,44,81,149,274

    The probability is 1 - 2*y/2^n = 1 - 2*274/2^10 = 0.46484375.

    To answer your specific cases, I get the following results to 8 d.p.:

    For n = 100, x = 5, Prob = 0.97168967
    For n = 100, x = 6, Prob = 0.80682055

    It helps if you use a computer!
     
    matt271829-news, Sep 6, 2005
    #4
  5. Care to justify this answer? It rationale is not obvious to me.

    Also, it looks like you are addressing the case of a fair coin only.
     
    Stephen J. Herschkorn, Sep 6, 2005
    #5
  6. Correct, I assume a fair coin (which I'm pretty sure is what the OP
    meant).

    Let me illustrate the derivation with x = 4, and you will see how it
    extends to all x.

    I construct a table of the count of all the different possible
    sequences of length n, such that there is no run of length 4 or
    greater. I break this down by possible endings: end with TH, THH, THHH,
    HT, HTT, or HTTT (no other ending is possible else you would have a run
    of at least 4).

    The first row, for n = 4, is easy to construct from first principles:

    n TH THH THHH HT HTT HTTT
    - ---- ---- ---- ---- ---- ----
    4 4 2 1 4 2 1

    To construct the next row we notice:

    - To end on TH with n = 5 we must have ended on HT, HTT or HTTT with n
    = 4 and then got H. There is only one way to get H; therefore the entry
    for n = 5, TH must be 4 + 2 + 1, or 7.

    - To end on THH with n = 5 we must have ended on TH with n = 4 and then
    got H. Therefore the entry for n = 5, THH must be 4:

    - To end on THHH with n = 5 we must have ended on THH with n = 4 and
    then got H. Therefore the entry for n = 5, THHH must be 2:

    And the second half of the table fills in in exactly the same way to
    give:

    n TH THH THHH HT HTT HTTT
    - ---- ---- ---- ---- ---- ----
    4 4 2 1 4 2 1
    5 7 4 2 7 4 2

    Now I'll continue the table for the next few rows:

    n TH THH THHH HT HTT HTTT
    - ---- ---- ---- ---- ---- ----
    4 4 2 1 4 2 1
    5 7 4 2 7 4 2
    6 13 7 4 13 7 4
    7 24 13 7 24 13 7
    8 44 24 13 44 24 13

    If we extend back to n = 2, where n = 2, 3 are "dummy" entries, you can
    see that numbers in the TH column for n = 2,3,4,5,... are
    1,2,4,7,13,24,... where 1,2,4 are the ascending powers of 2 that "kick
    off" the sequence, and thereafter each term in the sequence is the sum
    of the previous three terms.

    The number in the TH column is always half the sum of the previous row,
    so the same sequence 1,2,4,7,13,24,... serves to give us the half-sums
    for n = 1,2,3,4,...

    Let y be the n'th term in this sequence, and assume n >= 4. y is half
    the total number of sequences of n tosses s.t. there is no run of
    length >= 4. Therefore the total number of such sequences is 2*y. The
    total number of sequences overall is 2^n, and all sequences are
    equiprobable, so the probability that there are no runs of length >= 4
    is 2*y/2^n, and the probability that there is at least one run of
    length >= 4 is 1 - 2*y/2^n.
     
    matt271829-news, Sep 6, 2005
    #6
  7. I follow what you are doing, but you have to work out some kinks. For
    x=4, the answer for n=4 is 2/16 = 1/8, and the answer for n=5 is
    6/32 = 3/16. (I get these considering all possible sequences of four or
    five tosses.) Your formula gives 1 - 2*4 / 16 = 1/2 and 1 - 14/32 =
    9/16, respectively.
     
    Stephen J. Herschkorn, Sep 6, 2005
    #7

  8. Ah, I see now: The value for n tosses is 1 - y_(n+1) / 2^(n-1), where

    y_n = 2^(n-1) for n < x
    y_n = sum(k=1..x-1, y_(n-k)) for n >= x,

    as you said to begin with. Very good.
     
    Stephen J. Herschkorn, Sep 6, 2005
    #8
  9. I think you misread. For x = 4 the relevant sequence is, as stated,
    1,2,4,7,13,24,...

    The fourth term is 7, so the probability for n = 4 is 1 - 2*7/2^4 =
    1/8.

    The fifth term is 13, so the probability for n = 5 is 1 - 2*13/2^5 =
    3/16.

    This agrees with your answers.
     
    matt271829-news, Sep 6, 2005
    #9

  10. Now that I understand your method, we can generalize it to a coin with
    probability p of coming up heads. Let me revert to the use of k to
    represent the length of the run of identical outcomes.

    Let x(n,j) = the probability of ending up on the nth toss with a string
    of exactly j heads and never having thrown k identical tosses
    consecutively, 0 < j < k.
    Let y(n,j) = the probability of ending up on the nth toss with a string
    of exactly j tails and never having thrown k identical tosses
    consecutively, 0 < j < k.
    Our desired probability is 1 - sum(j=1..k-1, x(n,j) + y(n,j)).

    x(k,j) = p^j (1-p)
    y(k,j) = p (1-p)^j

    For n >= k,
    x(n+1, 1) = p sum(j=1..k-1, y(n,j))
    x(n+1, j) = p x(n, j-1) for j > 1
    y(n+1, 1) = (1-p) sum(j=1..k-1, x(n,j))
    y(n+1, j) = (1-p) y(n-1, j) for j > 1

    Thus, another way to express our answer is 1 - [x(n+1,1)/p +
    y(n+1,1)/(1-p)]. Off hand, I don't see a way to simplify this recursion
    as Matt did for the case of p = 1/2.
     
    Stephen J. Herschkorn, Sep 6, 2005
    #10
  11. Incorrect. We simply want sum(x=1..k-1, q(n,x) + q(n,-x)).
    This is also incorrect for i = 0. However, since I prefer Matt's
    method, I will not go through the effort of coming up with the correct
    formulae.
    Actually, the case of k=2 is easy to treat on its own.
     
    Stephen J. Herschkorn, Sep 6, 2005
    #11
  12. Nope, I scribbled out a few expansions and nothing immediately leapt to
    my mind either. You never know with these things though!
     
    matt271829-news, Sep 6, 2005
    #12
  13. Fairly obviously, for x = 2 the closed form expression for the
    probability is:

    1 - 1/2^(n-1)

    For x = 3 it is:

    1 - ((1+sqr(5))^(n+1) - (1-sqr(5))^(n+1))/(2^(2*n)*sqr(5))

    And for x = 4 it is:

    1 - (f(a) + f(b) + f(c))/2^(n-1)

    where:

    a, b and c are the three roots of x^3 + x^2 + x - 1 = 0 (two of
    which are complex), and f is defined as

    f(z) = 1/(z^(n+1)*(1 + 2*z + 3*z^2))

    Beyond this I don't know!
     
    matt271829-news, Sep 7, 2005
    #13
  14. Fakename

    Dana DeLouis Guest

    the n'th (and last) number by y. The desired probability is 1 -
    Hi. This link suggests you are very close, but slightly off.
    http://mathworld.wolfram.com/Fibonaccin-StepNumber.html

    Ok course, I'm not sure. A brute force on small sizes suggest the following
    is correct...
    [Using Mathematica 5.2]

    n = 10; k = 4;

    1. - FibonacciNStep[n + 2, k]/2^n

    0.2451171875

    n = 100; k = 5;

    1. - FibonacciNStep[n + 2, k]/2^n

    0.810109599196358

    Hope I got it right. :>)
     
    Dana DeLouis, Nov 12, 2005
    #14
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.