English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider random walks on discrete state spaces, such as general undirectedgraphs, where the random walkers are designed to approximate a target quantityover the network topology via sampling and neighborhood exploration in the formof Markov chain Monte Carlo (MCMC) procedures. Given any Markov chaincorresponding to a target probability distribution, we design a self-repellentrandom walk (SRRW) which is less likely to transition to nodes that were highlyvisited in the past, and more likely to transition to seldom visited nodes. Fora class of SRRWs parameterized by a positive real {\alpha}, we prove that theempirical distribution of the process converges almost surely to the the target(stationary) distribution of the underlying Markov chain kernel. We thenprovide a central limit theorem and derive the exact form of the arisingasymptotic co-variance matrix, which allows us to show that the SRRW with astronger repellence (larger {\alpha}) always achieves a smaller asymptoticcovariance, in the sense of Loewner ordering of co-variance matrices.Especially for SRRW-driven MCMC algorithms, we show that the decrease in theasymptotic sampling variance is of the order O(1/{\alpha}), eventually goingdown to zero. Finally, we provide numerical simulations complimentary to ourtheoretical results, also empirically testing a version of SRRW with {\alpha}increasing in time to combine the benefits of smaller asymptotic variance dueto large {\alpha}, with empirically observed faster mixing properties of SRRWwith smaller {\alpha}.

Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains