Practical Issue of Approximate Sampling Usually an approx.sampler runs some Markov chain ·Easy to show mixing Connected,aperiodic,stationary/reversible distribution Convergence theorem of Markov chains Hard to prove bounds on mixing time Path coupling,canonical path,spectral independence,information percolation,Cheeger's constant,(modified)log-Sobolev inequality,.. How to stop the chain when bounds on mixing time is bad/unknown?
Practical Issue of Approximate Sampling • Usually an approx. sampler runs some Markov chain • Easy to show mixing • Connected, aperiodic, stationary/reversible distribution • Convergence theorem of Markov chains • Hard to prove bounds on mixing time • Path coupling, canonical path, spectral independence, information percolation, Cheeger’s constant, (modified) log-Sobolev inequality, … • How to stop the chain when bounds on mixing time is bad/unknown?
Practical Advantage of Perfect Sampling Easy to design given a Markov chain based approx.sampler Coupling from the past [PW'96] Easy to show it halts almost surely When it stops,the output distribution is always correct Hard to implement efficiently Bounding chain [Hub'98,HN'99] Hard to prove bounds on stopping time Martingale,information percolation
Practical Advantage of Perfect Sampling • Easy to design given a Markov chain based approx. sampler • Coupling from the past [PW’96] • Easy to show it halts almost surely • When it stops, the output distribution is always correct • Hard to implement efficiently • Bounding chain [Hub’98, HN’99] • Hard to prove bounds on stopping time • Martingale, information percolation, …
Proof Overview Reduce general cases to binary domains State tensorization,a generalization of state compression in [FHY'21] Develop an algorithm for binary domains(arbitrary distribution) Coupling from the past and bounding chain Information percolation
Proof Overview • Reduce general cases to binary domains • State tensorization, a generalization of state compression in [FHY’21] • Develop an algorithm for binary domains (arbitrary distribution) • Coupling from the past and bounding chain • Information percolation