  We consider the problem of detecting a random walk on a graph, based on
observations of the graph nodes. When visited by the walk, each node of the
graph observes a signal of elevated mean, which we assume can be different
across different nodes. Outside of the path of the walk, and also in its
absence, nodes measure only noise. Assuming the Neyman-Pearson setting, our
goal then is to characterize detection performance by computing the error
exponent for the probability of a miss, under a constraint on the probability
of false alarm. Since exact computation of the error exponent is known to be
difficult, equivalent to computation of the Lyapunov exponent, we approximate
its value by finding a tractable lower bound. The bound reveals an interesting
detectability condition: the walk is detectable whenever the entropy of the
walk is smaller than one half of the expected signal-to-noise ratio. We derive
the bound by extending the notion of Markov types to Gauss-Markov types. These
are sequences of state-observation pairs with a given number of node-to-node
transition counts and the same average signal values across nodes, computed
from the measurements made during the times the random walk was visiting each
node's respective location. The lower bound has an intuitive interpretation:
among all Gauss-Markov types that are asymptotically feasible in the absence of
the walk, the bound finds the most typical one under the presence of the walk.
Finally, we show by a sequence of judicious problem reformulations that
computing the bound reduces to solving a convex optimization problem, which is
a result in its own right.
