# Probability of matching pair of 10-item baskets out of 100M people shopping 100 times in a year

This is from Exercise 1.2.2 of MMDS MMDS Book

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 [malicious people] will buy exactly the same set of 10 items (perhaps the ingredients for a [bad thing]?) 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 [actually malicious]?

My solution was:

$$\frac{{1e8 \choose 2}(\frac{100}{365})^2}{1e3 \choose 10} = 0.000000001.$$

My logic to find the expected number of instances (assuming randomness) was to multiply the number of possible pairs $${1e8 \choose 2}$$ by the chances that two people go shopping on the same day $$(\frac{100}{365})^2$$ and then multiplying by the chance that they pick the same 10 items.

My question is if my formula is correct and if I should square the denominator? I'm asking because a similar example in the book doesn't square the denominator. I figured it should be squared because each customer can independently choose which 10 items they want.

• Are you worried if the same person buys the same set of $10$ items twice? My shopping is similar each week. More generally, are purchases independent? I would guess a lot of people buy milk and pasta but few buy super-luxury vodka – Henry Apr 21 '19 at 22:43
• If my event were two different people out of 100e6 buying the same 10 items on the same day, I'm trying to find out how many random occurrences of that would happen. Hopefully, regardless of what they're buying – matthiasdenu Apr 21 '19 at 22:47
• I don't see that the question requires that they buy the same items on the same day, just that they buy the same items on some trip during the year. There seems to be an assumption that aside from malicious people the items bought are a random sample of the $1000$ on sale. – Ross Millikan Apr 21 '19 at 23:12

Assuming that the shopper's choices are independent and that all items are equally likely to be chosen, then given any two shoppers, the probability that their shopping baskets match by chance is $$1/\binom{1000}{10}$$. There are $$\binom{10^8}{2}$$ pairs of shoppers. So the expected number of matches is $$\lambda =\frac{\binom{10^8}{2}}{\binom{1000}{10}} \approx 1.90 \times 10^{-8}$$ The small value of $$\lambda$$ should be enough to convince us that having any matching baskets is very unlikely, but if a statement of probability is needed, then it seems we can approximate the total number of matches by a Poisson distribution with mean $$\lambda$$. Then if $$X$$ is the total number of matches, $$P(X>0) = 1 - P(X=0) = 1-e^{-\lambda} \approx \lambda$$
There are $${1000 \choose 10} \approx 2.634 \cdot 10^{23}$$ possible shopping baskets. This is a generalized birthday paradox problem. We must be intended to assume each customer takes a random independent sample of the possible baskets one each visit. There are $$10^{10}$$ samples taken. The number of samples needed to get a $$50\%$$ chance of a match is $$\sqrt {2 \ln (2) 2.634\cdot 10^{23}}\approx 6.042\cdot 10^{11}$$ so we decide it is rather unlikely that two baskets match by chance.