We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum circuits. However, what about classical probabilistic circuits?
It seems like if you had a "coin-flip" gate (takes no input/any input and produces 0 or 1, each with probability 1/2) and NAND, you could build any probabilistic circuit you want (up to some level of precision) with a rejection sampling procedure. The desired probabilistic circuit can be seen as a set of deterministic circuits, chosen according to some distribution; use rejection sampling to simulate that distribution and then apply the required deterministic circuit.
(by the same argument, any gate that produces a fixed, non-trivial probability distribution, plus NAND, would be universal).
Is this a question that has been looked into? Any results that I can cite?