Men with Hats

July 6, 2011
By

[This article was first published on mickeymousemodels, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.



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

Sponsors

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)