All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
9 labels and 9 jars (Posted on 2002-12-09) Difficulty: 4 of 5
There are 9 jars each with unique labels.

Someone has come and removed all the labels and mixed them up.

If you put the labels back on the jars (without knowing the contents), what is the expected number of labels which would match the contents?

See The Solution Submitted by Kozo Morimoto    
Rating: 3.5833 (12 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re(3): SOLUTION IS WRONG | Comment 12 of 14 |
(In reply to re(2): SOLUTION IS WRONG by Cory Taylor)

In fact, it's about 37% likely that there will be one correctly matched label. Out of the 9!=362880 permutations of the nine labels, the following are the number of ways of getting 0 through 9 correct, respectively:
133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0, 1.

When divided by 9! they give respective probabilities of:
.367879, .367882, .183929, .061343, .015278, .003125, .000463, .000099, .000000, .000003. Using these probabilities to weight the numbers from 0 through 9 does indeed give an average of 1. Note that as the number of labels increases, this distribution gets closer to the Poisson distr with mean 1.

The derivation of the number of ways of getting r correct out of n labels, is to start with n=1, r=1 and w(1,1) = 1 and w(1,x)=0 for all x other than 1.
From there, w(n,r)= w(n-1,r-1) + w(n-1,r)*(n-1-r) + w(n-1,r+1)*(r+1).

The first term comes from adding a correct label to a set of n-1 labels with r-1 matched. The second term is from swapping the new label with one of the non-matches from n-1. The last term comes from swapping the new label with one of the previously (in step n-1) matched labels.
  Posted by Charlie on 2003-03-24 10:20:32

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information