The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, is concerned with studying properties of probability distributions.
We cover the current status of distribution testing in several settings, starting with the traditional sampling model where the algorithms obtains independent samples from the distribution. We then discuss different recent models, in which one either grants the testing algorithms more powerful types of queries, or evaluates their performance against that of an information-theoretical optimal "adversary." In each setting, we describe the state-of-the-art for a variety of testing problems.
We hope this survey will serve as a self-contained introduction for those considering research in this field.
Added a section about competitive testing, as well as an appendix on Fano and Le Cam's methods.
The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, is concerned with studying properties of probability distributions.
We cover the current status of distribution testing in several settings, starting with the traditional sampling model where the algorithms obtains independent samples from the distribution. We then discuss different recent models, in which one either grants the testing algorithms more powerful types of queries, or evaluates their performance against that of an information-theoretical optimal ``adversary.'' In each setting, we describe the state-of-the-art for a variety of testing problems.
We hope this survey will serve as a self-contained introduction for those considering research in this field.