CaltechAUTHORS
  A Caltech Library Service

Generating Probability Distributions using Multivalued Stochastic Relay Circuits

Lee, David and Bruck, Jehoshua (2011) Generating Probability Distributions using Multivalued Stochastic Relay Circuits. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2011.ETR106

[img]
Preview
PDF
See Usage Policy.

711Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2011.ETR106

Abstract

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 as opposed to the algorithmic aspect. That is, given a network structure imposed by nature or physical devices, how can we build networks that generate arbitrary probability distributions in an optimal way? 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. Previous work was done on two-state relays. We generalize these results, describing a duality property and networks that generate 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 arbitrary binary probability distributions.


Item Type:Report or Paper (Technical Report)
Additional Information:The authors would like to thank Dan Wilhelm, Hongchao Zhou, and Ho-lin Chen for helpful discussions. They would also like to thank 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 to make this research possible.
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2011.ETR106
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2011.ETR106
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26137
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:09 Feb 2011
Last Modified:26 Dec 2012 13:54

Repository Staff Only: item control page