<p>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$.</p>

<p>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$.</p>

CC BY-SA 3.0
2015-12-02T17:11:38.810Z
Why the downvote?
Yuval Filmus
CC BY-SA 4.0
2018-05-10T20:01:07.080Z
this would give a probability of a path of length **exactly** k, not at most k; is that correct?
Daniel
CC BY-SA 4.0
2018-05-10T21:19:07.957Z
As it's written, it's for the "at most" variant.
Yuval Filmus
CC BY-SA 3.0
2015-11-30T22:25:40.163Z
2015-11-30T22:25:40.163Z
Yuval Filmus
<p>Define $G(n, p)$ as a random <strong>directed</strong> graph ($n$ vertices; we put edge between two vertices with probability $p$). </p>

<p>What are the known results for the following problem: </p>

<p>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. </p>

CC BY-SA 3.0
2015-11-29T22:52:24.083Z
What values of $p$ are you considering?
Igor Shinkar
CC BY-SA 3.0
2015-11-30T02:08:53.280Z
@IgorShinkar does it make much difference? I do not have a specific number in mind; a just a probability $p \in (0,1)$.
Daniel
CC BY-SA 3.0
2015-11-30T03:01:19.053Z
Did you try modifying the standard Erdos-Renyi approach, and if so what are the difficulties?
usul
CC BY-SA 3.0
2015-11-30T20:01:09.627Z
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.
Thomas Steinke
CC BY-SA 3.0
2015-12-02T11:17:03.210Z
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)$.
Daniel
CC BY-SA 3.0
2015-12-02T11:17:50.013Z
Did I get it right. @Thomas?
Daniel
CC BY-SA 3.0
2015-12-02T15:48:31.553Z
Looks right to me.
Thomas Steinke
<graph-theory><upper-bounds><random-walks><random-graphs>
Probability of two vertices being connected by some path in a random directed graph
Daniel
# Probability of two vertices being connected by some path in a random directed graph

(Asked by: username_0 on 2015-11-29)

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.

**Tags:** graph-theory, upper-bounds, random-walks, random-graphs
> **Comments:**
> **username_1**: What values of $p$ are you considering?  
> **username_0**: @IgorShinkar does it make much difference? I do not have a specific number in mind; a just a probability $p \in (0,1)$.  
> **username_2**: Did you try modifying the standard Erdos-Renyi approach, and if so what are the difficulties?  
> **username_3**: 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.  
> **username_0**: 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)$.  
> **username_0**: Did I get it right. @Thomas?  
> **username_3**: Looks right to me.  

---

## 1 answers

### Answer by username_4 on 2015-11-30. Score: 3 | Accepted answer

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$.

> **Comments:**
> **username_4**: Why the downvote?  
> **username_0**: this would give a probability of a path of length **exactly** k, not at most k; is that correct?  
> **username_4**: As it's written, it's for the "at most" variant.  

---

