Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits.

Our main results are:

\begin{itemize}
\item There are explicit $AC^0$ circuits of size poly(n) and depth $O(1)$ whose output distribution has statistical distance $1/2^n$ from the distribution $(X,\sum_i X_i) \in \{0,1\}^{n} \times \set{0,1,\ldots,n}$ for uniform $X \in \{0,1\}^n$, despite the inability of these circuits to compute $\sum_i x_i$ given $x$.

Previous examples of this phenomenon apply to different distributions such as $(X, \sum_i X_i \mod 2) \in \{0,1\}^{n+1}$.

We also prove a lower bound independent from $n$ on the statistical distance between the output distribution of $NC^0$ circuits and the distribution $(X,\maj(X))$. We show that $1-o(1)$ lower bounds for related distributions yield lower bounds for succinct data structures.

\item Uniform randomized $AC^0$ circuits of poly(n) size and depth $d = O(1)$ with error $\epsilon$ can be simulated by uniform randomized circuits of poly(n) size and depth $d+1$ with error $\epsilon + o(1)$ using $\le (\log n)^{O( \log \log n)}$ random bits.

Previous derandomizations [Ajtai and Wigderson '85; Nisan '91] increase the depth by a constant factor, or else have poor seed length.

\end{itemize}

Given the right tools, the above results have technically simple proofs.