Men with Hats

July 6, 2011
By

(This article was first published on mickeymousemodels, and kindly contributed to R-bloggers)

Suppose N people (and their hats) attend a party (in the 1950s). For fun, the guests mix their hats in a pile at the center of the room, and each person picks a hat uniformly at random. What is the probability that nobody ends up with their own hat?

`EstimateProbability <- function(n.people, n.simulations=10000) {  NobodyGotTheirHat <- function(n.people) {    people <- 1:n.people    hats <- sample(people, size=n.people, replace=FALSE)    return(all(people != hats))  }  mean(replicate(n.simulations, NobodyGotTheirHat(n.people)))}CalculateProbability <- function(n.people) {  InclusionExclusionTerm <- function(i) {    return(((-1) ^ (i + 1)) * choose(n.people, i) *           factorial(n.people - i) / factorial(n.people))  }  1 - sum(sapply(1:n.people, InclusionExclusionTerm))}x.max <- 40xs <- 1:x.maxdev.new(height=6, width=10)plot(xs, sapply(xs, EstimateProbability), pch=4, ylim=c(0, 0.60),     main="Men with Hats: N hats uniformly assigned to N people",     xlab="N",     ylab="probability that nobody ends up with their own hat")lines(xs, sapply(xs, CalculateProbability), col="firebrick", lwd=2)mtext("What is the probability that nobody ends up with their own hat?")legend("topleft", "True probability", bty="n", lwd=2, col="firebrick") legend("topright", "Estimate from 10k simulations", bty="n", pch=4)savePlot("men_with_hats.png")# The probability converges to e^-1 as N -> Infexp(1) ^ -1`

As in my earlier puzzle post, the solution is an application of the inclusion-exclusion principle. What’s fascinating about this particular puzzle is that the probability settles down not at zero or one, but instead converges to e^-1 as the number of people (and hats) grows large. I don’t know about you, but I never would have guessed.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...