OAI/Combinatorics/ContingencyTables/Main.lean

Sampling and counting contingency tables

Almost-uniform sampling has polynomial cost on every execution, while exact uniform sampling has polynomial expected bit cost. Cell-bounded counting admits a fully polynomial randomized approximation scheme, including structural zeros and infeasible inputs. The finite-box Prékopa–Leindler inequality, finite Cheeger inequality and shortest augmenting path bound supply the analytic and feasibility estimates.