New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions

We develop a new technique for proving distribution testing lower bounds for properties defined by inequalities on the individual bin probabilities (such as monotonicity and log-concavity). The basic idea is to find a base distribution $Q$ where these inequalities barely hold in many places. We then find two different ensembles of distributions that modify $Q$ in slightly different ways. We use a moment matching construction so that each ensemble has the same bin moments (in particular the expectation over the choice of distribution $p$ of $p_{i}^t$ is the same for the two ensembles for small integers $t$). We show that this makes it impossible to distinguish between the two ensembles with a small number of samples. On the other hand, we construct them so that one ensemble will tweak Q in such a way that it may violate the defining inequalities of the property in question in many places, while the second ensembles does not. Since any valid tester for this property must be able to reliably distinguish these ensembles, we obtain a lower bound of testing the property. Roughly speaking, if we can construct Q which nearly violates the defining inequalities in n places and if the desired error $\epilon$ is small enough relative to n, we hope to obtain a lower bound of roughly $\frac{n}{\epsilon^2}$ up to log factors. In particular, we obtain a lower bound of $\Omega( \min(n,(1/\epsilon)/ \log^3(1/\epsilon))\allowbreak / ( \epsilon^2 \log^7(1/\epsilon)))$ for monotonicity testing on $[n]$ and $\Omega(\log^{-7}(1/\epsilon) \epsilon^{-2} \min(n,\epsilon^{-1/2}\log^{-3/2}(1/\epsilon)))$ for log-concavity testing on $[n]$, the latter of which matches known upper bounds to within logarithmic factors. More generally, for monotonicity testing on $[n]^d$, we have the lower bound of $2^{-O(d)}d^{-d} \epsilon^{-2} \log^{-7}(1/\epsilon) \min(n,d \epsilon^{-1} \log^{-3}(1/\epsilon))^d$.