Table of Contents
Preface xi
Notation and Abbreviations xv
1 What is Monte Carlo Method? 1
1.1 Area Estimation 1
1.2 Optimal Location of Components 3
1.3 Reliability of a Binary System 6
1.4 Statistics: a Short Reminder 7
1.4.1 Unbiased estimators 7
1.4.2 Variance behavior of an estimator as sample size increases 9
1.4.3 Variance in a multinomial experiment 11
1.4.4 Confidence interval for population mean based on the normal approximation 12
1.4.5 Confidence interval for the binomial parameter: Poison approximation 13
1.5 Problems and Exercises 14
2 What is Network Reliability? 21
2.1 Introduction 21
2.1.1 General description 21
2.1.2 Networks: Topology 22
2.1.3 Networks: Reliability perspective 24
2.2 Spanning Trees and Kruskal's Algorithm 26
2.2.1 Spanning tree: definitions, algorithms 26
2.2.2 DSS - disjoint set structures 30
2.3 Introduction to Network Reliability 36
2.3.1 Static networks 36
2.3.2 Dynamic networks 40
2.4 Multistate Networks 40
2.5 Network Reliability Bounds 42
2.6 Problems and Exercises 43
3 Exponentially Distributed Lifetime 49
3.1 Characteristic Property of the Exponential Distribution 49
3.2 Exponential Jump Process 50
3.3 Examples 52
3.4 Problems and Exercises 56
4 Static and Dynamic Reliability 59
4.1 System Description. Static Reliability 59
4.2 Dynamic Reliability 61
4.3 Stationary Availability 62
4.4 Burtin-Pittel Formula 63
4.5 Pivotal Formula. Reliability Gradient 67
4.6 Problems and Exercises 70
5 Reliability Gradient 75
5.1 Definition of Border States 75
5.2 Gradient and Border States 77
5.3 Problems and Exercises 80
6 Order Statistics and D-spectrum 81
6.1 Reminder of Basics in Order Statistics 81
6.2 Min-Max Calculus 83
6.3 Destruction Spectrum (D-spectrum) 84
6.4 Number of Minimal size Min-Cuts 86
6.5 Problems and Exercises 88
7 Monte Carlo of Convolutions 91
7.1 CMC for Calculating Convolutions 91
7.2 Analytic Approach 92
7.3 Conditional Densities and Modified Algorithm 94
7.4 Generating Bm(T) 95
7.5 How Large is Variance Reduction Comparing to the CMC? 96
7.6 Importance Sampling in Monte Carlo 97
7.7 Problems and Exercises 98
8 Network Destruction 101
8.1 Introduction 101
8.2 Estimation of FN(t) = P(τ* ≤ t) 102
8.3 Unreliable Nodes 106
8.4 Identically Distributed Edge Lifetimes 107
8.5 Examples of Using D-spectra 111
8.6 Problems and Exercises 115
9 Lomonosov's "Turnip" 119
9.1 Introduction 119
9.2 The Turnip 120
9.2.1 The idea of the turnip 120
9.2.2 Artificial creation process 120
9.2.3 The closure 121
9.2.4 Turnip as evolution process with closure 122
9.3 Applications of Turnip 127
9.3.1 Availability Av(N) 127
9.3.2 The mean stationary UP and DOWN periods 127
9.3.3 Estimation of &CyrT;(N) for all-terminal connectivity 129
9.3.4 Estimation of &CyrT;(N) for T-terminal connectivity 130
9.3.5 Monte Carlo algorithm for the gradient 132
9.4 Unreliable Nodes 135
9.5 Problems and Exercises 135
10 Importance Measures and Spectrum 139
10.1 Introduction: Birnbaum Importance Measure 139
10.2 Cumulative Spectrum 140
10.3 BIM and the Cumulative C*-spectrum 142
10.4 BIM and the Invariance Property 145
10.5 Examples 147
10.6 Problems and Exercises 150
11 Optimal Network Synthesis 153
11.1 Introduction to Network Synthesis 153
11.2 "Asymptotic" Synthesis 158
11.3 Synthesis Based on Importance Measures 160
11.4 Problems and Exercises 164
12 Dynamic Networks 165
12.1 Introduction: Network Exit Time 165
12.2 Bounds on the Network Exit Time 166
13 Examples of Network Reliability 171
13.1 Colbourn & Harms' Ladder Network 171
13.2 Integrated Communication Network (ICN) 174
13.2.1 General description 174
13.2.2 ICN reliability 176
13.2.3 Network reinforcement 179
Appendix A O() and o() symbols 185
Appendix B Convolution of exponentials 187
Appendix C Glossary of D-spectra 189
References 195
Index 199
