23 December 2007

Tracking an intruder

From Yuliy Baryshnikov: an animation described as follows: "In the 40-by-40 array of sensors, a running intruder is represented as a black dot. Can you spot her? The catch: the sensors are prone to spontaneous signals ("false positives"). These signals are rare (just 2.5% probability), but what a mess they make!"

But of course, if you stare long enough you can see the intruder. The trick, is that the intruder moves slowly, say one grid square per second. If you overlay the grids at time n and n+1 on top of each other, there will be about eight pairs of (kingwise) adjacent squares such that the first square is a false positive at time n and the second square is a false positive at time n+1. (There are roughly 402 × 8 ordered pairs of kingwise adjacent squares.) If we consider it at three consecutive times our expected number of false positives is the 402 × 82 triples of kingwise adjacent squares, times the 40-3 probability that the three squares of such a triple are occupied at times n, n+1, n+2, for an expected 1.6 false positives. And so on -- there are one-fifth as many false positives for each extra consecutive step we look at.

If false positives occurred one-eighth of the time, though, then we'd have no hope; the number of "false positives" when looking at some window of length k would be constant, instead of decreasing exponentially with k. In general, you'd expect that if the intruder has r choices for her position of each step, then as the probability of false positives approaches 1/r the intruder becomes impossible to track.

A quick skim of titles of Baryshnikov's papers doesn't tell me if this is an illustration of something from his research. I'm curious, so I've sent him an e-mail to ask.

1 comment:

Ori Gurel-Gurevich said...

This is basically a percolation problem. Your expectation analysis shows that 1/r is a lower bound for the critical probability, i.e. the probability which separates the cases in which we can find the intruder from those in which we cannot.
However, a more careful analysis shows that the critical probability is strictly higher then 1/r. This is because the different possible paths for the intruder overlap. This means that the expected number of false positive paths will differ significantly from the probability of existence of a false positive.