6 comments

[ 0.26 ms ] story [ 17.4 ms ] thread
A O(log(n)) approach to syphilis testing by using the physical equivalent of search trees. Very interesting.

It only works well if a small percentage of the population is infected.

Really enjoyed this. Great applications to both cost reduction and privacy. I've seen pooling strategies like this for monitoring cars.
Why test everyone if the group is tainted? A binary search (subdividing into two groups) would seem more efficient. Perhaps they had to call everyone back in for a second sample and thought that three times would seem silly.
fegu,

That was precisely the reason. The paper mentions that they only collected enough for the group-level and subsequent exhaustive search.

The largest possible n is the total number of population, and if the expected number of infected soldiers is == 0 the largest n is also the optimal one. Since we know the percentage of infections is a lot more than 0, the largest n isn't optimal. Otherwise if 1 person is infected, you'd be back to square one and your initial test of a cocktail of your entire populations' samples was fruitless.

The second largest n one could choose is half the population by dividing into two groups. It's the most optimal n if the expected number of infected soldiers is around 1. Since we know the percentage of infections is a lot more than 1, the largest n isn't optimal. Otherwise, if 1 person in each group is infected, you'd be back to square one and your initial test of two cocktails of each half of the populations' samples was fruitless.

...etc...

At p = 0.01, the optimal n is, according to this article, around 20-25.

(comment deleted)