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.

*Related*

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...