Buckinghamshire CC ANPR cameras
John Wilson
tugwilson at gmail.com
Tue Jan 10 13:46:34 GMT 2012
On 10 January 2012 13:34, Clive D.W. Feather <clive at davros.org> wrote:
> 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.
Yes, collisions are quite common (they Sheffield paper points that
out). Te interesting question, given an arbitrary hash, how many valid
number plates could it represent? It's rather like the use of a
postcode in "anonymised" data sets. It doesn't have to identify a
single subject by itself as long as it narrows down the field
sufficiently.
John Wilson
More information about the ukcrypto
mailing list