Question

At a party n men take off their hats. After mixing up the hats, each man randomly picks one. We say a match occurs if a man picks his own has. what is the probability of no matches?

Answer 1

SOLUTION :-

Let E denote the event that no matches occur, and to make explicit the dependence on j write
Pj = P( E )
We start by conditioning on whether or not the first man selects his own hat -- call these events M and M^c
Then P_j = P( E ) = P( E|M )P( M ) + P( E|M^c )P( M^c ).
Clearly, P( E|M ) = 0, so

P_j= P( E|M^c )( j-1 )/j

Now,
P( E|M^c ) is the probability of no matches when j - 1 men select from a set of j - 1 hats that does not contain the hat of one of these men.
This can happen in either of two mutually exclusive ways.
Either there are no matches and the extra man does not select the extra hat ( this being the hat of the man that chose first ),
or
There are no matches and the extra man does select the extra hat.
The probability of the first of these events is just P_j-1,
Which is seen by regarding the extra hat as "belonging" to the extra man. As the second event has probability [ 1/( j - 1 )]P_j-2, we have

P( E|M^c ) = P_j-1 + ( 1/( n - 1 ))P_j-2

and thus, from above Equation

P_n = (( j - 1 )/j ) P_j-1 + ( 1/j ) P_j-2 OR P_j - P_j-1 = - ( 1/n )( P_j-1 - P_j-2)

However, as  P_j  is the probability of no matches when j men select among their own hats, we have   P₁ = 0 , P₂ = 1/2
so, from above Equation P₃ = ( 1/2! ) - ( 1/3! ) and P₄ = ( 1/2! ) -( 1/3! ) + (1/4! ) and, in general, we see that

P_j = ( 1/2! ) -( 1/3! ) + (1/4! ) - ........ + ( -1 )^j / j!

For j large, the probability of no match is close to 1/e