@conference {235161,
	title = {Optimal hypothesis testing with combinatorial structure: Detecting random walks on graphs},
	booktitle = {Proc. of Asilomar Conference on Signals, Systems and Computers},
	year = {2014},
	month = {Nov.},
	address = {Pacific Grove, CA},
	abstract = {Suppose we have a time series of observations for each node\&nbsp;in a network, and we wish to detect the presence of a particle\&nbsp;undergoing a random walk on the network. If there is no such\&nbsp;particle, then we observe only zero-mean Gaussian noise. If\&nbsp;present, however, the location of the particle has an elevated\&nbsp;mean. How well can we detect the particle at low signal-to-noise\&nbsp;ratios? This is a special case of the problem of detecting\&nbsp;hidden Markov processes (HMPs).
The performance metric we analyze is the error exponent of\&nbsp;the optimal detector, which measures the exponential rate of decay\&nbsp;in the miss probability if the false alarm probability is held\&nbsp;fixed as the observation time increases. This problem exhibits\&nbsp;deep connections to a problem in statistical physics: computing\&nbsp;the free energy density of a spin glass.\&nbsp;
We develop a generalized version of the random energy\&nbsp;model (REM) spin glass, whose free energy density provides\&nbsp;a lower bound for our error exponent, and compute the bound\&nbsp;using large deviations techniques. The bound closely matches\&nbsp;empirical results in numerical experiments, and suggests a\&nbsp;phase transition phenomenon: below a threshold SNR, the error\&nbsp;exponent is nearly constant and near zero, indicating poor\&nbsp;performance; above the threshold, there is rapid improvement\&nbsp;in performance as the SNR increases. The location of the phase\&nbsp;transition depends on the entropy rate of the Markov process.},
	author = {Ameya Agaskar and Yue M. Lu}
}
