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 structural 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 N 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 occurrences. 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.
© 2015 IEEE. Manuscript received 4 Apr. 2013; revised 30 May 2014; accepted 22 Jan. 2015. Date of publication 5 Feb. 2015; date of current version 11 Nov. 2015. The authors would like to thank Dan Wilhelm, Hongchao Zhou, and Ho-lin Chen for helpful discussions, and the Caltech SURF program, the Molecular Programming Project funded by the NSF Expeditions in Computing Program under grant CCF-0832824, and Aerospace Corporation for funding. D.T. Lee is the corresponding author.