gen_witt wroteon July 28th, 2008 at 10:25 pm |

## Practice Safe Sex

Back when I was in the 7th grade, in health class, we did an "experiment". Each student was given a vile with some sort of fluid. You were then to find 6 other people, write each others names on your card, and then exchange fluids with that person, you give them half of yours and take half of theirs. After all was said and done you added some other fluid to your fluid to detect the presents of some contaminate. Two students started with the contaminant and at the end inevitably almost everyone is infected. A mighty lesson in epidemiology. For those wanting to play at home, I suspect the contaminate agent was potato starch, and the test iodine.

Given that I had more brains then sense I took home all of the available data, and tried to reverse engineer who the two originally infected students were. I failed miserably. Man I want to invent a machine that can punch my former self in the face.

Now for some reason I thought about this in the shower this morning. And thought, hmm, I bet you could do some sort of topological sort on the graph of pairings and get all sorts of information. It works surprisingly well. I could run a constraint solver as this point, but in the vast majority of cases it wouldn't produce any more information. Here is a trial with 20 people, 1 starting with the infection, and 4 interactions. On the left is the initial graph built out of the available data (final status and a chronological list of partners), on the right is the graph with as much data as can be extrapolated. It's pretty clear that in this case if you knew there was only 1 infected person at the start that it would have to be either "0" or "19".

As an aside, with 34 students, 6 interactions, and 2 starting with the infection, there is a > 80% chance of everyone ending up infected; this makes it a very compelling argument to the dumb (aka children). When everyone is infected at the end, there is very little recoverable information.

Given that I had more brains then sense I took home all of the available data, and tried to reverse engineer who the two originally infected students were. I failed miserably. Man I want to invent a machine that can punch my former self in the face.

Now for some reason I thought about this in the shower this morning. And thought, hmm, I bet you could do some sort of topological sort on the graph of pairings and get all sorts of information. It works surprisingly well. I could run a constraint solver as this point, but in the vast majority of cases it wouldn't produce any more information. Here is a trial with 20 people, 1 starting with the infection, and 4 interactions. On the left is the initial graph built out of the available data (final status and a chronological list of partners), on the right is the graph with as much data as can be extrapolated. It's pretty clear that in this case if you knew there was only 1 infected person at the start that it would have to be either "0" or "19".

As an aside, with 34 students, 6 interactions, and 2 starting with the infection, there is a > 80% chance of everyone ending up infected; this makes it a very compelling argument to the dumb (aka children). When everyone is infected at the end, there is very little recoverable information.