paper<\/a>\u00a0in PNAS from a few years back that I missed, “Strong profiling is not mathematically optimal for discovering rare malfeasors” by William H. Press.<\/p>\nSuppose you have a large population of people and a single bad guy who you want to catch. \u00a0You could look through the entire population to \u00a0find the bad guy, or you could set up checkpoints (err I mean airline security screening areas) to look for people, sampling only some small fraction of the population that goes through the checkpoint. \u00a0 Now, if you don’t know anything about the population you’re sampling, you might as well just sample them randomly until you find your baddie, since you don’t have any other information that could help you.<\/p>\n
But suppose that you are able to come up with some prior probabilities for different people to be the bad guy. \u00a0I.e. you’ve developed a model for what makes someone more likely to be a bad guy, and further assume that this model is really pretty accurate. \u00a0To each person you can assign a probability $p_i$ that the person is indeed the bad guy. \u00a0Now you could continue to sample uniformly, but you have this great model that you want to use to help catch the bad guy. \u00a0What do you do?<\/p>\n
It turns out that the wrong<\/strong> thing to do is to sample in proportion to the probability $p_i$. \u00a0To figure out the correct strategy, suppose that you sample from the population with probability $q_i$. \u00a0Then if $k$ is your man, the probability that you get him in one sample is $q_k$. \u00a0Or, another way to say it is that the mean number of screenings you’ll need to find the baddie is $1\/q_k$. \u00a0Assuming your model is correct, the mean number of people you will have to sample is $sum_i p_i\/q_i$. \u00a0So now to calculate the optimum we need to minimize this expression for $q_i$ subject to the constraint that $sum_i q_i =1$.<\/p>\nTo calculate this optimum, you use a Lagrange multiplier<\/p>\n
$${partial over partial q_j} left[ sum_i {p_i over q_i} + lambda (sum_i q_i -1)right]=0$$<\/p>\n
or<\/p>\n
$$ – {p_j over q_j^2} + lambda = 0$$<\/p>\n
Which, in order to satisfy our contraints (and also positive probabilities) gives us the answer for the optimum of<\/p>\n
$$ q_j = { sqrt{p_j} \u00a0over sum_i sqrt{p_i}}$$<\/p>\n
Or, in other words, you should sample proportional to the square root of the probabilities. \u00a0Pretty cool, a nice easy, yet surprising answer.<\/p>\n
Even more awesome is that we got some square roots of probabilities in there. \u00a0Quantum probability amplitudes are, of course, like square roots of probabilities. \u00a0Now if only we could massage this into insight into quantum theory. \u00a0Do it. \u00a0Or the terrorist win.<\/p>\n","protected":false},"excerpt":{"rendered":"
[latexpage] An interesting\u00a0paper\u00a0in PNAS from a few years back that I missed, “Strong profiling is not mathematically optimal for discovering rare malfeasors” by William H. Press. Suppose you have a large population of people and a single bad guy who you want to catch. \u00a0You could look through the entire population to \u00a0find the bad … <\/p>\n
Continue reading “To Catch Terrorists, Think Quantum Mechanically?”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[20,26],"tags":[],"class_list":["post-443","post","type-post","status-publish","format-standard","hentry","category-quantum","category-statistics"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/posts\/443","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/comments?post=443"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/posts\/443\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/media?parent=443"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/categories?post=443"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/caelifera\/wp-json\/wp\/v2\/tags?post=443"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}