马尔可夫系统中间估计条件Monte Carlo方法的精确可靠性模拟与实验验证

可在www.sciencedirect.com在线获取理论计算机科学电子笔记321（2016）3-21www.elsevier.com/locate/entcs马尔可夫系统的中间估计条件MonteCarlo方法H'ectorCancela赫克特·坎塞拉1，2乌拉圭蒙得维的亚Repu'blic大学Leslie Murray莱斯利·默里1，3FacultaddeCienciasExactas，Ingenier'ıayAgrimensuraUniversidad Nacional de Rosario阿根廷罗萨里奥Gerardo Rubino杰拉多·鲁比诺1，4INRIA-雷恩布列塔尼大区，法国雷恩博摘要对于适合用连续马尔可夫链建模的系统，可靠性分析并不总是简单的。当这样的系统是大型和复杂的，它通常是不可能准确地计算其可靠性措施。 另一种解决方案是通过模拟来估计它们，通常Monte Carlo模拟。但对于高可靠性系统，标准模拟无法在合理的计算时间内达到令人满意的精度水平（由估计量的方差条件蒙特卡罗中间估计（CMIE）是一种模拟方法，旨在对高可靠马尔可夫系统的可靠性度量进行精确估计。 CMIE的基础的估计量的无偏性，并证明了其方差小于标准估计量的方差。一个变种的基本计划，适用于大型和高可靠性的多组分系统，介绍。给出了一些实验结果关键词：可靠性，模拟，稀有事件，条件蒙特卡罗。1 本 工 作 得到了以下机构的部分支 持 ：B'asicas 科 学 发 展 研 究 所 、 PEDECIBA-Inform'a t i c a 、 S T I C -A M S U D 项 目 1 3S T I C - 0 1A M M A “ 用 于 动 态 W D M 光 网 络 分 析 和 设 计 的 加 速 模 型 ” 和 1 5S T I C - 0 7 D A T “ 可 靠 性 分 析 工 具 ” 。2电子邮件：cancela@fing.edu.uy3电子邮件：leslie@eie.fceia.unr.edu.ar4电子邮件：Gerardo. inria.frhttp://dx.doi.org/10.1016/j.entcs.2016.02.0021571-0661/© 2016作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。4H. Cancela等人/理论计算机科学电子笔记321（2016）31引言我们考虑可以由有限状态空间S上的连续时间齐次马尔可夫链X不可约建模的系统（见[5，10，11]或[22]中的第6章）。链也可以是吸收的，这里描述的技术仍然有效，但它们更容易在不可约的情况下呈现。在这种情况下，一些可靠性的度量需要评估概率γ=P{τDτu}，其中时间τu和τD定义如下。<马尔可夫链的状态空间被划分为S=U<$D，使得在U中系统向上，在D中系统向下。过程X起始于某个初始状态u∈U。定义τu为返回u的时间，即τu= inf {t > 0：X（t）=u和X（t −）/= u}，τ D为D的命中时间，即τ D= inf {t > 0：X（t）∈D}。最简单和最基本的可靠性度量是平均故障时间该度量允许公知的由于我们关注的是γ的估计，所以我们可以将所有D坍缩为单个状态d，使其吸收。如前所述，事件{τdτu}意味着X在回到u之前在d处被吸收。<对于具有大量（或无限）状态的系统，γ的精确计算是不可行的，标准蒙特卡洛模拟将起作用，除非γ1，在这种情况下，我们面临着一个罕见事件问题，在这种情况下，估计量方差的可接受值只能以非常高的重复次数为因此，蒙特卡罗方法必须加以改进和调整，以有效地解决这一罕见事件的问题。在这方面的研究已经产生了大量的解决方案，其中大部分来自两个著名的技术家族，分别命名为分裂[7，8，13，19，26]和重要性抽样[4，5，9]。在[24]和[25]中可以找到分裂在高可靠系统背景下的一些应用，其中使用称为RESTART的变体分析可修复系统的可靠性和可用性估计。最近，在[3]和[12]中发表了一些关于静态系统的结果。从重要性抽样中衍生出来的一些方法，如零方差[15，16，17]和交叉熵[20，23]已经成功地应用于受罕见事件影响的系统的模拟。条件蒙特卡罗[12，21]是一种经典的方差缩减技术，在应用于可靠性估计的罕见事件领域中尚未产生许多方法。然而，在[1，2，6，27]中可以找到一些应用，但大多数都是针对处理重尾分布的模型中的罕见事件概率估计本文讨论了可靠性估计问题在迄今为止定义的模型中，并介绍了一种适用于γ估计的条件蒙特卡罗模拟方案。本文的其余部分组织如下。第2节展示了条件蒙特卡罗在马尔可夫系统上的基本应用。第3节是本文的核心，介绍了对基本条件蒙特卡罗算法的修改，以便H. Cancela等人/理论计算机科学电子笔记321（2016）35⎨^⎧⎪⎨我的天p.pd，使它变得可用和高效。第4、5和6节讨论了所提出的方法的一些性质和特征。第7节展示了如何将其应用于马尔可夫多组分系统的特殊情况。一些实验结果包括在第6节和第7节中。与拆分的比较见第8节。结论和未来方向见第9节。2条件蒙特卡罗算法γ值的估计有不同的模拟方法。在原始或标准模拟中，N1个复制从状态u开始，并且它们被模拟，直到它们在时间τu返回到u，或者在时间τd到达状态d。设I为事件{τd<τu}的指示随机变量：I=101 w. p.γ，100 W。p. 1 −γ。则γ=E{I}。其标准估计量γs为：N1（一）γ^s1= Nj=1第一（j）、（2）段其中I（j），j = 1，2，.，N1是从分布（1）中采样的N 1个独立值。令C={d，k，u}，其中k是S中除d或u之外的任何状态，并且令XC为一个随机变量，定义为C中的第一个状态，它被从u开始的复制命中：XC=kw. p. p k，萨科乌河p. pu。注意pd≤γ，因为γ是任何从u开始的复制在回到u之前到达d的概率，而pd是相同的概率，前提是同理，pu≤1 −γ。以XC的值为条件的I的期望由以下表达式给出：E{I|X C= d}= 1，E{I|X C=k}= γ k和E{I|X C= u}= 0（γ k是从状态k开始的复制在到达状态u之前到达状态d的概率）。因此，E{I|X C}是具有以下概率分布的随机变量：E{I|X C}=1 W. p.pd，γ kw.p. p k，100W. p.pu，（三）Σ16H. Cancela等人/理论计算机科学电子笔记321（2016）3ΣCCCCC⎪⎪⎪⎩ΣΣ˜CC}=1000000000000000.E {I|X C.（五）以及以下期望：E{E{I|XC}}= E{I}= 1 ×pd+ γ k×pk+0 ×pu= γ.两个随机变量I和E{I|Xc}是γ。因此，γ的另一个估计量（即条件蒙特卡罗估计量）为：1γ^c=NN1j=1E{I |X（j）}，（4）其中E{I |X（j）}，j = 1，2，. 是N1个共享分布的独立随机变量（3）。 样品E{I |X（j）}分两步获得：首先，对X（j）进行采样然后，对应的值E{I|X（j）}计算。在该介绍性示例中，要采样的X（j）的仅有的三个可能值是{u，k，d}，而E{I|X（j）}与它们相关联的分别是{1，γ k，0}。如果集合C包括除k之外的更多中间状态，则该方法也适用例如，如果C ={d，1，2，.，n，u}，E{I}的分布|X C}变为：101W. p. pd，γ1w. p. p1，⎪⎪γ nw. p. p n，0 w. p. pu，其中γi是从状态i开始的复制在到达状态u之前到达状态d的概率。现在：nE{E{I|X C}}= E{I}= 1 × pd+γ ip i+0 × pui=1n=γi pi=γ，i=0其中为了简单起见，包括符号γ0= 1和p0=pd表达式（4）中给出的估计量仍然有效，唯一的区别是从分布（5）而不是（3）中抽样图1描述了到目前为止定义的概率集，并显示了本文其余部分用来指代它们的命名法（当γu= 0时，项pu×γu等于0，这就是为什么它在图1中显示，但没有出现在任何进一步的表达式中的原因）。对于任何给定的集合C={d，1，2，...，n，u}，称为C=C|{d，u}，即仅由i个中间状态形成的子集，即C|={1，2， . ，n}。1H. Cancela等人/理论计算机科学电子笔记321（2016）37.Σ2我.Σ. −我ΣGN+1P0C1G0P1u1P2G1PN+12G2DPN1VDGN1N1图1.一、所有计算中使用的概率集（4）中的条件蒙特卡罗估计量的方差为：V{γ^}=1. E{E{I|X } }−E{E{I|X}}2个cN11=N1ni=0Cpi γ2−γ2πC.（六）另一方面，（2）中给出的标准估计量的方差已知为：V{γ^s}= 1γγ2 =1个N1N1ni=0pi γi−γ2.（七）比较表达式（6）和（7），并考虑γ i≤ 1，i = 0，.，n，因为所有这些值都是概率，很明显：n npiγ2≤i=0i =0这意味着（6）中给出的条件蒙特卡罗估计量的方差永远不会大于（7）中给出的标准蒙特卡罗估计量的方差。当然，这是条件蒙特卡罗方法的一般事实，但值得在我们的上下文中明确说明3中间估计的条件Monte Carlo使用条件蒙特卡罗的主要问题，正如到目前为止介绍的那样，是值γ1，γ2，.. . ，γn是未知的，这甚至可以作为8H. Cancela等人/理论计算机科学电子笔记321（2016）3^⎪^⎪⎩021nI×γ˜i=1⎨I<$=0，0，1， . ，0，0）w.p. p2，.我.（八）估计，定义Bernoulli随机变量集{Ji}n，以下为很难用γ本身的精确值来计算。为了解决这个问题，这些值现在将被估计值所取代。结果表明，在这种替换之后，该方法仍然是无偏的。 这是本文所介绍的建议的核心，也是所谓的条件蒙特卡罗中间估计（CMIE）方法的基础现在将描述该方法，并且在本节结束时，将确定相应估计量的方差。为了解决下面的计算，最好用随机向量I<$=（I0，I1，.，I n+1），其分量是相依二进制随机变量，使得一个且仅一个具有值1：（1，0，0，...，0，0）w. p. pd，（0，1，0，...，0，0）w. p. p1，⎪⎪（0，0，0，...，1，0）w. p. pn，（0，0，0，...，0，1）w. p. pu。那么，当γ0= 1时，标准估计量γs为：N1γ^s1= Nj=1N1I（j）×γ0n+I（j）×γ1 +I（j）×γ2 加... + I（j）×γ n（十）n+1个1= Nj=1（十）KKk=0（九）在（9）中，样本I（j），I（j），. . .，I（j）是通过模拟获得的，而0 1n值γ1，γ2，...，必须计算γn。 但是，如果这种计算太难，或者根本不可能，这些值可以用标准估计值代替。为了做到这一点，每次模拟达到状态i∈C时，必须在i处开始N2个独立的复制并进行模拟，直到它们达到d（并累积1）或u（并累加0）。一旦这些从i开始的N2次重复完成，就可以计算出标准估计量γ^i并代替γi使用。为了计算这些J=101 w. p.γ i，100 W。p. 1 −γi，i = 1，2，.，n.（十）从马尔可夫链的实际模拟中获得J i的样本，这与从分布（10）（J0= 1 w.p. ①的人。然后，+I概率分布：Σ1×0Σ1H. Cancela等人/理论计算机科学电子笔记321（2016）39^ΣΣΣΣΣ.ΣKK^^^在CMIE估计器中：KK简单地示出γ1是非偏置的：V{γ^cie}= V{E{γ^cie|I<$（x）}}+E{V{γ^cie|I<$（x）}}。意味着I0，I1 ，。......、是这个复制的组成部分。使用方差分解公式，估计量的方差可以写为：N2-Nn如果用公式9中的估计量γk代替γk，则标准估计量被变换为1N1γ.卢恩（十）1N2（i）^cie=N1j=1 N1k=0nIk×NN2JK2i=1=1μ mj=1（j）J（i）。k=0i=11E{γ^cie}=日本语简体中文ΣI（j）J（i）N1N2k=0i=11= N1N2nN1j=1k=0N2 pk γki=1=k=0为了确定γpk γ k= γ.，使得I<$（x）是I<$的一个可能的复制，而（十）（十）（十）^cie`Ax`Bx项A和B分别进行分析，经过一些代数运算（见[18]），我们得到：1V{γ^cie}=A+B=Nnk=0pkγ2−γ2<$+1N1N2nγ−k=0pkγ2.（十一）项A是条件蒙特卡罗估计量的方差值，当值γ1，γ2，.. . ，γn是精确已知的（见（6））。项B是由于值γ1、γ2、.. . ，γn用估计量代替4多组中间状态我们的条件蒙特卡罗应用于马尔可夫链的关键（如第2节所述）-称之为纯条件蒙特卡罗-是概率γ1，γ2，.. . ，γn.由于缺少这些值，因此必须使用估计值（如第3节所述）。该技术是本文提出的CMIE方法的核心。如图所示，估计n Σ.N1N2EKK1Σ10H. Cancela等人/理论计算机科学电子笔记321（2016）3量γ1，γ2，. . ，γ n可以通过每次中间状态1，2，.. . ，n到达。但这些值可以更准确地估计H. Cancela等人/理论计算机科学电子笔记321（2016）311˜˜˜˜ ˜ ˜˜˜˜Σ.ΣK˜˜官网�i图二、两组中间态C1和C 2的情况以如下方式递归地应用相同的条件蒙特卡罗方法。假设定义了两组中间状态，C1和C2，而不是一组，如图2所示。设C1<$C2=n且u，d/∈C1，C2.然后，一旦达到状态i∈C1，则必须在状态i开始N2个复制，并且它们必须被模拟，直到它们到达C2的状态，回到u，或者在d被吸收。这可以被认为是模拟的第二递归级别。目的是得到γ1J，γ2J，. . . ，γNJ1，表明这些N2复制中的每一个在d时被吸收的概率。 这些值不是通过平均值估计的的标准模拟，他们估计更准确地通过这种递归水平的条件蒙特卡罗模拟，使使用C2作为一组中间状态。 将此机制扩展到更递归的级别（具有更多的中间状态集）是很简单的。方差分析可以推广到两组中间变量的情况国家，C1和C2，以直线方式。概率是这样的如图2所示。在[18]中计算的方差如下：1.一、第1章1.1.1.1..2012年2月V{γ^cie}=pl γJ2−γ2+pl1/N2plkγ2−γJ2+N11氮2氮l=0γlJ−Ln2k=0N1p lkγ2l=0K Lk=0给定该表达式，可以得出在具有两组中间状态C1和C2的模型中获得的方差小于或等于在具有单个中间状态C1和C2的模型中获得的方差。GP0P00GN+1P01P0C1PW0C2p0n2P1G0u1GP11P2PW1G1PN+1PW2GP2PW22G2VDPN1DWGPWVDVDGN2简体中文N1GPN1N212H. Cancela等人/理论计算机科学电子笔记321（2016）3^ ^您的位置：^ ^您的位置：估计量V{γ^}，在（6）中导出。C^ ^您的位置：^^^ ^您的位置：KK^^^^ ^您的位置：^V{γ^cie}=k=0+k=0pk γk−γγ−pkγkγ− γ2Σk=0k=05方差比较分析在第3节中，我们推导出了只有一组中间态V{γcie}时CMIE估计量的方差。在本节中，将此方差与其他估计量的方差进行比较，即标准估计量V{γs}的方差（如（7）所示）和纯条件蒙特卡罗的方差当N2→ ∞时，V{γcie}→V{γc}.显然，如果在估计概率γ i，i = 0，.，n是无穷的，估计量收敛到相应的精确值，该方法成为纯条件蒙特卡罗。在第2节的结尾，我们已经证明了V{γc} ≤V{γs}，这意味着纯条件蒙特卡罗的精度永远不会低于标准蒙特卡罗的精度。显然，V{γ c}≤V{γ cie}。我们现在证明V{γcie}≤V{γs}，这意味着所提出的估计量永远不会比标准蒙特卡洛估计量更精确。npk γ2−γ2nγ−pk γ2N1N1 N2中国22+=+N1N1N1≤V{γ s}。无论N1和N2的值如何，不等式都成立.这意味着，即使对于少量的重复N1和N2，所提出的估计量γcie也决不会比标准蒙特卡罗估计量γs更不准确。最后，所涉及的三个方差的关系如下：V{γ c}≤V{γ cie}≤V{γ s}，这意味着CMIE总是比原始或标准蒙特卡罗更准确，但永远不会像纯条件蒙特卡罗那样准确，其中精确值γ i，i= 0，.，n，使用。6中间状态分析CMIE的方差缩减能力取决于中间状态集的选择.在本节中，考虑了中间态集合的两个性质。他们的事迹，可以在[18]中看到。 第一个是在现有集合中添加新状态后，估计量的方差永远不会增加，因此，方差可能会减少。第二个是说，如果我们比较两个不相交的集合得到的方差减少，最高的方差减少来自于某种程度上“更接近”初始状态u的切割这两个性质是一致的，因为如果将一个状态添加到现有的中间状态集合中产生的方差低于或最坏等于添加之前的方差，则产生最小方差的集合是Σ≤H. Cancela等人/理论计算机科学电子笔记321（2016）313C554EC663EC772EC88EC99^^˜ ˜˜^Σ⎝Cie1C04EC13EC22EC3EC4我0U234C104EC113EC122EC13EC141011121314F图3.第三章。连续时间马尔可夫链在实验方差分析中的应用由所有的状态组成：C=S。 但是，从实施的角度来看，因此，集合C=S等价于由相邻状态形成的集合，u，因为如果C=S，对于在初始状态u开始的任何复制，唯一可达的状态是相邻的状态。在两组或多组中间状态的情况下，第二组和连续的中间状态的选择必须在某种程度上类似于关于初始状态u的第一组中间状态的选择。只要有可能，第二个集合（在现有集合和状态d之间）必须由现有集合的相邻状态组成。集然而，这并不简单，必须针对每个特定的模型进行分析。这两个属性现在在Juneja和Shahabuddin在[11]中提出和使用的连续时间马尔可夫链上进行了测试，如图3所示。该系统有2个A类组件和4个B类组件。组件只能运行或发生故障。状态是对（NA，NB），其中Ni表示类别i中的故障组件的数量。A类和B类的故障率分别为1/2和1/2。如果所有类的所有组件都失败，则系统失败。如果同一类别的两个组件发生故障，则开始进行组修复（同时修复同一类别的所有故障组件）。 两个等级的组修理率相等到1.系统中只有一个维修人员，A类优先于B类。表1、2和3示出了在该模型上通过CMIE集合C1、C2和C3都是u和d之间的切割，它们被引用，利用图3中每个状态上方的数字。表3示出了当CMIE和标准模拟运行相同的执行时间时的比率V{γs}/V{γcie}CMIE方法使用gcc编译器以C语言编程估计量γcie及其方差的无偏估计量计算如下：1γ^cie=NN1γ（j） 和j=1V^{γ^cie}= 1⎛⎝1第1章γ（j）2γ−γ^2好吧（十二）j=1表1中的结果表明，达到最低方差的切割是E/2EE/2EE/2EE/2EE/2EN1−1N114H. Cancela等人/理论计算机科学电子笔记321（2016）3^一个由U的相邻状态形成。其相关切割接近状态u的估计量的方差也很低，并且非常相似。但是，当削减是在这些实验中，从状态u开始的复制数量是10，000，从中间状态发起的复制数量也是10，000。实验结果如表2所示，实验表明，随着切割次数的增加，估计量γcie的方差减小。在这些实验中，从状态u开始的复制次数为10，000，从中间状态开始的复制次数为100。包括表3中的实验以简要地显示CMIE方法的方差减少能力。对于所有情况，从中间状态启动的复制的数量为1，000;调整从状态u开始的复制的数量，使得四个模拟中的每一个的总执行时间为t= 500秒。这个时间是预先固定的，并且对于所有方法都是相等的，以便公平比较不同实验获得的准确度表1图3中的模型，= 0。01C-1γ^cieV^{γ^cie}12349表2图3中的模型，= 0。01C-1Cβ2C-13γ^cieV^{γ^cie}1-1-17应用于大型系统有时候马尔可夫链的状态空间S非常大，因此很难明确地选择中间状态。CMIE的思想如果按照以下方式进行调整，则更适合这些模型。在每次重复中，计算值是以以下条件为条件的感兴趣概率γ的样本：H. Cancela等人/理论计算机科学电子笔记321（2016）315表3图3中的模型，= 0。001C-1Cβ2C-13γ^cieV^{γ^cie}V^{γ^s}/V^{γ^cie}4-83-73随机变量XC的值（或达到的中间状态）。 最后，XC的值是从状态u开始的轨迹所遵循的路径πu的函数。但是γ的值可以由与以路径πu为自变量的不同函数相关的事件来决定在下面的小节中，介绍了这些功能的三种可能的替代方案7.1前进的步伐对于某些系统，可以检测在每次跳转时，复制是否向最终状态d移动。在这些情况下，只有在每次向目标状态移动D≥1步后才能进行递归调用。这样，无论模拟从哪里开始，它都必须不断向前和向后移动，直到它回到u，或者向前移动D步到d。如果达到u，复制终止;如果模拟将D步移近d，则启动新的复制（递归调用）。7.2连续失败在有故障和修理的多部件系统中，每一个故障都产生一个向前的步骤，即朝着最终状态d的一个步骤。 对于启动的复制，在某个状态i，有许多方法（路径）使D步更接近目标状态d。其中之一对应于D个连续故障发生的情况如果系统由多于D个部件组成，则会有许多不同的方式发生D个连续故障，所有这些方式都比D个步骤在向前和向后的曲折步骤之后完成的情况少。因此，指示符随机变量I可以以这样的D个连续故障的序列为条件。7.3稀有度的测量设πi，j是一条从状态i开始到状态j结束的路径，没有到达状态j。联合如果这条路径由状态i，k，，l，j，概率模拟通过它，是：P{π i，j}= p ik×. ×plj，其中pxy是从状态x到相邻状态y的概率，无论该跳跃是失败还是修复。为了应用CMIE，指示符变量I可以以事件为条件16H. Cancela等人/理论计算机科学电子笔记321（2016）3P{π i，j} ≤B，其中B是固定界。但是，由于在高度可靠的系统中，大多数概率pxy可能很低，因此值P{πi，j}可能非常低。因此，最好应用对数如下：− log（P{π i，j}）=- log（p ik）−... −log（plj），并以事件−log（P{πi，j}）≥W为条件（其中W=− log（B））。7.4实验比较提出的三种实现方式现在进行实验比较。所有的值--通过使用（12）中所示的公式获得的--与从已发表的论文中获得的结果一致。第一组实验中使用的模型由Cancela et.al. 在[5]中。它是由一个多处理器、一个双磁盘控制器、两个RAID磁盘驱动器、两个风扇、两个电源和一个双处理器间总线组成的计算机。当对偶系统中的一个组件发生故障时，子系统被重构为一个单纯形。这种串联计算机系统需要所有子系统、一个风扇和一个电源才能运行。故障率分别为5 ‰、2 ‰、4 ‰、0. 处理器、磁盘控制器、磁盘、风扇、电源和总线分别为1kHz和3kHz，kHz = 10−5故障/小时。只有一名修理工，所有部件的修理率为30次/小时，但公共汽车除外，其修理率为15次/小时。在表4所示的实验中，多处理器和磁盘各有两个单元，系统只需要一个单元就可以工作。FB、SFB和SFBP都是[5]中使用的重要抽样表5显示了相同系统的结果，但使用了四单元多处理器（四个处理器中仅需要一个处理器即可运行系统），并且每个RAID由5个驱动器组成，系统仅需要其中3个驱动器即可运行。使用的第三个系统，也取自[5]，由一个复制的数据库组成，其中有四个站点，每个站点都有一个RAID磁盘集群上的数据库的完整副本。所有集群都是相同的，具有相同的冗余（9个中的7个），并且故障率（对于每个磁盘）等于10−2。每个班有一名修理工，修理率为1.如果至少有一个数据库副本在工作，则认为系统已启动。结果示于表6中。只有当故障率和修复率有相当大的差异时，稀有度才是有效的。当情况并非如此时，稀有性的衡量标准会显著增加故障和维修，因此，这种测量的增加并不表示系统正在向目标事件移动。 的情况下对于复制的数据库，故障率和修复率分别为10-2和1。与所分析的其他系统的比率相比，这些比率相当接近。这就是为什么在表6中没有计算稀有度的原因。在第二组实验中，模型是L 'Ecuyer et.”[17]。在第一种情况下（[17]中的示例5），系统由两组处理器组成，每组两个处理器，两组磁盘控制器，每组两个控制器，以及六个磁盘群集，每个群集四个磁盘。处理器、控制器和磁盘的故障率分别为5× 10−5、2× 10−5和2 × 10−5，H. Cancela等人/理论计算机科学电子笔记321（2016）317表4串联计算机，第1版[5]方法γCIE1.33E-06V^{γ^cie} ×t表5Tandemccomputer，第二版[5]方法γ^cieV^{γ^cie} ×tFB 1.24E−07 1.88E−15SFB-1.57E−16SFBP1.25E-079.05E−17前进的步伐1.19E-075.55E−14C. 失败1.30E-076.17E−14M. 稀有1.24E-071.11E−14方法表6数据库在[5]γ^cieV^{γ^cie} ×tFB 8.54E−13 8.65E−25SFB1.16E−123.93E-23SFBP8.87E−132.37E-25前进的步伐8.04E−134.41E−26连续失败8.10E−134.18E−23稀有度的测量--FB^3.37E−14SFB1.27E-062.06E−15SFBP1.27E-062.20E−15前进的步伐1.21E-064.20E−13C. 失败1.19E−063.93E−13M. 稀有1.20E-065.38E−1318H. Cancela等人/理论计算机科学电子笔记321（2016）3表7[17]中的示例5（γ= 5.60E- 05）方法γ^cieV^{γ^cie} ×tBFB-4.93E−07SBLR-1.17E−03ZVA（v0）-6.21E−11ZVA（v1）-3.90E−11ZVA（v2）-4.80E−11前进步数5.59E−05 3.08E−11C. 故障5.51 E−052.83E−11M. 稀有度5.28 E−059.88E−11分别每种类型的组件的修复率为1。在每个磁盘集群中，数据都是复制的，这意味着单个磁盘的故障不会引起系统的失败。如果所有数据都可从两种处理器类型访问，则系统是可操作的，这意味着每种类型的至少一个处理器、一个控制器、一个每个群集有三个磁盘可运行。结果示于表7中。BFB、SBLR、ZVA（v0）、ZVA（v1）、ZVA（v2）和ZVA（v3）都是[17]中使用的重要性抽样最后一个例子是在[17]中被称为例子6的例子。该系统由20种组件组成，编号从0到19，每种组件4个。假设所有修复率均为1，但组件当10≤ 1≤19时，λi=i <$2/10，其中<$i=10−3。当总共7个组件出现故障时，系统出现故障。结果示于表8中。所有的CMIE估计可以被认为是在相同的顺序的精度和效率的其他方法的比较。8CMIE与分裂如果中间状态集是马尔可夫链模型图中的切割（u和d之间），则CMIE和Splitting之间存在形式等价性[7，8，13，14，26]。H. Cancela等人/理论计算机科学电子笔记321（2016）319ΣΣ˜˜˜^ ^您的位置：˜˜Σ IJΣ当集合C是割集时，CMIE估计量采用以下形式：IKK^N1nN2KKCie方法表8[17]中的实例6γ^cieV^{γ^cie} ×tBFB 3.10E−11 9.35E−17 SBLR-ZVA（v3）3.00E−11 1.26E−22前进步数3.03E−11 1.74E−23C. 故障2.93 E−114.28E−22M. 稀有度2.38 E−118.70E−211N1γ.卢恩（十）1N2（i）^cie=N1j=1 N1k=1NIk×NN2JK2i=1=1μ mj=1（j）J（i）。（十三）对同一模型的不同分析表明，任何从状态u开始的路径都有一个概率，比方说P1，在回到u之前到达集合C的任何状态。 同样，从集合C中的任何状态开始的路径有概率，比如说P2，在回到u之前到达状态d。集合C可以被看作是从u到d的路径中的边界或阈值，因此，分裂可以应用于f γ的估计分裂估计的形式为：γ^=P^1×P^2，其中P1和P2分别是P1和P2的标准估计量，如在任何普通拆分应用程序。图4显示了一组复制的一部分，其中一些从u开始并前进到C，而另一些从C开始并前进到d。根据这种方法，P1和P2的估计量是：N1nN1n（十）KN2（一）KP^=1一（j）和j=1k=1i=1P=，N1j=1Kk=12N1N2j=1n（十）Kk=1分裂估计量是：γ^spl=P^1×P^2=1 μ mj=1一（j）k=1J（i）=γ^.（十四）k=1N1N2i=1N1N21i=120H. Cancela等人/理论计算机科学电子笔记321（2016）3˜˜˜˜u1N12N2DVDP1P2N1C1图四、CMIE与拆分比较中的一些轨迹这导致的结论是，如果集合C ={1，2，...，n}是图中的切割的马尔可夫链，CMIE和分裂（基于一个单一的水平集）产生相同的估计。换句话说，具有单个水平集C的分裂是CMIE的特殊情况，其中集合C是马尔可夫链的图中的切割。在基本的分裂模型中，初始状态和最终状态之间存在界限或阈值，就像图4中的集合C一样。连续概率P1，P2，... 需要以某种方式进行评估。其中之一是从之前的阈值到达最终状态的概率。在第7节中使用的系统中，通常有不止一个最终状态分散在所有马尔可夫链中，其中一些可能位于阈值之间。这需要一个特定的设计师来设计一个重要的分裂功能，而CMIE的应用是简单的。另一个可能导致基本Splitting模型复杂化的特征是故障传播。有时，一个特定的故障可能会导致一组其他故障同时 在一个基本的分裂模型中，这意味着同时跨越多个阈值，这使得有必要根据分析中的系统修改基本方法。CMIE不受故障传播的影响。9结论和开放的研究路线本文提出了一种蒙特卡罗方法，称为条件蒙特卡罗与中间估计（CMIE），旨在减少在大型和高度可靠的马尔可夫系统的背景下的估计量CMIE被设想为估计在返回到初始状态（被接受为系统涨）。将普通的条件蒙特卡罗应用于这类模型需要知道模型中某些概率的确切值。为了克服这个概率是未知的事实，CMIE的建议是估计它们，为此，有必要从一些被称为中间状态的选定状态递归地启动该方法。分裂可以被看作是CMIE的特殊情况，其中事件是H. Cancela等人/理论计算机科学电子笔记321（2016）321通过马尔可夫链的状态空间中的阈值然而，在CMIE中递归地计算目标概率的方式比分裂算法简单，分裂算法需要确定以先前交叉为条件的跨越每个阈值的概率，跟踪每个阈值被跨越的次数。CMIE优于拆分的另一个优点出现在存在多于一个目标状态和/或故障传播的系统中。多于一个目标状态的存在是确定阈值（图中的切口）的缺点。由于故障传播的存在，可能发生多个阈值交叉。然后，需要特定的引擎来使Splitting适应这些特定的设置，而CMIE实现是直接的，并且相对于其中只有一个目标状态并且没有故障传播的那些实现没有差异。CMIE与文献中的一些其他方法进行了实证检验。在所有情况下，结果表明，CMIE是在相同的效率范围内的方法，它是比较，不仅在方差，而且在精度增益比较。证明了CMIE的一些性质，并给出了其方差的封闭形式。CMIE可以很容易地扩展到其他类型的罕见事件问题，例如，在静态（经典）或动态方法下的网络可靠性估计[19]。未来工作的一个可能路线是改进CMIE的渐近分析，例如，看看有界相对误差和/或有界正态近似有多接近或多远此外，还有两个重要的问题需要解决：中间状态集的选择方法和准则，以及精度和执行时间之间的引用[1] Asmussen，S.和D. Kortschak，错误率和改进算法的罕见事件模拟与重型威布尔尾，方法和计算应用概率（2013年），pp.1-21[2] Blanchet，J.，J. Li和M. K. Nakayama，用于估计具有随机需求的配电网络的故障概率的条件蒙特卡洛方法，在：冬季模拟会议论文集，WSC3837-3848URLhttp://dl.acm.org/citation.cfm?电话：+86-21 - 2315182431974[3] Botev，Z. I.和D. P. Kroese，通过广义分裂方法的有效蒙特卡罗模拟，统计与计算（2010），pp.1-URLhttp://dx.doi.org/10.1007/s11222-010-9201-4[4] Botev，Z.一、P. L'Ecuyer和B. Tu Jun，Markov chain importance sampling with applications to rareevent probability estimation，Statistics and Computing23（2013），pp.271-285。URLhttp://dx.doi.org/10.1007/s11222-011-9308-2[5] 坎塞拉，H.，G. Rubino和B. Tu Jun，使用马尔可夫模型的重要性抽样进行MTTF估计。Monte CarloMethods and Applications8（2002），pp.321-341[6] Chan，J. C.和D. P. Kroese，Rare-event probability estimation with conditional monte carlo，Annals ofOperations Research189（2011），pp.43比61URLhttp://dx.doi.org/10.1007/s10479-009-0539-y[7] 加弗尔斯湾杰杰，“罕见事件模拟中的分裂方法”，博士。论文，数学科学学院，特文特大学，荷兰（2000年）。[8] Glasserman，P.，P. Heidelberger，P. Shahabuddin和T. Zajic，分裂为罕见事件模拟：简单情况下的分析，在：1996年冬季模拟会议（1996年），pp。302- 30822H. Cancela等人/理论计算机科学电子笔记321（2016）3[9] Glynn，P. W.和D. L. Iglehart，随机模拟的重要性抽样，管理科学35（1989），pp. 1367-1392.[10] Goyal，A.，P. Shahabuddin，P. Heidelberger，V. F. Nicola和P.W. Glynn，统一框架用于模拟高度可靠系统的马尔可夫模型，IEEE Transactions on Computers 41（1992），pp. 36比51[11] Juneja ， S. Shahabuddin ， Fast Simulation of Markov Chains with Small Transition Probabilities ，Management Science47（2001），pp.547-562URLhttp://dx.doi.org/10.1287/mnsc.47.4.547.9827[12] Kroese，D. P.，T. Taimre和Z. I. Botev，[13] L'Ecuyer，P.，V. Demers和B. Tu n，稀有事件，分裂和准蒙特卡罗，ACM Trans.模型。Comput.你好17（2007年）。URLhttp://doi.acm.org/10.1145/1225275.1225280[14] L'Ecuyer，P.，F. Le Gland，P. Lezaud和B. Tu n，分裂技术，in