Of course before we can say we're really
done.
We need to look at the case where, x and y
don't belong to the same person.
So we want to figure out the probability
that, just at random, two [inaudible]
belonging to two totally different people,
match in at least one of these B functions
F.
Well, how might that happen?
Just at random, both of them have.
Initie in'k' position, so the probability
of that happening at random is'p' to
the'k' into'p' to the'k', ones for'x' and
one for'y' and one minus of this is the
chance is that they don't have When you
share in these K positions and then again
raising to the power B means that they
don't match in any of the B functions.
And 1- was that, again, is the chance that
at least one of these b functions f is
such that the two prints match in spite of
them being from totally different people.
And now if you plug in p = to.2 into this
form, we get.063 which is quite good.
Because what we are saying is that if the
two prints are from the same person, then
the locality sensitive hashing procedure.
Maps them onto the same bucket with a very
high probability.
But if they're not from the same person,
then the chance of a random match or our
procedure going wrong is only about six%.