  In this paper, we study the hypothesis testing problem of, among $n$ random
variables, determining $k$ random variables which have different probability
distributions from the rest $(n-k)$ random variables. Instead of using separate
measurements of each individual random variable, we propose to use mixed
measurements which are functions of multiple random variables. It is
demonstrated that $O({\displaystyle \frac{k \log(n)}{\min_{P_i, P_j} C(P_i,
P_j)}})$ observations are sufficient for correctly identifying the $k$
anomalous random variables with high probability, where $C(P_i, P_j)$ is the
Chernoff information between two possible distributions $P_i$ and $P_j$ for the
proposed mixed observations. We characterized the Chernoff information
respectively under fixed time-invariant mixed observations, random time-varying
mixed observations, and deterministic time-varying mixed observations; in our
derivations, we introduced the \emph{inner and outer conditional Chernoff
information} for time-varying measurements. It is demonstrated that mixed
observations can strictly improve the error exponent of hypothesis testing,
over separate observations of individual random variables. We also
characterized the optimal mixed observations maximizing the error exponent, and
derived an explicit construction of the optimal mixed observations for the case
of Gaussian random variables. These results imply that mixed observations of
random variables can reduce the number of required samples in hypothesis
testing applications. Compared with compressed sensing problems, this paper
considers random variables which are allowed to dramatically change values in
different measurements.
