| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 304.1 | | ALIEN::POSTPISCHIL | | Wed Jun 12 1985 18:22 | 11 |
| Assuming each person, and only those persons, who checked a hat receive a hat
when leaving, the probability that no person receives a correct hat and the
probability that exactly one person receives a correct hat both approach
1/e, or about .368, as the number of people increases.
Sorry, I have no proof available. Years ago, I figured out the function
which gives the probability of n correct matches with m choices, but I no
longer have it. Anybody want to give it a shot?
-- edp
|
| 304.2 | | ALIEN::POSTPISCHIL | | Thu Jun 13 1985 09:55 | 7 |
| Maybe I should have answered the question. If the probability that nobody
receives a correct hat is 1/e, the probability that somebody receives a
correct hat is 1-1/e, or about .632. Also, the mean number of hats correctly
returned is exactly 1, regardless of the number of hats.
-- edp
|
| 304.3 | | AURORA::HALLYB | | Fri Jun 14 1985 16:48 | 9 |
| A similar problem involves turning over cards from two decks simultaneously,
wondering if you would ever turn over the same card (rank and suit).
Back in college I made a bet against Rand Malmin, a strong Southern Baptist
non-drinking, non-gambling gentleman, who thought he would teach me the evils
of gambling. He was surprised when the tens of hearts coincided, then angry
when I told him how favorable my odds were...
John "a gentleman never bets on a sure thing" H.
|
| 304.4 | | TURTLE::GILBERT | | Fri Jun 14 1985 19:49 | 5 |
| But if you look at the problem a certain way, it would be surprising to
discover that NONE matched: "There are really quite a few people here --
certainly SOMEBODY must be lucky enough to get his own hat".
Somebody invariably picks the lottery number, right?
|
| 304.5 | | SPHINX::PATTERSON | | Mon Jun 17 1985 11:54 | 12 |
| If there are n people, (and therefore n hats involved), then
(1-1/n) is the probability that a given gentleman does not get his
own hat back.
Since, before anyone actually takes *some* hat, this is true of each
gentleman, the probability of all hats being returned incorrectly is
(1-1/n)^n.
for 'large' n this is e^-1, so the probability of at least one hat
being returned to its rightful owner is 1-e^-1 as stated earlier.
carl
|
| 304.6 | | ADVAX::J_ROTH | | Tue Jun 18 1985 20:37 | 18 |
| The choices are not independant, so the function (1-1/n)^n doesn't precisely
hold, tho its asymptotically a good approx.
I believe the number of permutations which will have no matches is given
by
N! N! N! N!
N! - -- + -- - -- + ... +/- --
1! 2! 3! N!
the series breaking off after N+1 terms.
So, for successive values of N, the probability of hitting a permutation
with no matches is given by including successively more terms in the
taylor series for e^-1, as can be checked by enumerating a few cases
for small N.
- Jim
|
| 304.7 | | TOOLS::STAN | | Tue Jun 18 1985 23:00 | 2 |
| I agree with Jim Roth. This number is known in the literature as !N,
N subfactorial. It is the number of derangements on N items.
|
| 304.8 | | SPHINX::PATTERSON | | Wed Jun 19 1985 09:35 | 10 |
| re .5
.6
After I posted my 'proof', JMunzer pointed out that in the case n=2
(1-1/n)^n gave incorrect probabilities. That was because I had assumed
independence, in *large* n cases that is of no consequence - for reasons
in .6 - but the *small* case is incorrect, (one can't after all have
1 mismatch).
carl
|