# Probability of duplicates

1. Aug 11, 2015

### DaanV

Mod note: Removed "Basic calculus" from thread title, as the question doesn't seem to have anything to do with calculus

1. The problem statement, all variables and given/known data
Real world kind of thing.

Assume I have a set of C components that I want to investigate.
I want to give each component a unique identifier. I have N identifiers.

What is the probability of having two components with the same identifier (duplicate), given N and C?

2. Relevant equations
What I'm looking for!

3. The attempt at a solution
So let's say one component gets some identifier. The probability that none of the other components get the same identifier would be:
(1- 1/N)C, assuming N>>C (how much bigger would N have to be than C for this to be a valid assumption, btw?)

However, by my logic this doesn't yet exclude the possibility that any of the other components have duplicate identifiers to one another. This is where I'm getting stuck.

Thanks in advance for any help provided!

Last edited by a moderator: Aug 11, 2015
2. Aug 11, 2015

### Dick

You might want to look at this. https://en.wikipedia.org/wiki/Birthday_problem

3. Aug 11, 2015

### DaanV

Well.. That just goes to show I should probably dive into Wikipedia first next time. :)
Thanks for your help, that solved it perfectly.

4. Aug 11, 2015

### insightful

If the "birthday solution" applies, then didn't you mean, "I want to give each component a randomly chosen identifier"?

5. Aug 11, 2015

### DaanV

Sorry, yes, I do suppose I meant that.
More completely:
"I am giving each component a randomly chosen identifier. I would like to give each component a unique identifier. How can I determine the number of unique identifiers N, so that I have at least 99% odds of having no duplicate identifiers?"

I think I have that figured out though. Thanks for clearing it up. :)

6. Aug 13, 2015

### DaanV

So I’ve been mulling this one over a bit more. I have come to the conclusion that the previous answer, although correct, actually wasn’t what I was looking for. The requirement of X% odds of having zero duplicates is too stringent for my application. So please allow me to introduce a new (and entirely related!) problem.

Mind you, I think I have the correct answer. I’m asking for feedback on if I’m making stupid assumptions. So here goes, thanks in advance!

1. The problem statement, all variables and given/known data
Real world kind of thing.

Assume I have a set of C components that I want to investigate.
I am giving each component a random identifier. I have N identifiers.
(e.g. if there are 500 components and 100 identifiers, L=C/N=5)

The problem:
How small must L be (or how much greater the number of identifiers than the number of components) for >= 99% of components to be assigned to a unique identifier?

2. Relevant equations
The partitioning of components into identifiers is described by a Poisson distribution (assumption! Is this likely to be correct?), where P(k;L) is the probability for there to be k components in one identifier given an average loading L.
$P(k;L) = \frac{L^k*e^{-L}}{k!}$

3. The attempt at a solution
Fraction of identifiers with exactly one component assigned to them is
$P(1;L) = \frac{L^1*e^{-L}}{1!} = L * e^{-L}$

To get number of identifiers with exactly 1 component (N1), multiply by N
$N1 = N * L * e^{-L} = C * e^{-L}$

The number of identifiers with exactly 1 component corresponds to the number of components that are uniquely assigned to an identifier (N1 = Cunique). The percentage of components uniquely assigned to an identifier is then given by
$\frac{Cunique}{C} = e^{-L}$

So that the critical value of 99% unique is obtained when:
$L = -ln(0.99) = 0.01005$ components/identifier
In other words, as long as there are at least ~100x as many identifiers as components, I can expect 99% of the components to be uniquely assigned to an identifier.

Is this correct?
The outcome looks.. surprisingly simple. Did I overlook something somewhere? Did I take a tremendous detour to get to this answer?
Thanks in advance for taking the time!

Regards, DaanV

7. Aug 13, 2015

### haruspex

That's not really valid because the probabilities of how many get assigned to a given label are not independent.
Also, you seem to be missing a parameter. You want the probability that 99% are unique.

This is quite a hard problem. Let's start with a simpler question. Given R distinct objects and N distinct buckets, how many ways are there of assigning objects to buckets such that no bucket gets exactly one object?
Do you know the principle of inclusion and exclusion?

8. Aug 13, 2015