Zhou, Hongchao and Chen, HoLin 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

PDF
See Usage Policy. 511Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2010.ETR101
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. 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 CCF0832824. Also available online http://www.paradise.caltech.edu/papers/etr101.pdf 
Group:  Parallel and Distributed Systems Group 
Subject Keywords:  Stochastic Flow Network, Graph, Feedback, Probability Synthesis 
Record Number:  CaltechPARADISE:2010.ETR101 
Persistent URL:  http://resolver.caltech.edu/CaltechPARADISE:2010.ETR101 
Usage Policy:  You are granted permission for individual, educational, research and noncommercial reproduction, distribution, display and performance of this work in any format. 
ID Code:  26132 
Collection:  CaltechPARADISE 
Deposited By:  Imported from CaltechPARADISE 
Deposited On:  03 Feb 2010 
Last Modified:  26 Dec 2012 13:54 
Repository Staff Only: item control page