Men with Hats

July 6, 2011

(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, 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",
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)

# 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 their blog: mickeymousemodels. 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...

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.

Search R-bloggers


Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)