Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2014 | Submitted
Journal Article Open

Synthesis of Stochastic Flow Networks

Abstract

A stochastic flow network is a directed graph with incoming edges (inputs) and outgoing edges (outputs), tokens enter through the input edges, travel stochastically in the network, and can exit the network through the output edges. Each node in the network is a splitter, namely, a token can enter a node through an incoming edge and exit on one of the output edges according to a predefined probability distribution. Stochastic flow networks can be easily implemented by beam splitters, or by DNA-based chemical reactions, with promising applications in optical computing, molecular computing and stochastic computing. In this paper, we address a fundamental synthesis question: Given a finite set of possible splitters and an arbitrary rational probability distribution, design a stochastic flow network, such that every token that enters the input edge will exit the outputs with the prescribed probability distribution. The problem of probability transformation dates back to von Neumann's 1951 work and was followed, among others, by Knuth and Yao in 1976. Most existing works have been focusing on the "simulation" of target distributions. In this paper, we design optimal-sized stochastic flow networks for "synthesizing" target distributions. It shows that when each splitter has two outgoing edges and is unbiased, an arbitrary rational probability ɑ/b with ɑ ≤ b ≤ 2^n can be realized by a stochastic flow network of size n that is optimal. Compared to the other stochastic systems, feedback (cycles in networks) strongly improves the expressibility of stochastic flow networks.

Additional Information

© 2012 IEEE. Manuscript received 16 May 2012; revised 17 Oct. 2012; accepted 24 Oct. 2012; published online 18 Nov. 2012; date of current version 29 Apr. 2014. Recommended for acceptance by J. Chen. This work was supported in part by the NSF Expeditions in Computing Program under Grant CCF-0832824. This paper was presented in part at IEEE International Symposium on Information Theory (ISIT), Austin, Texas, June 2010.

Attached Files

Submitted - 1209.0724v1.pdf

Files

1209.0724v1.pdf
Files (544.9 kB)
Name Size Download all
md5:bb11f8f33213e99d7c519a97d206626f
544.9 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 26, 2023