simulated by each gate. The compound circuit can also be treated as a new primitive that generates samples from the marginal distribution of the final output given the first input. As with digital gates, an enormous variety of circuits can be constructed using these simple rules.

Fast Bayesian Inference via Massively Parallel Stochastic Transition Circuits {#fast-bayesian-inference-via-massively-parallel-stochastic-transition-circuits .unnumbered}
=============================================================================

Most digital systems are based on deterministic finite state machines; the template for these machines is shown in Figure 2A. A stateless digital circuit encodes the transition function that calculates the next state from the previous state, and the clocking machinery (not shown) iterates the transition function repeatedly. This abstraction has proved enormously fruitful; the first microprocessors had roughly $2^{20}$ distinct states. In Figure 2B, we show the stochastic analogue of this synchronous state machine: a [*stochastic transition circuit*]{}.

Instead of the combinational logic circuit implementing a deterministic transition function, it contains a combinational stochastic circuit implementing a stochastic transition operator that samples the next state from a probability distribution that depends on the current state. It thus corresponds to a Markov chain in hardware. To be a valid transition circuit, this transition operator must have a unique stationary distribution $P(S|X)$ to 