April 28, 2015

In our paper, we study the problem of detecting a random walk on a graph from a sequence of noisy measurements at every node. The performance metric we consider resembles the free energy of a spin glass in statistical physics, and we borrow techniques from that field to develop a lower bound. Our fully rigorous analysis uses large deviations theory to show that the lower bound exhibits a phase transition: strong performance is only guaranteed when the signal-to-noise ratio exceeds twice the entropy rate of the random walk. Monte Carlo simulations show that the lower bound fully captures the behavior of the true exponent.