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.

$\endgroup$
  • $\begingroup$ What values of $p$ are you considering? $\endgroup$ – Igor Shinkar Nov 29 '15 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 Nov 30 '15 at 2:08
  • $\begingroup$ Did you try modifying the standard Erdos-Renyi approach, and if so what are the difficulties? $\endgroup$ – usul Nov 30 '15 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 Nov 30 '15 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 Dec 2 '15 at 11:17
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$.

$\endgroup$
  • $\begingroup$ Why the downvote? $\endgroup$ – Yuval Filmus Dec 2 '15 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 May 10 '18 at 20:01
  • 1
    $\begingroup$ As it's written, it's for the "at most" variant. $\endgroup$ – Yuval Filmus May 10 '18 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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