From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Mon Sep 15 2003 - 10:39:06 MDT
Hal Finney wrote:
>
> I imagine a more complex proof could show that the probability of white
> on both of any two rounds is constant, and presumably this could be
> generalized to any n rounds. But I don't see how to prove all this
> in a simple way.
If you were to prove that for any N sequential samples from this pot, the
probability of getting a sequence with M red chips and (N - M) white chips
is a constant regardless of the ordering of white and red chips, it would
prove both constant P(Wk) and constant P(Wj|Wk), j != k.
The above property, that an outcome containing M red chips and (N - M)
white chips has a constant probability regardless of the ordering of red
and white chips, is known as exchangeability.
Suppose the sequence is exchangeable. No matter how long the sequence
goes on, P(W1) and P(W1&W2) is constant, since this is computed in the
first two draws. P(W2) = P(W1), because P(R1&W2) + P(W1&W2) = P(W1&R2) +
P(W1&W2). P(W1&W2) = P(W2&W3) because P(W1&W2&W3) + P(W1&W2&R3) =
P(R1&W2&W3) + P(W1&W2&W3). The same holds for arbitrary P(Wi) and P(Wj|Wk).
Actually, if a sequence is exchangeable, we can swap any i, j != k in the
joint distribution, and properties such as P(Wi), P(Wi|Wk), P(Wi&Wk), and
so on, will remain constant.
To show that the sequence is exchangeable, consider any R, W of initial
red and white chips in the bowl, with a total number of chips N. The
probability of the sequence RWWRR is then given by:
R W W+1 R+1 R+2
- * --- * --- * --- * ---
N N+1 N+2 N+3 N+4
Changing the ordering of the R and W chips will not change the total
factors in the numerator and the denominator.
The entire proof is exactly analogous to the case of a bowl where, instead
of *adding* one chip of the color drawn, we draw a chip and discard it.
If we started with 5 red and 3 white chips, and drew a white chip, we
would be down to 5 red and 2 white chips, and so on, until we ran out of
chips after 8 rounds. Obviously, the probability of drawing a red or
white chip on any round N is the same as on round 1, if you have no
information about the chips previously drawn; and the probability of
drawing two red chips on any two rounds is the same; and the probability
you drew a red chip on round 2 if you drew a red chip on round 4, is the
same as the probability of drawing a red chip on round 2 if you drew a red
chip on round 1, since in either case there is one less red chip to go
around. You can imagine the chips "scattered" over N holes,
simultaneously, rather than being placed in sequence - this is what it
means for the sequence to be exchangeable. Swapping the labels of "round
1" to "round 3" has no effect on how the chips land in the holes.
If you start out with R red chips and W white chips, and draw without
replacement, the probability of getting a particular sequence is:
R W W-1 R-1 R-2
- * --- * --- * --- * ---
N N-1 N-2 N-3 N-4
Which is what makes this distribution exchangeable:
> Evil Hint #3:
>
> The classical version of the problem has a bowl where we sample without replacement - take the chip, and throw it away. Suppose there are M red chips and N chips. If you don't know what you got on the first round, the probability of getting a red chip on the second round is still M/N. The probability of getting a red chip on the second round, given that you got a red chip on the fourth round, is just (M-1)/(N-1), since there's one less red chip to go around. We can think of sprinkling the chips over holes, instead of drawing them in successive rounds, and it doesn't matter if you swap around the labels on the holes.
>
> The evil version of the bowl, instead of running out of the chips already sprinkled, has more and more of them, like a P2P file-sharing network. But that doesn't change anything important.
The math is also not affected if you instead add three chips of the color
drawn, or if you subtract two chips of the color drawn, and so on.
Christian Rovner has an interesting way to visualize this, which is that
the drawing procedure always leaves the bowl the same shade of pink
afterward. If you remove the chip drawn on each round, you're removing a
chip with a 3/8 probability of being white, from a bowl with a 3/8
probability of producing white chips. If you add a chip of the color
drawn on each round, you're adding a chip with a 3/8 probability of being
white, to a bowl with a 3/8 probability of producing white chips. If you
know that you drew a white chip on the first round, then on future rounds
with unknown draws you're adding chips with a 4/9 probability of being
white. And so on. It doesn't matter whether you *know* that the pot has
5 red and 3 white chips, as on the first round, or if you're working with
some probability distribution of mixes that add up to 3/8; it's all the
same shade of pink. The drawing procedure leaves the pinkness unchanged,
both for the main distribution, and for any differently shaded
subdistributions that you want to consider separately.
See also Chapter 3 of E.T. Jaynes's "Probability Theory: The Logic of
Science". (I did not get the problem from there; I made it up after
reading it. Though I am sure it is not original.)
-- Eliezer S. Yudkowsky http://singinst.org/ Research Fellow, Singularity Institute for Artificial Intelligence
This archive was generated by hypermail 2.1.5 : Mon Sep 15 2003 - 10:50:04 MDT