DocumentCode :
3070561
Title :
On the synthesis of stochastic flow networks
Author :
Zhou, Hongchao ; Chen, Ho-Lin ; Bruck, Jehoshua
Author_Institution :
Dept. of Electr. Eng., California Inst. of Technol., Pasadena, CA, USA
fYear :
2010
fDate :
13-18 June 2010
Firstpage :
1330
Lastpage :
1334
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 ≤ 2n 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/(2n) (a an integer) can be realized.
Keywords :
directed graphs; statistical distributions; stochastic processes; DNA based molecular systems; directed graph; optimal stochastic flow network synthesis; probability distribution; rational probability; tree network; Computer networks; Control system synthesis; DNA; Feedback; Network synthesis; Probability distribution; Stochastic processes; Stochastic systems; Tail; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on
Conference_Location :
Austin, TX
Print_ISBN :
978-1-4244-7890-3
Electronic_ISBN :
978-1-4244-7891-0
Type :
conf
DOI :
10.1109/ISIT.2010.5513754
Filename :
5513754
Link To Document :
بازگشت