Structure function
Definition taught in Reliability, part of Probability
Structure function
| Type | Definition |
| Taught in | Reliability |
| Part | Probability |
| Worked examples | 4 |
| Questions using it | 3 |
The structure function \varphi:\{0,1\}^n\to\{0,1\} equals 1 when the system works and 0 when it has failed. A system is monotone when \mathbf{x}\le\mathbf{y} implies \varphi(\mathbf{x})\le\varphi(\mathbf{y}): repairing a component cannot cause a failure.
Examples
A bridge of reliable links
Worked example from Reliability
Each of the five components of the bridge works with probability p=0.9, independently.
Question. Find the reliability of the bridge exactly, and by the rare-event approximation.
Solution. With every p_i=p the polynomial above collapses to
r(p)=2p^2+2p^3-5p^4+2p^5,
so r(0.9)=1.62+1.458-3.2805+1.181=0.9785. For the approximation, the minimal cuts \{1,2\} and \{4,5\} each fail with probability 0.1^2=0.01, and \{1,3,5\} and \{2,3,4\} each with 0.1^3=0.001, so
r\approx1-(0.01+0.01+0.001+0.001)=0.978.
The approximation is good to three decimal places, because with reliable components two cuts almost never fail together. It also shows where the risk is: the two-component cuts at each end contribute ten times as much as the three-component cuts through the cross link. For comparison, two parallel series paths without the cross link have reliability 1-(1-0.81)^2=0.964, so the link removes about 40% of the failure probability.
Structure of a k-out-of-n system
Question page: Structure of a k-out-of-n system
Write the structure function of a system that works if and only if at least k of its n components work.
\varphi(\mathbf x)=\begin{cases}1,&\sum_{i=1}^nx_i\ge k,\\0,&\text{otherwise}.\end{cases}
As a polynomial, the minimal path sets are the \binom nk subsets of size k, so \varphi(\mathbf x)=1-\prod_{|S|=k}\bigl(1-\prod_{i\in S}x_i\bigr). The cases k=n and k=1 give the series and parallel systems.
Pivoting the bridge
Question page: Pivoting the bridge
In the bridge with side paths 1–4 and 2–5 and cross link 3, the structure function has the form \varphi(\mathbf{x})=x_3 z_1+(1-x_3)z_2. Find z_1 and z_2.
When the cross link 3 works, it joins the two middle nodes, and the bridge becomes a parallel pair \{1,2\} in series with a parallel pair \{4,5\}:
z_1=\bigl(1-(1-x_1)(1-x_2)\bigr)\bigl(1-(1-x_4)(1-x_5)\bigr).
When it has failed, only the two side paths remain, in parallel:
z_2=1-(1-x_1x_4)(1-x_2x_5).
So \varphi(\mathbf x)=x_3z_1+(1-x_3)z_2.
Paths and cuts of the bridge
Question page: Paths and cuts of the bridge
The bridge has minimal path sets \{1,4\}, \{2,5\}, \{1,3,5\} and \{2,3,4\}. Write the structure function by the path formula, and expand it far enough to see the four path monomials. Say how the same system is drawn as a series arrangement of parallel modules, and as a parallel arrangement of series modules, if components may be duplicated in the drawing.
By the path formula,
\varphi(\mathbf x)=1-(1-x_1x_4)(1-x_2x_5)(1-x_1x_3x_5)(1-x_2x_3x_4).
Expanding, the terms of degree two and three are x_1x_4+x_2x_5+x_1x_3x_5+x_2x_3x_4, the four path monomials, followed by products of pairs of paths with alternating signs; reducing x_i^2=x_i gives the polynomial in the chapter.
The path formula draws the bridge as four series branches, 1–4, 2–5, 1–3–5 and 2–3–4, placed in parallel. The cut formula draws it as four parallel modules, \{1,2\}, \{4,5\}, \{1,3,5\} and \{2,3,4\}, placed in series. Both drawings repeat components, which is why the bridge itself is not a series–parallel system.
Used in
- Taught in Reliability, where the derivation and examples are.
- Also used in Random experiments and probability
- Questions that use it (3) — Structure of a k-out-of-n system · Pivoting the bridge · Paths and cuts of the bridge
- All 7 questions on Reliability
See also
Reliability function · Survival function · Hazard rate · Weibull distribution