# Testing properties of distributions in the streaming model

arXiv: https://arxiv.org/abs/2309.03245 · HTML: https://mlsanity.com/paper/2309.03245/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 26 references that are in the map.
- First posted on arXiv 6 Sep 2023.

## Builds on (most cited first, 7 of 7)

- [Testing Shape Restrictions of Discrete Distributions](https://mlsanity.com/paper/1507.03558/) (2015)
- [Communication and Memory Efficient Testing of Discrete Distributions](https://mlsanity.com/paper/1906.04709/) (2019)
- [Estimating Entropy of Distributions in Constant Space](https://mlsanity.com/paper/1911.07976/) (2019)
- [Big Data on the Rise: Testing monotonicity of distributions](https://mlsanity.com/paper/1501.06783/) (2015)
- [Estimation of Entropy in Constant Space with Improved Sample Complexity](https://mlsanity.com/paper/2205.09804/) (2022)
- [Improving and extending the testing of distributions for shape-restricted properties](https://mlsanity.com/paper/1609.06736/) (2016)
- [Testable Properties in General Graphs and Random Order Streaming](https://mlsanity.com/paper/1905.01644/) (2019)

## Built on by (most cited first, 3 of 3)

- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing](https://mlsanity.com/paper/2503.07775/) (2025)

## Abstract (arXiv)

We study distribution testing in the standard access model and the conditional access model when the memory available to the testing algorithm is bounded. In both scenarios, the samples appear in an online fashion and the goal is to test the properties of distribution using an optimal number of samples subject to a memory constraint on how many samples can be stored at a given time. First, we provide a trade-off between the sample complexity and the space complexity for testing identity when the samples are drawn according to the conditional access oracle. We then show that we can learn a succinct representation of a monotone distribution efficiently with a memory constraint on the number of samples that are stored that is almost optimal. We also show that the algorithm for monotone distributions can be extended to a larger class of decomposable distributions.