  We consider random walks on discrete state spaces, such as general undirected
graphs, where the random walkers are designed to approximate a target quantity
over the network topology via sampling and neighborhood exploration in the form
of Markov chain Monte Carlo (MCMC) procedures. Given any Markov chain
corresponding to a target probability distribution, we design a self-repellent
random walk (SRRW) which is less likely to transition to nodes that were highly
visited in the past, and more likely to transition to seldom visited nodes. For
a class of SRRWs parameterized by a positive real {\alpha}, we prove that the
empirical distribution of the process converges almost surely to the the target
(stationary) distribution of the underlying Markov chain kernel. We then
provide a central limit theorem and derive the exact form of the arising
asymptotic co-variance matrix, which allows us to show that the SRRW with a
stronger repellence (larger {\alpha}) always achieves a smaller asymptotic
covariance, in the sense of Loewner ordering of co-variance matrices.
Especially for SRRW-driven MCMC algorithms, we show that the decrease in the
asymptotic sampling variance is of the order O(1/{\alpha}), eventually going
down to zero. Finally, we provide numerical simulations complimentary to our
theoretical results, also empirically testing a version of SRRW with {\alpha}
increasing in time to combine the benefits of smaller asymptotic variance due
to large {\alpha}, with empirically observed faster mixing properties of SRRW
with smaller {\alpha}.
