A Competitive Test for Uniformity of Monotone Distributions.

Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha SureshAISTATS 2013 · OpenReview

Abstract

We propose a test that takes random samples drawn from a monotone distribution and decides whether or not the distribution is uniform. The test is nearly optimal in that it uses at most $O(n \sqrt{\log n})$ samples, where $n$ is the number of samples required by an all-knowing "genie" who only lacks a single bit of information about the distribution.

Introduction

In various scientific domains—from medicine to economics—researchers often need to determine if a set of observations follows a uniform distribution or exhibits a specific trend, such as a monotone increase or decrease. This problem is formally known as testing for uniformity against monotone alternatives.

Traditional statistical tests often rely on the $\ell_1$ distance (total variation) to measure the discrepancy from uniformity. However, the authors demonstrate that the $\ell_1$ distance can be misleading; two distributions may be equidistant from uniform in $\ell_1$ terms yet require significantly different sample sizes to distinguish. This paper addresses the challenge of creating an "instance-optimal" test that performs competitively against the best possible test for any specific distribution, shifting the focus from worst-case scenarios to distribution-specific performance.

Methodology: The $t_c$ Test

The authors introduce a novel test, $t_c$, which leverages the inherent shape of monotone distributions. The test is built upon two primary components:

1. Exponential Binning

Rather than using a standard uniform partition, the domain $[0, 1)$ is divided into $2k$ bins. These bins are structured such that their sizes increase exponentially toward the center and decrease toward the edges. This non-uniform binning is crucial for capturing the "jumps" or slopes of monotone distributions more efficiently than uniform binning.

The exponential binning strategy partitioning the domain into intervals.

2. Modified $\chi^2$ Test

Within these bins, a variation of Pearson’s chi-squared test is applied. The test measures the discrepancy between observed sample counts and expected counts under a uniform distribution. If the total discrepancy—or the discrepancy in any single bin—exceeds a threshold proportional to $\sqrt{\log n}$, the distribution is identified as non-uniform. To simplify the mathematical analysis of these independent intervals, the authors employ Poisson sampling.

Approximation of a monotone distribution (red line) using step functions and binning (black steps).

The "Genie" Benchmark and Competitive Optimality

A key contribution of this work is the shift from "minimax optimality" to "competitive optimality." The performance of the $t_c$ test is compared to a hypothetical "genie" test. This genie knows the exact underlying distribution and only needs to decide between that distribution and the uniform one. Achieving performance close to such an idealized benchmark is a significantly more rigorous standard than traditional worst-case analysis, as it accounts for the specific difficulty of the distribution at hand.

Key Results

The paper establishes both upper and lower bounds for the sample complexity of testing monotone distributions:

  • Upper Bound: The $t_c$ test distinguishes any monotone distribution from uniform using at most $O(n \sqrt{\log n})$ samples, where $n$ is the sample complexity of the optimal (genie) test for that specific distribution.
  • Lower Bound: The authors prove that the $\sqrt{\log n}$ factor is not a limitation of their specific test but a fundamental requirement. They demonstrate that for any test, there exists a monotone distribution requiring $\Omega(n \sqrt{\log n})$ samples to identify.
  • Near-Optimality: Together, these results show that the proposed test is nearly optimal across the entire class of monotone distributions.

Conclusion and Future Work

By exploiting the structural properties of monotone distributions and employing a sophisticated binning strategy, this research provides a nearly optimal framework for uniformity testing. While the current results are focused on monotone distributions over finite intervals, the authors suggest that the principles of competitive optimality and shape-restricted testing offer a robust foundation for future work in high-dimensional or non-monotone statistical analysis.

Summary updated

Abstract

We propose a test that takes random samples drawn from a monotone distribution and decides whether or not the distribution is uniform. The test is nearly optimal in that it uses at most O(n\sqrt\lo...
BibTeX
@inproceedings{acharya2013competitive,
  author = {Jayadev Acharya and Ashkan Jafarpour and Alon Orlitsky and Ananda Theertha Suresh},
  title = {{A Competitive Test for Uniformity of Monotone Distributions.}},
  booktitle = {AISTATS},
  year = {2013},
  url = {https://openreview.net/forum?id=lObrOw1iFP1d},
}
Figure