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 July 2010 | Published
Book Section - Chapter Open

On the 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. 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-sized 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.

Additional Information

© 2010 IEEE. Issue Date: 13-18 June 2010, Date of Current Version: 23 July 2010. This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824.

Attached Files

Published - 05513754.pdf

Published - Zhou2010p132632010_Ieee_International_Symposium_On_Information_Theory.pdf

Files

05513754.pdf
Files (356.4 kB)
Name Size Download all
md5:f3acc594a676ff577f3bfcba9e115262
178.2 kB Preview Download
md5:f3acc594a676ff577f3bfcba9e115262
178.2 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024