Re: flip a coin

briggs_at_encompasserve.org
Date: 06/07/04 

Date: 7 Jun 2004 07:46:37 -0600

In article <17b9a07c.0406062249.6d86ecf0@posting.google.com>, raydpratt@hotmail.com (raydpratt) writes:
> halfsearch@hotmail.com (John) wrote in message news:<74776ef2.0406041336.5b136547@posting.google.com>...
>> I'm stuck in the problem:
>> I flip a coin with P(H)=p until the pattern HTH appears, then I will
>> stop. What is the expected number of trials?
>> Thank you for any help.
>
> In three coin flips, the eight possible patterns are:
>
> TTT TTH THT HTT HHT *HTH* THH HHH
>
> As one responder already noted, this is 1 out of 8 possibilities, but

But, as has also been pointed out, the possibilities are not equally
probable.

> it does not answer the question of what the average expected number of
> trials will be to hit that sequence. As we add more coin flips per
> trial, we increase the chances that *HTH* will occur among the
> possibilities, but what should we call "the expected number of
> trials"?
>
> Are "the expected number of trials" the number that will give us a
> 50/50 chance or better that at least one of the trials will have the
> pattern *HTH*?

No. It's not.

> Does "the expected number of trials" have an agreed-upon quantitative
> meaning?

Yes, it does.

It is the "average" number of trials. Or the "mean" number of trials"
Or the "expected value" of the number of trials.

The expected value of a random variable n (number of trials in this case)
is:

    sum over all possible values of n
        of n times the probability that the outcome will be n

The number that you were thinking of doesn't have a name that I know of
but would be something like the _median_ number of trials. (Half
of the tests would have a number of trials above the median and
half below).

>
> In any event, let's see what happens when we add 1 more coin flip per
> trial (using a binary sequence pattern to assure complete coverage):
>
> TTTT TTTH TTHT TTHH THTT T*HTH* THHT THHH HTTT HTTH *HTH*T *HTH*H HHTT
> H*HTH* HHHT HHHH

Rather than counting the patterns explicitly, you could do a recursion.
This has been suggested or alluded to at least twice.

Look at your sequence so far. And your next flip.

a. If you have HT, you can flip H and get HTH with probability p.
                    or you can flip T and be left with nothing useful.

b. If you have H, you can flip T and get HT with probability p-1
                   or you can flip H and be left with H.

c. Every other leading pattern does you no good at all.
    If you have nothing, you can flip H and get H with probability p
                         or you can flip T and be left with nothing useful.

What we're after is the expected value of the number of flips required
to reach a pattern of HTH starting from nothing.

Call this number c.

If we flip H, we've got a good start with one flip used.
If we flip T, we're back where we started, with one flip used. So

c is given by

        probability we flip H times 1 + expected number of flips required
        given that we're starting with H

        plus

        probability we flip T times 1 + expected number of flips required
        given that we're starting with nothing.

Or, more compactly

        c = p * ( 1 + b ) +
            (1-p) * ( 1 + c )

So now we need to know b, the expected number of flips required given
that we're starting with H.

If we flip another H, we're left with H. But if we flip T, we're almost
there with HT. So

b is given by

        probability we flip H times 1 + expected number of flips required
        given that we're starting with H

        plus

        probability we flip T times 1 + expected number of flips required
        given that we're starting with HT

Or, more compactly:

        b = p * ( 1 + b ) +
            (1-p) * ( 1 + a )

And now we need to know a, the expected number of flips given that
we're starting with HT

If we flip H, we're done. But if we flip T, we're back where we started.
So

a is given by

        probability we flip H times 1 (Yay)

        plus

        probability we flip T times 1 + the expected number of
        flips given that we're starting with nothing

Or, more compactly:

        a = p +
            (1-p) * ( 1 + c )

Now you have three equations in three unknowns, a, b, and c.
Solve for c. Looks like a chance to do Gaussian elimination
symbolically.

There may be some other approaches involving the summation of infinite
series, but I can't see my way clear to a solution in that direction
right now.

        John Briggs

Relevant Pages
Quantcast