Probability with a Weighted Coin

Date: 04/12/2001 at 13:11:37
From: Jane Skinner
Subject: Probability: Weighted coin, 3 heads in a row

Hi,

I am trying to understand the answer to:

  Three Heads in a Row
  http://mathforum.org/dr.math/problems/curtis.01.25.01.html   

which talks about how many flips of a coin on average will it take to 
get three heads in a row. I'm getting lost with all the 1/2's floating 
around.

What if the coin is weighted so that the probability of getting a head 
is only 1/3? What if, instead of asking how many flips on average it 
takes to get two heads, I want to be 99% sure of getting two heads?

For my weighted coin, I think the second equation changes from:

     x = (1/2)(1+x) + (1/4)(2+x) + (1/4)(2)
to
     x = (2/3)(1+x) + (1/3)(2/3)(2+x) + (1/3)(1/3)(2)

     1 tail + x flips, 
     1 head, 1 tail  + x flips
     2 heads + no more flips

but I just don't see where I'd stick in a 99% requirement.   

Is there a formula for this or, if the question gets more complex, do 
I just need to write out all the possible permutations? (There has to 
be a better way...)

Date: 04/12/2001 at 23:58:46
From: Doctor Pat
Subject: Re: Probability: Weighted coin, 3 heads in a row

Jane,

Perhaps a Markov matrix approach will help you see what is happening 
here; it always made more sense to me.

Imagine that the process could be in any of four states (no heads in a 
row, one head on last flip, two heads in a row, three heads in a row).

Now if you're shooting for three in a row, all the other states are 
temporary, but once you've had three in a row, you want to preserve 
the honor; it's permanent. Let's lay out some probabilities for any 
coin. Call the probability of flipping heads p, and that of tails q. 
Then the probability that you go from NO heads to one head is p, and 
that is also the probability that you go from one to two, or two to 
three. On the other hand, at any position of two or less in a row, you 
go back to zero with probability q.

So the matrix looks like this:

                  TO
             0   1   2   3
           +---------------
     F   0 | q   p   0   0
     R   1 | q   0   p   0
     O   2 | q   0   0   p
     M   3 | 0   0   0   1

Now only the 4x4 matrix is part of the problem, the "FROM and "TO" is 
just to help make the process clear.  

Now if we multiply this matrix by itself, we get the probabilities 
after two flips. If we continue to raise it to the nth power, we get 
the probabilities after n flips.

Here is the fifth power of a matrix using p = 1/3 and q = 2/3 I will 
just copy the first row since that is the probabilities starting with 
NO heads.

     .63   .21   .07   .09

Which tells us the probability of being back at no heads in a row 
(tails on our last flip) is 63%, there is a 21% chance we are at one 
heads, 7% we are at two heads, and a 9% chance we have had three in a 
row by now.

If we run that out to ten flips, we get:

     .55   .19   .06   .20

and the last number tells us there is a 20% chance we have a three in 
a row by now.

What you want to know is what power makes that last number greater 
than .95, or .99, or whatever your level of certainty is. Now you can 
multiply out the matrix equation and see what happens each time you 
raise the index to another power. The probability, for instance, of 
being in the final state after five flips is (p^3)(pq+q^2+q+1).
Substitute the appropriate values for p and q and you find the 
probability. But for each new line, you have to matrix multiply the 
current probabilities by the original matrix to get each new row.

Hope this helps somewhat. Good luck.

- Doctor Pat, The Math Forum
  http://mathforum.org/dr.math/   

Date: 04/13/2001 at 10:42:44
From: Jane Skinner
Subject: Re: Probability: Weighted coin, 3 heads in a row

Doctor Pat,

Thanks for your reply! I understand what you said (I think!).

Jane

Date: 04/13/2001 at 12:59:13
From: Doctor Anthony
Subject: Re: Probability: Weighted coin, 3 heads in a row

One approach to this is to use difference equations. By this method 
you can easily extend the working to 4 or 5 heads in a row.

Expected Number of Throws
-------------------------
Let a = expected number of throws to first head.

We must make at least 1 throw, and we have probability 1/2 of throwing 
a head and probability 1/2 of returning to a, so:

          a = (1/2)1 + (1/2)(1+a)
     (1/2)a = 1
          a = 2

Let E = expected number of throws to two consecutive heads.

Consider that we have just thrown a head and what happens on the next 
throw. We are dealing with the (a+1)th throw. With probability 1/2 
this is not a head, and we return to E. So

          E = (1/2)(a+1) + (1/2)(a+1+E)

note we must have at least a+1 throws

     (1/2)E = a+1
          E = 2(a+1)

and now putting in the value a = 2 we get  E = 2(3) =  6

So the expected throws to 2 consecutive heads is 6.

The equation for 3 consecutive heads is:

          E = (1/2)(6+1) + (1/2)(6+1+E)
     (1/2)E = 7
          E = 14

The equation for 4 consecutive heads is:

          E = (1/2)(14+1) + (1/2)(14+1+E)
     (1/2)E = 15
          E = 30

The equation for 5 consecutive heads is:

          E = (1/2)(30+1) + (1/2)(30+1+E)
     (1/2)E = 31
          E = 62

So we could expect 62 throws before getting 5 heads in a row.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   

Date: 04/13/2001 at 17:22:10
From: Jane Skinner
Subject: Re: Probability: Weighted coin, 3 heads in a row

Hi,

The equations you show work great! Hard to wrap my mind around them at 
first, but *much* easier to use in the end.

Jane

Date: 04/16/2001 at 18:39:33
From: Jane Skinner
Subject: Re: Probability: Weighted coin, 3 heads in a row in a row)

Dr Pat,

The more I think about this Markov approach, the more I like it. 
Thanks and more thanks!

Jane

Date: 04/16/2001 at 23:37:54
From: Doctor Pat
Subject: Re: Probability: Weighted coin, 3 heads in a row

Jane,

You are very welcome. It is the only way I can think of to reasonably 
compute the probability of the event after N flips.

The expected value is easier by the iteration approach. I think you 
got an answer for the case when p is not equal to 1/2, but in case you 
didn't, I think you can do that by solving for the E(n+1) (the 
expected number of flips to n+1 successes) in terms of E(n) (the 
expected number of flips to n successes). If we call the probability 
of success p and the probability of a failure (tails) q, then by the 
formula Dr. Anthony used we get:

             E(1) = p + q(E(1)+1)
                  = p + qE(1) + q

but p+q = 1 so:

             E(1) = 1 + qE(1)
     E(1) - qE(1) = 1
        E(1)(1-q) = 1

and because 1-q = p:

             E(1) = 1/p

which is pretty basic.

     E(2) = p[E(1)+1] + q[E(1)+1+E(2)]
          = p[E(1)] + p + q[E(1)] + q + q[E(2)]

again by p+q = 1:

               E(2) = p(E(1)) + 1 + q[E(1)] + q[E(2)]

     E(2) - q[E(2)] = p[E(1)] + 1 + q[E(1)]

        (1-q)[E(2)] = (p+q)[E(1)]+1

            p[E(2)] = 1 [E(1)]+1

               E(2) = [E(1)+1]/p

Now we can use this again for the next level and we have a function 
that we can iterate for each new value.

Good luck.

- Doctor Pat, The Math Forum
  http://mathforum.org/dr.math/   

Date: 04/17/2001 at 07:40:45
From: Jane Skinner
Subject: Probability: Weighted coin, 3 heads in a row 

Oh good, I wasn't positive that I'd stuck the p's and q's in the right 
places in Dr. Anthony's equation. Sure is nice to have that checked.  

Many thanks!
Jane