  Construction of tight confidence regions and intervals is central to
statistical inference and decision making. This paper develops new theory
showing minimum average volume confidence regions for categorical data. More
precisely, consider an empirical distribution $\widehat{\boldsymbol{p}}$
generated from $n$ iid realizations of a random variable that takes one of $k$
possible values according to an unknown distribution $\boldsymbol{p}$. This is
analogous to a single draw from a multinomial distribution. A confidence region
is a subset of the probability simplex that depends on
$\widehat{\boldsymbol{p}}$ and contains the unknown $\boldsymbol{p}$ with a
specified confidence. This paper shows how one can construct minimum average
volume confidence regions, answering a long standing question. We also show the
optimality of the regions directly translates to optimal confidence intervals
of linear functionals such as the mean, implying sample complexity and regret
improvements for adaptive machine learning algorithms.
