Pith. sign in

REVIEW 5 minor 12 references

A linear-time randomized algorithm multiplicatively approximates the total variation distance between two product distributions.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-30 11:29 UTC pith:XU23MHD4

load-bearing objection Clean linear-time relative-error TV for products via a filtered Monte Carlo martingale estimator; proofs check out and the lower bound matches.

arxiv 2607.27088 v1 pith:XU23MHD4 submitted 2026-07-29 cs.DS stat.ME

Linear time approximation of the TV distance between product distributions

Konrad Anand , Alistair Benford , Heng Guo This is my paper
classification cs.DS stat.ME MSC 68W2068Q2560C05
keywords total variation distanceproduct distributionsmultiplicative approximationfiltered Monte Carlolinear-time algorithmrelative variancemedian of means
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Computing the total variation distance between two product distributions is #P-hard exactly, and earlier multiplicative approximation algorithms needed super-linear time. This paper shows that a simple filtered Monte Carlo estimator already has relative variance at most 1, so a constant number of independent runs (median-of-means) yields a (1±ε)-approximation with high probability in time linear in the input size. The estimator works by sampling one mixed sequence while maintaining the posterior bias between the two hypotheses and summing the predictable one-step increases of the absolute bias; each increase can be evaluated from the current coordinate’s marginals alone. A matching Ω(qn) query lower bound confirms that the linear dependence cannot be improved in the worst case. The result therefore settles the complexity of relative-error TV approximation for the most basic non-tensorising family of distributions.

Core claim

For any two product distributions P and Q on [q]^n given by their explicit marginals, and for any ε,δ ∈ (0,1], there is a randomized algorithm that returns a nonnegative random variable Z satisfying Pr[(1-ε)d_TV(P,Q) ӗ Z ӗ (1+ε)d_TV(P,Q)] ץ 1-δ and runs in O(qn ε^{-2} log(1/δ)) arithmetic operations.

What carries the argument

The filtered Monte Carlo estimator A = ∑ C_i, where each C_i is the conditional expected increase of the absolute posterior bias |U_i| given the past coordinates. Unbiasedness follows by telescoping; the second-moment bound E[A^{2}] ӗ 2 (E A)^{2} follows because the remaining sum of increments is at most d_TV of the still-unseen product factors.

Load-bearing premise

The argument needs the coordinates to stay independent after every step, so that the conditional remaining distance is still the TV distance of a product and each one-step increment can be computed from a single pair of marginals.

What would settle it

Exhibit two product distributions on [q]^n for which the estimator A of Algorithm 1 has relative variance strictly larger than 1, or show that any multiplicative approximation algorithm must make ω(qn) marginal queries in the worst case.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • For fixed accuracy the running time is linear in the input size, matching the trivial lower bound up to constants.
  • An alternative implementation that pre-sorts likelihood ratios improves the dependence on q whenever ε^{-2} log q is small.
  • Any earlier algorithm that relied on the slower coupling estimator of Feng et al. can be replaced by this filtered estimator whenever the underlying measure is a product.
  • Exact evaluation remains #P-hard, so the linear-time multiplicative approximation is essentially optimal among polynomial algorithms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same one-step bias-increment idea may extend to other f-divergences whose increments admit closed-form conditional expectations under product structure.
  • Because each C_i depends on only one coordinate, the method is embarrassingly parallel across coordinates once the shared posterior bias is known.
  • The technique suggests that filtered Monte Carlo could yield linear-time relative-error estimators for TV distance between other highly structured families (e.g., Bayesian networks of bounded tree-width) where exact computation is hard.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper gives a randomized linear-time multiplicative approximation algorithm for the total variation distance between two explicitly given product distributions P and Q on [q]^n. The estimator samples a hidden fair hypothesis H, draws a coordinate-wise sample from the corresponding product, maintains the posterior bias martingale U_i of H, and returns the sum of the predictable increments C_i = E[|U_i| - |U_{i-1}| | F_{i-1}]. Unbiasedness and a relative-variance bound of at most 1 are proved via a general algebraic identity for the one-step increment V and the product structure of the remaining coordinates; median-of-means then yields the (1±ε)-guarantee with failure probability δ in O(qn ε^{-2} log(1/δ)) unit-cost real arithmetic operations. An alternative implementation with per-coordinate sorting improves the dependence when q is large relative to ε^{-2}, and a matching Ω(qn) query lower bound is shown in the marginal-query model.

Significance. The result improves the previous best randomized bound of Feng–Guo–Jerrum–Wang from roughly O(qn^{1.5} ε^{-2} log(1/δ)) (after Kontorovich’s tensorization) to linear in the input size, which is optimal by the paper’s own lower bound. The filtered-Monte-Carlo estimator is conceptually different from the coupling and discretization approaches used in the earlier literature and is short enough that the three core lemmas can be checked by hand. Because product TV approximation is a primitive that has already been reused for Gaussians, Ising models and mixtures, a clean linear-time primitive is likely to propagate. The authors are transparent that the algorithm was discovered with ChatGPT; the proofs themselves are conventional and self-contained.

minor comments (5)
  1. [Theorem 1 / §1] The computational model (unit-cost real arithmetic and exact uniform sampling from (0,1)) should be stated once in the introduction or in the statement of Theorem 1, rather than only in the paragraph that follows it.
  2. [Algorithm 1] In Algorithm 1 the two branches of (2) are identical after swapping the roles of (α,P) and (β,Q); a single expression using the sign of α−β would shorten the pseudocode and match the unified statement already present in Lemma 4.
  3. [§2] The phrase “it is easy to rule out otherwise” for the case d_TV(P,Q)=0 deserves a one-line justification (compare all 2qn marginals in O(qn) time).
  4. [Proof of Lemma 3] Display (5) invokes both the equality E[remaining sum | F_{i-1}] = V and the inequality V ≤ d_TV; citing Lemma 4 explicitly at that line would make the dependence clearer for a reader who has not yet absorbed the general identity.
  5. [throughout] Several words in the extracted text contain spurious spaces (“APPROXIMA TION”, “DIST ANCE”, etc.); these are presumably PDF-extraction artefacts but should be cleaned in the camera-ready version.

Circularity Check

0 steps flagged

No circularity: self-contained martingale estimator with independent algebraic proofs

full rationale

The derivation chain is first-principles and non-circular. d_TV is rewritten via the mixture representation (Eq. 1); the estimator A is the sum of predictable increments C_i of the absolute posterior-bias martingale |U_i|; Lemma 4 is pure finite-sum algebra giving the closed form and the bound V ≤ (1−|u|)d_TV; Lemma 2 telescopes E[A]=E|U_n|=d_TV; Lemma 3 uses product structure once to bound the conditional remaining sum by d_TV and obtains E[A²]≤2(E A)². No parameter is fitted to data and then re-predicted; ε,δ are input accuracy parameters. Citations to FGJW23/FLL24 are baselines being improved upon, and Gla93 supplies the named technique, not a uniqueness theorem or ansatz that forces the second-moment bound. The O(qn) runtime and the Ω(qn) query lower bound are independent combinatorial arguments. The chain does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

Pure algorithmic result. It rests on standard probability (martingales, Bayes, Chebyshev, Chernoff) and the definition of TV and product distributions. No empirical fits, no new physical entities, and no ad-hoc constants beyond the usual accuracy parameters supplied by the user.

axioms (4)
  • domain assumption Unit-cost real arithmetic and unit-cost generation of a uniform real in (0,1).
    Stated explicitly for Theorem 1; standard in this style of TCS analysis but not free in bit-complexity models.
  • standard math Chebyshev’s inequality and Chernoff bounds for median-of-means concentration.
    Invoked in the proof of Theorem 1 to turn relative variance ≤1 into the (1±ε,1-δ) guarantee.
  • standard math Total variation is non-increasing under marginalization (used as d_TV(P_{i:n},Q_{i:n})≤d_TV(P,Q)).
    Applied in display (5) of the Lemma 3 proof.
  • domain assumption Product structure: coordinates are independent under both P and Q, so posteriors update by single-coordinate likelihood ratios and remaining experiments stay product.
    Essential both for O(q)-time evaluation of each C_i and for the conditional identification with V_{P_{i:n},Q_{i:n}} in Lemma 3.

pith-pipeline@v1.2.0-daily-grok45 · 11537 in / 2659 out tokens · 60595 ms · 2026-07-30T11:29:53.184743+00:00 · methodology

0 comments
read the original abstract

We present a linear time approximation algorithm of the total variation distance between two product distributions. The main algorithm was found using ChatGPT 5.6 Sol Ultra.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 2 linked inside Pith

  1. [1]

    Approximating the total variation distance between G aussians

    Arnab Bhattacharyya, Weiming Feng, and Piyush Srivastava. Approximating the total variation distance between G aussians. In AISTATS , pages 1846--1854, 2025

    2025

  2. [2]

    Meel, Dimitrios Myrisiotis, A

    Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinodchandran. Total variation distance meets probabilistic inference. In ICML , pages 3776--3794, 2024

    2024

  3. [3]

    Meel, Dimitrios Myrisiotis, A

    Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinodchandran. Total variation distance for product distributions is \# P -complete. Inf. Process. Lett. , 189:106560, 2025

    2025

  4. [4]

    Meel, Dimitrios Myrisiotis, Aduri Pavan, and N

    Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, Aduri Pavan, and N. V. Vinodchandran. Computational explorations of total variation distance. In ICLR , 2025

    2025

  5. [5]

    On approximating the f -divergence between two I sing models

    Weiming Feng and Yucheng Fu. On approximating the f -divergence between two I sing models. In ITCS , volume 362 of LIPIcs , pages 59:1--59:23. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2026

    2026

  6. [6]

    On computing total variation distance between mixtures of product distributions

    Weiming Feng, Yucheng Fu, Minji Yang, and Anqi Zhang. On computing total variation distance between mixtures of product distributions. arXiv , abs/2605.03839, 2026

    Pith/arXiv arXiv 2026

  7. [7]

    A simple polynomial-time approximation algorithm for the total variation distance between two product distributions

    Weiming Feng, Heng Guo, Mark Jerrum, and Jiaheng Wang. A simple polynomial-time approximation algorithm for the total variation distance between two product distributions. TheoretiCS , 2:Paper No. 7, 2023

    2023

  8. [8]

    On deterministically approximating total variation distance

    Weiming Feng, Liqiang Liu, and Tianren Liu. On deterministically approximating total variation distance. In SODA , pages 1766--1791, 2024

    2024

  9. [9]

    Approximating the total variation distance between spin systems

    Weiming Feng, Hongyang Liu, and Minji Yang. Approximating the total variation distance between spin systems. In COLT , pages 1974--2025, 2025

    1974

  10. [10]

    Filtered M onte C arlo

    Paul Glasserman. Filtered M onte C arlo. Math. Oper. Res. , 18(3):610--634, 1993

    1993

  11. [11]

    On the tensorization of the variational distance

    Aryeh Kontorovich. On the tensorization of the variational distance. Electron. Commun. Probab. , 30:Paper No. 32, 10, 2025

    2025

  12. [12]

    Total variation distance estimation in autoregressive models

    Eric Price, Kevin Tian, Zhiyang Xun, and Yusong Zhu. Total variation distance estimation in autoregressive models. arXiv , abs/2607.19510, 2026

    Pith/arXiv arXiv 2026