# Can't understand probability calculation appeared in “Mining of Massive Dataset” book

This is a summary of the excerpt:

Given that we have:

*$10^9$ people

*each person has a chance of 0.01 of going to a hotel

*we have $10^5$ hotels, each hotel holds 100 people

*Thus, $P(2 \text{ persons meet on the same hotel in any given day}) = 0.01 \cdot 0.01 \cdot 10^{-5}$

*and $P(2\text{ persons on the same hotel in$2$day}) = P(2 \text{ persons on the same hotel in any given days})^2 = 10^{-18}$

the book "Mining of Massive Dataset" said that the expected number of pairs who stay in the same hotel for 2 days is:

$P(2 \text{ persons on the same hotel in$2$days}) \cdot ( \text{number of pairs of people} ) \cdot (\text{number of pairs of days})$

this is the part where I got stuck. Can't understand how it come to this derivation. Can anybody explain it in more elaborate detail.

You can find the content on page 6 of this link: http://infolab.stanford.edu/~ullman/mmds/ch1.pdf (it is freely available)

• The 10^-18 is the chance that a specific pair of people will meet on a specific pair of days. So, to find the expected value, you have to multiply by all pairs of people and all pairs of days. Does that help? (if not, I can try to do the calculation from a different approach) – user1566 Jan 16 '16 at 18:11
• I still can't understand it. Perhaps I'm bad at making sense of intuitive things... what I think is the expected # pairs should be $E[expected\ captured\ pairs] = \sum\limits_{i=1}^n x_{i}P(x_{i})\ = (1)P(1\ pair\ captured) + (2)P(2\ pairs\ captured)\ +\ ...$ ,which will be a hell load of calculation(maybe it can be grouped to some closed form formula and ends up being as the book said?) – user1560335 Jan 16 '16 at 18:25
• Because the chances depend (strongly) on how people choose hotels, there is not sufficient information to answer this question. In fact, the situation as described in your reference is an impossible one because it posits conditions that are inconsistent with the implicit assumptions it uses in its calculations. It's simply a terrible analogy for illustrating the Bonferroni adjustment! – whuber Jan 16 '16 at 19:39

On any given day, there are 10^9 people with a 1% chance of going to a hotel, so there are 10^7 people going to 10^5 hotels, for an average of 100 people per hotel.

How many pair meetings are there on day 1? At each hotel, there are C(100,2) or 4950 meetings. Since there are 10^5 hotels, the total number of pair meetings is 10^5*4950 or 495,000,000, which we'll round off to 5*10^8.

How many pairs of people exist in total? That's C(10^9,2), which we'll round off to 5*10^17.

This means there's a (5*10^8)/(5*10^17) = 10^-9 chance that two randomly selected people will meet in a hotel.

In other words, given two randomly selected people, there's a (1-10^-9) chance they won't meet in a hotel today.

Reminder: (1-p)^q ~ 1 - pq for small values of p (binomial theorem)

What are the chances they won't meet over 1000 days (as given in the problem). This is:

(1-10^-9)^1000 ~ 1 - 1000*10^-9 = 1-10^-6


What are the chances they'll meet exactly once over 1000 days? That's

1000*(1-10^-9)^999*(10^-9) ~ 1000*(1 - 999*10^-9)*10^-9 ~

1000*(1-10^-6)*10^-9 = 10^-6*(1-10^-6) = 10^-6 - 10^-12


Thus, the chance they'll meet 0 or exactly 1 times is the sum of those two probabilities or 1-10^-12.

Thus, the chance they'll meet two or more times is 10^-12.

So, the chance that any randomly selected couple will meet 2 or more times in the same hotel over a period of 1000 days is 10^-12.

Since there are 5*10^17 possible couples (as above), the expected number of couples that will randomly meet in the same hotel two or more times in 1000 days is 5*10^17*10^-12 = 5*10^5 or 500,000 couples.

This is twice the answer the book gets. I believe the book is incorrect in stating:

"The chance that they will visit the same hotel on two different given days is the square of this number, 10^-18"

and that they undercount by a factor of 2, but it's possible there's an error in my own calculation.

Hopefully, however, this clarifies the orders of magnitude involved.

• Assuming--as anyone implicitly would when hearing this question--that the choices people make to go to hotels are independent, then on any given day there is essentially a $1/2$ chance that more than 1% of all people will choose to go to a hotel. There aren't enough hotels to hold all those people, so half of the time we wind up in an impossible situation. In order to proceed, it's imperative that you explicitly posit an explicit probability mechanism that is consistent with the given data. The need for this makes the question ambiguous. – whuber Jan 16 '16 at 19:51
• The link to the PDF problem gives more details on this. They arrive at the number 100 by assuming the 10^7 people split themselves evenly among the 10^5 hotels. – user1566 Jan 16 '16 at 19:53
• Which $10^7$ people? If all $10^9$ people independently choose to go to a hotel, each with a chance of $0.01$ as stated, then the hotels are overfull half the time. You need to find another way to choose the people going to hotels each night. One way is to divide all $10^9$ people into $100$ groups (once and for all) and each night choose one group at random to send its members to the hotels. You will get a very different answer using this process! You must be clear about the process you are using to choose people and assign them to hotels. – whuber Jan 16 '16 at 20:00
• Thanks @barrycarter, I believe your answer is doubled from the book because in the book, it refer to the event where each pair met on "Exactly" 2 days. Your answer is nevertheless give me a better understanding. – user1560335 Jan 16 '16 at 20:05
• After calculation, this is indeed the case(the book does assume event where each pair met exactly 2 times). Follow @barrycarter logic, the $$P(2\ pairs\ met\ on\ exactly\ 2\ days) = \binom {1000} {2} * \binom {2} {2} * (10^{-9})^2 * (1-10^{-9})^{998} = (1000*999)/2 * 10^{-18} * ((1-10^{-9})^{998})$$ handle the estimation of this equation and multiply $5*10^{17}$ back end up giving me 250,000 pairs :) – user1560335 Jan 16 '16 at 20:24