臺灣博碩士論文加值系統

近年來，利用隨機網路模型來模擬系統的運作已被廣泛地被運用,
而在隨機網路模型中，網路可靠度常被視為一項重要的績效指標。
實際上，當網路規模複雜時，精確地計算出網路可靠度是行不通的。
因此利用蒙地卡羅模擬法來估計網路可靠度則成為較可行的作法，
但是普通的模擬將耗費巨大的抽樣成本，
因此變異數縮減技術即是在不增加抽樣成本的情況下，得到更為精確的統計數據。
本論文提出了一個簡單遞迴重點和分層抽樣程序得到一個不偏且更精準的網路可靠度估計量。
在每個遞迴步驟中，利用重點抽樣不分配樣本給網路狀態已經決定的子網路，
而預先分配兩個樣本給未決定網路狀態的子網路，再利用比例分層抽樣分配剩餘的樣本，
如此加強遞迴分層抽樣的效果，得到更準確的不偏估計量和變異數的估計量。
實驗數據證實本論文所提出之簡易遞迴的重點和分層抽樣程序，
可達到顯著的變異數縮減效果，尤其是面臨高可靠度的隨機網路時。

Crude simulation for estimating reliability of a tochastic network often requires large sample size to obtain statistically significant results.
In this paper, we propose a simple recursive importance and stratified
sampling estimator which is shown to be unbiased and achieve smaller
variance. Preallocation of sampling efforts of size two to each
undetermined subnetwork on each stage makes it possible to estimate
the variance of the proposed estimator and significantly enhances
the effectiveness of variance reduction from stratification by
deferring the termination of recursive stratification. Experimental results show that the proposed estimator achieves significant
variance reduction, especially for highly reliable networks.

中文摘要 i
Abstract ii
誌謝 iii
1 Introduction 1
2 Preliminaries 4
2.1 Network Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Crude Monte Carlo sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Variance Reduction Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3.1 Common Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.2 Antithetic Variates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.3 Control Variates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.4 Stratied Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.5 Conditional Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.6 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Proposed Recursive Importance and Stratied Estimator 16
3.1 Algorithm of The Proposed Estimator . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Unbiasedness and Variance of The Proposed Estimator . . . . . . . . . . . . . . 21
4 Empirical Study 24
4.1 Proposed Estimator With and Without Preallocation of Sampling E ort . . . . 26
5 Comparison with Other Methods 29
6 Conclusion and Future Works 32
References 33
Curriculum Vitae 36
Publication List 37

[1] S. Bulteau, M. El Khadiri, A Monte Carlo simulation of the flow network reliability using
importance and stratied sampling, Technical Report, Institut de Recherche en Informa-
tique et Systemes Aleatoires and Institut National de Recherche en Informatique et en
Automatique, 3122 (1997).
[2] S. Bulteau, M. El Khadiri, A Monte Carlo algorithm based on a state-space decompo-
sition methodology for flow network reliability evaluation, Technical Report, Institut de
Recherche en Informatique et Systemes Aleatoires and Institut National de Recherche en
Informatique et en Automatique, 1012 (1996).
[3] S. Bulteau, M. El Khadiri, A new importance sampling Monte Carlo method for a flow
network reliability problem, Naval Research Logistics, 49 (2) (2002) 204-228.
[4] R.C.H. Cheng, Variance Reduction Methods, Proceedings of the 18th Conference on Win-
ter Simulation (1986) 60-68.
[5] C. Cristian, Using Multi-stage and Stratied Sampling for Inferring Fault-Coverage Prob-
ability, IEEE Transactions on Reliability 44 (4) (1995) 632-639.
[6] H. Cancela and M.E. Khadiri, A Recursive Variance-reduction Algorithm for Estimating
Communication-network Reliability, IEEE Transactions on Reliability 44 (4) (1995) 595-
602.
[7] H. Cancela and M.E. Khadiri, Series-parallel Reductions in Monte Carlo Network Relia-
bility Evaluation, IEEE Transactions on Reliability 47 (2) (1998) 159-164.
[8] H. Cancela and M.E. Khadiri, The Recursive Variance-reduction Simulation Algorithm for
Network Reliability Evaluation, IEEE Transactions on Reliability 52 (2) (2003) 207-212.
[9] J. S. Dagpunar, Simulation and Monte Carlo with Application in Finance and MCMC,
John Wiley & Sons, Ltd. (2007).
[10] P. Doulliez and E. Jamoulle, Transportation Networks with Random Arc Capacities,
R.A.I.R.O. 3 (1972) 45-60.
[11] M.C. Easton and C.K. Wong, Sequential Destruction Method for Monte Carlo Evaluation
of System Reliability, IEEE Transactions on Reliability 29 (1980) 27-32.
[12] T. Elperin, I.B. Gertsbakh and M. Lomonosov, An evolution model for Monte Carlo es-
timation of equilibrium network renewal parameters, Probability in the Engineering and
Informational Sciences 6 (1992) 457-469.
[13] T. Elperin, I.B. Gertsbakh and M. Lomonosov, Estimation of network reliability using
graph evolution models, IEEE Transactions on Reliability 40 (5) (1991) 572-581.
[14] G. Fishman, A Comparison of Four Monte Carlo Methods for Estimating the Probability
of s-t Connectedness, IEEE Transactions on Reliability 35 (1986) 145-154.
[15] G. Fishman, A Monte Carlo Sampling Plan for Estimating Network Reliability, Operations
Research 34 (4) (1986) 581-594.
[16] G. Fishman, Estimating the s-t Reliability Function Using Importance and Stratied Sam-
pling, Operations Research 37 (3) (1989) 462-473.
[17] G. Fishman and T.Y.D. Shaw, Evaluating Reliability of Stochastic Flow Networks, Prob-
ability in the Engineering and Informational Sciences 3 (1989) 493-509.
[18] P. Glasserman, Monte Carlo Methods in Financial Engineering, Springer-Verlag New York,
Inc. (2004) 221, 227.
[19] J.M. Hammersley, J.G. Mauldon, General principles of antithetic variates, Mathematical
Proceedings of the Cambridge Philosophical Society, 52 (1956) 476-481.
[20] K.P. Hui, N. Bean, M. Kraetzl and D.P. Kroese, The Cross-entropy Method for Network
Reliability Estimation Annals of Operations Research 134 (1) (2005) 101-118.
[21] R. Karp and M.G. Luby, A New Monte Carlo Method for Estimating the Failure Prob-
ability of an N-component System, Computer Science Division, University of California,
Berkely, 1983.
[22] M. El Khadiri, G. Rubino, A Monte-Carlo method based on antithetic variates for network
reliability computations, Technical Report, Institut de Recherche en Informatique et Sys-
temes Aleatoires and Institut National de Recherche en Informatique et en Automatique,
626 (1992).
[23] H. Kumamoto, K. Tanaka, K. Inoue and E.J. Henley, Dagger Sampling Monte Carlo for
System Unavailability Evaluation, IEEE Transactions on Reliability 29 (2) (1980) 122-125.
[24] H. Kumamoto, K. Tanaka, K. Inoue, Efficient evaluation of system reliability by Monte
Carlo method, IEEE Transactions on Reliability, 26 (5) (1977) 311-315.
[25] A. Konak, A.E. Smith and S. Kulturel-Konak, New Event-driven Sampling Techniques
for Network Reliability Estimation, Proceedings of Winter Simulation Conference 2004,
Washington, D.C., December 5-8, 224-231.
[26] A.L. Law, D.W. Kelton, Simulation modeling and analysis, 3rd Edition, Boston: McGraw-
Hill, (2000).
[27] S.S. Lavenberg, P.D. Welch, A perspective on the use of control variables to increase the
efficiency of Monte Carlo simulations, Management Science, 27 (1981) 322-335.
[28] M. Lomonosov, On Monte Carlo estimates in network reliability, Probability in the Engi-
neering and Informational Sciences, 8 (1994) 245-264.
[29] B.D. Ripley, Stochastic simulation, New York: Wiley, (1987).
[30] S.M. Ross, A new simulation estimator of system reliability, Journal of Applied Mathe-
matics and Stochastic Analysis, 7 (3) (1994) 331-336.
[31] R. Y. Rubinstein and G. Samorodnitsky, Variance Reduction by the Use of Common and
Antithetic Random Variables, J. Statist. Comput. Simulation 22 (1985) 161-180.
[32] P. Smith, M. Shafi and H. Gao, Quick Simulation: A Review of Importance Sampling Tech-
niques in Communications Systems, IEEE Journal on Selected Areas in Communications
15 (1997) 597-613.
[33] L.G. Valiant, The Complexity of Enumeration and Reliability Problems, SIAM Journal on
Computing 8 (3) (1979) 410-421.
[34] W.C. Yeh, A new Monte Carlo method for the network reliability, Proceedings of First
International Conference on Information Technologies and Applications, (2002).