# Probablily calculation question **URL:** \ **Category:** Factual Questions\ **Tags:** science-math\ **Created:** [March 28, 2025, 3:25pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259 "2025-03-28T15:25:56Z")\ **Posts on this page:** 13\ **Page:** 1
**Author:** ![Earl\_Snake-Hips\_Tucker](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/earl_snake-hips_tucker/32/3269_2.png) [@Earl\_Snake-Hips\_Tucker](https://boards.straightdope.com/u/Earl_Snake-Hips_Tucker)\ **Post date:** [March 28, 2025, 3:25pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/1 "2025-03-28T15:25:56Z")
I have a population x and I want to select y items and The items in population x are reusable, similar to the “Birthday Paradox,” how do I calculate the expected number of unique items? ---
**Author:** ![Stranger\_On\_A\_Train](https://avatars.discourse-cdn.com/v4/letter/s/13edae/32.png) [@Stranger\_On\_A\_Train](https://boards.straightdope.com/u/Stranger_On_A_Train)\ **Post date:** [March 28, 2025, 3:28pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/2 "2025-03-28T15:28:44Z")
Your question is unclear. Are you asking about ‘selection’ with replacement, and what the odds are of getting a previously selected item? Stranger ---
**Author:** ![Earl\_Snake-Hips\_Tucker](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/earl_snake-hips_tucker/32/3269_2.png) [@Earl\_Snake-Hips\_Tucker](https://boards.straightdope.com/u/Earl_Snake-Hips_Tucker)\ **Post date:** [March 28, 2025, 3:33pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/3 "2025-03-28T15:33:14Z")
Well, as an example,I have 100 items, and I select them one at a time, put them back, and reselect. If I do that 100 times, I’d expect to have selected maybe 60-65 unique items. Wondering what the general formula is. ---
**Author:** ![Stranger\_On\_A\_Train](https://avatars.discourse-cdn.com/v4/letter/s/13edae/32.png) [@Stranger\_On\_A\_Train](https://boards.straightdope.com/u/Stranger_On_A_Train)\ **Post date:** [March 28, 2025, 3:59pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/4 "2025-03-28T15:59:23Z")
What you are describing is a cascading chain of conditional probabilities, from which you could laboriously derive a composite probability distribution stretching between the two extremes of 100 unique items to selecting the exact same item 100 times in a row. Those two cases are the easiest to solve because they are linear chains, and everything in-between is branching, You could develop a formula for calculating the likelihood of getting y unique items in x draws by summing over all of the possible permutations but it won’t be a simple formula even if you go through the gyrations to reduce it down. From a practical standpoint, unless you want the academic exercise of working through a graduate-level problem in combinatorics, I would just set up a Monte Carlo simulation, run it a few million times, and trust the central limit theorem to give you a close approximation of that distribution. Stranger ---
**Author:** ![hogarth](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hogarth/32/1773_2.png) [@hogarth](https://boards.straightdope.com/u/hogarth)\ **Post date:** [March 28, 2025, 8:26pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/5 "2025-03-28T20:26:32Z")
The limit is 1 - 1/e (roughly 63.2%). > ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [March 28, 2025, 8:48pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/6 "2025-03-28T20:48:44Z")
Indeed so. It can be re-framed to be equivalent to something called a Derangement in Combinatorics (a term I always appreciated). And you tend to hit it pretty fast. After about 7 or 8 trials, you’re probably in the neighborhood of that limit already. > **[Derangement](https://en.wikipedia.org/wiki/Derangement)** > > In combinatorial mathematics, a derangement is a permutation of the elements of a set in which no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. > The number of derangements of a set of size n is known as the subfactorial of n or the n th derangement number or n th de Montmort number (after Pierre Remond de Montmort). Notations for subfactorials in common use include !n, Dn, dn, or n¡ .\[a\] > For n \> 0 , the subfactorial !n equal... ---
**Author:** ![Buck\_Godot](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/buck_godot/32/6573_2.png) [@Buck\_Godot](https://boards.straightdope.com/u/Buck_Godot)\ **Post date:** [March 28, 2025, 8:52pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/7 "2025-03-28T20:52:17Z")
If all you are interested in is the expected value, its not actually too hard. For a given element _i_ of the population let’s define a variable that is equal to 1 if that sample is seen and 0 if it isn’t. The total number of observations seen is going to be equal to the sum of these variables. And for each of these variables, the probability that a that variables will have a value of 1 is given by: P(_i_ will be seen) = 1-P(_i_ will not be seen in any of the y draws) = 1-P(_i_ will not be seen in one of the draws)^y = 1-P(1-1/x)^y Now as @Stranger_On_A_Train says, all of these variables are conditionally dependent. But if all we are interested in is the expected value, then it doesn’t matter. Regardless of the dependency the expectation of a sum of variables, is equal to the sum of their expectations. So since each of the X elements of population has an expectation equal to 1-P(1-1/x)^y the total number of unique hits will be equal to x\*(1-(1-1/x)^y). > [@hogarth](#): > > The limit is 1 - 1/e (roughly 63.2%). This is true only if y is approximately equal to x, since (1-1/x)^x approaches 1/e In general if x and y are large the proportion hit will be close to 1-exp(-y/x) ---
**Author:** ![Buck\_Godot](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/buck_godot/32/6573_2.png) [@Buck\_Godot](https://boards.straightdope.com/u/Buck_Godot)\ **Post date:** [March 28, 2025, 9:09pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/8 "2025-03-28T21:09:01Z")
> [@Buck\_Godot](#): > > the total number of unique hits will be equal to x\*(1-(1-1/x)^y To late to edit, this should read the total **expected** number of unique hits will be equal to x\*(1-(1-1/x)^y ---
**Author:** ![Earl\_Snake-Hips\_Tucker](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/earl_snake-hips_tucker/32/3269_2.png) [@Earl\_Snake-Hips\_Tucker](https://boards.straightdope.com/u/Earl_Snake-Hips_Tucker)\ **Post date:** [March 28, 2025, 9:42pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/9 "2025-03-28T21:42:30Z")
Thanks, and actually with some random (not to start _that_ debate!) testing, that pretty much reflects the results I found. ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [March 29, 2025, 4:05am UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/10 "2025-03-29T04:05:17Z")
I should hope so! The numbers should match the theory. But one problem that can exist with empirical testing is determining whether or not one has enough samples to form a general rule, which I imagine is where you were sitting before the thread. ---
**Author:** ![Honolulu\_Lulu](https://avatars.discourse-cdn.com/v4/letter/h/87869e/32.png) [@Honolulu\_Lulu](https://boards.straightdope.com/u/Honolulu_Lulu)\ **Post date:** [March 30, 2025, 11:58pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/11 "2025-03-30T23:58:30Z")
Is this what you’re looking for? Poisson distribution. Given N possible events, and Q random picks, What is the probability of “x” hits (e.g. Q=1m lottery players choose from N=3.9m choices, what are the odds of 2 winners) The limiting as N approaches infinity … A = Q/N (A is also the expected value or mean) P(x) = (e \*\* -A \* A\*\*x) / x! ---
**Author:** ![Earl\_Snake-Hips\_Tucker](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/earl_snake-hips_tucker/32/3269_2.png) [@Earl\_Snake-Hips\_Tucker](https://boards.straightdope.com/u/Earl_Snake-Hips_Tucker)\ **Post date:** [March 31, 2025, 1:14pm UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/12 "2025-03-31T13:14:12Z")
Thanks, but no. For what I was looking for, that looks a little fishy to me. And . . . this is not to open another discussion on the nuances and technicalities on what constitutes ‘random.’ For this situation, it’s random enough! Specifically where this came up was at my work, a person in another department was needing to do a ‘random’ sampling of 150 pieces of equipment out of a population of 250. I was somewhat familiar with the process they used, and I knew that the software a) often generated a previously used number, and b) expected duplicatesm especially with large samples of small groups, and just grabbed another random number if one had already been used. So, in a case of 150 out of 250, it might have to generate 200+ random numbers to get 150 unique ones. So, I was just curious as to how many unique values to expect if it stopped at 150. ---
**Author:** ![CookingWithGas](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cookingwithgas/32/485_2.png) [@CookingWithGas](https://boards.straightdope.com/u/CookingWithGas)\ **Post date:** [April 8, 2025, 3:08am UTC](https://boards.straightdope.com/t/probablily-calculation-question/1016259/13 "2025-04-08T03:08:32Z")
> [@Earl\_Snake-Hips\_Tucker](#): > > sampling of 150 pieces of equipment out of a population of 250 The way to do this is not to repeatedly generate random integers until you get 150 distinct ones. Generate 250 random _real_ numbers, such as in the interval [0-1], assigning a result to each machine. Then sort by the random numbers. Sample the machines with the lowest 150 numbers. You can to this pretty easily in Excel. This is a “shuffle” algorithm rather than a “selection with replacement” algorithm.