Buckinghamshire CC ANPR cameras

[Clive D.W. Feather]

John Wilson said:
> As the hash is only 24 bits and there are 34.5 million licensed
> vehicles on the road there must be collisions even if the hash
> function were perfect (and it's not).

Hmm. Let's assume for the moment that the overall algorithm brings 3 cars
into one hash on average. Then that's about 11.5 million hashes. At
2-second spacing, a camera over a lane would see 1800 cars per hour, so
let's assume 20,000 cars per day and assume no car passes the camera twice.
What's the chance of a hash collision in that lot?

If I've done my algebra correctly, I get the probability of no collision
as approximately:

    p = {r^k (n/r)!/(n/r - k)!} / {n!/(n - k)!}

where r = 3, n = 11.5 million, k = 20000. So that's:

    p = 3^20000 *  3833333! * 11480000! / (11500000! * 3813333!)

Using Stirling's formula and logs [ln n! = n (ln n - 1) + 0.5 ln n + 1.837877]
we get:

    ln p = 20000 ln 3 +  3833333 (ln  3833333 - 1) + 0.5 ln  3833333
                      + 11480000 (ln 11480000 - 1) + 0.5 ln 11480000
                      - 11500000 (ln 11500000 - 1) - 0.5 ln 11500000
                      -  3813333 (ln  3813333 - 1) - 0.5 ln  3813333

         = 21972.2458 +  3833333 (15.15925 - 1) + 0.5 * 15.15925
                      + 11480000 (16.25611 - 1) + 0.5 * 16.25611
                      - 11500000 (16.25786 - 1) - 0.5 * 16.25786
                      -  3813333 (15.15401 - 1) - 0.5 * 15.15401

         = -108.09

So the probability of a collision is 1 - 1.14e-47, or just about certain.

-- 
Clive D.W. Feather          | If you lie to the compiler,
Email: clive at davros.org     | it will get its revenge.
Web: http://www.davros.org  |   - Henry Spencer
Mobile: +44 7973 377646