Testing $k$-Modal Distributions: Optimal Algorithms via Reductions

Introduction

While it is surprising that these tasks can be performed using a sublinear number of samples, for many real-world applications using $\sqrt{n}$, $n^{2/3}$, or $\frac{n}{\log n}$ samples is still impractical. As these bounds characterize worst-case instances, one might hope that drastically better performance may be possible for many settings typically encountered in practice. Thus, a natural research direction, which we pursue in this paper, is to understand how structural properties of the distributions in question may be leveraged to yield improved sample complexities.

In this work we consider monotone, unimodal, and more generally $k$-modal distributions. Monotone, unimodal, and bimodal distributions abound in the natural world. The distribution of many measurements—heights or weights of members of a population, concentrations of various chemicals in cells, parameters of many atmospheric phenomena–often belong to this class of distributions. Because of their ubiquity, much work in the natural sciences rests on the analysis of such distributions (for example, on November 1, 2011 a Google Scholar search for the exact phrase “bimodal distribution” in the bodies of papers returned more than 90,000 hits). Though perhaps not as pervasive, $k$-modal distributions for larger values of $k$ commonly arise as mixtures of unimodal distributions and are natural objects of study. On the theoretical side, motivated by the many applications, monotone, unimodal, and $k$-modal distributions have been intensively studied in the probability and statistics literatures for decades, see e.g. [Gre56, Rao69, BBBB72, CKC83, Gro85, Bir87a, Bir87b, Kem91, Fou97, CT04, JW09].

Our main results are algorithms, and nearly matching lower bounds, that give a complete picture of the sample complexities of identity testing and estimating $L_{1}$ distance for monotone and $k$-modal distributions. We obtain such results in both the setting where the two distributions are given via samples, and the setting where one of the distributions is given via samples and the other is described explicitly.

We view the equivalence between the sample complexity of each of the above tasks on a monotone or unimodal distribution of domain $[n]$ and the sample complexity of the same task on an unrestricted distribution of domain $[\log n]$ as a surprising result, because such an equivalence fails to hold for related estimation tasks. For example, consider the task of distinguishing whether a distribution on $[n]$ is uniform versus far from uniform. For general distributions this takes $\Theta(\sqrt{n})$ samples, so one might expect the corresponding problem for monotone distributions to need $\sqrt{\log n}$ samples; in fact, however, one can test this with a constant number of samples, by simply comparing the empirically observed probability masses of the left and right halves of the domain. An example in the other direction is the problem of finding a constant additive estimate for the entropy of a distribution. On domains of size $[n]$ this can be done in $\frac{n}{\log n}$ samples, and thus one might expect to be able to estimate entropy for monotone distributions on $[n]$ using $\frac{\log n}{\log\log n}$ samples. Nevertheless, it is not hard to see that $\Omega(\log^{2}n)$ samples are required.

The reduction-like techniques which we use to establish both our algorithmic results and our lower bounds (discussed in more detail in Section 1.2 below) reveal an unexpected relationship between the class of $k$-modal distributions of support $[n]$ and the class of general distributions of support $[k\log n]$. We hope that this reduction-based approach may provide a framework for the discovery of other relationships that will be useful in future work in the extreme sublinear regime of statistical property estimation and property testing.

Comparison with prior work. Our results significantly extend and improve upon the previous algorithmic results of Batu et al [BKR04] for identity testing of monotone or unimodal ($k=1$) distributions, which required $O(\log^{3}n)$ samples. More recently, [DDS11] established the sample complexity of learning $k$-modal distributions to be essentially $\Theta(k\log(n)\epsilon^{-3})$. Such a learning algorithm easily yields a testing algorithm with the same sample complexity for all four variants of the testing problem (one can simply run the learner twice to obtain hypotheses ${\widehat{p}}$ and ${\widehat{q}}$ that are sufficiently close to $p$ and $q$ respectively, and output accordingly).

While the [DDS11] result can be applied to our testing problems (though giving suboptimal results), we stress that the ideas underlying [DDS11] and this paper are quite different. The [DDS11] paper learns a $k$-modal distribution by using a known algorithm for learning monotone distributions [Bir87b] $k$ times in a black-box manner; the notion of reducing the domain size—which we view as central to the results and contributions of this paper—is nowhere present in [DDS11]. By contrast, the focus in this paper is on introducing the use of reductions as a powerful (but surprisingly, seemingly previously unused) tool in the development of algorithms for basic statistical tasks on distributions, which, at least in this case, is capable of giving essentially optimal upper and lower bounds for natural restricted classes of distributions.

2 Techniques.

Our main conceptual contribution is a new reduction-based approach that lets us obtain all our upper and lower bounds in a clean and unified way. The approach works by reducing the monotone and $k$-modal distribution testing problems to general distribution testing and estimation problems over a much smaller domain, and vice versa. For the monotone case this smaller domain is essentially of size $\log(n)/\epsilon$, and for the $k$-modal case the smaller domain is essentially of size $k\log(n)/\epsilon^{2}.$ By solving the general distribution problems over the smaller domain using known results we get a valid answer for the original (monotone or $k$-modal) problems over domain $[n]$. More details on our algorithmic reduction are given in Section A.

The inspiration for our results is an observation of Birgé [Bir87b] that given a monotone-decreasing probability distribution over $[n]$, if one subdivides $[n]$ into an exponentially increasing series of consecutive sub-intervals, the $i$th having size $(1+\epsilon)^{i}$, then if one replaces the probability mass on each interval with a uniform distribution on that interval, the distribution changes by only $O(\epsilon)$ in total variation distance. Further, given such a subdivision of the support into $\log_{1+\epsilon}(n)$ intervals, one may essentially treat the original monotone distribution as essentially a distribution over these intervals, namely a distribution of support $\log_{1+\epsilon}(n)$. In this way, one may hope to reduce monotone distribution testing or estimation on $[n]$ to general distribution testing or estimation on a domain of size $\log_{1+\epsilon}(n)$, and vice versa. See Section B for details.

Notation and Preliminaries

We write $[n]$ to denote the set $\{1,\ldots,n\}$, and for integers $i\leq j$ we write $[i,j]$ to denote the set $\{i,i+1,\ldots,j\}$. We consider discrete probability distributions over $[n]$, which are functions $p:[n]\to$ such that $\mathop{{\textstyle\sum}}_{i=1}^{n}p(i)=1$. For $S\subseteq[n]$ we write $p(S)$ to denote $\mathop{{\textstyle\sum}}_{i\in S}p(i)$. We use the notation $P$ for the cumulative distribution function (cdf) corresponding to $p$, i.e. $P:[n]\to$ is defined by $P(j)=\mathop{{\textstyle\sum}}_{i=1}^{j}p(i)$.

A distribution $p$ over $[n]$ is non-increasing (resp. non-decreasing) if $p(i+1)\leq p(i)$ (resp. $p(i+1)\geq p(i)$), for all $i\in[n-1]$; $p$ is monotone if it is either non-increasing or non-decreasing. Thus the “orientation” of a monotone distribution is either non-decreasing (denoted $\uparrow$) or non-increasing (denoted $\downarrow$).

We call a nonempty interval $I=[a,b]\subseteq[2,n-1]$ a max-interval of $p$ if $p(i)=c$ for all $i\in I$ and $\max\{p(a-1),p(b+1)\}<c$. Analogously, a min-interval of $p$ is an interval $I=[a,b]\subseteq[2,n-1]$ with $p(i)=c$ for all $i\in I$ and $\min\{p(a-1),p(b+1)\}>c$. We say that $p$ is $k$-modal if it has at most $k$ max-intervals and min-intervals. We note that according to our definition, what is usually referred to as a bimodal distribution is a $3$-modal distribution.

Finally, a sub-distribution is a function $q:[n]\to$ which satisfies $\mathop{{\textstyle\sum}}_{i=1}^{n}q(i)\leq 1.$ For $p$ a distribution over $[n]$ and $I\subseteq[n]$, the restriction of $p$ to $I$ is the sub-distribution $p^{I}$ defined by $p^{I}(i)=p(i)$ if $i\in I$ and $p^{I}(i)=0$ otherwise. Likewise, we denote by $p_{I}$ the conditional distribution of $p$ on $I$, i.e. $p_{I}(i)=p(i)/p(I)$ if $i\in I$ and $p_{I}(i)=0$ otherwise.

2 Basic tools from probability.

We will require the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality ([DKW56]) from probability theory. This basic fact says that $O(1/\epsilon^{2})$ samples suffice to learn any distribution within error $\epsilon$ with respect to the Kolmogorov distance. More precisely, let $p$ be any distribution over $[n].$ Given $m$ independent samples $s_{1},\dots,s_{m}$ drawn from $p:[n]\to,$ the empirical distribution ${\widehat{p}}_{m}:[n]\to$ is defined as follows: for all $i\in[n]$, ${\widehat{p}}_{m}(i)=|\{j\in[m]\mid s_{j}=i\}|/m$. The DKW inequality states that for $m=\Omega((1/\epsilon^{2})\cdot\ln(1/\delta))$, with probability $1-\delta$ the empirical distribution ${\widehat{p}}_{m}$ will be $\epsilon$-close to $p$ in Kolmogorov distance. This sample bound is asymptotically optimal and independent of the support size.

Another simple result that we will need is the following, which is easily verified from first principles:

Let $I=[a,b]$ be an interval and let $u_{I}$ denote the uniform distribution over $I.$ Let $p_{I}$ denote a non-increasing distribution over $I$. Then for every initial interval $I^{\prime}=[a,b^{\prime}]$ of $I$, we have $u_{I}(I^{\prime})\leq p_{I}(I^{\prime}).$

3 Testing and estimation for arbitrary distribution

If $p\equiv q$ then with probability at least $1-\delta$ the algorithm outputs “accept;” and

If $p\equiv q$ then with probability at least $1-\delta$ the algorithm outputs “accept;” and

Testing and Estimating Monotone Distributions

Our main tool for testing monotone distributions is an oblivious decomposition of monotone distributions that is a variant of a construction of Birgé [Bir87b]. As we will see it enables us to reduce the problem of testing a monotone distribution to the problem of testing an arbitrary distribution over a much smaller domain.

The following simple lemma, proved in Section A, shows why reduced distributions are useful for us:

We now state our oblivious decomposition result for monotone distributions:

There is an analogous version of Theorem 5, asserting the existence of an “oblivious” partition for non-decreasing distributions (which is of course different from the “oblivious” partition ${\cal I}$ for non-increasing distributions of Theorem 5); this will be useful later.

While our construction is essentially that of Birgé, we note that the version given in [Bir87b] is for non-increasing distributions over the continuous domain $[0,n]$, and it is phrased rather differently. Adapting the arguments of [Bir87b] to our discrete setting of distributions over $[n]$ is not conceptually difficult but requires some care. For the sake of being self-contained we provide a self-contained proof of the discrete version, stated above, that we require in Appendix E.

2 Efficiently testing monotone distributions

From Monotone to k𝑘k-modal

In this section we establish our main positive testing results for $k$-modal distributions, the upper bounds stated in the final four rows of Table 1. In the previous section, we were able to use the oblivious decomposition to yield a partition of $[n]$ into relatively few intervals, with the guarantee that the corresponding flattened distribution is close to the true distribution. The main challenge in extending these results to unimodal or $k$-modal distributions, is that in order to make the analogous decomposition, one must first determine–by taking samples from the distribution–which regions are monotonically increasing vs decreasing. Our algorithm Construct-Flat-Decomposition$(p,\epsilon,\delta)$ performs this task with the following guarantee:

The following terminology will be useful: Let ${\cal I}=\{I_{i}\}_{i=1}^{r}$ and ${\cal I}^{\prime}=\{I^{\prime}_{i}\}_{i=1}^{s}$ be two partitions of $[n]$ into $r$ and $s$ intervals respectively. The common refinement of ${\cal I}$ and ${\cal I}^{\prime}$ is the partition ${\cal J}$ of $[n]$ into intervals obtained from ${\cal I}$ and ${\cal I}^{\prime}$ in the obvious way, by taking all possible nonempty intervals of the form $I_{i}\cap I^{\prime}_{j}.$ It is clear that ${\cal J}$ is both a refinement of ${\cal I}$ and of ${\cal I}^{\prime}$ and that the number of intervals $|{\cal J}|$ in ${\cal J}$ is at most $r+s.$ We prove the following lemma in Section A:

Let $p$ be any distribution over $[n]$, let ${\cal I}=\{I_{i}\}_{i=1}^{a}$ be a $(p,\epsilon,a)$-flat decomposition of $[n]$, and let ${\cal J}=\{J_{i}\}_{i=1}^{b}$ be a refinement of ${\cal I}.$ Then ${\cal J}$ is a $(p,2\epsilon,b)$-flat decomposition of $[n]$.

We describe the Test-Identity-Known-kmodal algorithm below.

The modifications required to obtain algorithms Test-Identity-Unknown-kmodal, $L_{1}$-Estimate-Known-kmodal and $L_{1}$-Estimate-Unknown-kmodal, and the analysis of these algorithms, are completely analogous to the modifications and analyses of Section 3.2 and are omitted.

We present Construct-Flat-Decomposition$(p,\epsilon,\delta)$ followed by an intuitive explanation. Note that it employs a procedure Orientation$({\widehat{p}},I)$, which uses no samples and is presented and analyzed in Section 4.2.

Roughly speaking, when Construct-Flat-Decomposition constructs a partition ${\cal I}$, it initially breaks $[n]$ up into two types of intervals. The first type are intervals that are “okay” to include in a flat decomposition, either because they have very little mass, or because they consist of a single point, or because they are close to uniform. The second type are intervals that are “not okay” to include in a flat decomposition – they have significant mass and are far from uniform – but the algorithm is able to ensure that almost all of these are monotone distributions with a known orientation. It then uses the oblivious decomposition of Theorem 5 to construct a flat decomposition of each such interval. (Note that it is crucial that the orientation is known in order to be able to use Theorem 5.)

In more detail, Construct-Flat-Decomposition$(p,\epsilon,\delta)$ works as follows. The algorithm first draws a batch of samples from $p$ and uses them to construct an estimate ${\widehat{p}}$ of the CDF of $p$ (this is straightforward using the DKW inequality). Using ${\widehat{p}}$ the algorithm partitions $[n]$ into a collection of $O(k/\epsilon)$ disjoint intervals in the following way:

A small collection of the intervals are “negligible”; they collectively have total mass less than $\epsilon$ under $p$. Each negligible interval $I$ will be an element of the partition ${\cal I}.$

Some of the intervals are “heavy points”; these are intervals consisting of a single point that has mass $\Omega(\epsilon/k)$ under $p$. Each heavy point $I$ will also be an element of the partition ${\cal I}.$

The remaining intervals are “moderate” intervals, each of which has mass $\Theta(\epsilon/k)$ under $p$.

2 The Orientation algorithm.

The Orientation algorithm takes as input an explicit distribution of a distribution ${\widehat{p}}$ over $[n]$ and an interval $I\subseteq[n].$ Intuitively, it assumes that ${\widehat{p}}_{I}$ is close (in Kolmogorov distance) to a monotone distribution $p_{I}$, and its goal is to determine the orientation of $p_{I}$: it outputs either $\uparrow$, $\downarrow$ or $\bot$ (the last of which means “close to uniform”). The algorithm is quite simple; it checks whether there exists an initial interval $I^{\prime}$ of $I$ on which ${\widehat{p}}_{I}$’s weight is significantly different from $u_{I}(I^{\prime})$ (the weight that the uniform distribution over $I$ assigns to $I^{\prime}$) and bases its output on this in the obvious way. A precise description of the algorithm (which uses no samples) is given below.

Orientation Inputs: explicit description of distribution ${\widehat{p}}$ over $[n]$; interval $I=[a,b]\subseteq[n]$ 1. If $|I|=1$ (i.e. $I=\{a\}$ for some $a\in[n]$) then return “$\bot$”, otherwise continue. 2. If there is an initial interval $I^{\prime}=[a,j]$ of $I$ that satisfies $u_{I}(I^{\prime})-({\widehat{p}})_{I}(I^{\prime})>{\frac{\epsilon}{7}}$ then halt and output “$\uparrow$”. Otherwise, 3. If there is an initial interval $I^{\prime}=[a,j]$ of $I$ that satisfies $u_{I}(I^{\prime})-({\widehat{p}})_{I}(I^{\prime})<-{\frac{\epsilon}{7}}$ then halt and output “$\downarrow$”. Otherwise, 4. Output “$\bot$”.

We proceed to analyze Orientation. We show that if $p_{I}$ is far from uniform then Orientation outputs the correct orientation for it. We also show that whenever Orientation does not output “$\bot$”, whatever it outputs is the correct orientation of $p_{I}$. The proof is given in Section C.3.

Let $p$ be a distribution over $[n]$ and let interval $I=[a,b]\subseteq[n]$ be such that $p_{I}$ is monotone. Suppose $p(I)\geq 99\epsilon/(10000k)$, and suppose that for every interval $I^{\prime}\subseteq I$ we have that $|{\widehat{p}}(I^{\prime})-p(I^{\prime})|\leq{\frac{\epsilon^{2}}{10000k}}.$ Then

If $p_{I}$ is non-decreasing and $p_{I}$ is $\epsilon/6$-far from the uniform distribution $u_{I}$ over $I$, then Orientation$({\widehat{p}},I)$ outputs “$\uparrow$”;

if Orientation$({\widehat{p}},I)$ outputs “$\uparrow$” then $p_{I}$ is non-decreasing;

if $p_{I}$ is non-increasing and $p_{I}$ is $\epsilon/6$-far from the uniform distribution $u_{I}$ over $I$, then Orientation$({\widehat{p}},I)$ outputs “$\downarrow$”;

if Orientation$({\widehat{p}},I)$ outputs “$\downarrow$” then $p_{I}$ is non-increasing.

Lower Bounds

Our algorithmic results follow from a reduction which shows how one can reduce the problem of testing properties of monotone or $k$-modal distributions to the task of testing properties of general distributions over a much smaller support. Our approach to proving lower bounds is complementary; we give a canonical scheme for transforming “lower bound instances” of general distributions to related lower bound instances of monotone distributions with much larger supports.

Definitions 2 and 3, given below, define a two-stage transformation of a generic distribution into a related $k$-modal distribution over a much larger support. This transformation preserves total variation distance: for any pair of distributions, the variation distance between their transformations is identical to the variation distance between the original distributions. Additionally, we ensure that given access to $s$ independent samples from an original input distribution, one can simulate drawing $s$ samples from the related $k$-modal distribution yielded by the transformation. Given any lower–bound construction $D$ for general distributions, the above transformation will yield a lower–bound instance $D_{k}$ for $(k-1)$-modal distributions (so monotone distributions correspond to $k=1$) defined by selecting a pair of distributions $(p,p^{\prime})\leftarrow D,$ then outputting the pair of transformed distributions. This transformed ensemble of distributions is a lower–bound instance, for if some algorithm could successfully test pairs of $(k-1)$-modal distributions from $D_{k},$ then that algorithm could be used to test pairs from $D$, by simulating samples drawn from the transformed versions of the distributions. The following proposition, proved in Section D, summarizes the above discussion:

Before proving this proposition, we state various corollaries which result from applying the Proposition to known lower-bound constructions for general distributions. The first is for the “testing identity, $q$ is unknown” problem:

This Corollary gives the lower bounds stated in lines 2 and 6 of Table 1. It follows from applying Proposition 6 to a (trivially modified) version of the lower bound construction given in [BFR+00, Val08b], summarized by the following theorem:

Our second corollary is for $L_{1}$ estimation, in the case that one of the distributions is explicitly given. This trivially also yields an equivalent lower bound for the setting in which both distributions are given via samples.

This Corollary gives the lower bounds claimed in lines 3, 4, 7 and 8 of Table 1. It follows from applying Proposition 6 to the lower bound construction given in [VV11a], summarized by the following theorem:

Note that the above theorem can be expressed in the language of Proposition 6 by defining the distribution $D^{\prime}$ over pairs of distributions which chooses a distribution according to $D$ for the first distribution of each pair, and always selects $u_{n}$ for the second distribution of each pair.

Our third corollary, which gives the lower bounds claimed in lines 1 and 5 of Table 1, is for the “testing identity, $q$ is known” problem:

The above corollary follows from applying Proposition 6 to the following trivially verified lower bound construction:

As noted previously (after Theorem 7), this fact can also be expressed in the language of Proposition 6.

Conclusions

We have introduced a simple new approach for tackling distribution testing problems for restricted classes of distributions, by reducing them to general-distribution testing problems over a smaller domain. We applied this approach to get new testing results for a range of distribution testing problems involving monotone and $k$-modal distributions, and established lower bounds showing that all our new algorithms are essentially optimal.

A general direction for future work is to apply our reduction method to obtain near-optimal testing algorithms for other interesting classes of distributions. This will involve constructing flat decompositions of various types of distributions using few samples, which seems to be a natural and interesting algorithmic problem. A specific goal is to develop a more efficient version of our Construct-Flat-Decomposition algorithm for $k$-modal distributions; is it possible to obtain an improved version of this algorithm that uses $o(k)$ samples?

References

Appendix A Shrinking the domain size: Reductions for distribution-testing problems

In this section we present the general framework of our reduction-based approach and sketch how we instantiate this approach for monotone and $k$-modal distributions.

The following useful lemma relates closeness of $p$ and $q$ to closeness of the reduced distributions:

We close this section with a result about partitions and flat decompositions which will be useful later. Let ${\cal I}=\{I_{i}\}_{i=1}^{a},$ ${\cal I}^{\prime}=\{I^{\prime}_{j}\}_{j=1}^{b}$ be two partitions of $[n]$. We say that ${\cal I}^{\prime}$ is a refinement of ${\cal I}$ if for every $i\in[a]$ there is a subset $S_{i}$ of $[b]$ such that $\cup_{j\in S_{i}}I^{\prime}_{j}=I_{i}$ (note that for this to hold we must have $a\leq b$). Note that $\{S_{i}\}_{i=1}^{a}$ forms a partition of $[b]$. We prove the following useful lemma:

Lemma 4. Let $p$ be any distribution over $[n]$, let ${\cal I}=\{I_{i}\}_{i=1}^{a}$ be a $(p,\epsilon,a)$-flat decomposition of $[n]$, and let ${\cal J}=\{J_{i}\}_{i=1}^{b}$ be a refinement of ${\cal I}.$ Then ${\cal J}$ is a $(p,2\epsilon,b)$-flat decomposition of $[n]$.

We now proceed to establish (1). Let $T\subseteq[n]$ and consider a partition of $T$ into $k$ nonempty sets $T_{i}$, $i\in[k]$. Denote $\mu\stackrel{{\scriptstyle\textrm{def}}}{{=}}p(T)/|T|$ and $\mu_{i}\stackrel{{\scriptstyle\textrm{def}}}{{=}}p(T_{i})/|T_{i}|$. Then, (1) can be re-expressed as follows

We shall prove the above statement for all sequences of numbers $p(1),\dots,p(n)$. Since adding or subtracting the same quantity from each number $p(t)$ does not change the validity of (2), for the sake of convenience we may assume all the numbers average to , that is, $\mu=0$. Consider the $i$-th term on the right hand side, $\mathop{{\textstyle\sum}}_{t\in T_{i}}|p(t)-\mu_{i}|$. We can bound this quantity from above as follows:

where the inequality follows from the triangle inequality (applied term by term), the first equality is by the definition of $\mu_{i}$, the second equality is trivial, and the final equality uses the assumption that $\mu=0$. The lemma follows by summing over $i\in[k]$, using the fact that the $T_{i}$’s form a partition of $T$. ∎

Appendix B Efficiently Testing Monotone Distributions

Our main tool for testing monotone distributions is an oblivious decomposition of monotone distributions that is a variant of a construction of Birgé [Bir87b]. As we will see it enables us to reduce the problem of testing a monotone distribution to the problem of testing an arbitrary distribution over a much smaller domain. The decomposition result is given below:

There is a dual version of Theorem 5, asserting the existence of an “oblivious” partition for non-decreasing distributions (which is of course different from the “oblivious” partition ${\cal I}$ for non-increasing distributions of Theorem 5); this will be useful later.

While our construction is essentially that of Birgé, we note that the version given in [Bir87b] is for non-increasing distributions over the continuous domain $[0,n]$, and it is phrased rather differently. Adapting the arguments of [Bir87b] to our discrete setting of distributions over $[n]$ is not conceptually difficult but requires some care. For the sake of being self-contained we provide a self-contained proof of the discrete version, stated above, that we require in Appendix E.

B.2 Efficiently testing monotone distributions

Appendix C Efficiently Testing k𝑘k-modal Distributions

In this section we establish our main positive testing results for $k$-modal distributions, the upper bounds stated in the final four rows of Table 1. The key to all these results is an algorithm Construct-Flat-Decomposition$(p,\epsilon,\delta)$. We prove the following performance guarantee about this algorithm:

The following terminology will be useful: Let ${\cal I}=\{I_{i}\}_{i=1}^{r}$ and ${\cal I}^{\prime}=\{I^{\prime}_{i}\}_{i=1}^{s}$ be two partitions of $[n]$ into $r$ and $s$ intervals respectively. The common refinement of ${\cal I}$ and ${\cal I}^{\prime}$ is the partition ${\cal J}$ of $[n]$ into intervals obtained from ${\cal I}$ and ${\cal I}^{\prime}$ in the obvious way, by taking all possible nonempty intervals of the form $I_{i}\cap I^{\prime}_{j}.$ It is clear that ${\cal J}$ is both a refinement of ${\cal I}$ and of ${\cal I}^{\prime}$ and that the number of intervals $|{\cal J}|$ in ${\cal J}$ is at most $r+s.$

The modifications required to obtain algorithms Test-Identity-Unknown-kmodal, $L_{1}$-Estimate-Known-kmodal and $L_{1}$-Estimate-Unknown-kmodal, and the analysis of these algorithms, are completely analogous to the modifications and analyses of Appendix B.2 and are omitted.

We present Construct-Flat-Decomposition$(p,\epsilon,\delta)$ followed by an intuitive explanation. Note that it employs a procedure Orientation$({\widehat{p}},I)$, which uses no samples and is presented and analyzed in Section 4.2.

Roughly speaking, when Construct-Flat-Decomposition constructs a partition ${\cal I}$, it initially breaks $[n]$ up into two types of intervals. The first type are intervals that are “okay” to include in a flat decomposition, either because they have very little mass, or because they consist of a single point, or because they are close to uniform. The second type are intervals that are “not okay” to include in a flat decomposition – they have significant mass and are far from uniform – but the algorithm is able to ensure that almost all of these are monotone distributions with a known orientation. It then uses the oblivious decomposition of Theorem 5 to construct a flat decomposition of each such interval. (Note that it is crucial that the orientation is known in order to be able to use Theorem 5.)

In more detail, Construct-Flat-Decomposition$(p,\epsilon,\delta)$ works as follows. The algorithm first draws a batch of samples from $p$ and uses them to construct an estimate ${\widehat{p}}$ of the CDF of $p$ (this is straightforward using the DKW inequality). Using ${\widehat{p}}$ the algorithm partitions $[n]$ into a collection of $O(k/\epsilon)$ disjoint intervals in the following way:

A small collection of the intervals are “negligible”; they collectively have total mass less than $\epsilon$ under $p$. Each negligible interval $I$ will be an element of the partition ${\cal I}.$

Some of the intervals are “heavy points”; these are intervals consisting of a single point that has mass $\Omega(\epsilon/k)$ under $p$. Each heavy point $I$ will also be an element of the partition ${\cal I}.$

The remaining intervals are “moderate” intervals, each of which has mass $\Theta(\epsilon/k)$ under $p$.

C.2 Performance of Construct-Flat-Decomposition: Proof of Lemma 3.

The claimed sample bound is obvious from inspection of the algorithm, as the only step that draws any samples is Step 2. The bound on the number of intervals in the flat decomposition follows directly from the upper bounds on the number of heavy points, negligible intervals and moderate intervals shown below, using also Theorem 5. It remains to show that the output of the algorithm is a valid flat decomposition of $p$. First, by the DKW inequality (Theorem 1) we have that with probability at least $1-\delta$ it is the case that

We make some preliminary observations about the weight that $p$ has on the intervals constructed in Steps 4 and 5. Since every atomic interval $I_{i}$ constructed in Step 4 has ${\widehat{p}}(I)\geq\epsilon/(100k)$ (except potentially the rightmost one), it follows that the number $\alpha$ of atomic intervals constructed in Step 3 satisfies

We now establish bounds on the probability mass that $p$ assigns to the moderate intervals, heavy points, and negligible intervals that are constructed in Step 4. Using (3), each interval $I_{i}$ that is declared to be a moderate interval in Step 4(a) must satisfy

By virtue of the greedy process that is used to construct atomic intervals in Step 3, each point $b$ that is declared to be a heavy point in Step 4(b) must satisfy ${\widehat{p}}(b)\geq 2\epsilon/(100k)$ and thus using (3) again

Moreover, each interval $[a,b-1]$ that is declared to be a negligible interval must satisfy ${\widehat{p}}([a,b-1])<\epsilon/(100k)$ and thus using (3) again

It is clear that $n_{m}$ (the number of moderate intervals) and $n_{h}$ (the number of heavy points) are each at most $\alpha.$ Next we observe that the number of negligible intervals $n_{n}$ satisfies

This is because at the end of each negligible interval $[a,b-1]$ we have (observing that each negligible interval must be nonempty) that $p(b-1)\leq p([a,b-1])\leq 101\epsilon/(10000k)$ while $p(b)\geq 199\epsilon/(10000k)$. Since $p$ is $k$-modal, there can be at most $\lceil(k+1)/2\rceil\leq k$ points $b\in[n]$ satisfying this condition. Since each negligible interval $I$ satisfies $p(I)\leq 101\epsilon/(10000k)$ we have that the total probability mass under $p$ of all the negligible intervals is at most $101\epsilon/10000.$

Thus far we have built a partition of $[n]$ into a collection of $n_{m}\leq\lceil 100k/\epsilon\rceil$ moderate intervals (which we denote $M_{1},\dots,M_{n_{m}}$), a set of $n_{h}\leq\lceil 100k/\epsilon\rceil$ heavy points (which we denote $h_{1},\dots,h_{n_{h}}$) and a set of $n_{n}\leq k$ negligible intervals (which we denote $N_{1},\dots,N_{n_{n}}$). Let $A\subseteq\{1,\dots,n_{m}\}$ denote the set of those indices $i$ such that Orientation$({\widehat{p}},M_{i})$ outputs $\bot$ in Step 6. The partition ${\cal I}$ that Construct-Flat-Decomposition constructs consists of $\{h_{1}\},\dots,\{h_{n_{h}}\}$, $N_{1},\dots,N_{n_{n}}$, $\{M_{i}\}_{i\in A}$, and $\bigcup_{i\in([n_{m}]\setminus A)}{\cal J}_{M_{i}}.$ We can thus write $p$ as

Using Lemma 15 (proved in Appendix F) we can bound the total variation distance between $p$ and $(p_{f})^{\cal I}$ by

Since $p(I)=(p_{f})^{\cal I}(I)$ for every $I\in{\cal I}$, this simplifies to

Recalling from (6) that $p(N_{j})\leq 101\epsilon/(10000k)$ for each negligible interval $N_{j}$, and recalling that $n_{n}\leq k$, the first summand in (9) is at most $101\epsilon/10000.$

Let $B\subset[n_{m}]\setminus A$ be such that, for all $j\in B$, $p_{M_{j}}$ is monotone. Summing the above over all $j\in B$ gives:

Given that $p$ is $k$-modal, the cardinality of the set $[n_{m}]\setminus(A\cup B)$ is at most $k$. So we have the bound:

C.3 The Orientation algorithm.

The Orientation algorithm takes as input an explicit distribution of a distribution ${\widehat{p}}$ over $[n]$ and an interval $I\subseteq[n].$ Intuitively, it assumes that ${\widehat{p}}_{I}$ is close (in Kolmogorov distance) to a monotone distribution $p_{I}$, and its goal is to determine the orientation of $p_{I}$: it outputs either $\uparrow$, $\downarrow$ or $\bot$ (the last of which means “close to uniform”). The algorithm is quite simple; it checks whether there exists an initial interval $I^{\prime}$ of $I$ on which ${\widehat{p}}_{I}$’s weight is significantly different from $u_{I}(I^{\prime})$ (the weight that the uniform distribution over $I$ assigns to $I^{\prime}$) and bases its output on this in the obvious way. A precise description of the algorithm (which uses no samples) is given below.

Orientation Inputs: explicit description of distribution ${\widehat{p}}$ over $[n]$; interval $I=[a,b]\subseteq[n]$ 1. If $|I|=1$ (i.e. $I=\{a\}$ for some $a\in[n]$) then return “$\bot$”, otherwise continue. 2. If there is an initial interval $I^{\prime}=[a,j]$ of $I$ that satisfies $u_{I}(I^{\prime})-({\widehat{p}})_{I}(I^{\prime})>{\frac{\epsilon}{7}}$ then halt and output “$\uparrow$”. Otherwise, 3. If there is an initial interval $I^{\prime}=[a,j]$ of $I$ that satisfies $u_{I}(I^{\prime})-({\widehat{p}})_{I}(I^{\prime})<-{\frac{\epsilon}{7}}$ then halt and output “$\downarrow$”. Otherwise, 4. Output “$\bot$”.

We proceed to analyze Orientation. We show that if $p_{I}$ is far from uniform then Orientation outputs the correct orientation for it. We also show that whenever Orientation does not output “$\bot$”, whatever it outputs is the correct orientation of $p_{I}$. For ease of readability, for the rest of this subsection we use the following notation:

Lemma 5. Let $p$ be a distribution over $[n]$ and let interval $I=[a,b]\subseteq[n]$ be such that $p_{I}$ is monotone. Suppose $p(I)\geq 99\epsilon/(10000k)$, and suppose that for every interval $I^{\prime}\subseteq I$ we have that

If $p_{I}$ is non-decreasing and $p_{I}$ is $\epsilon/6$-far from the uniform distribution $u_{I}$ over $I$, then Orientation$({\widehat{p}},I)$ outputs “$\uparrow$”;

if Orientation$({\widehat{p}},I)$ outputs “$\uparrow$” then $p_{I}$ is non-decreasing;

if $p_{I}$ is non-increasing and $p_{I}$ is $\epsilon/6$-far from the uniform distribution $u_{I}$ over $I$, then Orientation$({\widehat{p}},I)$ outputs “$\downarrow$”;

if Orientation$({\widehat{p}},I)$ outputs “$\downarrow$” then $p_{I}$ is non-increasing.

Let $I^{\prime}=[a,j]\subseteq I$ be any initial interval of $I.$ We first establish the upper bound

as this will be useful for the rest of the proof. Using (10) we have

Now using the fact that $p(I^{\prime})\leq p(I)$ and $p(I)\geq 99\epsilon/(10000k)$, we get that (12) is at least

So we have established the lower bound $p_{I}(I^{\prime})-({\widehat{p}})_{I}(I^{\prime})\geq-\epsilon/49.$ For the upper bound, similar reasoning gives

and so we have shown that $|p_{I}(I^{\prime})-({\widehat{p}})_{I}(I^{\prime})|\leq\epsilon/49$ as desired. Now we proceed to prove the lemma.

and thus Orientation outputs “$\uparrow$” in Step 3 as claimed.

Now we turn to Part 2 of the lemma. Suppose that Orientation$({\widehat{p}},I)$ outputs “$\uparrow$”. Then it must be the case that there is an initial interval $I^{\prime}=[a,j]$ of $I$ that satisfies $u_{I}(I^{\prime})-({\widehat{p}})_{I}(I^{\prime})>{\frac{\epsilon}{7}}.$ By (11) we have that $u_{I}(I^{\prime})-p_{I}(I^{\prime})>{\frac{\epsilon}{7}}-{\frac{\epsilon}{49}}={\frac{6\epsilon}{49}}$. But Observation 1 tells us that if $p_{I}$ were non-increasing then we would have $u_{I}(I^{\prime})-p_{I}(I^{\prime})\leq 0$; so $p_{I}$ cannot be non-increasing, and therefore it must be non-decreasing.

Finally, Part 4 of the lemma follows from analogous arguments as Part 2.∎

Appendix D Proof of Proposition 6

We start by defining the transformation, and then prove the necessary lemmas to show that the transformation yields $k$-modal distributions with the specified increase in support size, preserves $L_{1}$ distance between pairs, and has the property that samples from the transformed distributions can be simulated given access to samples from the original distributions.

The transformation proceeds in two phases. In the first phase, the input distribution $p$ is transformed into a related distribution $f$ with larger support; $f$ has the additional property that the ratio of the probabilities of consecutive domain elements is bounded. Intuitively the distribution $f$ corresponds to a “reduced distribution” from Section A. In the second phase, the distribution $f$ is transformed into the final $2(k-1)$-modal distribution $g$. Both stages of the transformation consist of subdividing each element of the domain of the input distribution into a set of elements of the output distribution; in the first stage, the probabilities of each element of the set are chosen according to a geometric sequence, while in the second phase, all elements of each set are given equal probabilities.

We now define this two-phase transformation and prove Proposition 6.

Fix $\epsilon>0$ and a distribution $p$ over $[n]$ such that $p_{min}\leq p(i)\leq p_{max}$ for all $i\in[n].$ We define the distribution $f_{p,\epsilon,p_{max},p_{min}}$in two steps. Let $q$ be the distribution on support $[c]$ with $c=1+\lceil\log_{1+\epsilon}p_{max}-\log_{1+\epsilon}p_{min}\rceil$ that is defined by $q(i)=(1+\epsilon)^{i-1}\frac{\epsilon}{(1+\epsilon)^{c}-1}.$ The distribution $f_{p,\epsilon,p_{max},p_{min}}$ has support $[cn]$, and for $i\in[n]$ and $j\in[c]$ it assigns probability $p(i)q(j)$ to domain element $c(i-1)+j.$

It is convenient for us to view the $\mod r$ operator as giving an output in $[r]$, so that “$r\mod r$” equals $r.$

Given $\epsilon,p_{min},p_{max},$ and access to independent samples from distribution $p$, one can generate independent samples from $f_{p,\epsilon,p_{max},p_{min}}$ and from $g_{k,p,\epsilon,p_{max},p_{min}}.$

To generate a sample according to $f_{p,\epsilon,p_{max},p_{min}},$ one simply takes a sample $i\leftarrow p$ and then draws $j\in[c]$ according to the distribution $q$ as defined in Definition 2 (note that this draw according to $q$ only involves $\epsilon,p_{min}$ and $p_{max}$). We then output the value $c(i-1)+j.$ It follows immediately from the above definition that the distribution of the output value is $f_{p,\epsilon,p_{max},p_{min}}.$

and thus $g_{1,p,\epsilon,p_{max},p_{min}}$ is indeed 0-modal since it is monotone non-increasing. For $k>1$ the above arguments apply to each of the $k$ equally-sized contiguous regions of the support, so there are $2(k-1)$ modes, namely the local maxima occurring at the right endpoint of each region, and the local minima occurring at the left endpoint of each region. ∎

For any distributions $p,p^{\prime}$ with support $[n]$, and any $\epsilon,p_{max},p_{min},$ we have that

Both equalities follow immediately from the fact that the transformations of Definitions 2 and 3 partition each element of the input distribution in a manner that is oblivious to the probabilities. To illustrate, letting $c=1+\lceil\log_{1+\epsilon}p_{max}-\log_{1+\epsilon}p_{min}\rceil,$ and letting $q$ be as in Definition 2, we have the following:

If $p$ has support $[n],$ then for any $\epsilon<1/2,$ the distribution $g_{k,p,\epsilon,p_{max},p_{min}}$ is supported on $[N]$, where $N$ is at most $k\frac{e^{\frac{8n}{k}\left(1+\log(p_{max}/p_{min})\right)}}{\epsilon^{2}}$.

The support of $f_{p,\epsilon,p_{max},p_{min}}$ is $n(1+\lceil\log_{1+\epsilon}p_{max}-\log_{1+\epsilon}p_{min}\rceil)\leq n\left(2+\frac{\log(p_{max}/p_{min})}{\log(1+\epsilon)}\right).$ Letting $a_{1}:=1$ and $b_{1}:=\lceil\frac{1}{\epsilon}\rceil,$ and defining $a_{i}:=\lceil a_{i-1}(1+\epsilon)\rceil,$ and $b_{i}:=\lceil b_{i-1}(1+\epsilon)\rceil,$ we have that $a_{i}\leq b_{i}$ for all $i$. Additionally, $b_{i+1}/b_{i}\leq 1+2\epsilon$, since all $b_{i}\geq 1/\epsilon,$ and thus the ceiling operation can increase the value of $(1+\epsilon)b_{i}$ by at most $\epsilon b_{i}$. Putting these two observations together, we have

For any $\epsilon\leq 1/2,$ we have that the support of $g_{k,p,1/2,p_{max},p_{min}}$ is at most

The proof is now a simple matter of assembling the above parts. Given a distribution $D$ over pairs of distributions of support $[n],$ as specified in the proposition statement, the distribution $D_{k}$ is defined via the process of taking $(p,p^{\prime})\leftarrow D,$ then applying the transformation of Definitions 2 and 3 with $\epsilon=1/2$ and to yield a pair $\left(g_{k,p,1/2,p_{max},p_{min}},g_{k,p^{\prime},1/2,p_{max},p_{min}}\right)$. We claim that this $D_{k}$ satisfies all the properties claimed in the proposition statement. Specifically, Lemmas 12 and 14, respectively, ensure that every distribution in the support of $D_{k}$ has at most $2(k-1)$ modes, and has support size at most $4ke^{\frac{8n}{k}\left(1+\log(p_{max}/p_{min})\right)}.$ Additionally, Lemma 13 guarantees that the transformation preserves $L_{1}$ distance, namely, for two distributions $p,p^{\prime}$ with support $[n],$ we have $L_{1}(p,p^{\prime})=L_{1}(g_{k,p,1/2,p_{max},p_{min}},g_{k,p^{\prime},1/2,p_{max},p_{min}}).$ Finally, Lemma 11 guarantees that, given $s$ independent samples from $p$, one can simulate drawing $s$ independent samples according to $g_{k,p,1/2,p_{max},p_{min}}.$ Assuming for the sake of contradiction that one had an algorithm that could distinguish whether $L_{1}(g_{k,p,1/2,p_{max},p_{min}},g_{k,p^{\prime},1/2,p_{max},p_{min}})$ is less than $\epsilon_{1}$ versus greater than $\epsilon_{2}$ with the desired probability given $s$ samples, one could take $s$ samples from distributions $(p,p^{\prime})\leftarrow D$, simulate having drawn them from $g_{k,p,1/2,p_{max},p_{min}}$ and $g_{k,p^{\prime},1/2,p_{max},p_{min}},$ and then run the hypothesized tester algorithm on those samples, and output the answer, which will be the same for $(p,p^{\prime})$ as for $(g_{k,p,1/2,p_{max},p_{min}},g_{k,p^{\prime},1/2,p_{max},p_{min}}).$ This contradicts the assumption that no algorithm with these success parameters exists for $(p,p^{\prime})\leftarrow D.$ ∎

Appendix E Proof of Theorem 5

We first note that we can assume that $\epsilon>1/n$. Otherwise, the decomposition of $[n]$ into singleton intervals $I_{i}=\{i\}$, $i\in[n]$, trivially satisfies the statement of the theorem. Indeed, in this case we have that $(1/\epsilon)\cdot\log n>n$ and $p_{f}\equiv p$.

Let $p$ be any non-increasing distribution over $[n]$. We will now show that the above described decomposition satisfies

where $p^{I}$ denotes the (sub-distribution) restriction of $p$ over $I$.

Let $I_{j}=[n_{j-1}+1,n_{j}]$ with $l_{j}=|I_{j}|=n_{j}-n_{j-1}$. Then we have that

Recall that $p_{f}$ is by definition constant within each $I_{j}$ and in particular equal to $\bar{p}_{f}^{j}=\mathop{{\textstyle\sum}}_{i=n_{j-1}+1}^{n_{j}}p(i)/l_{j}$. Also recall that $p$ is non-increasing, hence $p(n_{j-1})\geq p(n_{j-1}+1)\geq\bar{p}_{f}^{j}\geq p(n_{j})$. Therefore, we can bound from above the variation distance within $I_{j}$ as follows

To bound the above quantity we analyze summands with $l_{j}<1/\epsilon$ and with $l_{j}\geq 1/\epsilon$ separately.

Consider the short intervals and cluster them into groups according to their length; that is, a group contains all intervals in $S$ of the same length. We denote by $G_{i}$ the $i$th group, which by definition contains all intervals in $S$ of length $i$; note that these intervals are consecutive. The cardinality of a group (denoted by $|\cdot|$) is the number of intervals it contains; the length of a group is the number of elements it contains (i.e. the sum of the lengths of the intervals it contains).

Note that $G_{1}$ (the group containing all singleton intervals) has $|G_{1}|=\Omega(1/\epsilon)$ (this follows from the assumption that $1/\epsilon<n$). Hence $G_{1}$ has length $\Omega(1/\epsilon)$. Let $j^{\ast}<1/\epsilon$ be the maximum length of any short interval in $S$. It is easy to verify that each group $G_{j}$ for $j\leq j^{\ast}$ is nonempty, and that for all $j\leq j^{\ast}-1$, we have $|G_{j}|=\Omega\left((1/\epsilon)\cdot(1/j)\right)$, which implies that the length of $G_{j}$ is $\Omega(1/\epsilon)$.

To bound the contribution to (13) from the short intervals, we consider the corresponding sum for each group, and use the fact that $G_{1}$ makes no contribution to the error. In particular, the contribution of the short intervals is

where $p^{-}_{l}$ (resp. $p^{+}_{l}$) is the probability mass of the leftmost (resp. rightmost) point in $G_{l}$. Given that $p$ is non-increasing, we have that $p^{+}_{l}\geq p^{-}_{l+1}$. Therefore, we can upper bound (14) by

Now note that $p^{+}_{1}=O(\epsilon)\cdot p(G_{1})$, since $G_{1}$ has length (total number of elements) $\Omega(1/\epsilon)$ and $p$ is non-increasing. Similarly, for $l<j^{\ast}$, we have that $p^{+}_{l}=O(\epsilon)\cdot p(G_{l})$, since $G_{l}$ has length $\Omega(1/\epsilon)$. Therefore, the above quantity can be upper bounded by