  In this paper we consider the uniformity testing problem for high-dimensional
discrete distributions (multinomials) under sparse alternatives. More
precisely, we derive sharp detection thresholds for testing, based on $n$
samples, whether a discrete distribution supported on $d$ elements differs from
the uniform distribution only in $s$ (out of the $d$) coordinates and is
$\varepsilon$-far (in total variation distance) from uniformity. Our results
reveal various interesting phase transitions which depend on the interplay of
the sample size $n$ and the signal strength $\varepsilon$ with the dimension
$d$ and the sparsity level $s$. For instance, if the sample size is less than a
threshold (which depends on $d$ and $s$), then all tests are asymptotically
powerless, irrespective of the magnitude of the signal strength. On the other
hand, if the sample size is above the threshold, then the detection boundary
undergoes a further phase transition depending on the signal strength. Here, a
$\chi^2$-type test attains the detection boundary in the dense regime, whereas
in the sparse regime a Bonferroni correction of two maximum-type tests and a
version of the Higher Criticism test is optimal up to sharp constants. These
results combined provide a complete description of the phase diagram for the
sparse uniformity testing problem across all regimes of the parameters $n$,
$d$, and $s$. One of the challenges in dealing with multinomials is that the
parameters are always constrained to lie in the simplex. This results in the
aforementioned two-layered phase transition, a new phenomenon which does not
arise in classical high-dimensional sparse testing problems.
