# Probability of two vertices being connected by some path in a random directed graph

Define $G(n, p)$ as a random directed graph ($n$ vertices; we put edge between two vertices with probability $p$).

What are the known results for the following problem:

Fix two vertices $v$ and $u$. What is the probability that there is at least a path (of length at most $k$) between $u$ and $v$? (clearly the result should be a function of $n$, $p$ and $k$). Upper-bound would work too, if there is no known exact answer.

• What values of $p$ are you considering? Nov 29, 2015 at 22:52
• @IgorShinkar does it make much difference? I do not have a specific number in mind; a just a probability $p \in (0,1)$. Nov 30, 2015 at 2:08
• Did you try modifying the standard Erdos-Renyi approach, and if so what are the difficulties?
– usul
Nov 30, 2015 at 3:01
• Have you considered computing the expected number of paths? That should be much easier to compute/estimate due to linearity of expectations. It would also be a good proxy for the probability of there being a path. i.e. If the expected number of paths is 0.01, then with probability at least 99% there is no path. And if the expected number of paths is 100, then I would guess there is a path with high probability. Nov 30, 2015 at 20:01
• Good suggestion Thomas. Just to make sure I understand your idea: Denote the number of path of length $i$ with $Y_i$. The expected number of path of length $i$ is $E[Y_i] = { n-2 \choose i-1} (i-1)! p^i$ (right?). Define "X_i = (Y_i > 0)" which shows the event of having a path of size $i (i > 0)$ between two vertices (existence of path). I know that $P(X_i) = P(Y_i > 0) = \sum_{j=1}^{\infty} P(Y_i = j)$, which is upper bounded by $E[Y_i] = \sum_{j=0}^{\infty} j. P(Y_i = j)$. This would give an upper-bound of $\sum_{i=1}^{k}E[Y_i]$ on $P( \vee_{i=1}^k X_i =1 ) = P( \vee_{i=1}^k Y_i >0)$. Dec 2, 2015 at 11:17

Consider a BFS exploration process, which proceeds in $k$ stages. Put $V_0 = \{u\}$. Given $V_0,\ldots,V_i$, explore all edges from $V_i$ to $V \setminus \bigcup_{j=0}^i V_j$ (where $V$ is the set of all vertices), and set $V_{i+1}$ to consist of all vertices reached in this fashion; their number has a binomial distribution which can easily be calculated. After $k$ steps, check whether the vertex $v$ belongs to $\bigcup_{j=0}^k V_j$.
Note that this process is exactly the same in both the undirected and the directed case. Hence the answer, whatever it is, is identical for both models. Presumably in the undirected case the answer is known and can be looked up. Otherwise you can try to estimate it by estimating the sizes $|V_i|$ and so the probability $\frac{1}{n-1} \sum_{i=1}^k |V_i|$ that $v$ belongs to $\bigcup_{i=1}^k V_i$.