On coupling and the approximation of the permanent (Q1115170): Difference between revisions

An approximation algorithm for computing the permanent of dense 0-1 matrices is discussed. Possibilities and limitations are studied for the Markov chain simulation method as an approach to obtain efficient sampling schemes (and hence approximate counting algorithms), similarly as proposed by \textit{A. Broder} [How hard is it to marry at random, Proc. 18th ACM Symposium on Theory of Computing (1986))], for exponentially large populations with a nontrivial combinatorial structure. Bounding the variation distance of Markov chains is analyzed. The coupling technique and the way how it exhibits its limitations for the particular Markov chain is investigated. The Broder's Markov chain MC2 is studied especially and the construction of a coupling process C2 is attempted, C2 failure as a coupling is explained.