Algorithms for Generating Probabilities with Multivalued Stochastic Relay Circuits

摘要

The problem of random number generation dates back to Von Neumann’s work in 1951. Since then, many algorithms have been developed for generating unbiased bits from complex correlated sources as well as for generating arbitrary distributions from unbiased bits. An equally interesting, but less studied aspect is the component of random number generation. That is, given a set of primitive sources of randomness, and given composition rules induced by a device or nature, how can we build networks that generate arbitrary probability distributions? In this paper, we study the generation of arbitrary probability distributions in multivalued relay circuits, a generalization in which relays can take on any of states and the logical ‘and’ and ‘or’ are replaced with ‘min’ and ‘max’ respectively. These circuits can be thought of as modeling the timing of events which depend on other event occurences. We describe a duality property and give algorithms that synthesize arbitrary rational probability distributions. We prove that these networks are robust to errors and design a universal probability generator which takes input bits and outputs any desired binary probability distribution.