On Computing Total Variation Distance Between Mixtures of Product Distributions
Weiming Feng and Yucheng Fu and Minji Yang and Anqi Zhang · 2026
Read On Computing Total Variation Distance Between Mixtures of Product Distributions by Weiming Feng and Yucheng Fu and Minji Yang and Anqi Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03839.txt.
Introduction
Weiming Feng, Yucheng Fu, Minji Yang, and Anqi Zhang study how hard it is to compute the total variation distance. The distance is between two mixtures of product distributions over a discrete domain with n coordinates. It measures how far apart two distributions are. Mixtures of product distributions are a basic model in statistics and machine learning. Each mixture combines a set of component distributions.
The authors give a randomized algorithm that approximates the distance within a small multiplicative error, running in time polynomial in a term set by the total number of components. For the special case of mixtures of Boolean subcubes, they give a deterministic exact algorithm. They also show exact computation becomes counting-hard when the number of components grows linearly with dimension.
Catalog record
| CREATOR | Weiming Feng and Yucheng Fu and Minji Yang and Anqi Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 109 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.03839
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Computing Total Variation Distance Between Mixtures of Product Distributions Weiming Feng and Yucheng Fu and Minji Yang and Anqi Zhang Abstract We study the problem of approximating the total variation distance between two mixtures of product distributions over an n n -dimensional discrete domain. Given two mixtures ℙ \mathbb{P} and ℚ \mathbb{Q} with k 1 k_{1} and k 2 k_{2} product distributions over [ q ] n [q]^{n} , respectively, we give a randomized algorithm that approximates d TV ( ℙ , ℚ ) d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right) within a multiplicative error of ( 1 ± ε ) (1\pm\varepsilon) in time poly ( ( n q ) k 1 + k 2 , 1 / ε ) \mathrm{poly}((nq)^{k_{1}+k_{2}},1/\varepsilon) . We also study the special case of mixtures of Boolean subcubes over { 0 , 1 } n \{0,1\}^{n} . For this class, we give a deterministic algorithm that exactly computes the total variation distance in time poly ( n , 2 O ( k 1 + k 2 ) ) \mathrm{poly}(n,2^{O(k_{1}+k_{2})}) , and show that exact computation is # 𝖯 \#\mathsf{P} -hard when k 1 + k 2 = Θ ( n ) k_{1}+k_{2}=\Theta(n) . 1 Introduction Let \mathbb{P} and \mathbb{Q} be two discrete distributions over a sample space \Omega . The total variation distance (TV-distance) between \mathbb{P} and \mathbb{Q} is defined as \displaystyle d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)=\frac{1}{2}\sum_{\omega\in\Omega}\left|\mathbb{P}(\omega)-\mathbb{Q}(\omega)\right|=\sum_{\omega\in\Omega}\max\{0,\mathbb{P}(\omega)-\mathbb{Q}(\omega)\}. The TV-distance is one of the most fundamental metrics for measuring the difference between distributions, as it characterizes the optimal distinguishability between \mathbb{P} and \mathbb{Q} . Computing the TV-distance is therefore a basic problem arising in learning and testing. A line of research has investigated the problem of approximating the TV-distance between two high-dimensional distributions, which is particularly interesting when the two distributions admit succinct representations . Early works [ 22 , 8 , 10 , 19 , 5 ] studied the algorithms and complexity of approximating the TV-distance with additive error. More recently, [ 2 ] established that even for two product distributions, the exact computation of the TV-distance is \#\mathsf{P} -hard. In the same paper, the authors initiated the study of approximating the TV-distance with relative error , a more challenging task than the classical additive-error approximation. Subsequently, polynomial-time approximation algorithms have been developed for product distributions [ 2 , 12 , 14 ] , as well as for many high-dimensional distributions defined by local interactions , including Markov chains [ 14 ] , Bayesian networks [ 3 ] , and undirected graphical models [ 13 ] . Beyond local interactions, it is natural to consider more general high-dimensional distributions with inherently non-local structure . A fundamental and extensively studied example is given by mixtures of product distributions . Let [q]=\{1,2,\ldots,q\} and let \Omega=[q]^{n} denote the n -dimensional sample space. Fix two integers k_{1},k_{2}\geq 1 . For each s\in[k_{1}] , let \mathbb{P}^{(s)}=\bigotimes_{i=1}^{n}\mathbb{P}_{i}^{(s)} be a product distribution over \Omega , where \mathbb{P}_{i}^{(s)} denotes the marginal on the i -th coordinate, so that the coordinates are mutually independent under \mathbb{P}^{(s)} . Let \alpha^{(1)},\alpha^{(2)},\ldots,\alpha^{(k_{1})} be mixing weights satisfying \sum_{s=1}^{k_{1}}\alpha^{(s)}=1 . The resulting mixture distribution is written as \mathbb{P}=\sum_{s=1}^{k_{1}}\alpha^{(s)}\bigotimes_{i=1}^{n}\mathbb{P}^{(s)}_{i}. More explicitly, \mathbb{P} is the distribution over \Omega=[q]^{n} given by \displaystyle\forall\omega\in\Omega,\quad\mathbb{P}(\omega)=\sum_{s=1}^{k_{1}}\alpha^{(s)}\mathbb{P}^{(s)}(\omega)=\sum_{s=1}^{k_{1}}\alpha^{(s)}\prod_{i=1}^{n}\mathbb{P}_{i}^{(s)}(\omega_{i}), (1) Mixtures of product distributions form a fundamental class of latent-variable models and have been extensively studied in learning theory [ 11 , 17 , 9 , 16 , 15 ] . To draw a random sample X\sim\mathbb{P} , one first samples a hidden component index S\in[k_{1}] according to \mathbf{Pr}\left[S=s\right]=\alpha^{(s)} , and then samples X\sim\mathbb{P}^{(S)}=\bigotimes_{i=1}^{n}\mathbb{P}^{(S)}_{i} from the product distribution \mathbb{P}^{(S)} . Although each component \mathbb{P}^{(s)} is itself a product distribution, the hidden index S induces a highly non-local dependency that simultaneously couples all coordinates of the sample X=(X_{1},X_{2},\ldots,X_{n}) , which cannot be captured by any sparse local structure. In this paper, we study the problem of approximating the TV-distance between two mixtures of product distributions to within an arbitrarily small relative error, formally stated as follows. Problem 1.1 . Approximate the TV-distance between two mixtures of product distributions. • Input : An error bound \varepsilon>0 and two mixtures of product distributions over \Omega=[q]^{n} : \displaystyle\mathbb{P}=\sum_{s=1}^{k_{1}}\alpha^{(s)}\bigotimes_{i=1}^{n}\mathbb{P}^{(s)}_{i}\text{ and }\mathbb{Q}=\sum_{t=1}^{k_{2}}\beta^{(t)}\bigotimes_{i=1}^{n}\mathbb{Q}^{(t)}_{i}. The distribution \mathbb{P} is specified by the k_{1} mixing weights \alpha^{(1)},\alpha^{(2)},\ldots,\alpha^{(k_{1})} together with the k_{1} product distributions \mathbb{P}^{(1)},\mathbb{P}^{(2)},\ldots,\mathbb{P}^{(k_{1})} , where each \mathbb{P}^{(s)} is described by its n marginals \mathbb{P}_{1}^{(s)},\mathbb{P}_{2}^{(s)},\ldots,\mathbb{P}_{n}^{(s)} over [q] . The distribution \mathbb{Q} is given analogously. The total input size of the two mixtures is O((k_{1}+k_{2})nq) . • Output : A number \hat{d} such that \displaystyle(1-\varepsilon)d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)\leq\hat{d}\leq(1+\varepsilon)d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right). Due to the non-local nature of these dependencies among all coordinates, existing techniques for TV-distance approximation cannot be directly applied to mixtures of product distributions. The only prior progress is a polynomial-time algorithm for deciding whether d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)=0 or d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)>0 [ 4 ] , leaving the approximation problem open. We partially resolve this open question by giving an FPRAS for the TV-distance between two mixtures of product distributions, provided that the numbers of components k_{1} and k_{2} are constants. Theorem 1.2 . Let k_{1},k_{2}\geq 1 be constants. There exists an FPRAS for 1.1 : given any \varepsilon>0 and any pair of mixtures of product distributions \mathbb{P},\mathbb{Q} over [q]^{n} , where \mathbb{P}=\sum_{s=1}^{k_{1}}\alpha^{(s)}\bigotimes_{i=1}^{n}\mathbb{P}^{(s)}_{i} has k_{1} components and \mathbb{Q}=\sum_{t=1}^{k_{2}}\beta^{(t)}\bigotimes_{i=1}^{n}\mathbb{Q}^{(t)}_{i} has k_{2} components, it solves the problem in time O(\frac{q^{2}(nq)^{2(k_{1}+k_{2}-1)}}{\varepsilon^{2}}) with success probability at least 99\% . Our algorithm is a Monte Carlo algorithm based on a carefully designed estimator, and we provide an overview of it in Section 2 . Since the number of components k_{1}+k_{2} appears as an exponent in the running time, we require k_{1}+k_{2} to be a constant. A similar dependence on the number of components also arises in the running time of certain learning tasks for mixtures of product distributions [ 11 , 9 , 16 ] . We leave it as an open question to understand the computational complexity when the number of components grows with n . Our second result concerns mixtures of Boolean subcubes, a special case of mixtures of product distributions. A distribution \mathbb{P}=\sum_{s=1}^{k}\alpha^{(s)}\bigotimes_{i=1}^{n}\mathbb{P}_{i}^{(s)} over \{0,1\}^{n} is called a mixture of Boolean subcubes if \mathbb{P}_{i}^{(s)}(1)\in\{0,\frac{1}{2},1\} for every s\in[k] and i\in[n] , where \mathbb{P}_{i}^{(s)} denotes the marginal distribution of the i -th coordinate in the s -th component. Equivalently, for each component s , the product distribution \mathbb{P}^{(s)} fixes every coordinate i with \mathbb{P}_{i}^{(s)}(1)=1 to 1 , fixes every coordinate i with \mathbb{P}_{i}^{(s)}(1)=0 to 0 , and is uniform on the remaining coordinates. Mixtures of Boolean subcubes have been extensively studied in learning theory [ 9 , 6 , 7 ] and capture many natural distributions; for instance, the uniform distribution over the satisfying assignments of a decision tree is a mixture of Boolean subcubes [ 11 ] . In contrast to the general case, where we only obtain an FPRAS when k_{1}+k_{2}=O(1) , we show that the TV-distance between two mixtures of Boolean subcubes \mathbb{P} and \mathbb{Q} can be computed exactly in time polynomial in the dimension n , provided that k_{1}+k_{2}=O(\log n) . Problem 1.3 . Compute exactly the total variation distance between two mixtures of Boolean subcubes \mathbb{P}=\sum_{s=1}^{k_{1}}\alpha^{(s)}\bigotimes_{i=1}^{n}\mathbb{P}^{(s)}_{i} and \mathbb{Q}=\sum_{t=1}^{k_{2}}\beta^{(t)}\bigotimes_{i=1}^{n}\mathbb{Q}^{(t)}_{i} . • Input : two mixtures of Boolean subcubes, given in the same format as in 1.1 . • Output : the exact value of d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right) Theorem 1.4 . There exists