(11C) Probability of No Repetitions

[Albert Chan]

(01-10-2020 12:42 PM)Gamo Wrote:  Probability of No Repetitions in a Sample

Suppose a sample of size n is drawn with replacement from population
containing m different objects. Let P be the probability that there are no
repetitions in the sample, then

P = [1- (1/m)][1- (2/m)]....[1- (n-1)/m]

This is similar to thread (42S) Probability of Same Birthday Day

We can do approximation the same way: products of terms = exp of sum of ln(term)
Sum is approximated by integral with correction (bolded expression below)

If we let u = 1-x/m, we have x = m-m*u

XCas> f := ln(1-x/m)
XCas> expand(subst(int(f) - f/2 + diff(f)/12, x = m-m*u))   → m*u - 1/(12*m*u) - ln(u)/2 - m*u*ln(u)
XCas> g(m,u) := -1/(12*m*u) - ln(u)*(0.5 + m*u) + m*u       // ≈ sum formula
XCas> p(m,n) := exp(g(m, 1.-n/m) - g(m, 1.-1/m))                 // ≈ product(1-x/m, x=1 .. n-1)

XCas> p(365, 4)       → 0.9836440875
XCas> p(365,23)      → 0.4927027657
XCas> p(365,48)      → 0.03940202712