You are given 9 unlabeled bottles of wine, all different, and the 9 labels that belong on them, but you don't know which is which.

[ Editor: exactly 1, whatever the number of bottles. ]

Number the labels 1, 2, ..., n.  For i = 1, 2, ..., n define

   X_i = 1 if you put label number i on the right bottle
       = 0 if you didn't

Also define

   X = X_1 + X_2 + ... + X_n

Clearly X is a random variable whose value is the number of bottles
you labeled correctly.  Your goal is to find E(X), the expected value
of X.

Now since label i is equally likely (by symmetry) to end up on any
given bottle, and there are n bottles, P(X_i = 1) = 1/n, and
E(X_i) = 1/n for all i.  But then

   E(X) = E(X_1 + X_2 + ... + X_n)
        = E(X_1) + E(X_2) + ... + E(X_n)
        = 1/n + 1/n + ... + 1/n  (n times)
        = 1.

Now at this point I expect a whole bunch of flames complaining that
although P(X_i) = 1/n in isolation, I have ignored all the
interferences between the labels, in other words X_1 is highly
dependent on X_2 through X_n.  This is true and would make a big
difference if I were computing, say, P(X = 5).  But the formula
E(X + Y) = E(X) + E(Y) is true no matter what codependence exists
between X and Y, provided that X and Y each have finite expectation.

-- David A. Karr (karr@cs.cornell.edu)

Clearly the expected number of `hits' is E_1 + E_2 + ... + E_9
where E_i is the expected number of hits on the i'th bottle.

Clearly E_1 is 1/9: by symmetry the probability of a hit can be
nothing else; and only 0 or 1 hit on a given bottle is possible.

Clearly E_1 = E_2 = ... = E_9, again by symmetry.

E_1 + ... + E_9 = 1.  Q.E.D.

After concluding that E_1 = 1/9 it may be tempting to think that
E_2 is somehow affected, but how could E_1 and E_2 be unequal?
Perhaps you're waiting for the inclusion/exclusion step where
the interdependence of the events is considered.  But that step
just doesn't arise in the above construction.

For a good treatment of probability, random variables, etc. I recommend
_The Art of Probability for Engineers and Scientists_ by Richard W. Hamming.

-- James D. Allen (james@crc.ricoh.com)

[ Editor: see also the entry "derangement" for the probability that no
bottle is labeled correctly. ]

[ Editor: a direct count, from an answer to a question sent to the
rec.puzzles oracle about a wine tasting with 9 bottles. ]

The answer does rely upon the number of arrangements of 9 things.  It
also requires dividing all the possible arrangements into groups,
according to how many correct answers there are in each particular
arrangement.  Once you've done that, the average number of correct
answers is going to be the following big weighted sum, divided by the
total number of arrangements.

    0  *  number of arrangements with exactly 0 correct answers
+   1  *  number of arrangements with exactly 1 correct answer
+   2  *  number of arrangements with exactly 2 correct answers
+   3  *  number of arrangements with exactly 3 correct answers
+   ...
+   9  *  number of arrangements with exactly 9 correct answers.

(A sanity check is possible here:  if we add up all the "number of"s in
that sum, we get the total number of arrangements.  Since we're
weighting each of those values with a number from 0 to 9, and dividing
by the total arrangements, we'll end up with a number somewhere between
0 and 9.  Makes sense.)

Now about those various "number of"s...  There is 1 way to have exactly
9 right answers.  There are 0 ways to have exactly 8 right.  After that,
the number of arrangements with a certain number of right answers can
be counted by choosing which ones to have be wrong, and then
multiplying by the number of ways they can be made all wrong.

Choosing k positions to be assigned wrong can be done C(9,k) ways.
Arranging k things so that none of them is in its rightful place is
called derangements, and the usual symbol for the number of ways to do
it is D_k.  There is a closed form for D_k, but it's ugly.  There is a
simple recurrence relation, though, which is D_k = k * D_(k-1) +
(-1)^k [Editor: was (-1)^n].  D_1 is 0 (there's no way to rearrange 1
thing so it's in the wrong place).  From this we have that D_2 through
D_9 are 1, 2, 9, 44, 265, 1854, 14833, 133496.

So for the number of arrangements with various amounts of
correctly-placed things, we have:

exactly 9 right:                                                1
exactly 8 right:                                                0
exactly 7 right:  C(9,2) * D_2  =   36 * D_2  =   36 * 1      = 36
exactly 6 right:  C(9,3) * D_3  =   84 * D_3  =   84 * 2      = 168
exactly 5 right:  C(9,4) * D_4  =  126 * D_4  =  126 * 9      = 1134
exactly 4 right:  C(9,5) * D_5  =  126 * D_5  =  126 * 44     = 5544
exactly 3 right:  C(9,6) * D_6  =   84 * D_6  =   84 * 265    = 22260
exactly 2 right:  C(9,7) * D_7  =   36 * D_7  =   36 * 1854   = 66744
exactly 1 right:  C(9,8) * D_8  =    9 * D_8  =    9 * 14833  = 133497
exactly 0 right:  C(9,9) * D_9  =        D_9  =               = 133496

and our final answer (omitting 0 terms) is:

1*133497 + 2*66744 + 3*22260 + 4*5544 + 5*1134 + 6*168 + 7*36 + 9*1
-------------------------------------------------------------------
                             362880

= (133497 + 133488 + 66780 + 22176 + 5670 + 1008 + 252 + 9) / 362880

= 362880 / 362880 = 1

Yow!  So you'll average only 1 right out of 9 by straight guessing.
After all that work it came out to such a simple answer!  I was so
surprised that I redid the entire calculation using only 5 wine
bottles, and sure enough, it came out to 1 as well.

There must be something deeper going on here than I realize.  In
particular, there must be some other way to attack the problem, so that
the answer of "1" is "obvious" without going through the hairy
arithmetic that I did above.  But I don't see what it is.

-- Tom Magliery <mag@cs.uiuc.edu>