# Probability of getting items 1-N when selecting from population of 1-M (M\>N) **URL:** \ **Category:** Factual Questions\ **Created:** [August 16, 2018, 10:36pm UTC](https://boards.straightdope.com/t/probability-of-getting-items-1-n-when-selecting-from-population-of-1-m-m-n/819758 "2018-08-16T22:36:40Z")\ **Posts on this page:** 5\ **Page:** 2
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [August 19, 2018, 5:13pm UTC](https://boards.straightdope.com/t/probability-of-getting-items-1-n-when-selecting-from-population-of-1-m-m-n/819758/21 "2018-08-19T17:13:08Z")
Actual words (i.e., a non-uniform probability of collecting each of the 325 “coupons”) were considered in Post #11. Since one would have to estimate these probabilities by reading a dictionary anyway, I’m not sure a Monte Carlo estimate is really cheating compared to an “exact” answer in that case. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [August 19, 2018, 5:15pm UTC](https://boards.straightdope.com/t/probability-of-getting-items-1-n-when-selecting-from-population-of-1-m-m-n/819758/22 "2018-08-19T17:15:26Z")
> [@Leo\_Bloom](#): > > What was the job your friend interviewed for? Combinatorist, obviously 🙂 ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [August 19, 2018, 6:21pm UTC](https://boards.straightdope.com/t/probability-of-getting-items-1-n-when-selecting-from-population-of-1-m-m-n/819758/23 "2018-08-19T18:21:03Z")
> [@septimus](#): > > _Very_ elegant, **DPRK**! > > **Manlob** ’s approximate probability (1 - e[sup]-n/325[/sup])[sup]25[/sup] will often be more practical, I think. > I wonder what the limitations are on the approximation. It helps that 325 is largish, but I think the formula’s result is in the “ballpark” even for much smaller numbers. Obviously n can’t be too small to use that approximation; it should be at least 1000 or so. Perhaps a saddle point method applied to the function in Post #16 will yield a complete asymptotic expansion; do you have a good computer algebra system? ---
**Author:** ![iamthewalrus\_3](https://avatars.discourse-cdn.com/v4/letter/i/258eb7/32.png) [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)\ **Post date:** [August 19, 2018, 7:59pm UTC](https://boards.straightdope.com/t/probability-of-getting-items-1-n-when-selecting-from-population-of-1-m-m-n/819758/24 "2018-08-19T19:59:08Z")
> [@DPRK](#): > > Actual words (i.e., a non-uniform probability of collecting each of the 325 “coupons”) were considered in Post #11. Since one would have to estimate these probabilities by reading a dictionary anyway, I’m not sure a Monte Carlo estimate is really cheating compared to an “exact” answer in that case. I think you could read all the words into a trie that counts how many words start each way and then traverse the trie and get actual counts for each of the 325 pairings across the whole dictionary. I don’t think I care enough to code that up, but you could then calculate the recurrence relation exactly in a reasonable time. ---
**Author:** ![iamthewalrus\_3](https://avatars.discourse-cdn.com/v4/letter/i/258eb7/32.png) [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)\ **Post date:** [August 20, 2018, 5:29am UTC](https://boards.straightdope.com/t/probability-of-getting-items-1-n-when-selecting-from-population-of-1-m-m-n/819758/25 "2018-08-20T05:29:55Z")
> [@Leo\_Bloom](#): > > What was the job your friend interviewed for? > > I’m also interested also in the variety of jobs for which that could be a valid question from a (annoyingly ball-buster?) HR interviewer. It was a software job. I don’t know the specifics. To clarify: The question I asked in this thread was _not_ the question he was asked to answer in the interview. He was asked a different (simpler, algorithmic rather than combinatoric) question, and as we were discussing that one, this was one of the spinoff “I wonder…”. [Previous page](https://boards.straightdope.com/t/probability-of-getting-items-1-n-when-selecting-from-population-of-1-m-m-n/819758.md?page=1)