  Motivated by robotic surveillance applications, this paper studies the novel
problem of maximizing the return time entropy of a Markov chain, subject to a
graph topology with travel times and stationary distribution. The return time
entropy is the weighted average, over all graph nodes, of the entropy of the
first return times of the Markov chain; this objective function is a function
series that does not admit in general a closed form.
  The paper features theoretical and computational contributions. First, we
obtain a discrete-time delayed linear system for the return time probability
distribution and establish its convergence properties. We show that the
objective function is continuous over a compact set and therefore admits a
global maximum; a unique globally-optimal solution is known only for complete
graphs with unitary travel times. We then establish upper and lower bounds
between the return time entropy and the well-known entropy rate of the Markov
chain. To compute the optimal Markov chain numerically, we establish the
asymptotic equality between entropy, conditional entropy and truncated entropy,
and propose an iteration to compute the gradient of the truncated entropy.
Finally, we apply these results to the robotic surveillance problem. Our
numerical results show that, for a model of rational intruder over prototypical
graph topologies and test cases, the maximum return time entropy chain performs
better than several existing Markov chains.
