IBM Research | Ponder This | June 2008 challenges

Ponder This

June 2008

<<May June July>>

Ponder This Challenge:

This month's problems concern DNA testing. DNA tests can exclude people as the source of a DNA sample. Assume that the tests will never exclude the actual source but sometimes will fail to exclude someone who is not the actual source but who by chance happens to match the actual source at the DNA locations being tested.

1. Suppose before DNA testing we estimate X has p chance of being the actual source. Suppose there is a random match probability of 1/n. If testing does not exclude X what is our new estimate of the probability that X is the source?

2. Suppose we have a database of DNA data from k people. Suppose before comparing with the DNA sample we estimate that there is a chance p that the database contains the actual source and further that every person in the database is equally likely to be the actual source. Assume as above the random match probability for someone who is not the actual source is 1/n and that this probability is independent for multiple people who are not the actual source. Suppose we find exactly one person, X, in the database whose DNA matches the sample. What is our new estimate of the probability that the database contains the actual source (and therefore that the actual source is X).

3. In an actual case k was 338000 and the random match probability was said to be 1/1100000. Suppose we further assume (before checking) that there is a 20% chance that the actual donor is in the database and that everyone in the database is equally likely to be the actual donor. Suppose (as in the actual case) exactly one person, X, matching the sample is found in the database. Subject to the above assumptions, what is the probability that X is the actual donor? Give the probability rounded to four decimal places.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Challenge: 06/02/2008 @ 09:00 AM EST
Solution: 07/01/2008 @ 09:00 AM EST
List Updated: 07/03/2008 @ 10:00 AM EST

Chris Hills (06.02.2008 @01:55:32 PM EDT)
Joseph DeVincentis (06.02.2008 @02:42:15 PM EDT)
Frank Yang (06.02.2008 @02:46:09 PM EDT)
John Hart (06.02.2008 @03:45:43 PM EDT)
Arthur Breitman (06.02.2008 @06:21:02 PM EDT)
Mark Perkins (06.02.2008 @06:48:20 PM EDT)
Henry Bottomley (06.02.2008 @08:00:09 PM EDT)
John T. Robinson (06.03.2008 @01:34:25 AM EDT)
Willem H. de Boer (06.03.2008 @06:06:15 AM EDT)
Movin Jain & Siddharth Agarwal (06.03.2008 @09:10:14 AM EDT)
Dan Dima (06.03.2008 @09:21:27 AM EDT)
Jeff Steele (06.03.2008 @10:41:15 AM EDT)
Michael Quist (06.03.2008 @11:34:58 AM EDT)
Dion Harmon (06.03.2008 @12:45:37 PM EDT)
V Balakrishnan (06.03.2008 @05:50:56 PM EDT)
Wolf Mosle (06.03.2008 @06:15:39 PM EDT)
Krunoslav Kovac (06.03.2008 @07:17:46 PM EDT)
Joshua Green (06.04.2008 @01:15:55 AM EDT)
James Dow Allen (06.04.2008 @03:29:46 AM EDT)
Joseph C. Bonneau (06.04.2008 @04:31:53 AM EDT)
Ryan Milligan (06.04.2008 @11:51:58 AM EDT)
Sylvain Becker (06.04.2008 @01:50:03 PM EDT)
Michael Schaaf (06.04.2008 @ 02:41:05 PM EDT)
Ariel Flat (06.04.2008 @03:23:58 PM EDT)
Gary M Gerkin (06.05.2008 @05:53:05 AM EDT)
Jesse Kolman (06.05.2008 @06:19:09 AM EDT)
Derek Jennings (06.05.2008 @02:39:11 PM EDT)
Xiaoyang Guan (06.05.2008 @07:16:31 PM EDT)
Jimmy He (06.05.2008 @10:27:16 PM EDT)
Zhou Guang (06.06.2008 @12:18:48 AM EDT)
Hongcheng Zhu (06.06.2008 @05:18:07 AM EDT)
Samantha Casanova (06.06.2008 @03:59:06 PM EDT)
J K Viswanath Raju (06.06.2008 @04:03:28 PM EDT)
Mark Pilloff (06.06.2008 @08:16:33 PM EDT)
Dan Colestock (06.07.2008 @12:58:13 AM EDT)
Will Hasenplaugh (06.08.2008 @01:56:23 AM EDT)
Mithil Ramteke (06.08.2008 @02:18:59 AM EDT)
Vicent Pla (06.08.2008 @05:45:14 PM EDT)
Daniel Linhart (06.09.2008 @06:50:37 PM EDT)
Ashutosh Mahajan (06.11.2008 @11:11:24 AM EDT)
Donald T Dodson (06.11.2008 @11:44:09 AM EDT)
Mark Gordon (06.11.2008 @07:06:20 PM EDT)
Pascal Strubi (06.12.2008 @03:18:27 AM EDT)
Richard Bjorklund (06.12.2008 @06:41:16 PM EDT)
Nyles Heise (06.13.2008 @02:25:16 AM EDT)
Joachim Ripken (06.16.2008 @07:47:20 PM EDT)
Frank E. Mullin (06.17.2008 @11:10:22 AM EDT)
Fred Batty (06.17.2008 @12:02:57 AM EDT)
Greg Janee (06.17.2008 @11:54:57 PM EDT)
Gale Greenlee (06.17.2008 @12:25:19 PM EDT)
Ian Glover (06.20.2008 @06:16:37 AM EDT)
Amos Guler (06.21.2008 @03:36:58 PM EDT)
John Douma (06.22.2008 @02:20:54 PM EDT)
Ben Tarlow (06.23.2008 @06:55:14 AM EDT)
Albert Stadler (06.23.2008 @02:31:06 PM EDT)
Graham Hesketh (06.25.2008 @06:39:55 AM EDT)
Jiri Navratil (06.26.2008 @04:40:59 PM EDT)
Sha Lin Shan (06.28.2008 @05:14:45 AM EDT)
Boris Nikolaus (06.28.2008 @04:25:36 PM EDT)
Ranchu Mathew (06.29.2008 @04:47:54 AM EDT)
Andrea Andenna (06.29.2008 @05:14:51 PM EDT)
John G. Fletcher (06.30.2008 @02:25:25 PM EDT)
Phil Muhm (07.01.2008 @06:39:32 PM EDT)
Ramakrishna Katragadda (07.02.2008 @09:52:39 AM EDT)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.