  In this paper we consider the problem of uniformity testing with limited
memory. We observe a sequence of independent identically distributed random
variables drawn from a distribution $p$ over $[n]$, which is either uniform or
is $\varepsilon$-far from uniform under the total variation distance, and our
goal is to determine the correct hypothesis. At each time point we are allowed
to update the state of a finite-memory machine with $S$ states, where each
state of the machine is assigned one of the hypotheses, and we are interested
in obtaining an asymptotic probability of error at most $0<\delta<1/2$
uniformly under both hypotheses.
  The main contribution of this paper is deriving upper and lower bounds on the
number of states $S$ needed in order to achieve a constant error probability
$\delta$, as a function of $n$ and $\varepsilon$, where our upper bound is
$O(\frac{n\log n}{\varepsilon})$ and our lower bound is $\Omega
(n+\frac{1}{\varepsilon})$. Prior works in the field have almost exclusively
used collision counting for upper bounds, and the Paninski mixture for lower
bounds. Somewhat surprisingly, in the limited memory with unlimited samples
setup, the optimal solution does not involve counting collisions, and the
Paninski prior is not hard. Thus, different proof techniques are needed in
order to attain our bounds.
