An FPRAS for Cell-Bounded Contingency Tables
There exists a randomized algorithm (FPRAS) that, given binary-encoded margins , with equal total, cell bounds (allowing and with both part of the input), and rational , outputs a nonnegative rational satisfying , outputs on every execution if is empty, uses only independent unbiased random bits, requires no counting or sampling oracle, and has total bit operations bounded on every execution by a fixed polynomial in , where is the total binary input length.
Every component of Theorem 1.1—feasibility testing, contamination control, weight evaluation, Markov chain mixing, fair-bit coupling, unconditional bit-length bounds, and median amplification—is rigorously proved in Sections 2–7.
“Theorem 1.1. There is one randomized algorithm with the following guarantee. Given (r, c, b) as above and rational ε, δ ∈ (0, 1), it outputs a nonnegative rational Zb such that P ((1 − ε)Z(r, c, b) ≤ Zb ≤ (1 + ε)Z(r, c, b)) ≥ 1 − δ. If Ω(r, c, b) is empty, the output is zero on every execution. The algorithm uses independent unbiased bits, and one fixed polynomial in L, ε−1, and log(δ−1) bounds its total bit operations on every execution, where L is the total binary input length, including the accuracy parameters. No counting or sampling oracle is required.” · Show in paper