From: Ross A. Finlayson (extropy@apexinternetsoftware.com)
Date: Wed Oct 30 2002 - 03:42:37 MST
On Monday, October 28, 2002, at 03:55 PM, Eliezer S. Yudkowsky wrote:
> mlorrey@datamann.com wrote:
>> [quote from: Eliezer on 2002-10-28 at 16:08:43]
>>> Suppose that we flip a fair coin 20 times, and that a biased
>>> sampling procedure then randomly selects 5 coinflips from the
>>> set of coinflips that came up heads and reports on those
>>> coinflips; if there aren't 5 coinflips that came up heads, the
>>> biased sampling procedure reports all available heads and
>>> enough randomly selected tails to make up the gap.
>>> Suppose the biased sampling procedure reports that the first,
>>> sixth, eleventh, fifteenth, and eighteenth flips came up
>>> heads. Is there a simple general formula for calculating
>>> the probability that any given other coinflip came up tails?
>>> Clearly the probability is greater than 50%, but by how
>>> much? (I
>>> don't know the answer to this one; it's posed as a genuine
>>> math question, not a math problem.)
>
>> The probability of what you ask is 50%. The prob that any given flip
>> is one or
>> the other is 50% in any situation. The odds that every other flip IN
>> SEQUENCE
>> is tails is dependent upon how long your sequence is. In the case of
>> getting
>> five tails, the odds are 3.125%.
>
> Thanks, Mike, but this answer is incorrect. See the description of the
> problem. If a *random* sampler reports five heads, the other coinflips
> have a 50% chance of being heads. If a *biased* sampler reports five
> heads, that's an entirely different issue.
>
> -- Eliezer S. Yudkowsky http://singinst.org/
> Research Fellow, Singularity Institute for Artificial Intelligence
>
There are some 2^20 possible sequences: 1,048,576. Quite a few of those
have at least five heads. There are 2^15 possible sequences without the
spacings you mentioned already heads. If you assign the value zero for
tails and one for heads the average value of the number formed from the
sequence as a post-radix expansion is one half. For example, the list
of the possible sequences has 2^15 permutations, in binary:
.00000000000000000000 = 0
...
.11111111111111111111 = 1- 1/(2^15)
Now, these are among the 2^20 possible sequences, of those, 2^15 have
those heads in those particular locations in the sequence of twenty,
there are 2^5-1 other sequences of five coins with those locations each
with 2^15 other elements of the sequence of 20.
So, a guess at this point, 50% + 1/(2^5), or, 53.125 percent. That's
only a guess, though.
Now, this is where you are expecting for twenty coins, on average, ten
heads and ten tails. If five are heads then of the other fifteen are
expected five more heads and ten tails, with there thus being a
probability of 2/3 or 67%, er, 66.6^_%. Yet, that is of an unordered
sequence.
"Is there a simple general formula for calculating the probability that
any given other coinflip came up tails?"
For any one of the fifteen locations, the probability would be equal, so
a general formula for determining the first non-sampled coin will
suffice. Well, hmm, I wonder here if the biased sampling would
determine the first non-sampled coin to be more likely to be tails.
Anyways.
In this case, let's say we want to know the probability of the second
coin being tails. Lorrey has a point about it being fifty percent, the
probability of any fair cointoss being tails. Out of the twenty coin
tosses, where when the five known coins are heads then there are 2^15
permutations for the other fifteen, half begin with a head and the other
half with a tail.
Another thing to consider is how many of the set permutations of twenty
have at least five heads. Most of them do. I forget the formula, it's
something with factorial. I don't recall. Let's see, with three coins,
eight set permutations, the number of permutations with all three being
heads is 1 of 8, let's see, three permutations have two heads and three
two tails, and one zero heads. For four coins, having sixteen
combinations:
4 1
3 4
2 6
1 4
0 1
For five, of thirty-two:
5 1
4 5
3 10
2 10
1 5
0 1
For twenty coins then it looks like:
h c
20 1
19 20
18 19+18+17+16+15+14+13+12+11+10+9+8+7+6+5+4+3+2+1= 9*20+10 = 190
17 18+17+... = 8*19 + (17+16+...= 7*18+9 = 135) + (16+15
16
15
14
13
12
11
10
9 =c(11)
8 =c(12)
7 =c(13)
6 =c(14)
5 =c(15)
4 =c(16)
3 =c(17)
2 =c(18)
1 20=c(19)
0 1
I wrote the above and then read Lee Crocker's explanation which seemed
very good. I forgot the factorial form, surprisingly I minored in
statistics. Now, I have been reading the other replies, and can see why
it would be 2/3, as noted above. I could also see why it would be very
little less than 2/3, there is a probability that five or more coins are
heads out of twenty that is much greater than not.
What I like to wonder about are infinite sequences of fair cointosses.
Ross
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:17:53 MST