Sparse Covers for Sums of Indicators

Introduction

A Poisson Binomial Distribution of order $n$ is the discrete probability distribution of the sum of $n$ independent indicator random variables. The distribution is parameterized by a vector $(p_{i})_{i=1}^{n}\in^{n}$ of probabilities, and is denoted ${\rm PBD}(p_{1},\ldots,p_{n})$. In this paper we establish that the set ${\cal S}_{n}$ of all Poisson Binomial distributions of order $n$ admits certain useful covers with respect to the total variation distance $d_{\rm TV}\left(\cdot,\cdot\right)$ between distributions. Namely

For all $n,\epsilon>0$, there exists a set ${\cal S}_{n,\epsilon}\subset{\cal S}_{n}$ such that:

${\cal S}_{n,\epsilon}$ is an $\epsilon$-cover of ${\cal S}_{n}$ in total variation distance; that is, for all $D\in{\cal S}_{n}$, there exists some $D^{\prime}\in{\cal S}_{n,\epsilon}$ such that $d_{\rm TV}\left(D,D^{\prime}\right)\leq\epsilon$

$|{\cal S}_{n,\epsilon}|\leq n^{2}+n\cdot\left({1\over\epsilon}\right)^{O(\log^{2}{1/\epsilon})}$

${\cal S}_{n,\epsilon}$ can be computed in time $O(n^{2}\log n)+O(n\log n)\cdot\left({1\over\epsilon}\right)^{O(\log^{2}{1/\epsilon})}$.

Moreover, all distributions ${\rm PBD}(p_{1},\ldots,p_{n})\in{\cal S}_{n,\epsilon}$ in the cover satisfy at least one of the following properties, for some positive integer $k=k(\epsilon)=O(1/\epsilon):$

Covers such as the one provided by Theorem 1 are of interest in the design of algorithms, when one is searching a class of distributions $C$ to identify an element of the class with some quantitative property, or in optimizing over a class with respect to some objective. If the metric used in the construction of the cover is relevant for the problem at hand, and the cover is discrete, relatively small and easy to construct, then one can provide a useful approximation to the sought distribution by searching the cover, instead of searching all of $C$. For example, it is shown in [DP07, DP09, DP13] that Theorem 1 implies efficient algorithms for computing approximate Nash equilibria in an important class of multiplayer games, called anonymous [Mil96, Blo99].

We proceed with a fairly detailed sketch of the proof of our main cover theorem, Theorem 1, stating two additional results, Theorems 2 and 3. The complete proofs of Theorems 1, 2 and 3 are deferred to Sections 3, 4 and 5 respectively. Section 1.4 discusses related work, while Section 2 provides formal definitions, as well as known approximations to the Poisson Binomial distribution by simpler distributions, which are used in the proof.

At a high level, the proof of Theorem 1 is obtained in two steps. First, we establish the existence of an $\epsilon$-cover whose size is polynomial in $n$ and $(1/\epsilon)^{1/\epsilon^{2}}$, via Theorem 2. We then show that this cover can be pruned to size polynomial in $n$ and $(1/\epsilon)^{\log^{2}(1/\epsilon)}$ using Theorem 3, which provides a quantification of how the total variation distance between Poisson Binomial distributions depends on the number of their first moments that are equal.

We proceed to state the two ingredients of the proof, Theorems 2 and 3. We start with Theorem 2 whose detailed sketch is given in Section 1.2, and complete proof in Section 4.

$d_{\rm TV}\left(\sum_{i}{X_{i}},\sum_{i}{Y_{i}}\right)\leq 41/k;$

Theorem 2 implies the existence of an $\epsilon$-cover of ${\cal S}_{n}$ whose size is $n^{2}+n\cdot\left({1/\epsilon}\right)^{O({1/\epsilon^{2}})}$. This cover can be obtained by enumerating over all Poisson Binomial distributions of order $n$ that are in $k$-sparse or $(n,k)$-Binomial form as defined in the statement of the theorem, for $k=\lceil 41/\epsilon\rceil$.

The next step is to sparsify this cover by removing elements to obtain Theorem 1. Note that the term $n\cdot\left({1/\epsilon}\right)^{O({1/\epsilon^{2}})}$ in the size of the cover is due to the enumeration over distributions in sparse form. Using Theorem 3 below, we argue that there is a lot of redundancy in those distributions, and that it suffices to only include $n\cdot\left({1/\epsilon}\right)^{O(\log^{2}{1/\epsilon})}$ of them in the cover. In particular, Theorem 3 establishes that, if two Poisson Binomial distributions have their first $O(\log 1/\epsilon)$ moments equal, then their distance is at most $\epsilon$. So we only need to include at most one sparse form distribution with the same first $O(\log 1/\epsilon)$ moments in our cover. We proceed to state Theorem 3, postponing its proof to Section 5. In Section 1.3 we provide a sketch of the proof.

Condition $(C_{d})$ in the statement of Theorem 3 constrains the first $d$ power sums of the expectations of the constituent indicators of two Poisson Binomial distributions. To relate these power sums to the moments of these distributions we can use the theory of symmetric polynomials to arrive at the following equivalent condition to $(C_{d})$:

We provide a proof that $(C_{d})\Leftrightarrow(V_{d})$ in Proposition 2 of Section 6.

In view of Remark 1, Theorem 3 says the following:

“If two sums of independent indicators with expectations in [0,1/2] have equal first $d$ moments, then their total variation distance is $2^{-\Omega(d)}$.”

We note that the bound (1) does not depend on the number of variables $n$, and in particular does not rely on summing a large number of variables. We also note that, since we impose no constraint on the expectations of the indicators, we also impose no constraint on the variance of the resulting Poisson Binomial distributions. Hence we cannot use Berry-Esséen type bounds to bound the total variation distance of the two Poisson Binomial distributions by approximating them with Normal distributions. Finally, it is easy to see that Theorem 3 holds if we replace $[0,1/2]$ with $[1/2,1]$. See Corollary 1 in Section 6.

In Section 3 we show how to use Theorems 2 and 3 to obtain Theorem 1. We continue with the outlines of the proofs of Theorems 2 and 3, postponing their complete proofs to Sections 4 and 5.

2 Outline of Proof of Theorem 2

Given arbitrary indicators $X_{1},\ldots,X_{n}$ we obtain indicators $Y_{1},\ldots,Y_{n}$, satisfying the requirements of Theorem 2, in two steps. We first massage the given variables $X_{1},\ldots,X_{n}$ to obtain variables $Z_{1},\ldots,Z_{n}$ such that

that is, we eliminate from our collection variables that have expectations very close to or $1$, without traveling too much distance from the starting Poisson Binomial distribution.

Variables $Z_{1},\ldots,Z_{n}$ do not necessarily satisfy Properties 2a or 2b in the statement of Theorem 2, but allow us to define variables $Y_{1},\ldots,Y_{n}$ which do satisfy one of these properties and, moreover,

(2), (3) and the triangle inequality imply $d_{\rm TV}\left(\sum_{i}{X_{i}},\sum_{i}{Y_{i}}\right)\leq{41\over k}$, concluding the proof of Theorem 2.

Stage 2: The definition of $(q_{i})_{i}$ depends on the number $m$ of $p_{i}^{\prime}$’s which are not or $1$. The case $m\leq k^{3}$ corresponds to Case 2a in the statement of Theorem 2, while the case $m>k^{3}$ corresponds to Case 2b.

Case $m\leq k^{3}$: First, we set $q_{i}=p_{i}^{\prime}$, if $p_{i}^{\prime}\in\{0,1\}$. We then argue that each $p^{\prime}_{i}$, ${i\in\mathcal{M}}:=\{i~{}\vline~{}p_{i}^{\prime}\notin\{0,1\}\}$, can be rounded to some $q_{i}$, which is an integer multiple of $1/k^{2}$, so that (3) holds. Notice that, if we were allowed to use multiples of $1/k^{4}$, this would be immediate via an application of Lemma 2:

We improve the required accuracy to $1/k^{2}$ via a series of Binomial approximations to the Poisson Binomial distribution, using Ehm’s bound [Ehm91] stated as Theorem 5 in Section 2.1. The details involve partitioning the interval $[1/k,1-1/k]$ into irregularly sized subintervals, whose endpoints are integer multiples of $1/k^{2}$. We then round all but one of the $p_{i}^{\prime}$’s falling in each subinterval to the endpoints of the subinterval so as to maintain their total expectation, and apply Ehm’s approximation to argue that the distribution of their sum is not affected by more than $O(1/k^{2})$ in total variation distance. It is crucial that the total number of subintervals is $O(k)$ to get a total hit of at most $O(1/k)$ in variation distance in the overall distribution. The details are given in Section 4.2.1.

Case $m>k^{3}$: We approximate $\sum_{i}Z_{i}$ with a Translated Poisson distribution (defined formally in Section 2), using Theorem 6 of Section 2.1 due to Röllin [R0̈7]. The quality of the approximation is inverse proportional to the standard deviation of $\sum_{i}Z_{i}$, which is at least $k$, by the assumption $m>k^{3}$. Hence, we show that $\sum_{i}Z_{i}$ is $3/k$-close to a Translated Poisson distribution. We then argue that the latter is $6/k$-close to a Binomial distribution $B(m^{\prime},q)$, where $m^{\prime}\leq n$ and $q$ is an integer multiple of $\frac{1}{n}$. In particular, we show that an appropriate choice of $m^{\prime}$ and $q$ implies (3), if we set $m^{\prime}$ of the $q_{i}$’s equal to $q$ and the remaining equal to . The details are in Section 4.2.2.

3 Outline of Proof of Theorem 3

4 Related Work

It is believed that Poisson [Poi37] was the first to study the Poisson Binomial distribution, hence its name. Sometimes the distribution is also referred to as “Poisson’s Binomial Distribution.” PBDs have many uses in research areas such as survey sampling, case-control studies, and survival analysis; see e.g. [CL97] for a survey of their uses. They are also very important in the design of randomized algorithms [MR95].

In Probability and Statistics there is a broad literature studying various properties of these distributions; see [Wan93] for an introduction to some of this work. Many results provide approximations to the Poisson Binomial distribution via simpler distributions. In a well-known result, Le Cam [LC60] shows that, for any vector $(p_{i})_{i=1}^{n}\in^{n}$,

where ${\rm Poisson}(\lambda)$ is the Poisson distribution with parameter $\lambda$. Subsequently many other proofs of this bound and improved ones, such as Theorem 4 of Section 2.1, were given, using a range of different techniques; [HC60, Che74, BH84, DP86] is a sampling of work along these lines, and Steele [Ste94] gives an extensive list of relevant references. Much work has also been done on approximating PBDs by Normal distributions (see e.g. [Ber41, Ess42, Mik93, Vol95, CGS10]) and by Binomial distributions; see e.g. Ehm’s result [Ehm91], given as Theorem 5 of Section 2.1, as well as Soon’s result [Soo96] and Roos’s result [Roo00], given as Theorem 7 of Section 2.1.

These results provide structural information about PBDs that can be well approximated by simpler distributions, but fall short of our goal of approximating a PBD to within arbitrary accuracy. Indeed, the approximations obtained in the probability literature (such as the Poisson, Normal and Binomial approximations) typically depend on the first few moments of the PBD being approximated, while higher moments are crucial for arbitrary approximation [Roo00]. At the same time, algorithmic applications often require that the approximating distribution is of the same kind as the distribution that is being approximated. E.g., in the anonymous game application mentioned earlier, the parameters of the given PBD correspond to mixed strategies of players at Nash equilibrium, and the parameters of the approximating PBD correspond to mixed strategies at approximate Nash equilibrium. Approximating the given PBD via a Poisson or a Normal distribution would not have any meaning in the context of a game.

As outlined above, the proof of our main result, Theorem 1, builds on Theorems 2 and 3. A weaker form of these theorems was announced in [Das08, DP09], while a weaker form of Theorem 1 was announced in [DDS12].

Preliminaries

Covers: Let ${\cal F}$ be a set of probability distributions. A subset ${\cal G}\subseteq{\cal F}$ is called a (proper) $\epsilon$-cover of ${\cal F}$ in total variation distance if, for all $D\in{\cal F}$, there exists some $D^{\prime}\in{\cal G}$ such that $d_{\rm TV}\left(D,D^{\prime}\right)\leq\epsilon$.

Let $X_{1},\ldots,X_{n}$ be mutually independent indicators with expectations $p_{1}\leq p_{2}\leq\ldots\leq p_{n}$ respectively. Similarly let $Y_{1},\ldots,Y_{n}$ be mutually independent indicators with expectations $q_{1}\leq\ldots\leq q_{n}$ respectively. The distributions of $\sum_{i}X_{i}$ and $\sum_{i}Y_{i}$ are different if and only if $(p_{1},\ldots,p_{n})\neq(q_{1},\ldots,q_{n})$.

Translated Poisson Distribution: We say that an integer random variable $Y$ has a translated Poisson distribution with parameters $\mu$ and $\sigma^{2}$ and write $\mathcal{L}(Y)=TP(\mu,\sigma^{2})$ iff

where $\{\mu-\sigma^{2}\}$ represents the fractional part of $\mu-\sigma^{2}$.

Similarly, we write $f(x)=\Omega(g(x))$ if and only if there exist positive reals $M$ and $x_{0}$ such that

We are casual in our use of the order notation $O(\cdot)$ and $\Omega(\cdot)$ throughout the paper. Whenever we write $O(f(n))$ or $\Omega(f(n))$ in some bound where $n$ ranges over the integers, we mean that there exists a constant $c>0$ such that the bound holds true for sufficiently large $n$ if we replace the $O(f(n))$ or $\Omega(f(n))$ in the bound by $c\cdot f(n)$. On the other hand, whenever we write $O(f(1/\epsilon))$ or $\Omega(f(1/\epsilon))$ in some bound where $\epsilon$ ranges over the positive reals, we mean that there exists a constant $c>0$ such that the bound holds true for sufficiently small $\epsilon$ if we replace the $O(f(1/\epsilon))$ or $\Omega(f(1/\epsilon))$ in the bound with $c\cdot f(1/\epsilon)$.

We conclude with an easy but useful lemma whose proof we defer to Section 6.

Let $X_{1},\ldots,X_{n}$ be mutually independent random variables, and let $Y_{1},\ldots,Y_{n}$ be mutually independent random variables. Then

We present a collection of known approximations to the Poisson Binomial distribution via simpler distributions. The quality of these approximations can be quantified in terms of the first few moments of the Poisson Binomial distribution that is being approximated. We will make use of these bounds to approximate Poisson Binomial distributions in different regimes of their moments. Theorems 4—6 are obtained via the Stein-Chen method.

where ${\mathcal{B}}\left(n,\bar{t}\right)$ is the Binomial distribution with parameters $n$ and $\bar{t}$.

where $\mu=\sum_{i=1}^{n}t_{i}$ and $\sigma^{2}=\sum_{i=1}^{n}t_{i}(1-t_{i})$.

The approximation theorems stated above do not always provide tight enough approximations. When these fail, we employ the following theorem of Roos [Roo00], which provides an expansion of the Poisson Binomial distribution as a weighted sum of a finite number of signed measures: the Binomial distribution $\mathcal{B}({n,p})$ (for an arbitrary value of $p$) and its first $n$ derivatives with respect to the parameter $p$, at the chosen value of $p$. For the purposes of the following statement we denote by $\mathcal{B}_{n,p}(m)$ the probability assigned by the Binomial distribution ${\mathcal{B}}(n,p)$ to integer $m$.

Let $\mathcal{P}:=(p_{i})_{i=1}^{n}\in^{n}$, $X_{1},\ldots,X_{n}$ be mutually independent indicators with expectations $p_{1},\ldots,p_{n}$, and $X=\sum_{i}X_{i}$. Then, for all $m\in\{0,\ldots,n\}$ and $p\in$,

where for the purposes of the above expression:

where for the last definition we interpret $\mathcal{B}_{n,p}(m)\equiv{n\choose m}p^{m}(1-p)^{n-m}$ as a function of $p$.

If $\theta({\mathcal{P}},p)<1,$ then, for all $d\geq 0$:

Proof of Theorem 1

We next show that we can remove from ${\cal S}_{n,\epsilon}^{\prime}$ a large number of the sparse-form distributions it contains to obtain a $2\epsilon$-cover of ${\cal S}_{n}$. In particular, we shall only keep $n\cdot\left({1\over\epsilon}\right)^{O(\log^{2}{1/\epsilon})}$ sparse-form distributions by appealing to Theorem 3. To explain the pruning we introduce some notation. For a collection ${\mathcal{P}}=(p_{i})_{i\in[n]}\in^{n}$ of probability values we denote by ${\cal L}_{{\mathcal{P}}}=\{i~{}|~{}p_{i}\in(0,1/2]\}$ and by ${\cal R}_{{\mathcal{P}}}=\{i~{}|~{}p_{i}\in(1/2,1)\}$. Theorem 3, Corollary 1, Lemma 2 and Lemma 1 imply that if two collections ${\mathcal{P}}=(p_{i})_{i\in[n]}$ and $\mathcal{Q}=(q_{i})_{i\in[n]}$ of probability values satisfy

then $d_{\rm TV}({\rm PBD}({\mathcal{P}}),{\rm PBD}(\mathcal{Q}))\leq 2\cdot 13(d+1)^{1/4}2^{-(d+1)/2}$. In particular, for some $d(\epsilon)=O(\log 1/\epsilon)$, this bound becomes at most $\epsilon$.

For a collection ${\mathcal{P}}=(p_{i})_{i\in[n]}\in^{n}$, we define its moment profile $m_{{\mathcal{P}}}$ to be the $(2d(\epsilon)+1)$-dimensional vector

By the previous discussion, for two collections ${\mathcal{P}},\mathcal{Q}$, if $m_{{\mathcal{P}}}=m_{\mathcal{Q}}$ then $d_{\rm TV}({\rm PBD}({\mathcal{P}}),{\rm PBD}(\mathcal{Q}))\leq\epsilon$.

Given the above we sparsify ${\cal S}_{n,\epsilon}^{\prime}$ as follows: for every possible moment profile that can arise from a Poisson Binomial distribution in $k$-sparse form, we keep in our cover a single Poisson Binomial distribution with such moment profile. The cover resulting from this sparsification is a $2\epsilon$-cover, since the sparsification loses us an additional $\epsilon$ in total variation distance, as argued above.

We now bound the cardinality of the sparsified cover. The total number of moment profiles of $k$-sparse Poisson Binomial distributions is $k^{O(d(\epsilon)^{2})}\cdot(n+1)$. Indeed, consider a Poisson Binomial distribution ${\rm PBD}({\mathcal{P}}=(p_{i})_{i\in[n]})$ in $k$-sparse form. There are at most $k^{3}+1$ choices for $|{\cal L}_{{\mathcal{P}}}|$, at most $k^{3}+1$ choices for $|{\cal R}_{{\mathcal{P}}}|$, and at most $(n+1)$ choices for $|\{i~{}|~{}p_{i}=1\}|$. We also claim that the total number of possible vectors

is $k^{O(d(\epsilon)^{2})}$. Indeed, if $|\mathcal{L}_{{\mathcal{P}}}|=0$ there is just one such vector, namely the all-zero vector. If $|\mathcal{L}_{{\mathcal{P}}}|>0$, then, for all $t=1,\ldots,d(\epsilon)$, $\sum_{i\in{\cal L}_{{\mathcal{P}}}}p_{i}^{t}\in(0,|{\cal L}_{{\mathcal{P}}}|]$ and it must be an integer multiple of $1/k^{2t}$. So the total number of possible values of $\sum_{i\in{\cal L}_{{\mathcal{P}}}}p_{i}^{t}$ is at most $k^{2t}|{\cal L}_{{\mathcal{P}}}|\leq k^{2t}k^{3}$, and the total number of possible vectors

The same upper bound applies to the total number of possible vectors

The moment profiles we enumerated over are a superset of the moment profiles of $k$-sparse Poisson Binomial distributions. We call them compatible moment profiles. We argued that there are at most $k^{O(d(\epsilon)^{2})}\cdot(n+1)$ compatible moment profiles, so the total number of Poisson Binomial distributions in $k$-sparse form that we keep in the cover is at most $k^{O(d(\epsilon)^{2})}\cdot(n+1)=n\cdot\left({1\over\epsilon}\right)^{O(\log^{2}{1/\epsilon})}$. The number of Poisson Binomial distributions in $(n,k)$-Binomial form is the same as before, i.e. at most $n^{2}$, as we did not eliminate any of them. So the size of the sparsified cover is $n^{2}+n\cdot\left({1\over\epsilon}\right)^{O(\log^{2}{1/\epsilon})}$.

Proof of Theorem 2

We organize the proof according to the structure and notation of our outline in Section 1.2. In particular, we proceed to provide the details of Stages 1 and 2, described in the outline. The reader should refer to Section 1.2 for notation.

Define ${\cal L}_{k}:=\left\{i~{}\vline~{}i\in[n]\wedge p_{i}\in(0,1/k)\right\}$ and ${\cal H}_{k}:=\left\{i~{}\vline~{}i\in[n]\wedge p_{i}\in(1-1/k,1)\right\}.$ We define the expectations $(p_{i}^{\prime})_{i}$ of the intermediate indicators $(Z_{i})_{i}$ as follows.

First, we set $p^{\prime}_{i}=p_{i}$, for all $i\in[n]\setminus{\cal L}_{k}\cup{\cal H}_{k}$. It follows that

Next, we define the probabilities $p^{\prime}_{i}$, $i\in{\cal L}_{k}$, using the following procedure:

Set $r=\left\lfloor\frac{\sum_{i\in{\cal L}_{k}}p_{i}}{1/k}\right\rfloor$; and let ${\cal L}_{k}^{\prime}\subseteq{\cal L}_{k}$ be an arbitrary subset of cardinality $|{\cal L}_{k}^{\prime}|=r$.

Set $p_{i}^{\prime}=\frac{1}{k}$, for all $i\in{\cal L}_{k}^{\prime}$, and $p_{i}^{\prime}=0$, for all $i\in{\cal L}_{k}\setminus{\cal L}_{k}^{\prime}$.

We bound the total variation distance $d_{\rm TV}\left(\sum_{i\in{\cal L}_{k}}X_{i},\sum_{i\in{\cal L}_{k}}Z_{i}\right)$ using the Poisson approximation to the Poisson Binomial distribution. In particular, Theorem 4 implies

Similarly, $d_{\rm TV}\left(\sum_{i\in{\cal L}_{k}}Z_{i},{\rm Poisson}\left(\sum_{i\in\mathcal{L}_{k}}p^{\prime}_{i}\right)\right)\leq 1/k.$ Finally, we use Lemma 3 (given below and proved in Section 6) to bound the distance

where we used that $|\sum_{i\in\mathcal{L}_{k}}p_{i}-\sum_{i\in\mathcal{L}_{k}}p^{\prime}_{i}|\leq 1/k$. Using the triangle inequality the above imply

We follow a similar rounding scheme to define $(p_{i}^{\prime})_{i\in\mathcal{H}_{k}}$ from $(p_{i})_{i\in{\cal H}_{k}}$. That is, we round some of the $p_{i}$’s to $1-1/k$ and some of them to $1$ so that $|\sum_{i\in\mathcal{H}_{k}}p_{i}-\sum_{i\in\mathcal{H}_{k}}p^{\prime}_{i}|\leq 1/k$. As a result, we get (to see this, repeat the argument employed above to the variables $1-X_{i}$ and $1-Z_{i}$, $i\in{\cal H}_{k}$)

Using (5), (6), (7) and Lemma 2 we get (2).

2 Details of Stage 2

Recall that ${\cal M}:=\{i~{}|~{}p^{\prime}_{i}\notin\{0,1\}\}$ and $m:=|{\cal M}|$. Depending on on whether $m\leq k^{3}$ or $m>k^{3}$ we follow different strategies to define the expectations $(q_{i})_{i}$ of indicators $(Y_{i})_{i}$.

First we set $q_{i}=p^{\prime}_{i}$, for all $i\in[n]\setminus{\cal M}.$ It follows that

For the definition of $(q_{i})_{i\in\mathcal{M}}$, we make use of Ehm’s Binomial approximation to the Poisson Binomial distribution, stated as Theorem 5 in Section 2.1. We start by partitioning $\mathcal{M}$ as $\mathcal{M}=\mathcal{M}_{l}\sqcup\mathcal{M}_{h}$, where $\mathcal{M}_{l}=\{i\in\mathcal{M}~{}|~{}p^{\prime}_{i}\leq 1/2\}$, and describe below a procedure for defining $(q_{i})_{i\in\mathcal{M}_{l}}$ so that the following hold:

$d_{\rm TV}\left(\sum_{i\in\mathcal{M}_{l}}Z_{i},\sum_{i\in\mathcal{M}_{l}}Y_{i}\right)\leq 17/k$;

for all $i\in\mathcal{M}_{l}$, $q_{i}$ is an integer multiple of $1/k^{2}$.

To define $(q_{i})_{i\in\mathcal{M}_{h}}$, we apply the same procedure to $(1-p_{i}^{\prime})_{i\in\mathcal{M}_{h}}$ to obtain $(1-q_{i})_{i\in\mathcal{M}_{h}}$. Assuming the correctness of our procedure for probabilities $\leq 1/2$ the following should also hold:

$d_{\rm TV}\left(\sum_{i\in\mathcal{M}_{h}}Z_{i},\sum_{i\in\mathcal{M}_{h}}Y_{i}\right)\leq 17/k$;

for all $i\in\mathcal{M}_{h}$, $q_{i}$ is an integer multiple of $1/k^{2}$.

Now that we have (9), using (8) and Lemma 2 we get (3).

So it suffices to define the $(q_{i})_{i\in\mathcal{M}_{l}}$ properly. To do this, we define the partition $\mathcal{M}_{l}=\mathcal{M}_{l,1}\sqcup\mathcal{M}_{l,2}\sqcup\ldots\sqcup\mathcal{M}_{l,k-1}$ where for all $j$:

(Notice that the length of interval used in the definition of $\mathcal{M}_{l,j}$ is ${j\over k^{2}}$.) Now, for each $j=1,\ldots,k-1$ such that $\mathcal{M}_{l,j}\neq\emptyset$, we define $(q_{i})_{i\in\mathcal{M}_{l,j}}$ via the following procedure:

Set $p_{j,\min}:={1\over k}+{(j-1)j\over 2}{1\over k^{2}}$, $p_{j,\max}:={1\over k}+{(j+1)j\over 2}{1\over k^{2}}$, $n_{j}=|\mathcal{M}_{l,j}|$, $\bar{p}_{j}={\sum_{i\in{\cal M}_{l,j}}p_{i}^{\prime}\over n_{j}}$.

Set $r=\left\lfloor\frac{n_{j}(\bar{p}_{j}-p_{j,\min})}{j/k^{2}}\right\rfloor$; let ${\cal M}_{l,j}^{\prime}\subseteq{\cal M}_{l,j}$ be an arbitrary subset of cardinality $r$.

Set $q_{i}=p_{j,\max}$, for all $i\in{\cal M}_{l,j}^{\prime}$;

for an arbitrary index $i_{j}^{*}\in{\cal M}_{l,j}\setminus{\cal M}_{l,j}^{\prime}$, set $q_{i^{*}_{j}}=n_{j}\bar{p}_{j}-(rp_{j,\max}+(n_{j}-r-1)p_{j,\min})$;

finally, set $q_{i}=p_{j,\min}$, for all $i\in{\cal M}_{l,j}\setminus{\cal M}_{l,j}^{\prime}\setminus\{i^{*}_{j}\}$.

$\sum_{i\in{\cal M}_{l,j}}p_{i}^{\prime}=\sum_{i\in{\cal M}_{l,j}}q_{i}\equiv n_{j}\bar{p}_{j}$;

for all $i\in{\cal M}_{l,j}\setminus\{i_{j}^{*}\}$, $q_{i}$ is an integer multiple of $1/k^{2}$.

A similar derivation gives $d_{\rm TV}\left(\sum_{i\in\mathcal{M}_{l,j}}Y_{i},{\mathcal{B}}\left(n_{j},\bar{p}_{j}\right)\right)\leq{8\over k^{2}}$. So by the triangle inequality:

As Eq (10) holds for all $j=1,\ldots,k-1$, an application of Lemma 2 gives:

Moreover, the $q_{i}$’s defined above are integer multiples of $1/k^{2}$, except maybe for $q_{i_{1}^{*}},\ldots,q_{i_{k-1}^{*}}$. But we can round these to their closest multiple of $1/k^{2}$, increasing $d_{\rm TV}\left(\sum_{i\in\mathcal{M}_{l}}Z_{i},\sum_{i\in\mathcal{M}_{l}}Y_{i}\right)$ by at most $1/k$.

Let $t=|\{i~{}|~{}p^{\prime}_{i}=1\}|$. We show that the random variable $\sum_{i}Z_{i}$ is within total variation distance $9/k$ from the Binomial distribution ${\mathcal{B}}(m^{\prime},q)$ where

$\left(\sum_{i\in{\cal M}}p_{i}^{\prime}+t\right)^{2}\leq(\sum_{i\in{\cal M}}p_{i}^{\prime 2}+t)(m+t)$, by the Cauchy-Schwarz inequality; and

$\frac{\sum_{i\in{\cal M}}p_{i}^{\prime}+t}{m^{\prime}}\leq{\sum_{i\in\mathcal{M}}p_{i}^{\prime}+t\over\frac{\left(\sum_{i\in{\cal M}}p_{i}^{\prime}+t\right)^{2}}{\sum_{i\in{\cal M}}p_{i}^{\prime 2}+t}}={\sum_{i\in{\cal M}}p_{i}^{\prime 2}+t\over\sum_{i\in{\cal M}}p_{i}^{\prime}+t}\leq 1$.

For fixed $m^{\prime}$ and $q$, we set $q_{i}=q$, for all $i\leq m^{\prime}$, and $q_{i}=0$, for all $i>m^{\prime}$, and compare the distributions of $\sum_{i\in{\cal M}}Z_{i}$ and $\sum_{i\in{\cal M}}Y_{i}$. For convenience we define

The following lemma compares the values $\mu$, $\mu^{\prime}$, $\sigma$, $\sigma^{\prime}$.

The proof of Lemma 4 is given in Section 6. To compare $\sum_{i\in{\cal M}}Z_{i}$ and $\sum_{i\in{\cal M}}Y_{i}$ we approximate both by Translated Poisson distributions. Theorem 6 implies that

where for the last inequality we assumed $k\geq 3$, but the bound of $3/k$ clearly also holds for $k=1,2$. Similarly,

where for the last inequality we assumed $k\geq 3$, but the bound of $3/k$ clearly also holds for $k=1,2$. By the triangle inequality we then have that

It remains to bound the total variation distance between the two Translated Poisson distributions. We make use of the following lemma.

where for the last inequality we assumed $k>3$, but the bound clearly also holds for $k=1,2,3$. Using (15) and (16) we get

Proof of Theorem 3

For all $p\in$, by combining Theorem 7 and Lemma 6 and we get that

Plugging $p=\bar{p}:=\frac{1}{n}\sum_{i}p_{i}$ into Proposition 1, we get

But $(C_{d})$ implies that $\sum_{i}q_{i}=\sum_{i}p_{i}=\bar{p}$. So we get in a similar fashion

Deferred Proofs

Proof of Lemma 1: Let $X=\sum_{i}X_{i}$ and $Y=\sum_{i}Y_{i}$. It is obvious that, if $(p_{1},\ldots,p_{n})=(q_{1},\ldots,q_{n})$, then the distributions of $X$ and $Y$ are the same. In the other direction, we show that, if $X$ and $Y$ have the same distribution, then $(p_{1},\ldots,p_{n})=(q_{1},\ldots,q_{n})$. Consider the polynomials:

Since $X$ and $Y$ have the same distribution, $g_{X}$ and $g_{Y}$ are equal, so they have the same degree and roots. Notice that $g_{X}$ has degree $n-|\{i~{}|~{}p_{i}=0\}|$ and roots $\{-{1\over p_{i}}~{}|~{}p_{i}\neq 0\}$. Similarly, $g_{Y}$ has degree $n-|\{i~{}|~{}q_{i}=0\}|$ and roots $\{-{1\over q_{i}}~{}|~{}q_{i}\neq 0\}$. Hence, $(p_{1},\ldots,p_{n})=(q_{1},\ldots,q_{n})$. $\blacksquare$

Proof of Lemma 2: It follows from the coupling lemma that for any coupling of the variables $X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{n}$:

We proceed to fix a specific coupling. For all $i$, it follows from the optimal coupling theorem that there exists a coupling of $X_{i}$ and $Y_{i}$ such that $\Pr[X_{i}\neq Y_{i}]=d_{\rm TV}\left(X_{i},Y_{i}\right)$. Using these individual couplings for each $i$ we define a grand coupling of the variables $X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{n}$ such that $\Pr[X_{i}\neq Y_{i}]=d_{\rm TV}\left(X_{i},Y_{i}\right)$, for all $i$. This coupling is faithful because $X_{1},\ldots,X_{n}$ are mutually independent and $Y_{1},\ldots,Y_{n}$ are mutually independent. Under this coupling Eq (19) implies:

Proof of Claim 1: We use dynamic programming. Let us consider the following tensor of dimension $2{\delta}+5$:

Every cell of $A$ is assigned value or $1$, as follows:

Inductively, to complete layer $i+1$, we consider all the non-zero entries of layer $i$ and for every such non-zero entry and for every $v_{i+1}\in\mathcal{T}_{i+1}$, we find which entry of layer $i+1$ we would transition to if we chose $p_{i+1}=v_{i+1}$. We set that entry equal to $1$ and we also save a pointer to this entry from the corresponding entry of layer $i$, labeling that pointer with the value $v_{i+1}$. The bit operations required to complete layer $i+1$ are bounded by

Therefore, the overall time needed to complete $A$ is

Having completed $A$, it is easy to check if there is a solution to $(\Sigma)$. A solution exists if and only if

and can be found by tracing the pointers from this cell of $A$ back to level $1$. The overall running time is dominated by the time needed to complete $A$. $\blacksquare$

Proof of lemma 3: Without loss of generality assume that $0<\lambda_{1}\leq\lambda_{2}$ and denote $\delta=\lambda_{2}-\lambda_{1}$. For all $i\in\{0,1,\ldots\}$, denote

Finally, define $\mathcal{I}^{*}=\{i:p_{i}\geq q_{i}\}$.

Combining the above we get the result. $\blacksquare$

As $\mu^{\prime}=m^{\prime}q$ and $m^{\prime}\leq n$, we get ${\mu}\leq\mu^{\prime}\leq\mu+1.$ Moreover, since $m\geq k^{3}$,

For all $d\in[n]$, Condition $(C_{d})$ in the statement of Theorem 3 is equivalent to the following condition:

Next, for all $t\in[n]$, define $\pi_{t}({\mathcal{P}})$ to be the power sum symmetric polynomial of degree $t$

The implication $(C_{d})\Rightarrow(V_{d})$ is established in a similar fashion. $(C_{d})$ says that

Using the Binomial theorem and induction, we see that (25) implies:

Acknowledgement

We thank the anonymous reviewer for comments that helped improve the presentation.

References