Problem Set due Sep 22, 2020 16:59 PDT

Problem 5. Hats in a box

5 points possible (graded)

Each one ofn

persons, indexed by1,2,...,n

, has a clean hat and throws it into a box. The persons then pick hats from the box, at random. Every assignment of the hats to the persons is equally likely. In an equivalent model, each person picks a hat, one at a time, in the order of their index, with each one of the remaining hats being equally likely to be picked. Find the probability of the following events.

(You need to answer all 5 questions before you can submit.)

1. Every person gets his or her own hat back.

2. Each one of persons1,...,m

gets his or her own hat back, where1mn

.

3. Each one of persons1,...,m

gets back a hat belonging to one of the lastm

persons (personsnm+1,...,n

), where1mn

.

Now assume, in addition, that every hat thrown into the box has probabilityp

of getting dirty (independently of what happens to the other hats or who has dropped or picked it up). Find the probability that:

4. Persons1,...,m

will pick up clean hats.