In insic o de ing, combina o ial numbe s and
eliabili y enginee ing
Luis Gonz´alez∗
Resea ch Ins i u e o In elligen Sys ems &Nume ical Applica ions in Enginee ing,
Depa men o Ma hema ics, Uni e si y o Las Palmas de G an Cana ia,
Campus de Ta i a, 35017 Las Palmas de G an Cana ia, Spain
Abs ac
A new algo i hm o e alua ing he op e en p obabili y o la ge aul ees
(FTs) is p esen ed. This algo i hm does no equi e any p e ious quali a i e
analysis o he FT. Indeed, i s e iciency is independen o he FT logic, and
i only depends on he numbe no basic sys em componen s and on hei
ailu e p obabili ies. Ou me hod p o ides exac lowe and uppe bounds
on he op e en p obabili y by using new p ope ies o he in insic o de
ela ion be ween bina y s ings. The in insic o de enables one o selec
bina y n- uples wi h la ge occu ence p obabili ies wi hou necessi y o e al-
ua e hem. This d as ically educes he complexi y o he p oblem om
exponen ial (2nbina y n- uples) o linea (nBoolean a iables). Ou algo-
i hm is mainly based on a ecu si e o mula o apidly compu ing he sum
o he occu ence p obabili ies o all bina y n- uples wi h weigh mwhose
1s a e placed among he k igh -mos posi ions. This o mula, as well as he
balance be ween accu acy and compu a ional cos , is closely ela ed o he
amous Pascal’s iangle.
Keywo ds: Reliabili y enginee ing modelling; aul ee analysis; op e en
p obabili y; in insic o de ; in insic o de g aph; Hamming weigh
∗Tel.: +34 928458832
Email add ess: [email p o ec ed] (Luis Gonz´alez)
P ep in submi ed o Applied Ma hema ical Modelling July 29, 2012
1. In oduc ion
One o he mos common echniques o analyzing sys em sa e y and elia-
bili y is he aul ee analysis (FTA), an ex ensi ely used me hod wo ldwide,
which is mainly based on p obabili y heo y and Boolean algeb a [1, 2, 3].
La ge, complex sys ems whe e FTA has been widely applied can be ound in
many di e en scien i ic o enginee ing a eas, such as ae onau ics, chemis y
and ma e ials, ene gy esou ces, mechanics, me eo ology and clima ology,
nuclea physics, obo ics, e c. (see, e.g., [4] o an exhaus i e lis o such
subjec ca ego ies).
FTA was i s concei ed in 1961 by H. A. Wa son o Bell Telephone Lab-
o a o ies o pe o m a sa e y e alua ion o he Minu eman Launch Con ol
Sys em [5]. The basic idea o FTA is he ansla ion o he ailu e beha io o
a echnical sys em in o a isual diag am in ol ing logic ga es, i.e., he aul
ee (FT) [6]. A FT is a logical ep esen a ion o he manne in which combi-
na ions o ailu es o he basic componen s o a sys em lead o he undesi ed
s a e o he sys em, he so-called op e en [7, 8].
One o he main opics in FTA is o es ima e he ailu e p obabili y o
he whole sys em –also called he sys em una ailabili y, o he op e en
p obabili y. Many di e en echniques ha e been p oposed in he li e a u e
o e alua e he sys em una ailabili y; see, e.g., [6, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21] and he e e ences con ained he ein.
Th oughou his pape , we conside complex sys ems depending on an
a bi a ily la ge numbe no s a is ically independen andom Boolean a i-
ables x1, . . . , xn. The usual con en ion is o assign he alue 1 o 0 o a iable
xii componen i ails o wo ks, espec i ely. So, each one o he bina y n-
uples o 0s and 1s, u= (u1, . . . , un)∈ {0,1}n, desc ibes he cu en si ua ion
o he nbasic componen s o he sys em ( ailing o wo king) and, in he ol-
lowing, we shall e e o hese bina y n- uples as bina y s ings, o as sys em
elemen a y s a es.
Then, using a mo e p ecise algeb aic e minology, he FT can be desc ibed
by a s ochas ic Boolean unc ion
Φ : {0,1}n−→ {0,1}
(x1, . . . , xn)7→ Φ (x1, . . . , xn)
depending on he nbasic a iables xio he sys em. Assuming ha Φ = 1 i
he sys em ails, Φ = 0 o he wise, hen he ailu e p obabili y o he whole
sys em can be e alua ed by compu ing he p obabili y P {Φ = 1}.
2
Le us ecall ha a aul ee is said o be cohe en i i s s uc u e unc ion
Φ sa is ies he ollowing wo condi ions (see, e.g., [22, 23, 24])
(i) Rele ance. Each componen xiis ele an , i.e., i con ibu es o he
sys em s a e. Fo mally, o all i= 1,2, . . . , n
Φ (0i, x)6= Φ (1i, x), o some ec o x,
whe e
Φ (0i, x) = Φ (x1, . . . , xi−1,0, xi+1, . . . , xn),
Φ (1i, x) = Φ (x1, . . . , xi−1,1, xi+1, . . . , xn).
(ii) Mono onici y. The sys em nei he ansi s om a ailed s a e o a good
s a e by he ailu e o a componen , no ansi s om a good s a e o
a ailed s a e by he epai o a componen . Fo mally, he s uc u e
unc ion Φ is non-dec easing in each a iable, i.e.,
Φ (x)≥Φ (y) i x > y,
whe e x, y ∈ {0,1}n, and x>ymeans ha xi≥yi o e e y componen
i= 1,2, . . . , n, wi h xi> yi o some i.
When a leas one o he wo abo e condi ions is no ul illed, he sys em
is non-cohe en .
Mos o FTA me hods o e alua ing he op e en p obabili y P {Φ = 1}
a e based on he minimal cu se app oach [8]. A (minimal) cu se is a
(minimal) combina ion o componen ailu es ha leads o he sys em ailu e
( op e en ). Howe e , o la ge, complex FTs i is no possible, in gene al, o
enume a e all i s minimal cu se s due o high memo y equi emen s and long
compu ing ime, since he numbe o po en ial minimal cu se s exponen ially
inc eases, in gene al, wi h he size o he FTs, ha is, wi h he numbe s o
hei basic e en s and ga es [13].
The main goal o his pape is o p esen a new algo i hm o ob aining
exac lowe and uppe bounds on he op e en p obabili y ( o bo h cohe en
and non-cohe en sys ems), wi h no need o ind he minimal cu se s. Mo e-
o e , indeed ou me hod does no equi e any p e ious quali a i e analysis
o he FT o es ima e he sys em una ailabili y.
A he end o his pape , we will explain in de ail he cha ac e is ics and
ad an ages o ou p oposed me hod. A his momen , le us men ion ha
3
i s main ad an age, compa ed wi h many o he echniques p oposed in he
li e a u e o ob ain exac lowe and uppe bounds on sys em una ailabili y, is
he ollowing. Ou algo i hm does no equi e any knowledge o in o ma ion
(o en equi ed by o he echniques) abou he Boolean (s uc u e) unc ion
o he FT. Mo eo e , we shall p o e ha i is possible (and easy) o assu e
a p io i he maximum admissible e o in he es ima ion, since his e o is
independen o he FT o be e alua ed, and i only depends on he occu ence
p obabili ies o ce ain selec ed bina y n- uples.
The bounds on sys em una ailabili y can be ob ained om he occu ence
p obabili ies o any subse o selec ed sys em elemen a y s a es. Howe e , he
main poin is ha he accu acy in he es ima ion (di e ence be ween uppe
and lowe bounds) o P {Φ = 1}imp o es a he same ime as he sum o he
occu ence p obabili ies o all he selec ed elemen a y s a es inc eases. Hence,
in o de o ge a good comp omise be ween accu acy and compu a ional
cos , we need o selec as ew bina y n- uples uas possible, wi h occu ence
p obabili ies P {u}as la ge as possible.
Fo selec ing he bina y s ings uwi h la ge occu ence p obabili ies, we
use a heo em ha s a es new p ope ies ela ed o he in insic o de c i e-
ion (IOC). IOC is a simple, posi ional c i e ion ha allows us o compa e
he occu ence p obabili ies P {u},P { }o wo gi en bina y n- uples u,
wi h no need o e alua e hem, simply looking a he ela i e posi ions o
hei 0s and 1s. IOC was i s desc ibed in [25]: a heo e ical pape whe e he
in insic o de ing is in oduced in he con ex o he e alua ion o s ochas ic
Boolean unc ions.
O he heo e ical esul s and p ac ical applica ions o IOC can be ound
in [26, 27, 28, 29, 30, 31, 32]. Le us b ie ly desc ibe he main ideas o
echniques p esen ed in hese wo ks. In [26], di e en cha ac e iza ions as
well as necessa y condi ions and su icien condi ions o he in insic o de
a e de i ed. In [28, 30], we p o ide wo di e en algo i hms o coun ing and
gene a ing all he bina y n- uples which a e always mo e p obable (less p ob-
able) han a ixed n- uple u∈ {0,1}n. Based on hese algo i hms, in [31] we
de e mine, o any ixed bina y n- uple u, all i s possible “ anks” (posi ions)
in he lis o all he 2nbina y n- uples, a anged in dec easing o de o hei
occu ence p obabili ies. The usual ep esen a ion o he in insic o de ,
he so-called in insic o de g aph, is cons uc ed in [29], and some o de -
heo e ic and g aph- heo e ic p ope ies o his g aph a e de i ed in [32].
All he abo e commen ed pape s a e mainly heo e ical, and hey do no
con ain algo i hms o e alua ing he una ailabili y o echnical sys ems. An
4
algo i hm o es ima ing he op e en p obabili y is gi en in [27], and i is
also based on IOC. The main di e ences be ween he algo i hm pe o med
in [27] and he one p oposed he e a e he ollowing:
(i) The o me selec s a p ope se o bina y n- uples, basically by aking in o
accoun he weigh (numbe o 1-bi s in he bi s ing) and he lexicog aphic
( u h- able) o de be ween he bi s ings. The la e imp o es his selec ion
s a egy by using new p ope ies o he in insic o de ins ead o he lexico-
g aphic o de . This leads o a mo e e icien algo i hm, since he occu ence
p obabili ies o he selec ed bi s ings a e now la ge , and hus he numbe
o bina y n- uple p obabili ies ha need o be compu ed is educed.
(ii) Fo compu ing he occu ence p obabili y o each selec ed bina y n- uple
wi h weigh m, he o me needs o mul iply n ac o s, while he la e only
needs o mul iply m+ 1 ac o s. This is especially use ul, o compu a ional
pu poses, when he selec ed bina y n- uples ha e small weigh s, which is in
gene al he case in he algo i hm p oposed in his pape .
(iii) Fo compu ing he maximum e o in he es ima ion o he sys em un-
a ailabili y (so ha we can assu e he equi ed accu acy), bo h algo i hms
e alua e he o al sum o he selec ed bina y n- uple p obabili ies. Howe e ,
while he o me uses a non- ecu si e o mula o his pu pose, he la e uses
a ecu ence ela ion, which is compu a ionally mo e e icien .
Mo eo e , he balance be ween accu acy and compu a ional cos in ou
new algo i hm is based on he abo e men ioned ecu si e o mula, which is
closely ela ed o he amous Pascal’s iangle.
This pape has been o ganized as ollows. Sec ion 2 is de o ed o se he
assump ions and basic no a ions used in his wo k. In Sec ion 3, we p esen
all he equi ed backg ound abou he abo e men ioned de e minis ic me hod
o es ima ing he sys em una ailabili y and abou he in insic o de ela ion.
Beginning wi h ou new, unpublished esul s, in Sec ion 4, we s a e some
new p ope ies o he in insic o de . Sec ion 5 is de o ed o p esen a simple
ecu ence ela ion, closely ela ed o he Pascal’s o mula, o compu ing he
sums o he selec ed bina y s ing p obabili ies. In Sec ion 6, we p esen ou
algo i hm o es ima ing he sys em una ailabili y, and we illus a e i wi h
a eal-li e example. Finally, in Sec ion 7 we p esen ou conclusions.
2. Assump ions and no a ion
2.1. Assump ions
(i) The componen s and sys em ha e bina y s a es.
5

(ii) The basic componen s a e non- epai able.
(iii) The FT con ains only s a ic ga es; i is no a dynamic FT.
(i ) The basic e en s a e assumed o be mu ually s a is ically independen .
( ) The p obabili y o ailu e o each basic e en is gi en.
In addi ion o he abo e assump ions, le us men ion ha he numbe o
basic componen s and he numbe o ga es o he FT o be sol ed may be
a bi a ily la ge. Mo eo e , any e en , basic o ga e, may appea a mul iple
loca ions in he FT (i.e., epea ed e en s a e allowed). Finally, ou me hod
can be applied o bo h cohe en and non-cohe en FTs, and he FT logic
may be a bi a ily complex.
2.2. Nomencla u e and no a ion
nnumbe o basic sys em componen s
{0,1}nse o all he 2nbina y n- uples
xii- h basic Boolean a iable o he sys em:
xi= 1 i componen i ails, xi= 0 o he wise
xinega ion o a iable xi
pibasic ( ailu e) p obabili y o componen i:
pi= P {xi= 1}, 1 −pi= P {xi= 0}
qia quo ien : qi=pi/(1 −pi), 1 ≤i≤n
u= (u1, . . . , un) bina y n- uple desc ibing a sys em elemen a y s a e
Mu
he (2 ×n)-ma ix whose i s and second ow a e
he bina y n- uples uand , espec i ely
P {u}occu ence p obabili y o sys em elemen a y s a e u
Φ Boolean (s uc u e) unc ion desc ibing he FT:
Φ = 1 i he sys em ails, Φ = 0 o he wise
P {Φ = 1} op e en p obabili y o sys em una ailabili y
C1,C0subse s o he se s o bina y n- uples o which
Φ = 1,0, espec i ely:
C1⊆ {u∈ {0,1}n|Φ (u) = 1}
C0⊆ {u∈ {0,1}n|Φ (u) = 0}
L,Ulowe and uppe bounds on sys em una ailabili y
wH(u) Hamming weigh o u, i.e., i s numbe o 1-bi s:
wH(u) = Pn
i=1 ui
u(10 decimal numbe ing o bina y n- uple u:
6
u(10 =Pn
i=1 2n−iui
in insic o de ela ion be ween bina y n- uples
.co e ing ela ion associa ed o he in insic o de
In he pa ially o de ed se ({0,1}n,)
S0occu ence p obabili y o he bina y n- uple (0,...,0):
S0= P {(0,...,0)}=Qn
i=1 (1 −pi)
Ck
mse o all bina y n- uples wi h weigh mwhose 1s a e
placed among he k igh -mos posi ions
Sk
msum o p obabili ies o all bina y n- uples o Ck
m
 equi ed accu acy o es ima e sys em una ailabili y
Cse o selec ed bina y n- uples used in he algo i hm
T o al numbe o bina y n- uples used in he algo i hm
Ssum o occu ence p obabili ies o all bina y n- uples
used in he algo i hm
A−Bse di e ence: A−B={x∈A|x /∈B}
u+Ca i hme ic sum o elemen uand se C:
u+C={u+ | ∈C}
|·| ca dinali y o a se
3. P elimina y esul s
As commen ed in Sec ion 1, ou algo i hm will p o ide exac lowe and
uppe bounds on he ailu e p obabili y P {Φ = 1}o an n-componen sys-
em. In he nex subsec ion, we explain how such bounds can be ob ained
om any a bi a y subse o he se {0,1}no all sys em elemen a y s a es.
3.1. Bounds on sys em una ailabili y
Deno ing by pi he ailu e p obabili y o he i- h sys em componen , i.e.,
P {xi= 1}=pi,P {xi= 0}= 1 −pi,1≤i≤n,
hen, due o he s a is ical independence be ween basic componen s, he
occu ence p obabili y o each sys em elemen a y s a e uis gi en by he
exp ession
P {u}= P {(u1, . . . , un)}=
n
Y
i=1
pui
i(1 −pi)1−ui o all u∈ {0,1}n.(3.1)
7
In o he wo ds, Eq. (3.1) means ha P {u}can be simply compu ed as he
p oduc o ac o s pio 1 −pi, i ui= 1 o ui= 0, espec i ely.
Now, i is well known ha he p obabili y o a Boolean unc ion Φ aking
alue 1 can be exac ly compu ed as he sum o he occu ence p obabili ies o
all sys em elemen a y s a es o which Φ = 1 o , al e na i ely, as he emain-
de o 1 o he sum o he occu ence p obabili ies o all sys em elemen a y
s a es o which Φ = 0 [33]. Tha is,
X
u∈{0,1}n
Φ(u)=1
P {u}= P {Φ = 1} ≡ 1−P {Φ = 0}= 1 −X
u∈{0,1}n
Φ(u)=0
P {u}.(3.2)
Fo small alues o he numbe no basic sys em componen s, Eq. (3.2)
enables one o exac ly compu e he ailu e p obabili y, P {Φ = 1}, o he
sys em. Howe e , o la ge alues o n his p ocedu e is no easible in p ac-
ice because o he exponen ial na u e o he p oblem. Jus hink ha he e
a e 2nbina y n- uples o 0s and 1s. To o e come his obs acle, we can ob ain
lowe and uppe bounds L,Uon he op e en p obabili y, P {Φ = 1}, as
ollows.
Le C⊆ {0,1}nbe an a bi a y subse o bina y n- uples (sys em ele-
men a y s a es), and le C1and C0be he wo subse s o C o which Φ = 1
and Φ = 0, espec i ely, i.e.,
C1={u∈C|Φ (u) = 1}, C0={u∈C|Φ (u) = 0}.
Then using Eq. (3.2) we ha e
X
u∈C1
P {u} ≤ X
u∈{0,1}n
Φ(u)=1
P {u}= P {Φ = 1},(3.3)
X
u∈C0
P {u} ≤ X
u∈{0,1}n
Φ(u)=0
P {u}= P {Φ = 0}(3.4)
and om (3.3) and (3.4) we ge he ollowing lowe and uppe bounds L,U
L=X
u∈C1
P {u} ≤ P {Φ = 1} ≡ 1−P {Φ = 0} ≤ 1−X
u∈C0
P {u}=U.
(3.5)
8
No e ha , o a ixed se Co bina y n- uples, he abo e bounds Land
Udepend on he Boolean unc ion Φ, because he same happens wi h he
se pa i ion
C={u∈C|Φ (u) = 0}∪{u∈C|Φ (u) = 1}=C0∪C1.
Howe e , he maximum e o in he es ima ion (di e ence be ween uppe
and lowe bounds)
U−L= 1−X
u∈C0
P {u}!−X
u∈C1
P {u}= 1 −X
u∈C0∪C1=C
P {u}(3.6)
is comple ely independen o he FT logic (i.e., i is he same o any Boolean
unc ion Φ), and i only depends on he o al sum, Pu∈CP {u}, o he occu -
ence p obabili ies o all he selec ed bina y n- uples u∈C. Mo e p ecisely,
he accu acy in he es ima e o he sys em una ailabili y, P {Φ = 1}, im-
p o es a he same ime as he maximum e o U−Ldec eases, i.e., a
he same ime as his o al sum, Pu∈CP {u}, inc eases, as Eq. (3.6) has
shown [27].
Consequen ly, he main ques ion is how o selec he mino numbe o
sys em elemen a y s a es, u∈C, wi h occu ence p obabili ies, P {u}, as
la ge as possible, in o de o minimize he compu a ional cos –by inc easing
he las sum in Eq. (3.6)– when es ima ing he sys em una ailabili y wi h
an accep able accu acy, by using Eq. (3.5).
No e ha he simples answe o his ques ion, namely o de ing he 2n
bina y n- uple p obabili ies is no alid, because o he exponen ial na u e o
he p oblem and he high compu a ional cos s in so ing algo i hms. To a oid
his obs acle, in [25] we ha e es ablished a simple, posi ional c i e ion ha
allows us o compa e wo gi en elemen a y s a e p obabili ies, P {u},P { },
wi hou compu ing hem, simply looking a he posi ions o he 0s and 1s in
he n- uples u, . This c i e ion is explained in de ail below.
3.2. The in insic o de
In he ollowing, we indis inc ly deno e he n- uple u∈ {0,1}nby i s
bina y ep esen a ion (u1, . . . , un) o by i s decimal ep esen a ion, deno ed
he e by u(10 , and we use he symbol “≡” o indica e he con e sion be ween
hem, i.e.,
u= (u1, . . . , un)≡u(10 =
n
X
i=1
2n−iui,
9
Ob iously, i uis a bina y n- uple wi h weigh mwhose 1s a e placed
among he k−1 igh -mos posi ions, hen uis also a bina y n- uple wi h
weigh mwhose 1s a e placed among he k igh -mos posi ions, i.e.,
Cm
m⊂Cm+1
m⊂ · · · ⊂ Ck−1
m⊂Ck
m⊂ · · · ⊂ Cn−1
m⊂Cn
m,
and hus
Sm
m< Sm+1
m<· · · < Sk−1
m< Sk
m<· · · < Sn−1
m< Sn
m.
Theo em 4.1. Le n≥1. Then
(i)Fo e e y bina y n- uple wi h weigh m > 0, he e exis s, a leas , one
bina y n- uple uwi h weigh m−1such ha u .
(ii)Fo e e y bina y n- uple ∈Ck
m−Ck−1
m, such ha 0< m < k ≤n, he e
exis s, a leas , one bina y n- uple u∈Ck−1
msuch ha u .
P oo . We gi e a cons uc i e p oo explici ly de ining he bina y s ings u.
(i) Le be a bina y n- uple wi h weigh m > 0. Choose any index j∈
{1, . . . , n}such ha j= 1. De ine uas ollows
ui=0 i i=j,
ii i6=j.
In his way, wH(u) = wH( )−1 = m−1. Mo eo e , ma ix Mu
has exac ly
one 0
1column (i s j- h one), while i s emaining n−1 columns a e ei he 0
0
o 1
1. Hence, Mu
has no 1
0columns and hen, by Theo em 3.1, i sa is ies
IOC. The e o e, by De ini ion 3.1, u .
(ii) Le ∈Ck
m−Ck−1
m(m<k≤n). Then is a bina y n- uple wi h weigh
mwhose 1s a e placed among he k igh -mos posi ions, bu no among he
k−1 igh -mos posi ions. Hence, since n−k+1 is he bi placed a he k- h
posi ion om igh o le in he n- uple , we ha e
n−k+1 = 1 and ∃j > n −k+ 1 s. . j= 0.
De ine uas ollows
ui=


0 i i=n−k+ 1,
1 i i=j,
ii i6=n−k+ 1, j.
16

In his way, wH(u) = wH( ) = m, and u∈Ck−1
m. Mo eo e , ma ix Mu
has exac ly one 1
0column (i s j- h one) and exac ly one 0
1column (i s
(n−k+ 1)- h one), while i s emaining n−2 columns a e ei he 0
0o 1
1.
Hence, he only 1
0column o Mu
is p eceded by a co esponding 0
1column
(since n−k+1 < j), and hus, by Theo em 3.1, Mu
sa is ies IOC. The e o e,
by De ini ion 3.1, u .
Theo em 4.1 and i s p oo can be illus a ed by Fig. 3, whe e he dig aph
o I4( he igh -mos one in Fig. 2) is depic ed using now he bina y ep e-
sen a ion o hei nodes, ins ead o hei decimal equi alen s. Fo ins ance,
conside he bina y 4- uple = (1,1,0,0) ∈ {0,1}4. On one hand, since
m=wH( ) = 2 hen, acco ding o Theo em 4.1-(i), we can choose, e.g.,
u= (1,0,0,0), so ha wH(u) = 1 and u . On he o he hand, since
= (1,1,0,0) ∈C4
2−C3
2 hen, acco ding o Theo em 4.1-(ii), we can choose,
e.g., u= (0,1,1,0), so ha wH(u) = 2, u∈C3
2and u .
(0,0,0,0)
|
(0,0,0,1)
|
(0,0,1,0)
|
(0,0,1,1) (0,1,0,0)
|
(0,1,0,1) (1,0,0,0)
||
(0,1,1,0) (1,0,0,1)
||
(0,1,1,1) (1,0,1,0)
|
(1,0,1,1) (1,1,0,0)
|
(1,1,0,1)
|
(1,1,1,0)
|
(1,1,1,1)
Fig. 3. The in insic o de g aph o n= 4 using bina y ep esen a ion.
17
5. The sums Sk
mand he Pascal’s iangle
In his sec ion, we p esen a simple ecu ence ela ion, closely ela ed
o he Pascal’s iangle, o apidly compu ing he sums Sk
mde ined in he
p e ious sec ion. This ela ion is gi en in he nex heo em. Due o i s
ecu si eness, ou o mula is e y adequa e o compu a ional pu poses and,
indeed, i is he main esul unde lying ou algo i hm o es ima ing he
sys em una ailabili y –p esen ed in he nex sec ion.
Fi s , we associa e o each one o he basic p obabili ies pi(1 ≤i≤n),
he co esponding quo ien
qi=pi
1−pi
o all i= 1,2, . . . , n.
No e ha , due o ou hypo hesis (3.7) and o he inc easing cha ac e o
unc ion y=x
1−x, we ha e
0< q1≤q2≤ · · · ≤ qn≤1.
Rema k 5.1. We mus highligh he e ha he abo e quo ien s qican be
used o educe he compu a ional cos , when compu ing he occu ence p ob-
abili ies o he bina y n- uples u= (u1, . . . , un). Ins ead o using Eq. (3.1),
aking ad an age o he occu ence p obabili y S0o he ze o n- uple (com-
pu ed by Eq. (4.1)), we ha e
P {u}= P {(u1, . . . , un)}=
n
Y
i=1
pui
i(1 −pi)1−ui=
n
Y
i=1
ui=1
pi
n
Y
i=1
ui=0
(1 −pi)
=
n
Y
i=1
ui=1
pi
1−pi
n
Y
i=1
(1 −pi) = P 0,n
|{z}
. . . , 0 n
Y
i=1
ui=1
qi=S0
n
Y
i=1
ui=1
qi,
so ha
P {u}= P {(u1, . . . , un)}=S0
n
Y
i=1
ui=1
qi.(5.1)
The abo e s a egy o de i ing Eq. (5.1) (which compu es he bina y s ing
p obabili ies) has also been used in [27] o a di e en pu pose, namely o
ob aining an explici , non- ecu si e o mula o compu e he maximum e o
in he es ima ion o he sys em una ailabili y.
18
We s ess ou he ac ha Eq. (5.1) is especially use ul o educing he
compu a ional cos , when he Hamming weigh o u(i.e., he numbe o bi s
ui= 1) is small, which is in gene al he case o he bi s ings used in he
algo i hm ha we p opose in he nex sec ion. Indeed, suppose ha we wan
o compu e he occu ence p obabili y o a bina y n- uple u= (u1, . . . , un)
wi h a small weigh m. I we use Eq. (3.1), we need o mul iply he n ac o s
pui
i(1 −pi)1−ui=pii ui= 1,
1−pii ui= 0 (1 ≤i≤n).
O he wise, using Eq. (5.1), we only need o mul iply he m+ 1 ac o s
S0, qi1, . . . , qim, whe e i1, . . . , ima e he posi ions o he m1-bi s in u. Fo
ins ance, o
n= 9, u = (0,0,1,0,0,0,0,1,1) , wH(u) = 3,
using Eq. (3.1), we ge
P {u}= (1 −p1) (1 −p2)p3(1 −p4) (1 −p5) (1 −p6) (1 −p7)p8p9,
while, using Eq. (5.1), we ge
P {u}=S0q3q8q9.
Theo em 5.1. Fo all n≥1and o all m, k such ha 1≤m≤k≤n
Sk
m=Sk−1
m+qn−k+1Sk−1
m−1,(5.2)
whe e we adop he con en ions ha Sk
0=S0 o all k= 0,1, . . . , n −1and
Sm−1
m= 0 o all m= 1,2, . . . , n.
P oo . Fi s , no e ha , acco ding o he de ini ion o he sums Sk
m, he
exp essions Sk
0(0 ≤k≤n−1) and Sm−1
m(1 ≤m≤n), o which he abo e
con en ions a e e e ed, do no make sense. We dis inguish he ollowing
wo cases.
(a) Fo k=m, we ha e
Sm
m= P ( 0,n−m
|{z}
. . . , 0,1,m
|{z}
. . . , 1!)
=pn−m+1
1−pn−m+1
P ( 0,n−m+ 1
|{z }
. . . , 0,1,m−1
|{z}
. . . , 1!)=qn−m+1Sm−1
m−1
19
and his is exac ly Eq. (5.2) o k=m, since we ha e adop ed he con en ion
ha Sm−1
m= 0 (1 ≤m≤n).
(b) Fo k > m, we gi e a combina o ial p oo . The se Ck
mo he bina y
n- uples (u1, . . . , un) wi h weigh mwhose 1s a e placed among he k igh -
mos posi ions, namely n−k+1, . . . , n, can be pa i ioned in o he ollowing
wo subse s:
(b.1) The subse o n- uples u∈Ck
msuch ha un−k+1 = 0.
(b.2) The subse o n- uples u∈Ck
msuch ha un−k+1 = 1.
The i s subse is exac ly he se o bina y n- uples wi h weigh mwhose
m1s a e placed among he k−1 igh -mos posi ions, i.e., he se Ck−1
m. The
second subse is exac ly he se o bina y n- uples wi h weigh msuch ha
un−k+1 = 1 and whose emaining m−1 1-bi s a e placed among he k−1
igh -mos posi ions, i.e., he se
0,n−k
|{z}
. . . , 0,1,0,k−1
|{z}
. . . , 0!+Ck−1
m−1
=( 0,n−k
|{z}
. . . , 0,1,0,k−1
|{z}
. . . , 0!+  ∈Ck−1
m−1).
So, we ha e he se pa i ion
Ck
m=Ck−1
m∪" 0,n−k
|{z}
. . . , 0,1,0,k−1
|{z}
. . . , 0!+Ck−1
m−1#(5.3)
and hus we ge
Sk
m=Sk−1
m+qn−k+1Sk−1
m−1,
since Sk
m,Sk−1
mand qn−k+1Sk−1
m−1a e ob iously he sums o he occu ence
p obabili ies o all he n- uples belonging o he se s
Ck
m, Ck−1
mand 0,n−k
|{z}
. . . , 0,1,0,k−1
|{z}
. . . , 0!+Ck−1
m−1,
espec i ely. 
The abo e combina o ial p oo sugges s a igh connec ion be ween ou
model and he amous Pascal’s iangle. Indeed, no e ha each sum Sk
mis
20
aken o e he co esponding se Ck
m, whose ca dinali y is he combina o ial
numbe k
m, since m1s mus be placed among kposi ions. Tha is,
Sk
m=X
u∈Ck
m
P {u}and Ck
m=k
m,1≤m≤k≤n. (5.4)
In Fig. 4, we illus a e his connec ion. The le iangle con ains he
sums Sk
m(1 ≤m≤k≤4) o sys em elemen a y s a e p obabili ies. The
igh iangle con ains he binomial coe icien s k
m(1 ≤m≤k≤4), ha
is, i is he Pascal’s iangle whe e i s le -mos diagonal k
0k≥0has been
dele ed in o de o a oid he epe i ion o he ze o n- uple p obabili y S0.
Clea ly, Eq. (5.4) shows ha each one o he sums Sk
mis aken o e exac ly
k
mbina y s ings. The in e p e a ion o Fig. 4, o he ela ionship be ween
accu acy and compu a ional cos , is he ollowing. The e o es ima e o
he sys em una ailabili y, P {Φ = 1}, is educed by he quan i y Sk
ma he
same ime as he Boolean unc ion Φ, desc ibing he FT logic, needs o be
e alua ed a k
mbina y s ings.
S1
1
S2
1S2
2
S3
1S3
2S3
3
S4
1S4
2S4
3S4
4
1
1
2
1 2
2
3
1 3
2 3
3
4
1 4
2 4
3 4
4
Fig. 4. Accu acy/compu a ional cos a io and he Pascal’s iangle.
Mo eo e , o he case m < k, coun ing he bina y n- uples in ol ed in
each o he h ee sums o o mula (5.2) o , equi alen ly, coun ing he bina y
n- uples belonging o each o he h ee se s o pa i ion (5.3), we ge
Ck
m=Ck−1
m+Ck−1
m−1,
and hen, using Eq. (5.4), we ob ain he amous Pascal’s o mula
k
m=k−1
m+k−1
m−1.
6. The algo i hm
Based on he p e ious ideas and p oposi ions, in his sec ion we p esen
a new algo i hm o e alua ing he sys em una ailabili y. We call i he
21

FTA ia In insic O de ing &Pascal’s T iangle Algo i hm (FTAIOPT -
Algo i hm, o sho ) because he FTA o he cu en sys em is based on
an adequa e selec ion o bina y n- uples (i.e., wi h la ge occu ence p ob-
abili ies) igh ly connec ed o bo h he in insic o de ing and he Pascal’s
iangle. Nex , we illus a e ou app oach on a eal-wo ld analysis p oblem
aken om [35].
6.1. The FTAIOPT-Algo i hm
Fo each gi en maximum admissible e o ε, he FTAIOPT-Algo i hm
p o ides lowe and uppe bounds on he ailu e p obabili y P {Φ = 1}o
a (cohe en o non-cohe en ) sys em depending on nmu ually independen
basic componen s. The se {pi}n
i=1 o basic p obabili ies mus sa is y he
(non- es ic i e) hypo hesis (3.7). I his assump ion is no sa is ied by he
cu en sys em, hen we p oceed as explained in Rema k 3.1 and nex , we
ew i e he Boolean unc ion Φ using he new Boolean a iables.
The ollowing a e he main ideas o he FTAIOPT-Algo i hm:
(i) Theo em 4.1-(i) has s a ed ha o e e y nonze o bina y n- uple o
weigh mwe can always ind a bina y n- uple uo weigh m−1, s. . P {u}>
P { }. Theo em 4.1-(ii) has s a ed ha o e e y nonze o bina y n- uple
o weigh mwhose 1s a e placed among he k igh -mos posi ions, bu no
among he k−1 igh -mos posi ions, we can always ind a bina y n- uple
uo weigh mwhose 1s a e placed among he k−1 igh -mos posi ions,
s. . P {u}>P { }. Hence, we selec he se s Ck
mo bina y n- uples in
inc easing o de o he weigh m( o m= 1 o n), and o each ixed weigh
m, in inc easing o de o k( o k=m o n).
(ii) To compu e he sums Sk
m, we use he ecu ence o mula (5.2) s a ed by
Theo em 5.1.
(iii) In o de o ge he equi ed accu acy (maximum admissible e o ε), we
selec he bina y n- uples un il we assu e ha he sum o hei occu ence
p obabili ies is g ea e han o equal o 1 −ε. In his way, acco ding o
Eq. (3.6), we ha e
X
u∈C
P {u} ≥ 1−ε⇔U−L= 1 −X
u∈C
P {u} ≤ ε. (6.1)
(i ) Fo each one o he selec ed bina y n- uples, u∈C, we compu e i s oc-
cu ence p obabili y, P {u}, by Eq. (3.1) and e alua e he Boolean unc ion
Φ. Acco ding o Eq. (3.5), we ge he lowe and uppe bounds on sys em
22
una ailabili y
L=X
u∈C, Φ(u)=1
P {u} ≤ P {Φ = 1} ≤ 1−X
u∈C, Φ(u)=0
P {u}=U,
sa is ying, as desi ed,
U−L≤ε.
Based on hese ideas, ou algo i hm can be desc ibed as ollows.
The FTAIOPT-Algo i hm
S ep 1. Fo i= 1 o ncompu e qi=pi
1−pi.
S ep 2. Compu e S0= P 0,n
|{z}
. . . , 0(using Eq. (4.1)).
S ep 3. I S0≥1−( he ze o n- uple is enough!) hen go o S ep 9 (due o
Eq. (6.1))
S ep 4. Fo k= 0,1, . . . , n −1 : de ine Sk
0=S0(by con en ion, Theo em
5.1).
S ep 5. Fo m= 1,2, . . . , n : de ine Sm−1
m= 0 (by con en ion, Theo em
5.1).
S ep 6. Call S=S0.
S ep 7. Fo m= 1 o n(due o Theo em 4.1)
Fo k=m o n(due o Theo em 4.1)
compu e Sk
m=Sk−1
m+qn−k+1Sk−1
m−1(by Theo em 5.1)
i S+Sk
m≥1− hen go o S ep 8 (due o Eq. (6.1))
Nex k
Compu e S=S+Sn
m(Sis he sum o he p obabili ies o all
n- uples wi h weigh s 0, . . . , m, due o Eq. (4.2))
Nex m
S ep 8. Fo all nonze o selec ed n- uples u∈Cn
1∪ · · · ∪ Cn
m−1∪Ck
mcompu e
P {u}(using Eq. (5.1)).
S ep 9. Fo all nonze o selec ed n- uples u∈Cn
1∪ · · · ∪ Cn
m−1∪Ck
mand o
he ze o n- uple do:
I Φ (u) = 1 hen L=L+ P {u},
I Φ (u) = 0 hen V=V+ P {u}.
S ep 10. Compu e U= 1 −Vand w i e (due o Eq. (3.5))
L≤P {Φ = 1} ≤ U.
23
6.2. A eal-wo ld example
Ou eal-li e example co esponds o he accumula o sys em (ACC) o
a p essu ed wa e eac o (PWR) in a nuclea powe plan , which has been
aken om [35]. The ACC is a passi e injec ion sys em ha is a pa o he
PWR eme gency co e coolan injec ion sys em, whe e one accumula o is a -
ached o he cold leg o each loop o he eac o coolan sys em o p o ide a
sou ce o eme gency make-up wa e o ha loop i a loss o coolan acciden
(LOCA) occu s. The accumula o is simply a p essu e essel pa ially illed
wi h bo a ed wa e , and p essu ized wi h ni ogen gas. When p essu e in
he cold leg d ops below 650 psig, he check al es open, and bo a ed wa e
is o ced in o he eac o coolan sys em. The PWR has 3 loops, hence he e
a e h ee accumula o s, one a ached o cold leg o each loop. The con en s o
2 accumula o s a e equi ed o success ully e lood he co e ollowing a la ge
LOCA. I a LOCA occu s in a cold leg, he con en o he co esponding
accumula o is los h ough he b eak; hus bo h o he emaining 2 accu-
mula o s mus success ully discha ge hei con en s in o he eac o coolan
sys em o p o ec he co e. The e o e, success o he accumula o discha ge
o he eac o coolan sys em o he pos ula ed cold leg LOCA equi es bo h
accumula o s. The o al CPU ime equi ed o sol e his nume ical example
was less han one second, using a 2GHz Pen ium IV.
The ACC ailu e beha io is ep esen ed by a cohe en aul ee wi h
83 basic componen s and 42 logic ga es. Fo a maximum admissible e o
= 10−6, i was enough o use he ze o 83- uple (wi h weigh m= 0); all he
83 bina y 83- uples o weigh m= 1; and he 34
2= 561 bina y 83- uples o
weigh m= 2, whose 1s a e placed among he k= 34 igh -mos posi ions.
Tha is, he se o selec ed bina y 83- uples was
C={0} ∪ C83
1∪C34
2.
Then, using a o al numbe o (see Eq. (5.4) and Fig. 4)
T=|{0}| +C83
1+C34
2=83
0+83
1+34
2= 645
bina y 83- uples, he sum o he occu ence p obabili ies o all selec ed bi -
s ings was (see Eqs. (4.1) & (5.4))
X
u∈C
P {u}=S=S0+S83
1+S34
2= 9999.99065·10−4≥9999.99·10−4= 1−.
24
In his way, we ha e ob ained he ollowing lowe and uppe bounds on he
ACC una ailabili y
L= 3.74552 ·10−4≤P {Φ = 1} ≤ 3.75487 ·10−4=U,
sa is ying, as desi ed (see Eq. (6.1) and S ep 7),
U−L= 9.35 ·10−7<10−6=.
No e ha S eps 1-7 o he algo i hm ha e de e mined ha he abo e
bina y 83- uples a e enough o es ima ing he ACC una ailabili y wi h he
equi ed accu acy = 10−6. These s eps only in ol e he basic p obabili ies
piand he equi ed accu acy . Thus, he same 645 bina y s ings a e also
enough o es ima e he op e en p obabili y o any o he cohe en o non-
cohe en 83-sys em wi h he same se {pi}83
i=1 o basic p obabili ies as he
ACC sys em, and o he same maximum admissible e o = 10−6.
Nex , in S ep 8 he occu ence p obabili ies o hese 645 selec ed bina y
s ings a e compu ed. O cou se, due o he way in which S ep 7 selec s
he bina y n- uples (in inc easing o de o hei Hamming weigh s), hese
calcula ions can be ca ied ou , wi h a e y low compu a ional cos ( aking
ad an age o he alue S0compu ed in S ep 2), simply by using Eq. (5.1).
See Rema k 5.1 and S ep 8.
No e ha he Boolean s uc u e ( unc ion) o he sys em has no ye
used, i.e., he esul s ob ained by S eps 1-8 a e alid wi h independence o
he FT logic! In pa icula , i is also i ele an whe he he cu en sys em
is cohe en o non-cohe en .
Then, o each gi en s uc u e unc ion Φ, we only need o e alua e he
cu en Boolean unc ion Φ on he 645 selec ed bina y 83- uples o ob ain-
ing he co esponding exac lowe and uppe bounds L, U o each gi en
maximum admissible e o (S eps 9-10).
Unde qui e gene al hypo heses, ou algo i hm p o ides exac lowe and
uppe bounds on sys em una ailabili y o a gi en accu acy. The main cha -
ac e is ics and ad an ages o he p oposed me hod a e he ollowing:
(i) Ou algo i hm, based on Eq. (3.5) and on he IOC, does no equi e any
knowledge o in o ma ion ( ha o he echniques o en equi e) abou he FT
s uc u e unc ion. This is he main ad an age, compa ed wi h many o he
me hods. (ii) Because o Eqs. (3.5) and (3.6), he accu acy in he es ima ion
is independen o he FT logic, and i only depends on he sum o he oc-
cu ence p obabili ies o he selec ed bina y n- uples. (iii) Due o Eqs. (3.5)
25