How to estimate the conditional probability of node reachability on a random graph?

293 Views Asked by At

Let $G=(V,E)$ be an undirected random graph such that

  • $V$ is the node set, $E$ is the edge set.

  • Each edge $uv \in E$ is associated with a probability $p_{uv}$, i.e., $uv$ is kept with probability $p_{uv}$, otherwise removed.

Let $a-b$ denote the event that $b$ is rechable from node $a$. If so, as $G$ is undirected, $a$ is also reachable from node $a$.

My question is

given three nodes $a,b,k$, what is the probability of $a-k$ under the condition $a-b$, i.e., can we estimate the value of $P(a-k|a-b)$?

I am wondering if the value can be estimated, because no more information is known about the random graph. If the value can be represented by $P(a-k)$, $P(a-b)$ or something else?

EDIT: From the first answer, we've known $P(a-k|a-b)\geq P(a-k)$ and $P(a-k|a-b)\geq P(b-k)$. Can we have $f,g$ which are functions of $P(a-k)$ and $P(b-k)$ such that $g(P(a-k),P(b-k)) \geq P(a-k|a-b) \geq f(P(a-k),P(b-k))$?

1

There are 1 best solutions below

6
On BEST ANSWER

One thing I can say: $P(a-k|a-b) \geq P(b-k)$ since you can reach $k$ from $a$ through $b$ but you are not limited to it.