DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.51

On Computing Total Variation Distance Between Mixtures of Product Distributions

Authors: Weiming Feng, Yucheng Fu, Minji Yang, and Anqi Zhang

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

We study the problem of approximating the total variation distance between two mixtures of product distributions over an n-dimensional discrete domain. Given two mixtures ℙ and ℚ with k₁ and k₂ product distributions over [q]ⁿ, respectively, we give a randomized algorithm that approximates d_TV(ℙ,ℚ) within a multiplicative error of (1±ε) in time poly((nq)^{k₁+k₂}, 1/ε). We also study the special case of mixtures of Boolean subcubes over {0,1}ⁿ. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time poly(n, 2^O(k₁+k₂)), and show that exact computation is #𝖯-hard when k₁+k₂ = Θ(n).

Cite as

Weiming Feng, Yucheng Fu, Minji Yang, and Anqi Zhang. On Computing Total Variation Distance Between Mixtures of Product Distributions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.APPROX/RANDOM.2026.51,
  author =	{Feng, Weiming and Fu, Yucheng and Yang, Minji and Zhang, Anqi},
  title =	{{On Computing Total Variation Distance Between Mixtures of Product Distributions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.51},
  URN =		{urn:nbn:de:0030-drops-277689},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.51},
  annote =	{Keywords: Randomized algorithm, Total variation distance}
}

Search Results

Documents authored by Zhang, Anqi

On Computing Total Variation Distance Between Mixtures of Product Distributions

Abstract

Cite as

Thanks for your feedback!

Could not send message