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


* $V$ is the set of nodes, and $E$ is the set of edges
* Assume the ground graph $G$ is sparse enough, for example, $\frac{|E|}{|V|}= c \in [10, 40]$ or some not large number ?
* 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,k$ be three nodes of the graph. 


Let $a-b$ be the event that $a$ is reachable from $b$. Of course, because the graph is undirected, $b$ is also reachable from $a$.


My question is



> 
> Can we estimate the conditional probability $\mathbf{P}(a-k|a - b)$?
> 
> 
> 


When the graph only has $a,b,k$, and $p\_{ab}=1$, then its value is $p\_{ak}+(1-p\_{ak})p\_{bk}$. But this case impossible when the graph is big enough.


When $a=b$, then its value is $\mathbf{P}(a-k,a-k|a - a)=\mathbf{P}(a-k)$.


What about the general case?



Can we estimate the probability $\mathbf{P}(a-k|a - b) $ on a random graph?
If you're willing to take $n$ large then we can use some known results about the "giant component," since the asymptotic situation is a good approximation to reality. [Here](http://www.renyi.hu/~p_erdos/1960-10.pdf) is a paper by Erdos and Renyi, and [here](https://www.ndsu.edu/pubweb/~novozhil/Teaching/767%20Data/36_pdfsam_notes.pdf) is a nice expository write-up (the break-down on pages 3 and 4 is excellent). If $p = c\log(n)/n$ then the random graph is connected, so your $P(a-b|a-k) = 1$ for any $a,b,k$. See also [this](https://mathoverflow.net/questions/60075/) MO question. If $p \sim c/n$ for a constant $c>1$ then there is a giant component and some smaller components. If you look into the Erdos-Renyi paper you can write down the probability a vertex lands in the giant component as a function of $n$. Let's call this probability $q$. Since there's no relationship between b and k, the probability you seek is bounded below by the probability that each of a,b,k are in the giant component, which is approximately $q^3$. You can get even more precise if you want, using the distribution of smaller components to discuss the situation where a and b are in the same component but not the giant component. In that case your $P(a-k|a-b)$ is just $P(k$ is in that component too). 


If $p$ is very small compared to $n$, like $o(1/n)$ then $G(n,p)$ is a disjoint union of trees, and Erdos-Renyi analyze the sizes of these trees. You can use their formulas to compute for each tree the probability that $k$ is in the tree. Then take the weighted sum over all trees (weighted by the size of the tree, which is proportional to the probability $a$ is in the tree) and you can compute $P(a-k)$. I think here the extra information that $a-b$ is not going to help much, since $b$ and $k$ have no relationship. To me, knowing $a-b$ occurs just tells me that either $a=b$ or that $a$ is not isolated. The first is very unlikely if $a,b,k$ are chosen at random, while the second can be factored into your computation by ruling out trees of size 1, again using the formulas from Erdos-Renyi to see how likely those trees are. You can conduct a similar analysis for $p\sim c/n$ for $c<1$ or other cases, but I think those in the first paragraph sound more likely to be helpful based on your question. The lecture notes are a good reference.


