Experimenting with Beta Distributions for Approximating Hammocks’ Reliability

Abstract

It is a well-known fact that, in general, the combinatorial problem of finding the reliability polynomial of a two-terminal network belongs to the class of $\# P$-complete problems. In particular, hammock (aka brick-wall) networks are particular two-terminal networks introduced by Moore and Shannon in 1956. Rather unexpectedly, hammock networks seem to be ubiquitous, spanning from biology (neural cytoskeleton) to quantum computing (layout of quantum gates). Because computing exactly the reliability of large hammock networks seems unlikely (even in the long term), the alternatives we are facing fall under approximation techniques using: (i) simpler ‘equivalent’ networks; (ii) lower and upper bounds; (iii) estimates of (some of) the coefficients; (iv) interpolation (e.g., Bézier, Hermite, Lagrange, splines, etc.); and (v) combinations of (some of) the approaches mentioned above. In this paper we shall advocate—for the first time ever—for an approximation based on an ‘equivalent’ statistical distribution. In particular, we shall argue that as counting (lattice paths) is at the heart of the problem of estimating reliability for such networks, the binomial distribution might be a (very) good starting point. As the number of alternatives (lattice paths) gets larger and larger, a continuous approximation like the normal distribution naturally comes to mind. Still, as the number of alternatives (lattice paths) becomes humongous very quickly, more accurate and flexible approximations might be needed. That is why we put forward the beta distribution (as it can match the binomial distribution), and we use it in conjunction with a few exact coefficients (which help fitting the tails) to approximate the reliability of hammock networks.

1 Introduction

The unrelenting pace of technological advances makes it possible to envisage 3 nm processors in the not too distant future [1]. In fact, a 3 nm Gate-All-Around (GAA) technology process development kit was announced in May 2019 [2], while a first prototype has been reported in January 2020 [3]. There is a large body of evidence [4] that the development of such minuscule devices leads to beneficial improvements of system level performances (e.g., lower power consumption), but has challenging counter effects (e.g., how to tame the statistical uncertainties unavoidable at the atomic scale) [5,6,7].

Fundamentally, although at the system level we are treading on information measured in bits (a word put forward around late 1940s by John W. Tukey, cf. [8]), which are either $0$ or $1$, scaling is hampered by physical imperfections at the device and circuit levels [9]. That is why the latest and mightiest chips (like, e.g., Cerebras Wafer Scale Engine, having 1.2 trillion transistors [10]) had to address this challenge, and are incorporating various types of redundancy (a trend started discreetly a long time ago with the parity bit). A much less mature but aspiring contender is represented by quantum computing, which lately has also been making big strides [11, 12]. In this case we are talking about qubits (a word coined by Benjamin Schumacher in 1995 [13]), and statistics is now the name of the game. Before going further it is worth quoting from John W. Tuckey: “Far better an approximate answer to the right question, which is often vague, than an exact answer to the wrong question, which can always be made precise” [14]. Although pertaining to data analysis, this statement bears a lot of meaning for both software and hardware, as advocated by this paper.

The solution to develop large scale reliable (hardware) systems in the face of statistical uncertainties is to design systems using schemes which can enhance reliability. The majority-voting and multiplexing schemes (both at the gate-level) were proposed by John von Neumann in five seminal lectures presented at Caltech in January 1952, https://sites.google.com/site/michaeldgodfrey/vonneumann/vN_Caltech_Lecture.pdf. A printed version of those lectures was published in April 1956 [15], followed in September 1956 by the pioneering hammock networks concept of Moore and Shannon [16] (the first device-level based reliability scheme). The network reliability field was born, and has been evolving ever since [17,18,19,20].

The basic questions in network reliability are related to two-terminal, $k$-terminal, and all-terminal reliability of a given network. All of them are known to be $\# P$-complete in general [21,22,23], hence exact algorithms are way too slow even for small networks. That is why lower and upper bounds were investigated as time-efficient alternatives [24], with bounding or approximating the coefficients of the reliability polynomial as another possible option [25,26,27].

In this paper the focus will be on hammock networks [16], which have started to be investigated in details only lately [28,29,30]. Hammocks are two-terminal networks $H_{w,l}$, of width $w$ and length $l$. Reliability (or probabilistic $st$-connectedness) is defined as the probability that two nodes $S$ (the source) and $T$ (the terminus) can communicate (are connected). In fact, $H_{w,l}$ are modeled as graphs in which nodes communicate through $n$ ($= wl$) edges (see Fig. 1, where edges are represented as resistors), edges which have statistically independent probabilities of failing $q = 1 - p$ (nodes are assumed to be perfectly reliable).

Fig. 1.

Hammock networks for $w = l = 4$ (see [16]): (a) $H_{4,4}$ ($S$ and $T$ and 4 other nodes); and (b) $H_{4,4}^{ + }$ ($S$ and $T$ and 5 other nodes).

2 A Fresh Take on Approximating the Reliability Polynomial

We have realized (about six years ago) that there are obvious similarities between reliability polynomials $h\left( p \right)$ (also $Rel\left( p \right)$ or $Rel\left( {G;p} \right)$) and cumulative distribution functions (cdfs) of random variables (rvs). This was not difficult to fathom as both are sigmoid ($S$-shaped) functions embodying probabilities. Following on that observation, we did a few preliminary simulations but have started only very recently to properly experiment with approximating the two-terminal reliability of Moore-Shannon hammocks by the cdf of various probability distributions.

We tried $\Phi \left( {\frac{{p - p_{0} }}{\sigma }} \right)$ first, being the cdf of the normal distribution $N\left( {p_{0} , \sigma^{2} } \right)$, where the median $p_{0}$ was found by solving numerically $h\left( {p_{0} } \right) = 1/2$, and $\sigma$ was chosen by hand to produce a good fit. The results were quite promising. Looking for an explanation why $h\left( p \right)$ should resemble the cdf, we turned to the Binomial distribution

$$ X \sim Bin\left( {n, p_{1} } \right), $$

(1)

$n$ being the number of edges in the graph underlying a Moore-Shannon hammock network, reasoning that, in some sense, the connectivity of a random sub-graph of a given graph correlates with the number of edges that are present, which follows a binomial distribution, due to the customary assumption of independent, identically distributed (i.i.d.) Boolean edges. All of these suggested that $h\left( p \right)$ might have some connection, at least, with $X \sim Bin\left( {n, p_{1} } \right)$ for some $p_{1}$.

One disadvantage of $N\left( {p_{0} , \sigma^{2} } \right)$ is that it is supported on the whole real line, whereas $h\left( p \right)$, and hence $h'\left( p \right)$, are defined only for $0 \le p \le 1$ (with $h'\left( p \right)$ vanishing at the endpoints of that interval). Another advantage of a binomial distribution, therefore, is that its probability mass function (pmf) is compactly supported. Yet another reason for trying a binomial distribution is that these are, notoriously, well approximated by normal distributions, which we had already found to give promising results, in spite of their disadvantages.

Our first attempt with $X \sim Bin\left( {n,p_{1} } \right)$ was to scale its cdf horizontally, approximating $h\left( p \right)$ by the piecewise constant function

$$ f\left( p \right) = P\left( {X \le pn} \right). $$

(2)

In order that $f\left( {p_{0} } \right)$ should approximately equal $1/2$, we needed $X$ to have median approximately equal to $p_{0} n$. However, any median of such an $X$ lies between $\left\lfloor {np_{1} } \right\rfloor$ and $\left\lceil {np_{1} } \right\rceil$, so we set $p_{1} = p_{0}$, and $X \sim Bin\left( {n,p_{0} } \right)$. Having thus forced $f\left( p \right)$ to have a median similar to that of $h\left( p \right)$, we found that the approximation was otherwise poor, the rate of change of $f$ at $p_{0}$ being quite different from that of $h$ at $p_{0}$. Replacing $X \sim Bin\left( {n,p_{0} } \right)$ by $X \sim Bin\left( {N,p_{0} } \right)$ and $f\left( p \right) = P\left( {X \le pn} \right)$ by $f\left( p \right) = P\left( {X \le pN} \right)$, we found that, choosing $N$ by hand, we could greatly improve this. However, the optimal values of $N$ being relatively low, the piecewise constant function $f\left( p \right)$ was a relatively coarse approximation to the continuous function $h\left( p \right)$.

To solve this problem, we replaced the scaled Binomial distribution cdf $f\left( p \right) = P\left( {X \le pN} \right)$, where $X \sim Bin\left( {N ,p_{0} } \right)$, by the regularised incomplete beta function

$$ I_{x} \left( {a,b} \right) = \frac{{B\left( {x;a,b} \right)}}{{B\left( {a,b} \right)}} $$

(3)

where

$$ B\left( {a,b} \right) = \int_{0}^{1} {t^{a - 1} \left( {1 - t} \right)^{b - 1} dt} $$

(4)

is the beta function (see [31] for a data fitting/analysis application), and

$$ B\left( {x;a,b} \right) = \int_{0}^{x} {t^{a - 1} \left( {1 - t} \right)^{b - 1} dt} $$

(5)

is the incomplete beta function. The reason being that, as is well known, if $Y \sim Bin\left( {m,r} \right)$, then for $k \in \left\{ {0,1,2, \ldots ,m} \right\}$

$$ P\left( {Y \le k} \right) = I_{1 - r} \left( {m - k,k + 1} \right), $$

(6)

hence $I_{{1 - p_{0} }} \left( {N - pN,pN + 1} \right)$ smoothly interpolates our piecewise constant function $f\left( p \right)$. We found that by using the optimal values of $N$ that we had previously determined by hand, $I_{{1 - p_{0} }} \left( {N - pN,pN + 1} \right)$ gave very good approximations to $h\left( p \right)$.

At this point, we realized that in associating the cdf of a binomial distribution with $h\left( p \right)$, we had perhaps not made the most logical choice of parameter. Rather than fixing $p_{0}$ in $X \sim Bin\left( {N,p_{0} } \right)$ and varying $p$ in $f\left( p \right) = P\left( {X \le pN} \right)$, we decided instead to fix $a$ and let $g\left( p \right) = P\left( {Z \ge a} \right)$, while varying $p$ in $Z \sim Bin\left( {N,p} \right)$. This would be a more natural way to assert some correlation between the event that the two terminals ($S$ and $T$) of a hammock network are connected, and the event that sufficiently many edges are present in a random sub-graph of the graph underlying the hammock. This idea was partly inspired by the work of Erdős, Rényi and Gilbert [32,33,34] in what is now known as percolation theory in random graphs.

Since

$$ P\left( {Z \ge a} \right) = P\left( {N - Z \le N - a} \right) = P\left( {W \le k} \right), $$

(7)

where $W = N - Z$, $k = N - a$, and $W \sim Bin\left( {N,1 - p} \right)$, and since, as noted above, we can write

$$ P\left( {W \le k} \right) = I_{{1 - \left( {1 - p} \right)}} \left( {N - k,k + 1} \right) = I_{p} \left( {N - k,k + 1} \right), $$

(8)

therefore, substituting $b - 1$ for $k$ and $a + b{-}1$ for $N$, we have

$$ P\left( {Z \ge a} \right) = I_{p} \left( {a, b} \right), $$

(9)

where $Z \sim Bin\left( {a + b - 1,p} \right)$.

Equations (3)–(5) show that, in line with our initial ideas, the new approximation $I_{p} \left( {a,b} \right)$ for $h\left( p \right)$ is indeed a cdf, not of a binomial distribution, but of the so-called beta distribution whose probability density function (pdf) is

$$ beta\left( {a,b} \right)\left( p \right) = \frac{{\left( {a + b - 1} \right)!}}{{\left( {a - 1} \right)!\left( {b - 1} \right)!}}p^{a - 1} \left( {1 - p} \right)^{b - 1} . $$

(10)

Indeed, for positive integers $a$ and $b$, integrating by parts and then solving the resulting recurrence relation, one can demonstrate directly that $beta\left( {a, b} \right)\left( p \right)$ has cdf

$$ \int_{0}^{p} { beta\left( {a, b} \right)\left( t \right)dt} \; = \;\sum\nolimits_{k = a}^{a + b - 1} {\left( {\begin{array}{*{20}c} {a + b - 1} \\ k \\ \end{array} } \right)} p^{k} \left( {1 - p} \right)^{a + b - 1 - k} = P\left( {Z \ge a} \right). $$

(11)

where $Z \sim Bin\left( {a + b - 1,p} \right)$. This is one way to prove Eq. (6).

Bearing in mind that in future we may generalize to non-integer $a$ and $b$ by replacing $P\left( {Z \ge a} \right)$ by $I_{p} \left( {a,b} \right)$, our strategy in this paper was to choose integer parameters $a$ and $b$ so that our approximation $P\left( {Z \ge a} \right)$ to $h\left( p \right)$, where $Z \sim Bin\left( {a + b - 1,p} \right)$, is a homogeneous polynomial of degree $a + b - 1$ in $p$ and $q$, where $q = 1 - p$. Provided $a + b - 1 \le n$, we can then multiply this polynomial by $1 = \left( {p + q} \right)^{n - a - b + 1}$ to obtain a homogeneous polynomial of degree $n$ in $p$ and $q$, so that we may easily compare the coefficients of the latter with those of $h\left( {p,q} \right)$ one by one—the expression of $h\left( p \right)$ in the scaled Bernstein basis of degree $n$. The resulting formula is:

$$ P\left( {Z \ge a} \right) = \sum\nolimits_{k = a}^{n} {\sum\nolimits_{{j = \hbox{max} \left( {0,k - a - b + 1} \right)}}^{{\hbox{min} \left( {n - a - b + 1,k - a} \right)}} {\left( {\begin{array}{*{20}c} {n - a - b + 1} \\ j \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {a + b - 1} \\ { k - j} \\ \end{array} } \right)p^{k} q^{n - k} .} } $$

(12)

In case we are dealing with a self-dual hammock (see [28, 30]), we have $h\left( p \right) = 1 - h\left( {1 - p} \right)$, hence $h'\left( p \right) = h'\left( {1 - p} \right)$, i.e., $h'\left( p \right)$ is symmetric about the line $p = 1/2$. Therefore our approximation $beta\left( {a,b} \right)$ to $h'\left( p \right)$ should also be symmetric about that line. For this we have to set $a = b$, which means, in this case, that we need only choose a single integer parameter ($a$) rather than two ($a$ and $b$). In particular, all square hammocks of odd $w$ and $l$ are self-dual (see [28, 30]), and therefore allow us this simplification.

3 Simulations and Comparisons

In this section we present detailed simulations for $H_{5,5}$, starting with the exact reliability polynomial determined in [28]

$$ \begin{aligned} h_{5,5} \left( {p,q} \right) =\,& 52p^{5} q^{20} + 994p^{6} q^{19} + 8983p^{7} q^{18} + 50796p^{8} q^{17} + 200559p^{9} q^{16} + \\ & 584302p^{10} q^{15} + 1294750p^{11} q^{14} + 2220298p^{12} q^{13} + \\ & 2980002p^{13} q^{12} + 3162650p^{14} q^{11} + 2684458p^{15} q^{10} + \\ & 1842416p^{16} q^{9} + 1030779p^{17} q^{8} + 471717p^{18} q^{7} + 176106p^{19} q^{6} + \\ & 53078p^{20} q^{5} + 12650p^{21} q^{4} + 2300p^{22} q^{3} + 300p^{23} q^{2} + 25p^{24} q\,+ \\ & p^{25} . \\ \end{aligned} $$

(13)

Table 1. The reliability polynomial for $H_{5,5}$ as well as several approximations. For simulations we have not used the three approximations which are shaded.

Promising approximation techniques are relying on:

• simpler ‘equivalent’ networks;

• upper/lower bounds;

• estimating/bounding the coefficients;

• interpolation (e.g., Hermite, Lagrange, splines, etc.); and

• combinations of these methods.

Looking into the literature published on hammock networks we have found a very fresh Hermite interpolation [35]

$$ Hermite_{w,l} \left( {p,q} \right) = p^{l} \left[ {\sum\nolimits_{i = 0}^{w - 1} {\left( {\begin{array}{*{20}c} {i + l - 1} \\ {l - 1} \\ \end{array} } \right)q^{i} } } \right] $$

(14)

as well as a novel cubic spline interpolation [36].

The reliability polynomial together with the approximations we have used in this paper are presented in Table 1. This table includes several versions of the same type of approximation, where the first and second non-zero coefficients (red), as well as the associated symmetric coefficients (red), were forced to match the exact values determined in [29, 35]. For beta, forcing these coefficients allow us to fit the tails.

Detailed simulations are presented as follows. In Fig. 2 we can see five of the polynomials detailed in Table 1, together with the continuous beta function, plotted in both linear and logarithmic scale. From Fig. 2(a) it would seem that, with the exception of the cubic spline, all other approximations are performing quite well. Still, from Fig. 2(b), the cubic spline approximation is outstanding for $p < 0.1$, while beta₂₅(6,6) is clearly not that good. By adjusting/forcing the first and second non-zero coefficients for both the Hermite₂₅ and the beta₂₅ approximation they are becoming excellent themselves (for $p < 0.1$). An even more detailed understanding can be grasped from Fig. 3, where the absolute and relative errors are plotted in Figs. 3(a) and 3(b) respectively, with zooms on the regions of interest in Figs. 3(c) and 3(d). All of these unambiguously show that beta₂₅(6,6) adjusted (red line) is outperforming all other approximations.

Another perspective on the approximations from Table 1 has been obtained by plotting all the 26 coefficients of the polynomials under test, allowing for a one-on-one comparison. Figure 4 presents stair-step plots of the coefficients of the different polynomials together with the corresponding binomial coefficients in cyan (as polynomials are in Bernstein form). All approximations seem to behave quite similarly with the exception of the cubic spline, an assessment which is pairing that from Fig. 2. For completeness, Fig. 5 presents the absolute and relative errors on each and every one of the 26 coefficients. It can be seen that these stair-step plots are very closely resembling Fig. 3 (they look in fact like discretized versions of Fig. 3). These confirm once again that beta₂₅(6,6) adjusted (red line) gives by far the best match not only for the reliability polynomial but in fact for each and every coefficient.

Fig. 2.

Reliability of hammock $H_{5,5}$ as well as several approximations (see Table 1) versus $p$: (a) linear scale; and (b) logarithmic scale.

Fig. 3.

The errors between the reliability approximations considered (see Table 1) and reliability of hammock $H_{5,5}$ versus $p$: (a) absolute errors; (b) relative errors; (c) zoom on absolute errors, and (d) zoom on relative errors.

Fig. 4.

The binomial coefficients $\left( {\begin{array}{*{20}c} {25} \\ i \\ \end{array} } \right)$ for $i = 0, 1, \ldots , 25$ (cyan), together with the corresponding coefficients of the reliability polynomial for $H_{5,5}$ (yellow), as well as those of several approximations (see Table 1): (a) linear scale; and (b) logarithmic scale.

Fig. 5.

The absolute and relative errors of the $26$ coefficients of several approximations (see Table 1) versus the corresponding coefficients of the reliability polynomial of $H_{5,5}$: (a) absolute errors; (b) relative errors; (c) zoom on absolute errors, and (d) zoom on relative errors.

4 Conclusions

This paper has suggested a fresh approach for approximating the reliability of hammock networks $H_{w,l}$ [16, 28]. The unorthodox approximation method proposed relies on: (i) using the beta distribution; (ii) translating it into a Bernstein polynomial (of degree $n = wl$); and finally (iii) adjusting/correcting the tails of this cdf based on four known coefficients (for which exact computations are known and straightforward/simple [29, 35]).

We have reported detailed simulations and have compared the results obtained using our approach with those of other approximations. All the simulations performed are very encouraging, and support the claim that beta approximation is much more accurate than any other known approximation. We plan to continue this line of research by:

• trying to find both theoretical proofs and accurate bounds for the approximation method we have introduced here; and

• investigating other distributions (we plan to start with Poisson distributions of the coefficients, as suggested by beta₂₅(6,6) adjusted (red line) in Fig. 4(a)).