Stochastic switching circuits are relay circuits that consist of stochastic switches called pswitches. The study of stochastic switching circuits has widespread applications in many fields of computer science, neuroscience, and biochemistry. In this paper, we discuss several properties of stochastic switching circuits, including robustness, expressibility, and probability approximation. First, we study the robustness, namely, the effect caused by introducing an error of size Є to each pswitch in a stochastic circuit. We analyze two constructions and prove that simple series-parallel circuits are robust to small error perturbations, while general series-parallel circuits are not. Specifically, the total error introduced by perturbations of size less than Є is bounded by a constant multiple of Є in a simple series-parallel circuit, independent of the size of the circuit. Next, we study the expressibility of stochastic switching circuits: Given an integer q and a pswitch set S = 1 q,2 q,...,q-1 q , can we synthesize any rational probability with denominator q^n (for arbitrary n) with a simple series-parallel stochastic switching circuit? We generalize previous results and prove that when q is a multiple of 2 or 3, the answer is yes. We also show that when q is a prime number larger than 3, the answer is no. Probability approximation is studied for a general case of an arbitrary pswitch set S = s_1, s_2,... , s_(|S|) . In this case, we propose an algorithm based on local optimization to approximate any desired probability. The analysis reveals that the approximation error of a switching circuit decreases exponentially with an increasing circuit size.
Resistances may be placed in circuit either in series or in parallel, or in various combinations of these methods. There are also networks such as the Wheatstone net, which are neither series nor parallel arrangements, and these are excluded from what follows. Every combination considered here consists of other combinations either in series or in parallel. Each must either consist of parallel combinations arranged in series, or of series combinations arranged in parallel. For the study of the subject it is convenient to make a few definitions. Two linear conductors may be placed either in series or in parallel. These arrangements may be defined as being conjugate the one of the other. It will be observed that the second of the arrangements merely differs in description from the first by the substitution of the word “parallel” for the word “series”. To generalise the notion we may define two combinations to be conjugate when their descriptions merely differ by the interchange of the words “series” and “parallel”. A single linear conductor should, for the sake of unity, be regarded as being either in series or in parallel, and, further, as being a combination which is self-conjugate. A combination consisting of parallel combinations in series will be called a series combination, and one consisting of series combinations in parallel a parallel combination. Thus, in the usual diagrammatic representation, Shannon in his 1938 Masterpsilas Thesis demonstrated that any Boolean function can be realized by a switching relay circuit, leading to the development of deterministic digital logic. Here, we replace each classical switch with a probabilistic switch (pswitch). We present algorithms for synthesizing circuits closed with a desired probability, including an algorithm that generates optimal size circuits for any binary fraction. We also introduce a new duality property for series-parallel stochastic switching circuits. Finally, we construct a universal probability generator which maps deterministic inputs to arbitrary probabilistic outputs. Potential applications exist in the analysis and design of stochastic networks in biology and engineering.