Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My problem is the following. I have a set of vertices $N$ and a set of vertices $H$. Each vertex $n \in N$ is connected by means of an edge to each vertex $h \in H$. So the two sets of vertices and the set of edges form a complete bipartite graph. The graph is also undirected. Let us say that two vertices $n_1,n_2 \in N$ can communicate with each other if there exists a path $n_1h_1n_2$ of length 2, where $h_1 \in H$. Since we start out with a complete bipartite graph, initially all vertices in $N$ can communicate with each other. However, now there is a probability $p$ assigned to each edge. This probability is the same for all edges and it models the probability that a vertex $n \in N$ is disconnected from a vertex $h \in H$ after some fixed amount of time $t$. Moreover, the probability of two vertices being disconnected is independent of the probability of two other vertices being disconnected. Thus, given that vertices can be disconnected, what is the probability that there does not exist a path $n_1h_1n_2$, for some $n_1, n_2 \in N$ and some $h_1 \in H$ when the time $t$ has elapsed? In other words, what is the probability that two vertices from the set $N$ cannot communicate after $t$ has elapsed?

Edit: To give some background, what I am trying to model is a computer network comprised of computing nodes, represented by the set of vertices $N$, and hubs, represented by the set of vertices $H$. Computing nodes cannot communicate directly with each other, but only by means of an intermediate hub. The edges basically represent cables connecting nodes and hubs. The probability $p$ represents the probability that a cable suffers a failure, e.g., breaks, in an interval of time $[0, t]$.

share|cite|improve this question
Is time continuous here? If not, do you assume that some pair of $n$s are disconnected at each point in time? – user17794 Jun 18 '12 at 17:29
I am assuming that a disconnection can occur in each edge at any point in time within the interval $[0, t]$ with probability $p$. So as I understand it, time should be modeled as continuous. – davitenio Jun 18 '12 at 18:45
up vote 1 down vote accepted

so let's denote by $D_{n,h}$ the event that $n$ and $h$ are disconnected at time $t$. $n_1$ and $n_2$ can't communicate if the event $A_{n_1,n_2} := \bigcap_{h \in H} (D_{n_1,h} \cup D_{n_2,h})$ occurred (that is, each path of length 2 is destroyed). We have using indenpence and denoting complementation by ${}^c$: \begin{align*} P(A_{n_1, n_2}) &= \prod_{h\in H} P(D_{n_1, h} \cup D_{n_2,h})\\\ &= \prod_{h\in H} \bigl(1 - P(D_{n_1, h}^c \cap D_{n_2, h}^c)\bigr)\\\ &= \prod_{h\in H} \bigl(1 - P(D_{n_1,h}^c)P(D_{n_2,h}^c)\bigr)\\\ &= \prod_{h\in H} \bigl(1 - (1-p)^2\bigr)\\ &= \bigl(1 - (1-p)^2\bigr)^{|H|} \end{align*}

share|cite|improve this answer
For $n_1$ and $n_2$ not being able to communicate it is not necessary that both edges of each path of length 2 between them is destroyed. For instance, let's assume the graph has a total of 4 vertices, two vertices $h_1, h_2 \in H$ and $n_1, n_2 \in N$. The edges are initially $\{n_1, h_1\}, \{n_1, h_2\}, \{n_2, h_1\},$ and $\{n_2, h_2\}$. If when time $t$ has elapsed, $\{n_1, h_2\}$ and $\{n_2, h_1\}$ have been disconnected, then $n_1$ and $n_2$ cannot communicate. Notice that in that case no event $D_{n1, h1} \cup D_{n2, h1}$ nor $D_{n1, h2} \cup D_{n2, h2}$ has occurred. – davitenio Jun 18 '12 at 19:16
@davitenio There is a union $\cup$. $D_{n_1, h_1} \cup D_{n_2, h_1}$ has occured, since the second event has, $D_{n_1, h_2} \cup D_{n_2, h_2}$ since the first has. – martini Jun 18 '12 at 19:39
Sorry, I don't understand what you are trying to tell me in your comment. – davitenio Jun 18 '12 at 19:52
$D_{n_1, h_2} \cup D_{n_2, h_2}$ describes the event that $\{n_1, h_2\}$ or $\{n_2, h_2\}$ is broken. – martini Jun 18 '12 at 19:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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