True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration

We study true self-avoiding walk (TSAW) as a mechanism for improving empirical integral estimation via Markov chain Monte Carlo (MCMC). We consider finite-state adaptive sampling dynamics associated with an irreducible Markov kernel P on a finite set, with stationary distribution π, in which the transition probabilities are penalized according to empirical overuse. Our main result is that the empirical occupation counts Lt(i) and transition counts Nt(i,j) of the resulting TSAW-based walk satisfy [ Lt(i)-tπi = O(√log t) quadandquad Nt(i,j)-tπiPij=O(√log t) qquadalmost surely ] for every state i and every edge (i,j) with Pij>0. Consequently, for every bounded function f:V→mathbb R, the error of our integral estimator converges as [ left|frac1tsums=0t-1 f(Xs)-sumi∈ Vπi f(i)right| = Oleft(frac√log ttright) qquadalmost surely. ] These results show that, in contrast with the usual t-1/2 error scaling for empirical averages under standard random-walk-based methods, TSAW-based estimator yields empirical integral errors of order O(√log t/t) almost surely, thereby achieving a substantially sharper dependence on the sample size t.