電腦模擬常被用來估計隨機網路的失效率，但是估計高度可靠隨機網路的失效率需要巨大的抽樣成本。本論文根據網路中數個最小割集提出一個重點抽樣程序以估計高度可靠隨機網路的失效率，其構想是在網路失效域中使重點抽樣分布儘可能貼近原始分布，並直接產生失效的系統狀態。本論文所提出的估計量可證實具有不偏性並可推導其變異數。實驗結果證實本論文所提出之重點抽樣估計程序可明顯地降低估計量的變異數，對高度可靠的隨機網路效果尤其顯著。

Computer simulation is often used to estimate the system unavailability of a stochastic network. However, sampling efforts required for estimating unavailability of a highly reliable network become formidable. An importance sampling scheme based on a subset of the minimal cuts of the network is proposed. The idea is to keep the importance distribution close to the original state distribution over the region of system failure and directly generate the failure states. The proposed estimator is shown to be unbiased and the variance of the estimator is derived. Empirical results show that for highly reliable networks the proposed estimator can achieve substantial variance reduction.

[1] Adewunmi, A. A. , "Selection of Simulation Variance Reduction
Techniques Through a Fuzzy Expert System" Ph.D dissertation,
University of Nottingham, Nottingham, UK (2008).
[2] Andreasson, I. J., "Antithetic methods in queueing simulations",
Technical report NA 72.58, Royal Institute of Technology, Stock-
holm, (1972).
[3] Asmussen, S. and Glynn, P. W., Stochastic Simulation, New York:
Springer-Verlag, (2007).
[4] Avramidis, A. N., Bauer Jr, K. W. and Wilson, J. R., "Simulation
of stochastic activity networks using path control variates", Journal
of Naval Research, Vol. 38, pp. 183-201 (1991).
[5] Ball, M. O., "Computational complexity of network reliability anal-
ysis: An overview", IEEE Transactions on Reliability, Vol. 35, No.
3, pp. 230-239 (1986).
[6] Barlow, R. and Proschan, F., Statistical Theory of Reliability and
Life Testing, New York: Holt, Rinehart and Wilson, (1975).
[7] Bulteau, S. and Khadiri, M. El, "A Monte Carlo algorithm based on
a state-space decomposition methodology for
flow network reliability
evaluation", Technical Report, IRISA-INRIA, 1012 (1996).
[8] Bulteau, S. and Khadiri, M. El, "A Monte Carlo simulation of the
flow network reliability using importance and strati ed sampling",
Technical Report, IRISA-INRIA, 3122 (1997).
[9] Bulteau, S. and Khadiri, M. El, "A new importance sampling Monte
Carlo method for a
ow network reliability problem", Naval Re-
search Logistics, Vol. 49, No. 2, pp. 204-228 (2002).
[10] Burt, J. M., Gaver, D. P. and Perlas., M., "Simple stochastic net-
works: Some problems and procedures", Technical report, Naval
Research Logistics Quarterly, (1970).
[11] Cancela, H. and Khadiri, M. E., "A recursive variance-reduction
algorithm for estimating communication-network reliability", IEEE
Transactions on Reliability, Vol. 44, No. 4, pp. 595-602 (1995).
[12] Cancela, H. and Khadiri, M. E., "Series-parallel reductions in Monte
Carlo network reliability evaluation", IEEE Transactions on Relia-
bility, Vol. 47, No. 2, pp. 159-164 (1998).
[13] Cancela, H. and Khadiri, M. E., "The recursive variance-reduction
simulation algorithm for network reliability evaluation", IEEE
Transactions on Reliability, Vol. 52, No. 2, pp. 207-212 (2003).
[14] Cancela, H., L'Ecuyer, P., Lee, M., Rubino, G. and Tu n, B. ,
"Analysis and improvements of path-based methods for Monte Carlo
reliability evaluation of static models", Simulation Methods for Re-
liability and Availability of Complex Systems, S. M. J. Faulin, A. A.
Juan and E. Ramirez-Marquez, Eds. Springer Verlag, (2009).
[15] Cheng, R. C. H., "Variance reduction methods", Proceedings of the
18th Conference on Winter Simulation, pp. 60-68 (1986).
[16] Colbourn, C. J., The Combinatorics of Network Reliability, New
York: Oxford University Press, (1987).
[17] Cristian, C., "Using multi-stage and strati ed sampling for inferring
fault-coverage probability", IEEE Transactions on Reliability, Vol.
44, No. 4, pp. 632-639 (1995).
[18] Dagpunar, J. S., Simulation and Monte Carlo with Application in
Finance and MCMC, John Wiley & Sons, Ltd. (2007).
[19] Doulliez, P. and Jamoulle, E., "Transportation Networks with Ran-
dom Arc Capacities", R.A.I.R.O., Vol. 3, pp. 45-60 (1972).
[20] . Easton, M. C. and Wong, C. K., "Sequential destruction method
for Monte Carlo evaluation of system reliability", IEEE Transactions
on Reliability, Vol. R-29, No. 1, pp. 27-32 (1980).
[21] Elperin, T., Gertsbakh, I. B. and Lomonosov, M.," Estimation of
network reliability using graph evolution models", IEEE Transac-
tions on Reliability, Vol. 40, No. 5, pp. 572-581 (1991).
[22] Elperin, T., Gertsbakh, I. B. and Lomonosov, M., "An evolution
model for Monte Carlo estimation of equilibrium network renewal
parameters", Probability in the Engineering and Informational Sci-
ences, Vol. 6, pp. 457-469 (1992).
[23] Fishman, G., "A Comparison of Four Monte Carlo Methods for Es-
timating the Probability of s-t Connectedness", IEEE Transactions
on Reliability, Vol. 35, pp. 145-154 (1986).
[24] Fishman, G., "A Monte Carlo Sampling Plan for Estimating Net-
work Reliability", Operations Research, Vol. 34, No. 4, pp. 581-594
(1986).
[25] Fishman, G., "Estimating the s-t Reliability Function Using Impor-
tance and Strati ed Sampling", Operations Research, Vol. 37, No.
3, pp. 462-473 (1989).
[26] Fishman, G. and Shaw, T. Y. D., "Evaluating Reliability of Stochas-
tic Flow Networks", Probability in the Engineering and Informa-
tional Sciences, Vol. 3, pp. 493-509 (1989).
[27] Fishman, G. S. and Huang, B. D., "Antithetic variates revisited",
Communication ACM, Vol. 26, No. 11, pp. 964-971 (1983).
[28] Gal, S., Rubinstein, Y. and Ziv, A., "On the optimality and e -
ciency of common random numbers", Mathematics and Computers
in Simulation, Vol. 26, pp. 502-512 (1984).
[29] Gertsbakh, I. B. and Shpungin, Y., Models of Network Reliability,
Boca Raton, FL: CRC Press, (2009).
[30] Glasserman, P. and Yao., D. D., "Some guidelines and guarantees
for common random numbers", Management Science, 38(6):884-908,
1992.
[31] Glasserman, P., Monte Carlo Methods in Financial Engineering,
Springer-Verlag New York, Inc. (2004).
[32] Glynn, P. W. and Iglehart, D. L., "Importance Sampling for Stochas-
tic Simulations", Management Science, Vol. 35, No. 11, pp. 1367-
1392 (1989).
[33] Hammersley, J. M. and Handscomb, D. C., Monte Carlo Methods,
Chapman and Hall: London, (1964).
[34] Heegaard, P. E., "Speed-up techniques for simulation", Telektronikk,
Vol. 91, No. 2, (1995).
[35] Heidelberger, P., Shahabuddin, P. and Nicola, V. F., "Bounded rela-
tive error in estimating transient measures of highly dependable non-
Markovian systems", ACM Transactions on Modeling and Computer
Simulation, Vol. 4, pp. 137-164 (1994).
[36] Hui, K. P., Bean, N., Kraetzl, M. and Kroese, D. P., "The Cross-
entropy Method for Network Reliability Estimation", Annals of Op-
erations Research, Vol. 134, No. 1, pp. 101-118 (2005).
[37] Juneja, S. and Shahabuddin, P., Rare event simulation techniques:
An introduction and recent advances, Simulation, ser. Handbooks
in Operations Research and Management Science, S. G. Henderson
and B. L. Nelson, Eds. Amsterdam, The Netherlands: Elsevier, pp.
291-350 (2006).
[38] Kahn, H. and Marshall, "A.W. Methods of reducing sample size
in Monte Carlo computations", Journal of the Operations Research
Society of America. Vol. 1, pp. 263-271 (1953).
[39] Karp, R. and Luby, M. G., A new Monte Carlo method for esti-
mating the failure probability of an n-component system, Computer
Science Division, University of California, Berkeley, (1983).
[40] Khadiri, M. E. and Rubino, G., "A Monte-Carlo method based on
antithetic variates for network reliability computations", Technical
Report, IRISA-INRIA, 626 (1992).
[41] Kleijnen, J. P. C., "Antithetic variates, common random numbers
and optimal computer time allocation in simulations", Management
Science, Vol. 21, pp. 1176-1185 (1975).
[42] Konak, A., Smith, A. E. and Kulture, S., "New event-driven sam-
pling techniques for network reliability estimation", Proceedings
of Winter Simulation Conference , Washington, D.C., pp. 224-231
(2004).
[43] Kroese, D. P. and Hui, K. P.," Applications of the Cross-Entropy
Method in Reliability", Computational Intelligence in Reliability En-
gineering, G. Levitin, ed., Springer-Verlag, pp. 37-82 (2007).
[44] Kumamoto, H., Tanaka, K. and Inoue, K., "E cient evaluation of
system reliability by Monte Carlo method", IEEE Transactions on
Reliability, Vol. 26, No. 5, pp. 311-315 (1977).
[45] Kumamoto, H., Tanaka, K., Inoue, K. and Henley, E. J,. "Dagger-
sampling Monte Carlo for system unavailability evaluation", IEEE
Transactions on Reliability, Vol. R-29, No. 2, pp. 122-125 (1980).
[46] Kwon, C. and Tew, J. D., "Strategies for combining antithetic vari-
ates and control variates in designed simulation experiments", Man-
agement Science, Vol. 40, pp. 1021-1034 (1994).
[47] Lassila, P. E. and Virtamo, H. T., "Nearly optimal importance sam-
pling for Monte Carlo simulation of loss systems", ACM Transac-
tions on Modeling and Computer Simulation, Vol. 10, No. 4, pp.
326-347 (2001).
[48] Law, A. M., Simulation Modeling and Analysis. McGraw-Hill, New
York, NY, USA, 4th edition, (2007).
[49] L'Ecuyer, P., Mandjes, M. and Tu n, B., "Importance sampling and
rare event simulation", Rare Event Simulation Using Monte Carlo
Methods, G. Rubino and B. Tu n, Eds. Wiley, pp. 17-38 (2009).
[50] L'Ecuyer, P., Rubino, G., Saggadi, S. and Tu n, B., "Approximate
zero-variance importance sampling for static network reliability es-
timation", IEEE Transactions on Reliability, Vol. 60, No. 3, pp.
590-604 (2011).
[51] L'Ecuyer, P. and Buist, E., "Variance reduction in the simulation
of call centers". Proceedings of the 38th conference on Winter sim-
ulation, Monterey, California, Winter Simulation Conference, pp.
604-613 (2006).
[52] Lin, C. H., and Yang, W. N., "A simple and e cient importance
sampling scheme for stochastic network unreliability estimation",
Simulation Modelling Practice and Theorey, Vol. 19, pp. 924-935
(2011).
[53] Megiddo, N., Hakimi, S. L., Garey, M. R., Johnson, D. S. and Pa-
padimitriou, C.H., "The complexity of searching a graph" (prelimi-
nary version) Proc. IEEE Foundations of Computer Science Symp.,
Nashville, pp. 376-385 (1981)
[54] Monien, B and Sudborough, I. H., "Min cut is NP-complete for edge
weighted trees", Theoretical Computer Science, Vol. 58, pp. 209-229,
(1988).
[55] Nelson, B. L., "Control variates remedies". Operations Research,
Vol. 38, pp. 974-992 (1990).
[56] Pagano, M. and Sandmann, W. "E cient Rare Event Simulation: A
Tutorial On Importance Sampling", HET-NETs '05, pp. 1-38 (2005).
[57] Ross, S. M., " A new simulation estimator of system reliability",
Journal of Applied Mathematics and Stochastic Analysis, Vol. 7, No.
3, pp. 331-336 (1994).
[58] Rubino, G., "Network reliability evaluation", State-of-the art in per-
formance modeling and simulation, K. Bagchi and J. Walrand, Eds.
Gordon and Breach Books, (1998).
[59] Rubinstein, R. Y., Simulation and the Monte Carlo Method, Wiley
New York (1981).
[60] Sandmann, W., "E ciency of importance sampling estimators",
Journal of Simulation, Vol. 1, pp. 137-145 (2007).
[61] Schruben, L. W. and Margolin, B. H., "Pseudorandom number as-
signment in statistically designed simulation and distribution sam-
pling experiments", Journal of the American Statistical Association,
Vol. 73, pp. 504-525 (1978).
[62] Smith, P., Sha , M. and Gao, H., "Quick Simulation: A Review
of Importance Sampling Techniques in Communications Systems",
IEEE Journal on Selected Areas in Communications, Vol. 15, pp.
597-613 (1997).
[63] Srinivasan, R., Importance Sampling, Springer-Verlag: Berlin Hei-
delberg New York, (2002).
[64] Stoer, M. and Wagner, F,. "A simple min-cut algorithm", Journal
of the ACM, Vol. 44, pp. 585-591 (1997).
[65] Tew, J. D. and Wilson, J. R., "Estimating simulation metamodels
using combined correlation based variance reduction techniques".IIE
Transactions, Vol. 26, pp. 2-26 (1994).
[66] Valiant, L. G., "The Complexity of Enumeration and Reliability
Problems", SIAM Journal on Computing, Vol. 8 No. 3, pp. 410-421
(1979).
[67] Yang, W. N. and Nelson, B. L.," Using common random numbers
and control variates in multiple-comparison procedures", Operations
Research, Vol. 39, No. 4, pp.583-591 (1991).
[68] Yang, W. N. and Liou, W. "Combining antithetic variates and con-
trol variates in simulation experiments", ACM Transactions Model
Computation Simulation, Vol. 6, No. 4, pp. 243-260 (1996).
[69] Yang, W. N., Shih, W. L. and Yeh, J. C., "A simple recursive im-
portance and strati ed sampling scheme for stochastic network reli-
ability estimation", Simulation Modelling Practice and Theory, Vol.
29, pp. 137-148 (2012).
[70] Yeh, W. C., "A new Monte Carlo method for the network reliabil-
ity", Proceedings of First International Conference on Information
Technologies and Applications, (2002).