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 <- 40
xs <- 1:x.max
dev.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 -> Inf
exp(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.

To leave a comment for the author, please follow the link and comment on his blog: mickeymousemodels.

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



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.