The King of Pointland

I'm just going to guess 2 1/4.

Nope.

3?

Correct! How did you figure it out?

I got 3 -- and I'll tell you how I got it.

I started out the crude way. Take a whole bunch of cases, and assume a perfect distribution of the probable outcomes. Let's say we make 16 "attempts", where each "attempt" is a series of flips that ends when both sides have been seen. 8 of those attempts will end after two flips (IOW half the time, the second flip will show the opposite face from what you saw the first time). From the 8 that are left: half the time, or four times, we will see our hitherto unrepresented face on the next flip -- in this case, the third flip. And so on -- of the remaining attempts, half the time your attempt will be complete with one more flip.

So your distribution starts to look like:

8 * 2 + 4 * 3 + 2 * 4 + 1 * 5 + (?)

The problem here is in working out that last bit. The parts without the question mark only account for 15 of the 16 tries. But when that leftover bit represents a small enough portion of the whole, we can make a guess, see where that takes us, and see if we can draw some conclusions.

Since the number of flips for that remaning portion must be greater than 5, I figured I'd try 5.5, plug that in, and see where it got me. So, plugging that into the question mark spot, pedantically multiplying by 1 to represent the "16th attempt", and doing the cross product as described above gives us

8*2 + 4 * 3 + 2 * 4 + 1 * 5 + 1 * 5.5 = 46.5

And dividing by the number of attempts, 16, to get the average, gives us about 2.9. Kind of close to 3, so that might be our answer.

I wondered how I could get better accuracy, and the first thing I noticed was a basic error in my logic for the "punt" value. If the "first 15" attempts were the ones that took 5 tosses or less, the last attempt must represent all the cases that took more than 5 tosses -- i.e. 6 or more tosses (you can't have 5.1 tosses to drag that average down below 6), so the average would have to be greater than 6, not merely greater than 5. So I set my next guess at 6.5. Plug that into the cross product above (47.5), divide by 16 to get the average, and you get 2.96875 -- dangerously close to 3.

Turns out that if you just make your mystery value an even 7, you'll get exactly 3. That must mean that declaring the remainder as 7 is somehow representative of the 3 avg. tosses it'll take you on top of the 5 that you've already tossed one way, but that's more mental gymnastics than I feel up to right now.

Actually 2 1/4 is correct, if the coin you are flipping is a quarter. It is the most commonly flipped coin, after all.

I forgot to come back and post that I wrote a perl script to figure this out for me by trying it a few million times. I consider this to be cheating, though. I think I had tried a preview of pasting in the perl code, here, but unsurprisingly, it did not work, and I must have seen something shiny and gotten distracted.

I have a really weak understanding of probability, it's something I've always meant to get a textbook on, but I've never gotten around to it.

First, I missed Bob's post. Your thinking is kind of how I approached it, but from the other direction (you'll see what I mean). I had a more formal proof, but it's not as illuminating. I really do think that 3 is the correct answer (and I tested it out with a Python script).

I imagine a football stadium of coin flippers. I tell them all to to flip their coin once. Nobody will have seen both heads (H) and tails (T), so I tell them to flip again. Anybody who, after two flips, sees both a H and a T (1/2 of them, roughly), is asked to write down how many flips it took on a scrap of paper (i.e. 2) and then leave the scrap on their seat and go home.

Of the remaining people left in the stadium (about half of the original population), I tell them to flip again, and so on. After the nth flip, all the people who have finally gotten at least one H and one T write down "n" on their scrap of paper and go home.

The question is: After I collect all the scraps, what's the average value written on all the scraps?

After the 1st flip, assuming you've failed so far, there's always a 50% chance of succeeding on your next flip. (You've either seen only heads and just need a tail, or vice versa). So you can see that the probability of succeeding on the second flip is 1/2, and then of the remaining half of the people in the stadium, 1/2 of them (or 1/2 * 1/2 = 1/4 of the original population) will succeed on their third flip, and then (1/2)*(1/2)*(1/2) = 1/8 will succeed on the fourth flip, and so on.

To find the average number of flips, we need to calculate the expectation value: (1/2)*2 flips + (1/4) * 3 flips + (1/8) * 4 flips + (1/16) * 5 flips + ....

It turns out that this infinite sum converges: The sum of [ i / (2^(i-1)) ] where i goes from 2 to infinity is 3.

Maybe this will work:

#!/usr/bin/env python

#

import random

#

N = 10000

tot = 0

count = 0

for i in range(1,N+1):

    trials = 0

    tally = [0, 0]

    while 1:

        t = random.randint(0,1)

        trials = trials + 1

        tally[t] = tally[t] + 1

        if tally[0] and tally[1]:

            break 

    # print trials

    tot += trials

    count = count+1

#

print "Average: ", (1.0*tot / count)

$ ./series.py 

Average:  2.9831

$ ./series.py 

Average:  3.0074

Hmm, well, it's not like indentation is important in python or anything. I'll fix this later. Update: I think the blank lines are auto-converted to paragraph tags, so I had to add some octothorpes. What's up with the blank lines now?