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?