Date: Apr 13, 2005 12:22 AM
Author: Glenn C. Rhoads
Subject: Re: say I flip a coin 100 times...

george wrote:
> HERC777 wrote:
>

Inserting HERC777's original question.

>>> and 1,000,000 other people all flip 100 coins themselves.
>>> on average, will someone flip the same 100 long sequence I did?
>>> how long a sequence will they match up to on average?

>>
>> there's about 1,000,000 combinations of a sequence of 20 coin flips
>> 2^10 = 1024
>> 2^20 = a million
>>
>> so on average they should copy your sequence up to the 1st 20

flips..
>>
>> Agree?

>
> No. Jesus.
> First of all, you have to know what you are
> averaging OVER. You are overaging over FLIPPERS,
> or flip-sequences. You are averaging over a million
> things. For each of these million strings (of H or T),
> you want to know how long its prefix-matching-you is.
> The number of flippers matching-you-so-far starts out
> at a million after 0 flip-positions and falls by half
> with every flip(in time) thereafter. Half the million
> will flip opposite from you on the first flip and so
> will have a prefix-matching-you of length 0.
> 1/4 of them will match you on the first flip and
> miss on the 2nd, and have a match-you length of 1.
> 1/8 of them will match you on the first two but miss
> on the 3rd, and have a match-you length of 2.
> On the 20th flip, the EXPECTED number of flippers
> continuing to match you all this way will be less than 1.
> Furthermore, the AVERAGE, over all flippers, of the
> initial-length-of-match-you-prefix, is ALSO
> LESS THAN 1.
>
> NOT 20.
>
> This is HIGH SCHOOL algebra, herc.


He may have meant "on average, what will be the length of
the longest matching prefix."