__
TR21-129 | 6th September 2021 15:24
__

#### A Lower Bound on the Complexity of Testing Grained Distributions

**Abstract:**
A distribution is called $m$-grained if each element appears with probability that is an integer multiple of $1/m$.

We prove that, for any constant $c<1$, testing whether a distribution over $[\Theta(m)]$ is $m$-grained requires $\Omega(m^c)$ samples.