Probability of two people authenticating as the same person

Question

Suppose that a system is designed to detect N different “features” of a fingerprint, and each of these features can take on D different values. Further, assume that for any given fingerprint these values are all equally likely for every feature. Suppose you have P individuals randomly sampled from the population. N, D, and P are variables. For given values of these variables, you want to know how likely it is if you have a sample of P individuals that at least one of them will be able to authenticate as someone else in the sample. 

a) Write down an equation you can use to approximate the solution to this problem. (Hint: this is very similar to detecting a hash collision)

b) What is the likelihood for N=10, D=5, and P=100?

c) For N=10, D=5, and P=1,000?

d) For N=20, D=10, and P=10,000?

Answer 1

If there are N different features, each with D different values, so there are N^D possible values. We have P individuals in the population.

For N = 10 and D = 5, D^N = 9765625

The probability of at least one collision is 1 - the probability of no collisions.

The probability of no collisions is D^N-1/D^N * D^N-2/D^N *... * D^N-P+1/D^N

For D^N large, (D^N - x)/N^D = e^(-x/D^N), and 1 + 2 + ... + P-1 = P(P-1)/2, so 1-D^N-1/D^N * D^N-2/D^N *... * D^N-P+1/D^N is approximately 1 - e^-(P(P-1)/2/D^N is approximately 1 - e^-P^2/(2 D^N) (the sum would be less but the original fractions produce a larger negative coefficient, so this is a great idea).

a) For P = 100, if we use the final approximation 1 - e^-P^2/(2 D^N), we get

1 - e^-(100)^2/(2*9765625) = .000512

If we use the previous approximation 1 - e^-(P*(P-1))/(2 D^N), 1 - e^-(100*99)/(2*9765625) =

The exact answer is 1 - 9765624/9765625*9765623/9765625*...*9765526/9765625 = .000507

b) For P = 1000, if we use the final approximation 1 - e^-P^2/(2 D^N), we get

1 - e^-(1000)^2/(2*9765625) = 0.049911

If we use the previous approximation 1 - e^-(1000*999)/(2*9765625) = 0.049863

The exact answer is 1 - 9765624/9765625*9765623/9765625*...*9764626/9765625 = 0.049864

c) For P = 10000, if we use the final approximation 1 - e^-P^2/(2 D^N), we get

1 - e^-(10000)^2/(2*9765625) = 0.994024

If we use the previous approximation 1 - e^-(10000*9999)/(2*9765625) = 0.994021

The exact answer is 1 - 9765624/9765625*9765623/9765625*...*9755626/9765625 = 0.994031

Note how the first approximation, with less terms in the exponent, is not as good in the first 2 cases, with the second approximation being almost exactly correct, but with a large number of individuals, the approximation with more terms is less correct.

Answer 2

Well as you have N different features and D different values, number of possible combinations of features are D X D X D ... (N times) so D^N

If you choose P individuals, supposing they all have a different combination of features.

The first individual we can choose their features in D^N ways

Second individual D^N-1 ways

Third D^N-2 ways

So number of ways = D^N.D^N-1. ... D^N-P+1 ways (if P=1, we must get D^N here) call this A

Number of ways of choosing the features for the P individuals is (D^N)^P = D^NP call this B

So the required probability will be 1 - (A/B)

= 1 - (1). (1/D) . (1/D²). (1/D³). (1/D^P-1)

= 1 - ( 1/ D ^{1 + 2 + P-1}) = 1 - ( 1/D^{0.5 P (P-1)})

You can finish the question by substituting in values

Mike