Approximating the TV Distance Between Two Product Distributions

on YouTube ↗44m

" summary

Proves FPRAS and FPTAS for total variation between general product distributions, using a greedy coupling and a ratio random variable estimator: sample from a conditioned product coupling (distribution π), compute f(σ) = Pr_opt/Pr_greedy and average to get TV; runtime for the randomized estimator is polynomial (≈Õ(n^2/ε^2)). Gives a deterministic FPTAS by iteratively sparsifying ratio distributions (merge intervals, bound support) with runtime roughly polynomial in input size and in log(1/TV). Methods extend to n-step Markov chains and succeed with provable guarantees.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 1:04Total variation distance
3. 3:37Challenges with product distributions
4. 6:51Previous work and open problems
5. 9:50Main results
6. 10:53Randomized algorithm overview
7. 14:25Coupling distributions
8. 17:39Greedy coupling
9. 21:19Monte Carlo ratio estimation
10. 27:55Deterministic algorithm framework
11. 33:28Sparsification
12. 38:33Results and open questions
13. 40:20Q&A