Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods), are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample from the desired distribution. The quality of the sample improves as a function of the number of steps. We will use such a thing for generating a random perfect matching.
Reference :
Approximating the permanent M Jerrum, A Sinclair - SIAM journal on computing, 1989 - link.aip.org
How hard is it to marry at random? AZ Broder - Proceedings of the eighteenth annual ACM symposium …, 1986 - portal.acm.org
