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

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

Problem Statement
The paper addresses the finite-time quality of empirical integral estimation in Markov Chain Monte Carlo (MCMC) methods. Given a finite state space $V$, an irreducible Markov kernel $P$, and a stationary distribution $\pi$, the goal is to estimate the stationary integral $\pi(f) = \sum_{x \in V} \pi(x)f(x)$ using the empirical average of a trajectory $(X_t)_{t \geq 0}$.

Standard random-walk-based MCMC methods suffer from "local oversampling," where the trajectory revisits recently explored regions, leading to slow correction of occupation imbalances. Consequently, the error of the empirical average typically scales as $O(t^{-1/2})$ almost surely. While recent work on self-repellent random walks (SRRW) has improved the asymptotic variance constant, the error scaling remains at the standard $O(t^{-1/2})$ level. The authors seek a mechanism to achieve a sharper dependence on the sample size $t$ for the empirical integral error.

Methodology
The authors propose a True Self-Avoiding Walk (TSAW) dynamics where transition probabilities are penalized based on empirical overuse. The methodology proceeds in three distinct stages:

1. Warm-up on the Star Graph: The authors first analyze a simplified model on a star graph (a hub connected to $n$ leaves). By employing an exponential-race embedding, they map the discrete TSAW dynamics to a continuous-time birth process. This allows for a detailed analysis of the cover time, demonstrating that exponential self-avoidance reduces the exploration scale from the classical coupon-collector order $O(n \log n)$ to $O(n \log \log n)$.

2. Finite-Alphabet Self-Balancing Model: The authors construct a local sampling rule for a finite alphabet $[d]$ with a target distribution $p$. The transition probability to state $i$ at time $t$ is defined via a softmax function penalized by the "excess" or "deficit" of visits relative to the target:
   $$P(X_{t+1} = i \mid \mathcal{F}_t) \propto \exp\left(-\lambda \Delta_i(t)\right),$$
   where $\Delta_i(t) = L_t(i) - t p_i$ is the deviation from the target count.
   Using a Lyapunov function $V(t) = e^{\alpha M(t)}$ (where $M(t)$ is the maximum excess), they prove an exponential drift inequality. This establishes that the maximal excess remains bounded within $O(\sqrt{\log t})$ almost surely, with uniform exponential moment bounds.

3. Lifting to General Finite-State Markov Kernels: The local mechanism is extended to a general irreducible Markov kernel $P$ on a finite set $V$. The transition rule penalizes directed edges $(i, j)$ based on the discrepancy between the empirical transition count $N_t(i, j)$ and the expected flow $L_t(i)P_{ij}$:
   $$P(X_{t+1} = j \mid X_t = i, \mathcal{F}_t) \propto P_{ij} \exp\left(-\lambda \epsilon_t(i, j)\right),$$
   where $\epsilon_t(i, j) = N_t(i, j) - L_t(i)P_{ij}$.
   The analysis involves:

   • Row-wise Reduction: Isolating the process at departure times from each state $i$, reducing the global dynamics to a collection of local finite-alphabet processes.
   • Global Discrepancy Bounds: Applying the local exponential moment bounds to derive a global tail bound for the maximum edge discrepancy $M(t)$.
   • Poisson Equation: Utilizing the group inverse of the operator $(I - P^\top)$ to relate the edge discrepancy $\epsilon_t$ to the vertex occupation discrepancy $L_t - t\pi$. This converts the edge bounds into bounds on the occupation counts.

Key Contributions and Results
The paper establishes the following almost-sure bounds for the TSAW-based walk:

• Occupation and Transition Counts: For every state $i$ and edge $(i, j)$ with $P_{ij} > 0$, the discrepancies satisfy:
  $$L_t(i) - t\pi_i = O(\sqrt{\log t})$$
  $$N_t(i, j) - t\pi_i P_{ij} = O(\sqrt{\log t})$$
  almost surely.

• Integral Estimation Error: For every bounded function $f: V \to \mathbb{R}$, the error of the integral estimator converges as:
  $$\left| \frac{1}{t} \sum_{s=0}^{t-1} f(X_s) - \sum_{i \in V} \pi_i f(i) \right| = O\left(\frac{\sqrt{\log t}}{t}\right)$$
  almost surely.

• Recurrence: The authors prove that under these dynamics, every state and every directed edge with positive transition probability is visited infinitely often almost surely.

Significance and Claims
The paper claims that the TSAW-based estimator achieves a substantially sharper dependence on the sample size $t$ compared to standard random-walk-based methods and existing self-repellent walk estimators. Specifically:

• Standard methods and SRRW (as analyzed in Doshi, Hu, and Eun [1]) exhibit error scaling of $O(t^{-1/2})$.
• The proposed TSAW estimator achieves $O(\sqrt{\log t}/t)$, representing an improvement factor of $O(\sqrt{t/\log t})$.

The authors position their work at the intersection of self-avoiding random walks, nonlinear Markov chains, and MCMC variance reduction. They emphasize that their primary novelty lies in providing explicit finite-time pathwise control of empirical occupation and transition errors, rather than just asymptotic variance reduction. The paper concludes that this construction offers a rigorous mechanism for improving empirical estimation and provides a general design paradigm for building non-Markovian random walks from self-avoiding local balancing rules.