Zhou, Hongchao and Chen, Ho-Lin and Bruck, Jehoshua (2010) On the Synthesis of Stochastic Flow Networks. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2010.ETR101
- Submitted Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2010.ETR101
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. We address the following 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 synthesis dates back to von Neummann's 1951 work and was followed, among others, by Knuth and Yao in 1976, who demonstrated that arbitrary rational probabilities can be generated with tree networks; where minimizing the expected path length, the expected number of coin tosses in their paradigm, is the key consideration. Motivated by the synthesis of stochastic DNA based molecular systems, we focus on designing optimal size stochastic flow networks (the size of a network is the number of splitters). We assume that each splitter has two outgoing edges and is unbiased (probability 1/2 per output edge). We show that an arbitrary rational probability a/b with a ≤ b ≤ 2^n can be realized by a stochastic flow network of size n, we also show that this is optimal. We note that our stochastic flow networks have feedback (cycles in the network), in fact, we demonstrate that feedback improves the expressibility of stochastic flow networks, since without feedback only probabilities of the form a/2^n (a an integer) can be realized.
|Item Type:||Report or Paper (Technical Report)|
|Additional Information:||This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824.|
|Group:||Parallel and Distributed Systems Group|
|Subject Keywords:||Stochastic Flow Network, Graph, Feedback, Probability Synthesis|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||03 Feb 2010|
|Last Modified:||20 Jan 2016 00:04|
Repository Staff Only: item control page