过分伤痛5 Detection: Mathematical Model and Results
In this section, we will address problems P3 and P4 proposed in Section 3. Suppose the design house asks the foundry to fabricate n copies and N ? n is the number that the foundry really makes. P3 asks the expected number of tests to find a duplicate if N > n or the number of tests to convince designer that N = n . P4 requires an estimation of N once the first unauthorized is found. We take the dishonest foundry’s best strategy in that he
makes duplicates for each original copy. It is proven that for a fixed , the dishonest foundry has the best chance to survive in this equiprobable case.
Theorem 5.1. Draw l from objects which consist of k copies of n distinct ones,
the probability that there is no duplicate, denoted by Prob[n,k,l], is
(1)
which has an upper bound
(2)
where .
Prob[n,k,l] is the probability that there are no unauthorized parts found after l random tests (without replacement), provided that there are k copies for each of the n originals. It decreases as k increases, since when the population (N ) grows, it becomes more difficult to find duplicates; it also decreases as l , the number of tests, increases.
The quantity 1-Prob[n,k,l] is the confidence that the designer can achieve from l con-secutive successful tests. Success means that no duplicate is found. Table 1 shows some k 1–N k n ?=N k n ?=1k 1–N 1–------------–12k 1–()N 2–-------------------–…1l 1–()k 1–()N l 1–()–-------------------------------–?1p n --–12p ?n ---------–…1l 1–()p ?n ----------------------–?p 11k ?–=
