1
00:00:00,000 --> 00:00:04,560
Of course before we can say we're really
done.

2
00:00:04,880 --> 00:00:11,060
We need to look at the case where, x and y
don't belong to the same person.

3
00:00:12,320 --> 00:00:19,325
So we want to figure out the probability
that, just at random, two [inaudible]

4
00:00:19,325 --> 00:00:27,059
belonging to two totally different people,
match in at least one of these B functions

5
00:00:27,059 --> 00:00:29,697
F.
Well, how might that happen?

6
00:00:29,697 --> 00:00:37,041
Just at random, both of them have.
Initie in'k' position, so the probability

7
00:00:37,041 --> 00:00:44,348
of that happening at random is'p' to
the'k' into'p' to the'k', ones for'x' and

8
00:00:44,348 --> 00:00:52,571
one for'y' and one minus of this is the
chance is that they don't have When you

9
00:00:52,571 --> 00:00:59,513
share in these K positions and then again
raising to the power B means that they

10
00:00:59,513 --> 00:01:06,385
don't match in any of the B functions.
And 1- was that, again, is the chance that

11
00:01:06,385 --> 00:01:13,617
at least one of these b functions f is
such that the two prints match in spite of

12
00:01:13,617 --> 00:01:20,849
them being from totally different people.
And now if you plug in p = to.2 into this

13
00:01:20,849 --> 00:01:27,728
form, we get.063 which is quite good.
Because what we are saying is that if the

14
00:01:27,728 --> 00:01:34,960
two prints are from the same person, then
the locality sensitive hashing procedure.

15
00:01:35,240 --> 00:01:41,193
Maps them onto the same bucket with a very
high probability.

16
00:01:41,193 --> 00:01:49,230
But if they're not from the same person,
then the chance of a random match or our

17
00:01:49,230 --> 00:01:53,200
procedure going wrong is only about six%.