Local Samplers for Product Distributions

Consider the task of sampling n independent bits, each equal to 1 with probability 1/4. Given 2n uniform random bits as input, this distribution can be sampled exactly by letting each output bit be the AND of two input bits. What if we are given only 1.99n uniform random bits? Can we still sample the distribution so that each output depends on only constant many input bits?

 

In this talk, I will present several results on sampling product distributions in a local and randomness-efficient manner:

 

- Let D = (D_1, D_2, ..., D_n) be a product distribution where each D_i has constant support and dyadic probabilities (i.e., probabilities of the form (a/2^b), where a,b are integers). Then D can be sampled in constant time in the bit-probe model (equivalently, in NC^0) using (h(D) + ε)n random bits, where h() is the binary entropy function, up to exponentially small statistical error.  Moreover, the dyadic assumption is necessary.

 

- We characterize the tradeoffs between locality and statistical distance for sampling the 1/4-biased distribution with 1.99n uniform bits. With 2 bit probes, essentially no nontrivial approximation is possible. With 3 bit probes, we construct a sampler achieving statistical distance 1/poly(n), and show this is best possible.  Finally, 4 bit probes suffice to achieve exponentially small statistical distance.

 

- Every p-biased distribution can be sampled in constant time in the cell-probe model with randomness complexity h(p)n + √n · polylog(n), up to a polynomially small statistical distance.

 

Our constructions rely on pseudorandom distributions that are bounded-uniform on average.  These are obtained using tools from low-density parity-check codes, as well as recent results on succinct and retrieval data structures.