IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v34y1986i4p581-594.html
   My bibliography  Save this article

A Monte Carlo Sampling Plan for Estimating Network Reliability

Author

Listed:
  • George S. Fishman

    (The University of North Carolina at Chapel Hill, Chapel Hill, North Carolina)

Abstract

For an undirected network G = ( V , E ) whose arcs are subject to random failure, we present a relatively complete and comprehensive description of a general class of Monte Carlo sampling plans for estimating g = g ( s , T ), the probability that a specified node s is connected to all nodes in a node set T . We also provide procedures for implementing these plans. Each plan uses known lower and upper bounds [ B , A ] on g to produce an estimator of g that has a smaller variance ( A − g )( g − B )/ K on K independent replications than that obtained for crude Monte Carlo sampling ( B = 0, A = 1). We describe worst-case bounds on sample sizes K , in terms of B and A , for meeting absolute and relative error criteria. We also give the worst-case bound on the amount of variance reduction that can be expected when compared with crude Monte Carlo sampling. Two plans arc studied in detail for the case T = { t }. An example illustrates the variance reductions achievable with these plans. We also show how to assess the credibility that a specified error criterion for g is met as the Monte Carlo experiment progresses, and show how confidence intervals can be computed for g . Lastly, we summarize the steps needed to implement the proposed technique.

Suggested Citation

  • George S. Fishman, 1986. "A Monte Carlo Sampling Plan for Estimating Network Reliability," Operations Research, INFORMS, vol. 34(4), pages 581-594, August.
  • Handle: RePEc:inm:oropre:v:34:y:1986:i:4:p:581-594
    DOI: 10.1287/opre.34.4.581
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.34.4.581
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.34.4.581?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ramirez-Marquez, José Emmanuel & Rocco, Claudio M., 2008. "All-terminal network reliability optimization via probabilistic solution discovery," Reliability Engineering and System Safety, Elsevier, vol. 93(11), pages 1689-1697.
    2. Zdravko I. Botev & Pierre L'Ecuyer & Gerardo Rubino & Richard Simard & Bruno Tuffin, 2013. "Static Network Reliability Estimation via Generalized Splitting," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 56-71, February.
    3. Paredes, R. & Dueñas-Osorio, L. & Meel, K.S. & Vardi, M.Y., 2019. "Principled network reliability approximation: A counting-based approach," Reliability Engineering and System Safety, Elsevier, vol. 191(C).
    4. Zhou, Yifan & Liu, Libo & Li, Hao, 2022. "Reliability estimation and optimisation of multistate flow networks using a conditional Monte Carlo method," Reliability Engineering and System Safety, Elsevier, vol. 221(C).
    5. K.-P. Hui & N. Bean & M. Kraetzl & Dirk Kroese, 2005. "The Cross-Entropy Method for Network Reliability Estimation," Annals of Operations Research, Springer, vol. 134(1), pages 101-118, February.
    6. Yi-Kuei Lin & Cheng-Fu Huang & Chin-Chia Chang, 2022. "Reliability of spare routing via intersectional minimal paths within budget and time constraints by simulation," Annals of Operations Research, Springer, vol. 312(1), pages 345-368, May.
    7. Sebastio, Stefano & Trivedi, Kishor S. & Wang, Dazhi & Yin, Xiaoyan, 2014. "Fast computation of bounds for two-terminal network reliability," European Journal of Operational Research, Elsevier, vol. 238(3), pages 810-823.
    8. Chan, Jianpeng & Papaioannou, Iason & Straub, Daniel, 2022. "An adaptive subset simulation algorithm for system reliability analysis with discontinuous limit states," Reliability Engineering and System Safety, Elsevier, vol. 225(C).
    9. Masahiro Sasabe & Miyu Otani & Takanori Hara & Shoji Kasahara, 2024. "Path reachability including distance-constrained detours," Journal of Risk and Reliability, , vol. 238(1), pages 79-92, February.
    10. Azaron, Amir & Katagiri, Hideki & Sakawa, Masatoshi & Modarres, Mohammad, 2005. "Reliability function of a class of time-dependent systems with standby redundancy," European Journal of Operational Research, Elsevier, vol. 164(2), pages 378-386, July.
    11. J. L. Cook & J. E. Ramirez-Marquez, 2007. "Reliability of capacitated mobile ad hoc networks," Journal of Risk and Reliability, , vol. 221(4), pages 307-318, December.
    12. H. Cancela & M. Khadiri & G. Rubino, 2012. "A new simulation method based on the RVR principle for the rare event network reliability problem," Annals of Operations Research, Springer, vol. 196(1), pages 111-136, July.
    13. Davila-Frias, Alex & Yodo, Nita & Le, Trung & Yadav, Om Prakash, 2023. "A deep neural network and Bayesian method based framework for all-terminal network reliability estimation considering degradation," Reliability Engineering and System Safety, Elsevier, vol. 229(C).
    14. Cook, Jason L. & Ramirez-Marquez, Jose Emmanuel, 2009. "Optimal design of cluster-based ad-hoc networks using probabilistic solution discovery," Reliability Engineering and System Safety, Elsevier, vol. 94(2), pages 218-228.
    15. Cook, Jason L. & Ramirez-Marquez, Jose Emmanuel, 2008. "Reliability analysis of cluster-based ad-hoc networks," Reliability Engineering and System Safety, Elsevier, vol. 93(10), pages 1512-1522.
    16. George S. Fishman, 1989. "Monte Carlo estimation of the maximal flow distribution with discrete stochastic arc capacity levels," Naval Research Logistics (NRL), John Wiley & Sons, vol. 36(6), pages 829-849, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:34:y:1986:i:4:p:581-594. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.