3
$\begingroup$

Example: I have nodes A, B and C.
A is connected to B and C.
B is also connected to C.

The link between two nodes have a probability to fail. For the link between A and B, the probability is pAB Between A and C, it's pAC B and C, pBC

The probability that A is connected to C is $P = (1-pAC) + pAC(1-pAB)(1-pBC)$

Question: What is the probability P{A is connected to E} for this graph:

enter image description here

Please write the steps and explain how you find the probability.

Edit:
The only part I have to go on is the A-B-C graph. The problem is that the graph on the picture has 4 routes from A to E, out of those two have the length of 3 steps and two have 4 steps.

I don't know what to do when that situation arises. Consider this graph:

Graph

Is it, \begin{align} P\{A\ to\ D\} = &(1-pAB)(1-pBD) + pAB(1-pAC)(1-pCD) + \\ &pBD(1-pAC)(1-pCD) + pAC(1-pAB)(1-pBD) + \\ &pCD(1-pAB)(1-pBD) + pAB(pBD)(1-pAC)(1-pCD) + \\ &pAC(pCD)(1-pAB)(1-pBD) \end{align} ?

Or it it simply just $P\{A\ to\ D\} = (1-pAB)(1-pBD) + pAB*pBD(1-pAC)(1-pCD)$? I don't know how to think when there are routes of the same length, or when there is a straight route with a node inbetween, like A - B - C instead of just A - C.

Also, what is this called? I've been trying to solve the graph for 3 days now to no avail.

$\endgroup$
4
  • $\begingroup$ We welcome questions like this, but we treat them differently. Please add the [self-study] tag & read its wiki. Then edit your Q to state what you understand thus far & where you're stuck. We'll provide hints to help you get unstuck. Please make these changes as just posting your homework & hoping someone will do it for you is grounds for closing. $\endgroup$ Oct 28, 2014 at 20:45
  • 2
    $\begingroup$ Okay, I've added more information now. $\endgroup$
    – Solrik
    Oct 28, 2014 at 21:04
  • $\begingroup$ Your information does not seem internally consistent, unless I misread the graphs or the notation. The first illustration shows no connection between $A$ and $C$, yet your formula includes a term "$p_{AC}$" which seems to imply those nodes are directly connected with an edge that has probability $p_{AC}$ of failing. You cannot use this notation to refer both to the probability of a single edge failing and to the probability of a path failing, because some nodes connected by single edges are connected by other paths, too. So what exactly does this notation mean? $\endgroup$
    – whuber
    Oct 28, 2014 at 21:27
  • $\begingroup$ The first formula is not for the same graph as the picture below. Then after "Question:" is the actual problem I have to solve. After "Consider this graph:" is a more detailed description of what I don't understand. I'm sorry if it's unclear. $\endgroup$
    – Solrik
    Oct 28, 2014 at 21:37

3 Answers 3

1
$\begingroup$

The easiest way to solve this problem is via the law of total probability.

Suppose the $C$-$D$ link has failed. Then there are only two paths from $B$ to $E$, and so there is a connection from $B$ to $E$ as long as at least one of the paths $B$-$C$-$E$ and $B$-$D$-$E$ has both links working. Now, the probability that both links on the $B$-$C$-$E$ path are working is $V_{BC}V_{CE}$ where $V_{XY}$ is the probability that the link from $X$ to $Y$ is Viable, and similarly, $V_{BD}V_{DE}$ is the probability that the $B$-$D$-$E$ path is working. Hence, $$P(B\to D \mid C\text{-}D~\text{failed}) = V_{BC}V_{CE}+V_{BD}V_{DE} - V_{BC}V_{CE}V_{BD}V_{DE}.\tag{1}$$

If the above puzzles you, ponder on the result that $P(G\cup H) = P(G)+P(H)-P(G\cap H)$.

Suppose the $C$-$D$ link is Viable. Then, there is a path from $B$ to $D$ exactly when at least one of the links $B$-$C$ and $B$-$D$ is Viable AND at least one of $C$-$E$ and $D$-$E$ is Viable. Thus,

$$P(B\to D \mid C\text{-}D~\text{working})= \left(V_{BC}+V_{BD}- V_{BC}V_{BD}\right)\left(V_{CE}+V_{DE} - V_{CE}V_{DE}\right).\tag{2}$$

Now, combine $(1)$ and $(2)$ together using the law of total probability and then add on what happens with link $A$-$B$, and you are done.

$\endgroup$
0
$\begingroup$

Here are my thoughts on case with ABCD, trying to give insights for the more general cases.

They are two important things in your problem

  • counting the number of different paths
  • being able to understand how to count them, i.e. to weight them.

In the ABCD case, there are two routes you can take : ABD ou ACD.

  1. Assume we start from ABD path. Then, the probability that one can reach D from A is $(1-p_{AB})(1-p_{BD})$.
  2. Then there also is the path with ACD, the probability that it exists being $(1-p_{AC})(1-p_{CD})$.
  3. If we just add these two probabilities, first one can check that we can have a probability greater than one, which is never a good sign, second there are a cases we count two times : one path interests us only if the other is not taken. If we assume as we did that we started with ABD, then the ACD path adds to our problem only if the path ABD dos not work, that is either when AB is broken ($p_{AB}$) or when AB is here but BD is broken ($(1 - p_{AB})(p_{BD})$)

Therefore I arrive at

$$ \mathbb{P}(A->D) = (1-p_{AB})(1-p_{BD}) + (p_{AB} + (1 - p_{AB})p_{BD})(1-p_{AC})(1-p_{CD}) $$

Note that you should (and I think it is the case) get the same result if you start by the path ABD. In this particular case, one can also check that if you develop the formula, B and C play similar roles.

To calculate that more generally, I think you should try it in matrix form with an adjacency matrix, but I will not look at it for now.

$\endgroup$
7
  • $\begingroup$ I followed your algorithm and it would be nice to have a second word about wether it's correct or not. There are 4 paths from B to E. For BCE: (1-BC)(1-CE) For BDG: (BC+(1-BC)CE + (1-BC)CD*CE)(1-BD)(1-DE) For BDCE: BC*DE(1-BD)(1-CD)(1-CE) For BCDE: BD*CE(1-BC)(1-CD)(1-DE) Using a matrix is not what we are supposed to use to solve the graph. $\endgroup$
    – Solrik
    Oct 29, 2014 at 10:56
  • $\begingroup$ I do not think your weights are correct. Try to reason in another order : BCE then BCDE then BDE then BDCE. Moreover, what is your class in which you have this exercice (might help with the answer). $\endgroup$ Oct 29, 2014 at 13:14
  • $\begingroup$ It's called "Data Communications". Shouldn't the probability be the same for any order? I was thinking that taking the shortest paths first should be prioritised before the longer ones. $\endgroup$
    – Solrik
    Oct 29, 2014 at 13:47
  • $\begingroup$ It should definititely be the same for any order. But as at the start you have two choices : either BD or BC, I just think it is easier is you keep this dichotomy $\endgroup$ Oct 29, 2014 at 14:14
  • $\begingroup$ Okay, so I assume that the equation is correct. How can I check if it is the correct equation? $\endgroup$
    – Solrik
    Oct 29, 2014 at 14:35
0
$\begingroup$

For your graph:

Write an adjacency matrix $A$ whose coefficients are $1-p_{AB}$, etc. rather than 1. Set $A_{5,5}$ to 1. Then the answer is $A^4 \begin{bmatrix}1 \\ 0 \\ 0 \\ 0 \\ 0\end{bmatrix}$.

In general, there is an elegant combinatorics solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.