Markov Chains Approximate Message Passing

Markov chain Monte Carlo algorithms have long been observed to obtain near-optimal performance in various Bayesian inference settings. However, developing a supporting theory that makes these studies rigorous has proved challenging. In this paper, we study the classical spiked Wigner inference problem, where one aims to recover a planted Boolean spike from a noisy matrix measurement. We relate the recovery performance of Glauber dynamics on the annealed posterior to the performance of Approximate Message Passing (AMP), which is known to achieve Bayes-optimal performance. Our main results rely on the analysis of an auxiliary Markov chain called restricted Gaussian dynamics (RGD). Concretely, we establish the following three results. First, RGD can be reduced to an effective one-dimensional recursion which mirrors the evolution of the AMP iterates. Second, from a warm start, RGD rapidly converges to a fixed point in correlation space, which recovers Bayes-optimal performance when run on the posterior. Third, conditioned on widely believed mixing results for the SK model, we recover the phase transition for non-trivial inference. The full version of this paper can be found on arXiv (arXiv ID: 2512.02384).