ABSTRACT
The unreliable elements are the edges. It was assumed that all edges are independent and have equal up probabilities p(e) ranging from 0.1 to 0.99. Using the best up-to-date known lower (LB) and upper (UB) bounds, Colbourn & Harms compared these bounds with their exact analytic results R0(G, p). Table 13.1, columns 2 and 3 present their lower and upper bounds for various p values given in column 1. Our simulation results RˆMC(G, p) obtained by the turnip algorithm (Section 9.2) are presented in column 5. They were obtained by averaging N independent replications, column 6. It
Table 13.1: Colbourn & Harms Bounds and Monte-Carlo Results
1 2 3 4 5 6 p(e) LB UB R0(G, p) RMC(G, p) N 0.5 0.1052 0.2049 0.170 0.1578 100 0.6 0.2423 0.4415 0.3841 0.3648 100 0.7 0.45 0.7081 0.6409 0.6216 100 0.8 0.7081 0.8712 0.8548 0.8426 100 0.9 0.9302 0.9733 0.9710 0.9675 100 0.94 0.9791 0.9913 0.9908 0.9895 100 0.96 0.9922 0.9964 0.9962 0.9962 1000 0.98 0.99855 0.99914 0.99913 0.99912 1000 0.99 0.999714 0.999793 0.999791 0.999788 1000
is worth noting that in most cases, a relatively small number of replications N was needed to obtain an estimate RˆMC(G, p) which lies within fairly tight bounds LB and UB.
