Jun 27, 2018

Student Puzzle Corner 21

Deadline: September 7, 2018

Here’s Anirban DasGupta’s latest puzzle, probability this time:

This problem is a comparatively simple one. You can get a reasonable idea of the answers to the questions that we pose by large simulations, but you cannot get the algebraic answers that we are asking for. Here is the setup.

In a town, there are N residents. A subset of n residents have x1, x2, …, xn acquaintances (i.e. friends) respectively. The acquaintance sets are random subsets of {1, 2, …, N}, and let us assume these sets are formed independently. To keep this problem simple, here are three fairly straightforward problems:

a) find an expression for the probability that the n residents do not have a common acquaintance.

b) Give a numerical value for the probability that these n residents have at most one common acquaintance when N=106, n = 15 and each xi = 4×105.

c) Give an analytic approximation to the probability that they have exactly one common acquaintance when n = N, and each xi = N − log N , with the parameter N .

[Note that part (c) is asking what is the probability that there is exactly one person in town who is a friend of everybody?]


The solution to the previous puzzle is here. Find out who submitted a correct answer!


Leave a comment




Welcome to the IMS Bulletin website! We are developing the way we communicate news and information more effectively with members. The print Bulletin is still with us (free with IMS membership), and still available as a PDF to download, but in addition, we are placing some of the news, columns and articles on this blog site, which will allow you the opportunity to interact more. We are always keen to hear from IMS members, and encourage you to write articles and reports that other IMS members would find interesting. Contact the IMS Bulletin at bulletin@imstat.org

What is “Open Forum”?

In the Open Forum, any IMS member can propose a topic for discussion. Email your subject and an opening paragraph (to bulletin@imstat.org) and we'll post it to start off the discussion. Other readers can join in the debate by commenting on the post. Search other Open Forum posts by using the Open Forum category link below. Start a discussion today!

About IMS

The Institute of Mathematical Statistics is an international scholarly society devoted to the development and dissemination of the theory and applications of statistics and probability. We have about 4,500 members around the world. Visit IMS at http://imstat.org
Latest Issue