There's been some excitement among criminal defense bloggers such as Mr. Greenfield, Mr. Katz, and the Dude over a fascinating Los Angeles Times article about some strange search results in some of the major DNA databases.

State crime lab analyst Kathryn Troyer was running tests on Arizona's DNA database when she stumbled across two felons with remarkably similar genetic profiles.

The men matched at nine of the 13 locations on chromosomes, or loci, commonly used to distinguish people.

The FBI estimated the odds of unrelated people sharing those genetic markers to be as remote as 1 in 113 billion. But the mug shots of the two felons suggested that they were not related: One was black, the other white.

Troyer went on to find 144 other 9-loci matches in the Arizona database, and other people have found comparable numbers of stray matches in other state databases.

The article summarizes the response to this from Steven Myers of the California Department of Justice:

Many of the Arizona matches were predictable, Myers said, given the type of search Troyer had conducted.

In a database search for a criminal case, a crime scene sample would have been compared to every profile in the database -- about 65,000 comparisons. But Troyer compared all 65,000 profiles in Arizona's database to each other, resulting in about 2 billion comparisons. Each comparison made it more likely she would find a match.

When this "database effect" was considered, about 100 of the 144 matches Troyer had found were to be expected statistically, Myers found.

Myers is talking about a famous non-intuitive statistical result called the birthday paradox. Suppose we're in a room with about 50 people, and I offer you a simple even money bet that at least two people in the room have the same birthday.  Should you take the bet?

The math seems simple: There are 365 possible birthdays, so 50 people cover 50/365 of the possible birthdays. It seems like I'm offering you even money on something with only about a 1 in 7 chance of happening, which sounds like a good deal for you.

Actually, it's a sucker bet. With 50 people in the room, there's about a 97% chance of two or more people having matching birthdays. I'd only lose this bet about 1 out of every 30 times I tried it.

It's easiest to understand why this works if you imagine admitting the people to the room one at a time, checking their birthdays as they enter, and stopping when you get a match. The first person gets in free, because there's no one to match. The second person is then checked against the first. The chance of a match stopping the process at the second person is therefore 1/365 (we're ignoring leap years). To put it another way, the chance of continuing is 364/365.

The third person to enter the room can match either of the two people already in it, so the chance of a match is 2/365 and the chance of a non-match is 363/365. But the third person is not allowed to enter unless the second one didn't match either, so the chance of no match with three people requires that both fail to match, the chance of which is calculated by multiplying (364/365) x (363/365) = 0.991796. That's the chance of failure to match, so the chance of success is given by 1 - 0.991796 = 0.008204, less than 1%.

For the fourth person, the chances of failure to match the other three is 362/365, bringing the total chance of failure to get a match for 4 people to (364/365) x (363/365) x(362/365) = 0.983644, meaning the chance of success is 1.6356%.

Note that each person who enters the room is checked against everybody in the room, so the first person is not checked at all, the second person is checked against the first, the 3rd person is checked against the 1st and 2nd, for a total 3 pairs checked. Person #4 is checked against the first 3, bringing the total to 6 pairs checked. By the time we get to the tenth person, we've checked 45 pairs of birthdates, and the chance of success has accumulated to 11.69%.

Here's the rundown of all 50:

# People	Chance of Success	# Pairs Checked
1	0.00%	0
2	0.27%	1
3	0.82%	3
4	1.64%	6
5	2.71%	10
6	4.05%	15
7	5.62%	21
8	7.43%	28
9	9.46%	36
10	11.69%	45
11	14.11%	55
12	16.70%	66
13	19.44%	78
14	22.31%	91
15	25.29%	105
16	28.36%	120
17	31.50%	136
18	34.69%	153
19	37.91%	171
20	41.14%	190
21	44.37%	210
22	47.57%	231
23	50.73%	253
24	53.83%	276
25	56.87%	300
26	59.82%	325
27	62.69%	351
28	65.45%	378
29	68.10%	406
30	70.63%	435
31	73.05%	465
32	75.33%	496
33	77.50%	528
34	79.53%	561
35	81.44%	595
36	83.22%	630
37	84.87%	666
38	86.41%	703
39	87.82%	741
40	89.12%	780
41	90.32%	820
42	91.40%	861
43	92.39%	903
44	93.29%	946
45	94.10%	990
46	94.83%	1035
47	95.48%	1081
48	96.06%	1128
49	96.58%	1176
50	97.04%	1225

Note that the actual break-even 50/50 chance of a match occurs when there are only 23 people in the room. Also note that by the time we've reached 50 people, we've checked 1225 pairs. Since each pair has a 1/365 chance of matching, we should actually have several matches by now.

A similar statistical effect should be at work in the DNA database. Troyer's database search was comparing everyone in the database against everyone else. Since each person is compared with every other person, the chances of a successful match are much higher than intuition suggests. With 65,000 entries in the database, Troyer checked 2 billion pairs of people for a match.

That still doesn't get us over the hump of the FBI's claimed 113 billlion-to-one odds, but there's another difference between Troyer's search and a typical cold DNA search.

The second part of Myers' explanation for the strange DNA results is here:

Troyer's search also looked for matches at any of 13 genetic locations, while in a real criminal case the analyst would look for a particular profile -- making a match far less likely.

To understand this, suppose you want to flip 3 coins and have three heads come up to win. What are the odds? If you flip the coins, there are 8 possible outcomes:

TTT

TTH

THT

THH

HTT

HTH

HHT

HHH !

Since only one of these has three heads (marked with an !) , the chance of three heads with three coins tossed is 1/8.

Now let's look at the chance of getting 3 heads by tossing 4 coins. Here are the possible results:

TTTT	HTTT
TTTH	HTTH
TTHT	HTHT
TTHH	HTHH !
THTT	HHTT
THTH	HHTH !
THHT	HHHT !
THHH !	HHHH !

Now there are 5 winners out of 16, which means we've more than doubled the chance of getting three heads just by allowing an extra flip. This is the unsurprising result of the fact that the more tries we get to win, the greater our chance of success.

Something similar happens in the DNA database, but to understand it, we have to look at how a database match is normally done.

When some DNA evidence is found at a crime scene, a forensic technician attempts to find samples of all 13 of the loci that are used for a standard test. If the sample is degraded, there may not be enough surviving loci. It's my understanding that unless the tech finds 9 or more usable loci, the sample is considered too poor for forensic purposes.

So, if the tech finds 9 loci, she plugs them into the database and looks for someone who matches on all 9. However, if the tech finds 10, she has to do a search for someone who matches on all 10. A match on 9 isn't good enough, because that would mean that the sample doesn't match on the 10th loci, and any mismatch excludes a person from the search.

That's the key: In a real search, you have to match on every loci in the evidence sample. 9 out of 9, 10 out of 10, 13 out of 13.

In the search that Troyer did, however, she compared each 13-loci database entry with every other 13-loci entry, but considered it a match if only 9 out of 13 were successful.

From the information I've found, I can make a rough estimate of what that does to the search. If a 9-out-of-9 match happens by chance one in 113 billion times as the FBI says, that works out to the chance of a random match at each loci of only about 5.9%. In other words, to get a 9-out-of-9 match by accident, the sample would have to beat that 5.9% probability 9 times in a row. (5.9% is about 1 chance in 17, so beating the odds at all 9 loci works out to about 1 in 17⁹, or 1 in 119 billion, which is a rounding error off the FBI's number.)

So, with a per-loci probability of 5.9%, we can use the binomial distribution to determine that the probability of 9 matches out of 13 is about 1 in 197 million, which is about 570 time more likely than the FBI's estimate for a 9-out-of-9 match. Further, since Troyer's query checked 2 billion pairs, we could expect about 10 matches at those odds.

Myers said the expected number of matches was 100, which is 10 times my figure. I assume he's working with better data than I am.

In particular, my way of calculating the per-loci probability of a match assumes that all loci have equal variance, and that all values found at each loci are equally likely. Both of those assumptions are almost certainly wrong for real DNA data, and any deviation would lead to clumping that would make some loci values more likely to match than others, which would increase the chance of a coincidental match.

I also setup an Excel spreadsheet to run the birthday paradox math based on a 1 in 197 million match per pair, and the chance of a match is even money when there are only 16500 samples in the database. So it's not surprising that these kinds of searchs find people who match on 9 loci.

So, what does it all mean? For one thing, my back-of the envelope calculations come close enough to Myers' caluculations that I don't think he's saying anything too outlandish when he says this is nothing to panic about.

On the other hand, I'm not accusing Troyer of doing anything wrong in her experiments, either. Her selection of 9 out of 13 loci and her all-against-all match in the database are an attempt to simulate a very large number of real-world searches. As long as she and everyone who uses her results understand the statistical issues, there's no problem.

The real questions require more detail than the blunt numbers that I'm using. Some of the results obtained by Troyer and others cannot be explained as statistical artifacts. Defenders fo the DNA databases have invoked some suspicious just-so explanations. For example, suggesting that a perfect 13-out-of-13 match is either a duplicate entry or a pair of twins.

While either explanation could be correct, simply asserting it doesn't make it so, at least not until the matter has been properly investigated by statisticians, DNA experts, and law enforcement.

Unless there is already a track record showing that all such matches inevitably have ordinary explanations, it's probably worth further investigation. It could be that DNA testing doesn't quite work the way we think it does, and the large law-enforcement database could be a fruitful source of scientific data worth studying.

And that's where we hit a bit of a snag. The FBI is resisting these kinds of queries in its CODIS database.

In California, Michael Chamberlain, a state Department of Justice official, persuaded judges that such a search could have "dire consequences" -- violating the privacy of convicted offenders, shutting down the database for days and risking the state's expulsion from the FBI's national DNA system. All this for a search whose results would be irrelevant and misleading to jurors, Chamberlain argued.

In Illinois,

Callaghan suggested they tell the judge that Illinois could be disconnected from the national database system, the summary shows. Callaghan then told the lab officials that "it would in fact be unlikely that IL would be disconnected," according to the summary.

In an interview, Callaghan disputed he said that.

"I didn't say it was unlikely to happen," he said. "I was asked specifically, what's the likelihood here? I said, I don't know, but it takes a lot for a state to be cut off from the national database."

And in Maryland,

After the defense filed a contempt-of-court motion, Michelle Groves, the state's DNA administrator, argued in court and in an affidavit that, based on conversations with Callaghan at the FBI, she believed the request was burdensome and possibly illegal.

According to Groves, Callaghan had told her that complying with the court order could lead Maryland to be disconnected from CODIS -- a result Groves' lawyer said would be "catastrophic."

...

After the judge, Steven Platt, rejected her arguments, Groves returned to court, saying the search was too risky. FBI officials had now warned her that it could corrupt the entire state database, something they would not help fix, she told the court.

...

The search went ahead in January 2007. The system did not go down, nor was Maryland expelled from the national database system.

Some of these excuses don't pass the smell test. The query "could corrupt the entire state database"? I wonder if the IT staff running CODIS are aware that someone in the FBI is badmouthing them this way.

I can understand that the folks running CODIS might not want it to be used in ways that slow down processing and waste valuable resources, and I can understand that only certain uses of the CODIS database are authorized by Congress, but there is something not quite right about the way the FBI is fighting these searchs.

For one thing, it just sounds funny when law enforcement agencies suddenly become concerned about the privacy rights of the people they've arrested.

Besides, the FBI keeps telling us that CODIS has extensive privacy protection. This is presumably why states have been able to find matches, but have not been able to investigate further and learn the reasons for the matches.

Also, each state has apparently only searched the DNA profiles that they themselves have submitted. Presumably the same data exists in non-database form in each state's crime labs.

Finally, the apparent fear of these kinds of database searches is inconsistent with the continued assertions that the science is sound. If the science is good, it will stand up to further investigation. That's the definition of good science.

To use the favorite formulation of every cop: If they're not doing anything wrong, they shouldn't have anything to worry about.

(Note: As is often the case in this blog, I'm trying to sing outside my range. While some of this is simple statistics, a lot of it is based on information in the original Los Angeles Times piece by Jason Felch and Maura Dolan. I also used Wikipedia for details about DNA testing and the CODIS DNA database. Wikipedia also has a more rigorous description of the Birthday Paradox.)