8
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ What values of $p$ are you considering? $\endgroup$
    – Igor Shinkar
    Commented Nov 29, 2015 at 22:52
  • $\begingroup$ @IgorShinkar does it make much difference? I do not have a specific number in mind; a just a probability $p \in (0,1)$. $\endgroup$
    – Daniel
    Commented Nov 30, 2015 at 2:08
  • $\begingroup$ Did you try modifying the standard Erdos-Renyi approach, and if so what are the difficulties? $\endgroup$
    – usul
    Commented Nov 30, 2015 at 3:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – Thomas Steinke
    Commented Nov 30, 2015 at 20:01
  • $\begingroup$ 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)$. $\endgroup$
    – Daniel
    Commented Dec 2, 2015 at 11:17

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Why the downvote? $\endgroup$
    – Yuval Filmus
    Commented Dec 2, 2015 at 17:11
  • $\begingroup$ this would give a probability of a path of length exactly k, not at most k; is that correct? $\endgroup$
    – Daniel
    Commented May 10, 2018 at 20:01
  • 1
    $\begingroup$ As it's written, it's for the "at most" variant. $\endgroup$
    – Yuval Filmus
    Commented May 10, 2018 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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