4

Suppose two people go grocery shopping $100$ times each. Each time, they pick $10$ items randomly from the $1000$ items at the store. As a result, each person has $100$ randomly chosen baskets of $10$ items.

What is the probability that, by the end, both people have one identical randomly chosen basket?

This problem is straightforward if I know that the $100$ random baskets are unique (in which case you can calculate the probability as having person two pick one of the $100$ random baskets person one chose in $100$ tries), but I don't know how to account for the fact that each person could have fewer than $100$ unique random baskets.

As I write this question, I realized it might be possible to write the probability as a sum over the number of unique random baskets person one chose.

Community
  • 1
  • 1
    Idea: Suppose P1 picks $100$ unique baskets. Then the probability that P2 picks an identical basket is $1 - \left(1 - 100/\binom{1000}{10}\right)^{100}$. Now to get the real probability, you have to sum across all possible number of unique baskets where if P1 picks $i$ unique baskets, the probability that P2 has an identical one is $1 - \left(1 - i/\binom{1000}{10}\right)^{100}$. However, this expression has numbers too extreme to be accurately calculated... –  Sep 01 '15 at 16:53
  • What do you mean "numbers too extreme to be accurately calculated"? Do you mean using standard computer floating point to represent all your numbers, with naive direct calculations on those numbers using your formulas? It seems to me that with a few tricks, e.g. getting a really good approximation for the small expression $1 - (1-x)^{100}$ when $x$ is close to $0$, and computing on the log scale to avoid underflow, it shouldn't be that bad. – user2566092 Sep 01 '15 at 17:46
  • Yes I meant naively on a calculator. –  Sep 01 '15 at 17:48
  • Exactly one (i.e., no other pair is identical), or at least one? – barak manos Sep 06 '15 at 05:37

1 Answers1

0

The number of pairs $(f,g)$ of maps from an $m$-set into an $n$-set having disjoint images is $A(n,m)$ where $A(\cdot,\cdot)$ is the function appearing as OEIS A212085.

For this situation, $n=\binom{1000}{10}$ is the number of possible baskets and $m=100$ is the number of trials for each of the two people. There are $n^{2m}$ pairs of maps total, so the probability that the two sets of baskets intersect is $$1-\frac{A(n,m)}{n^{2m}}.$$

Tad
  • 6,679