The Cross-Entropy Method for Network Reliability Estimation

Consider a network of unreliable links, modelling for example a communication network. Estimating the reliability of the network—expressed as the probability that certain nodes in the network are connected—is a computationally difficult task. In this paper we study how the Cross-Entropy method can be used to obtain more efficient network reliability estimation procedures. Three techniques of estimation are considered: Crude Monte Carlo and the more sophisticated Permutation Monte Carlo and Merge Process. We show that the Cross-Entropy method yields a speed-up over all three techniques.     

Honest Importance Sampling With Multiple Markov Chains

Importance sampling is a classical Monte Carlo technique in which a random sample from one probability density, π₁, is used to estimate an expectation with respect to another, π. The importance sampling estimator is strongly consistent and, as long as two simple moment conditions are satisfied, it obeys a central limit theorem (CLT). Moreover, there is a simple consistent estimator for the asymptotic variance in the CLT, which makes for routine computation of standard errors. Importance sampling can also be used in the Markov chain Monte Carlo (MCMC) context. Indeed, if the random sample from π₁ is replaced by a Harris ergodic Markov chain with invariant density π₁, then the resulting estimator remains strongly consistent. There is a price to be paid, however, as the computation of standard errors becomes more complicated. First, the two simple moment conditions that guarantee a CLT in the iid case are not enough in the MCMC context. Second, even when a CLT does hold, the asymptotic variance has a complex form and is difficult to estimate consistently. In this article, we explain how to use regenerative simulation to overcome these problems. Actually, we consider a more general setup, where we assume that Markov chain samples from several probability densities, π₁, …, π_k, are available. We construct multiple-chain importance sampling estimators for which we obtain a CLT based on regeneration. We show that if the Markov chains converge to their respective target distributions at a geometric rate, then under moment conditions similar to those required in the iid case, the MCMC-based importance sampling estimator obeys a CLT. Furthermore, because the CLT is based on a regenerative process, there is a simple consistent estimator of the asymptotic variance. We illustrate the method with two applications in Bayesian sensitivity analysis. The first concerns one-way random effect models under different priors. The second involves Bayesian variable selection in linear regression, and for this application, importance sampling based on multiple chains enables an empirical Bayes approach to variable selection.     

用重要性抽样法估计单调关联系统不可靠度

本文首先叙述了基于单调关联故障树模型成败型仿真的重要性抽样的基本原理，然后通过设计几种执行重要性抽样的试验方案，总结得到了在实践中执行重要性抽样若干有益的规则，最后的小结简述了似然比的概念在仿真研究中的重要应用。     

Sampling colourings of the triangular lattice

We show that the Glauber dynamics on proper 9‐colourings of the triangular lattice is rapidly mixing, which allows for efficient sampling. Consequently, there is a fully polynomial randomised approximation scheme (FPRAS) for counting proper 9‐colourings of the triangular lattice. Proper colourings correspond to configurations in the zero‐temperature anti‐ferromagnetic Potts model. We show that the spin system consisting of proper 9‐colourings of the triangular lattice has strong spatial mixing. This implies that there is a unique infinite‐volume Gibbs distribution, which is an important property studied in statistical physics. Our results build on previous work by Goldberg, Martin and Paterson, who showed similar results for 10 colours on the triangular lattice. Their work was preceded by Salas and Sokal's 11‐colour result. Both proofs rely on computational assistance, and so does our 9‐colour proof. We have used a randomised heuristic to guide us towards rigourous results. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 501–533, 2012     

FTA法和重要度分析在某系统可靠性中的应用

应用失效树分析（Fault Tree Analysis）法（简称FTA法）,对某型火炮遥控系统进行了可靠性分析,建立了该系统的失效树,并在此基础上计算了该系统的可靠性参数,讨论了部件的概率重要度和相对比重要度,并把部件的概率重要度和相对比重要度推广到了分系统,结合所建的失效树给出了相应的结果。通过重要度分析,找到了提高系统可靠性中的途径。     

Computing Normalizing Constants for Finite Mixture Models via Incremental Mixture Importance Sampling (IMIS)

This article proposes a method for approximating integrated likelihoods in finite mixture models. We formulate the model in terms of the unobserved group memberships, z, and make them the variables of integration. The integral is then evaluated using importance sampling over the z. We propose an adaptive importance sampling function which is itself a mixture, with two types of component distributions, one concentrated and one diffuse. The more concentrated type of component serves the usual purpose of an importance sampling function, sampling mostly group assignments of high posterior probability. The less concentrated type of component allows for the importance sampling function to explore the space in a controlled way to find other, unvisited assignments with high posterior probability. Components are added adaptively, one at a time, to cover areas of high posterior probability not well covered by the current importance sampling function. The method is called incremental mixture importance sampling (IMIS).

IMIS is easy to implement and to monitor for convergence. It scales easily for higher dimensional mixture distributions when a conjugate prior is specified for the mixture parameters. The simulated values on which the estimate is based are independent, which allows for straightforward estimation of standard errors. The self-monitoring aspects of the method make it easier to adjust tuning parameters in the course of estimation than standard Markov chain Monte Carlo algorithms. With only small modifications to the code, one can use the method for a wide variety of mixture distributions of different dimensions. The method performed well in simulations and in mixture problems in astronomy and medical research.     

基于系统可靠性的组件综合重要度变化机理分析

重要度理论是一种重要的系统薄弱环节识别和评估方法,被广泛应用于系统可靠性设计优化、维修资源分配、维修决策以及风险分析等领域。本文以组件状态转移率为纽带,分析了组件综合重要度对系统可靠性的影响机理,识别对系统可靠性变化影响最大的组件,综合重要度评估了单位时间内系统可靠性的变化。首先给出综合重要度的定义;其次讨论系统可靠性的组件重要度表示方法;最后在串联和并联系统中,分析综合重要度随着组件状态转移率的变化机理。     

Reliability Importance Measures of the Components in a System Based on Semivalues and Probabilistic Values

The main contribution of this paper consists in providing different ways to value importance measures for components in a given reliability system or in an electronic circuit. The main tool used is a certain type of semivalues and probabilistic values. One of the results given here extends the indices given by Birnbaum [3] and Barlow and Proschan [2], which respectively coincide with the Banzhaf [1] and the Shapley and Shubik [15] indices so well-known in game theory.     

Gamma分布下混联系统综合重要度扩展及应用

综合重要度分析不仅可以有效的识别系统的薄弱环节,还可以合理分配资源,最大化整个系统的正常运行时间。本文主要对劣化系统的组(部)件进行综合重要度分析,假设组(部)件寿命服从Gamma分布,推导出并-串联和串-并联两种典型混联系统综合重要度的等价计算公式,同时给出物理意义。以波音737客机的液压能源混联系统为例,计算各组(部)件的综合重要度以及仿真案例分析,最后案例分析结果表明:在Gamma分布条件下的混联系统中,组(部)件的综合重要度与失效率和尺度参数成正相关,和形状参数成负相关关系。     

一类线性规划问题的随机中心路径算法

本文针对一类仅具不等式约束的线性规划问题提出了一种随机化的中心路径算法,并证明了算法的收敛性.初步的数值实验说明了算法的有效性.     

线形(n,f,k)系统和系统的可靠度计算新方法

本文应用两端同时进行的有限马尔可夫链嵌入法给出了具有复合失效准则的(n,f,k)系统和系统可靠度计算公式及公式中连接矩阵的结构特点。数值计算结果表明,随着构成系统的单元个数的增加,应用两端同时进行的有限马尔可夫链嵌入法比应用传统的有限马尔可夫链嵌入法计算可靠度能节省大量运算时间,特别是对于具有对称结构的(n,f,k)和系统效果更加明显。