3
$\begingroup$

I have been struggling with the following question and would greatly appreciate any help :)

Suppose we have information about the supermarket purchases of 100 million people. Each person goes to the supermarket 100 times in a year and buys 10 of the 1000 items that the supermarket sells. We believe that a pair of criminals will buy exactly the same set of 10 items at some time during the year. If we search for pairs of people who have bought the same set of items, would we expect that any such people found were truly criminals? Assume our hypothesis to be that a pair of criminals will surely buy a set of 10 items in common at some time during the year.

This is meant to be an illustration of Bonferroni's principle. Suppose there are no criminals and that everyone behaves at random. Would we find any pairs of people who appear to be criminals?

We must initially find the expected number of pairs who buy the same 10 items per year. I'm not sure whether I do this correctly...

Here is how I've been going about solving it:

Number of possible pairs of people: $\binom{10^6}{2} = \frac{10^{12}}{2} = 5 \times 10^{11}$, using the fact that $\binom{n}{2} \approx \frac{n^2}{2}$, when $n$ is large.

Number of possible 10-item selections: $\binom{10^3}{10} \approx 2.6 \times 10^{23}$

Probability of a customer buying 10 particular items at a point in time: $\frac{1}{2.6 \times 10^{23}}$

Probability of a customer buying 10 particular items at least once over the course of 100 periods in time: $\frac{100}{2.6 \times 10^{23}}$

Probability of a pair buying exactly the same 10 items (both at least once) over the course of 100 periods in time: $(\frac{100}{2.6 \times 10^{23}})^2 = (\frac{1}{2.6 \times 10^{21}})^2 = \frac{1}{6.76 \times 10^{42}}$

The expected number of pairs who buy the same 10 items per year is thus:

$ 5 \times 10^{11} \times \frac{1}{6.76 \times 10^{42}} = \frac{5}{6.75 \times 10^{31}}$

Because the above number is so low if we do find a pair buying the same 10 items then, under our hypothesis, they are likely to be criminals and not a false positive case.

I am just wondering whether my solution to the above is correct?

$\endgroup$
  • 2
    $\begingroup$ Is it not 10^8 people? $\endgroup$ – John May 29 '14 at 0:46
2
$\begingroup$

If a person $A$ buys some (any) $10$ of the $1000$ items, then the probability that some other person $B$ buys the same set of $10$ items is $$\frac{1}{\binom{1000}{10}}.$$

For $N = 10^6$ people, and over $T = 100$ time units, the number of pairs of people is $T \binom{N}{2} = 100 \binom{10^6}{2}$.

So the expected number of occurrences of a pair of people buying the same set of items at the same time is $$\frac{100 \binom{10^6}{2}}{\binom{1000}{10}} \approx \frac{100 \times 10^{12}/2}{2.6 \times 10^{23}} \approx \frac{2 \times 10^{13}}{10^{23}} \approx \frac{1}{5 \times 10^{9}},$$

which is small, but not as small as you calculated.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm having difficulty with the # of pairs of people part. Why don't we say possible # of pairs? Also could you intuitively explain why we multiply by 100? Aren't there technically only (10^6 2) pairs? $\endgroup$ – John May 29 '14 at 1:18
  • $\begingroup$ @Anonymous: What is the difference you're thinking of between "number of pairs" and "possible number of pairs"? And yes, with $N$ people there are $\binom{N}{2}$ pairs, but over $T$ time units of buying, there are $T\binom{N}{2}$ opportunities for a pair of people to buy the same set of items at the same time. (For each pair of people, there are $T$ times when they could buy the same thing.) $\endgroup$ – ShreevatsaR May 29 '14 at 2:28
  • $\begingroup$ Thank you, makes sense. If it were instead the same set of items on the same day of the year with T=1, how would we compute the probability? Would we multiply (1/365) and 1/(1000 10)? $\endgroup$ – John May 29 '14 at 10:22
  • $\begingroup$ @Anonymous: I'm not sure I understand the question. Could you clarify? (You could post it as a new question, too.) $\endgroup$ – ShreevatsaR May 29 '14 at 10:47
2
$\begingroup$

First of all, your calculations on the number of pairs of people are wrong. There are 100 000 000 people, that's ${10}^{8}$, which gives us $5 \times {10}^{15}$ pairs of people (using the formula you wrote).

The probability of two people buying the same set of objects is ${1 \over 10^{23}}^2$ - because the same set has to be picked twice.

At the end we would get $100 \times (5 \times 10^{15}) \times ({1 \over 10^{23}})^2 ≈ 5 \times (10^{17}) \times {1 \over 10^{46}} ≈ {5 \over 10^{29}} ≈ {1 \over 2\times10^{28}} ≈ {1 \over 10^{28}}$ (I dropped the 2.6 just to make the equation simpler)

The main question here is:

"If we search for pairs of people who have bought the same set of items, would we expect that any such people found were truly criminals?"

The answer is yes, because:

"The Bonferroni principle says that we may only detect terrorists by looking for events that are so rare that they are unlikely to occur in random data"

and our event is very unlikly to happen.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

My understanding of the problem is as follows: Person A has 100 sets of 10 items because he went to the store 100 times in the year. Now the probability that B goes to the store and buys a set that was also bought by A is
$$ 100*\frac{1}{1000\choose 10} $$

This was for B's one visit. The 100 that we see in the product comes from the fact that A had 100 items. Now we know B also went to the store 100 times so probability that A and B had a same set of 10 items becomes
$$ 100*\frac{1}{1000\choose 10}*100 $$

Knowing that we have 100 million people, possible pairs of A and B $$ {10^8\choose 2} $$ Hence the final answer to me seems to be $$ 100*\frac{1}{1000\choose 10}*100*{10^8\choose 2} \sim \frac{10^{20}}{10^{30}}*10\,! $$ I would be happy to discuss the solution.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.