1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability of duplicates

  1. Aug 11, 2015 #1
    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. jcsd
  3. Aug 11, 2015 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You might want to look at this. https://en.wikipedia.org/wiki/Birthday_problem
     
  4. Aug 11, 2015 #3
    Well.. That just goes to show I should probably dive into Wikipedia first next time. :)
    Thanks for your help, that solved it perfectly.
     
  5. Aug 11, 2015 #4
    If the "birthday solution" applies, then didn't you mean, "I want to give each component a randomly chosen identifier"?
     
  6. Aug 11, 2015 #5
    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. :)
     
  7. Aug 13, 2015 #6
    Thread revival!

    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.
    The ‘loading’ (L) is the average number of components per identifier.
    (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
     
  8. Aug 13, 2015 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  9. Aug 13, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Thinking about this some more, I suggest making an approximation appropriate to the question asked.
    Since you are interested in the case where there are very few duplicates, the probability of three or more getting the same label is vanishingly small.
    So consider this:
    r distinct objects are placed in n distinct buckets. In how many ways can t <= r/2 buckets get exactly two, and no bucket get more than two?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted