1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hat matching problem

  1. Nov 4, 2016 #1

    hotvette

    User Avatar
    Homework Helper

    1. The problem statement, all variables and given/known data
    N men throw their hats on to the floor, mix them up, and draw at random. What is the probability that no man gets his own hat

    2. Relevant equations
    $$P(E_1^c E_2^c \dots E_N^c) = 1-P(E_1 \cup E_2 \dots \cup E_N)$$
    $$P(\text{n-tuple}) = \frac{1}{n!}$$

    3. The attempt at a solution
    The way I've seen this explained appears to me to have an inconsistency that I don't know how to resolve.

    1). Total # arrangements of N hats among N men is [itex]N![/itex] This is the denominator in the probability expression.

    2). Define [itex]E_i[/itex] as the event that n=1 man chooses his own hat. Imagine man #1 choosing a hat first. There is only 1 way he can choose his own hat. The remaining [itex](N-1)[/itex] hats can be arranged [itex](N-1)![/itex] ways. But, since each man can choose first, we must multiply by [itex]C_1^N = N[/itex]. Thus [itex]P(E_1) = P(E_2) \dots = P_N) = N (N-1)!/N! = 1 = \frac{1}{n!}[/itex]

    3) Same argument for k=2, k=3, etc. gives the result stated above.

    Here is what doesn't make sense to me. If we argue that there are N ways that a man can choose first, that implies order of choosing is important. If order is important, then the order of choosing 2nd, 3rd, etc. is also important, which isn't accounted for in the above argument.

    What am I missing?
     
  2. jcsd
  3. Nov 4, 2016 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You are confusing yourself by supposing a particular order for choosing. The probability that man i chooses his own hat is ##P(E_i) = 1/N## for all ##i = 1,2 \cdots, N.## The easiest and surest way to see this is similar to what you did: among all the ##N!## permutations, hat number ##i## falls in position ##i## in ##(N-1)!## of the cases, so ##P(E_i) = (N-1)!/N! = 1/N.## Of course we have that that ##\sum_{i=1}^N P(E_i) = 1##, but that is only a small first step towards the probability that at least one man gets his own hat. Note that the occurrence of event ##E_i## says nothing at all about whether some other men also get their own hats; it just looks at what happens to man ##i##.

    Next, for any fixed pair ##i < j##, the number of permutations in which hat ##i## falls in position ##i## and hat ##j## in position ##j## is ##(N-2)!##, so ##P(E_i, E_j) = (N-2)!/N! = 1/[N(N-1)].## Thus, ##\sum_{i < j} P(E_i,E_j) = {N \choose 2}/[N(N-1)] = 1/2! .## (Here I use the notation ##P(A,B)## instead of ##P(A \cap B) .##) Similarly, ##\sum_{i < j < k} P(E_i, E_j, E_k) = 1/3!##, etc.

    Now use the general inclusion-exclusion principle to get ##P_{\geq 1}## =probability that at least one man gets his own hat:
    $$P_{\geq 1} \equiv P(E_1 \cup E_2 \cup \cdots \cup E_N) = S_1 - S_2 + S_3 - \cdots \pm S_N, $$
    where
    $$S_1 = \sum_{i} P(E_i)=1,\\
    S_2 = \sum_{i < j} P(E_i, E_j)=1/2!, \\
    S_3 = \sum_{i < j < k} P(E_i,E_j,E_k)= 1/3!\\
    \vdots\\
    S_N = P(E_1,E_2, \ldots, E_N) = 1/N!
    $$
    Of course, the probability that 0 men get their own hats is ##P_0 = 1 - P_{\geq 1} .##

    All of this stuff is presented beautifully in Feller, "An Introduction to Probability Theory and its Applications", Vol. I, Wiley (1968). That treatment is now considered old-fashioned, but in my opinion is still the clearest and most direct.
     
    Last edited: Nov 4, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Hat matching problem
  1. Derivative of r^hat (Replies: 4)

Loading...