1
$\begingroup$

Let $G$ be a directed graph with $n$ nodes and an edge between two nodes with probability $p$. (As in a directed Erdos-Renyi graph $G(n,p)$). For simplicity we assume that we pick each direction by probability $p/2$. I wanted to answer the question: "What is the probability that a given node $i$ has only edges going either outwards or only towards it?"

My idea was to use, that each node can have maximally $(n-1)$ incident edges. So I came to following formula for the wanted probability: $$\sum_{k=0}^{n-1} 2\cdot(p/2)^k \cdot{n-1\choose k}\cdot (1-p)^{(n-1-k) }$$

Is this correct or am I missing something?

$\endgroup$
  • 2
    $\begingroup$ That looks very complicated. Why not just $(1-p/2)^{n-1}$ for "only nodes going towards it"? And thus $2(1-p/2)^{n-1}-(1-p)^{n-1}$ for either only incoming or only outgoing or both? $\endgroup$ – Henning Makholm Oct 9 '18 at 13:30
  • 1
    $\begingroup$ That sum looks very complicated and, moreover, incorrect: it simplifies to $2$, which is not the correct probability of any event. You are certainly missing something, but it's hard to say what without understanding where you got the terms of the sum from. $\endgroup$ – Misha Lavrov Oct 9 '18 at 13:42
  • $\begingroup$ @MishaLavrov I just looked at all the different possibilities: the node $i$ can have $k$ edges pointing only outwards or only inwards (so $2 \cdot (p/2)^k$) and to all the other $n-1-k$ neighbor nodes there is no edge at all (from this I got $(1-p)^{n-1-k} {n-1 \choose n-k-1}$ , because there are several possibilities to choose these nodes from the total $n$ nodes). And then summing up over all possible $k$'s. $\endgroup$ – Alisat Oct 9 '18 at 13:58
  • $\begingroup$ If you change the $(1-p/2)^{n-1-k}$ to $(1-p)^{n-1-k}$ then your formula is nearly correct. $\endgroup$ – Misha Lavrov Oct 9 '18 at 13:59
1
$\begingroup$

The formula $$ \sum_{k=0}^{n-1} 2\cdot(p/2)^k \cdot{n-1\choose k}\cdot (1-p)^{(n-1-k) } $$ is very nearly correct: the $k^{\text{th}}$ term counts the probability that we have $k$ outgoing edges and $n-1-k$ non-edges, or $k$ ingoing edges and $n-1-k$ non-edges.

The exception is the $k=0$ term. In this case, we should not have the factor of $2$, because having $0$ outgoing edges and $n-1$ non-edges is the same as having $0$ ingoing edges and $n-1$ non-edges. So the formula should be corrected by subtracting a $(1-p)^{n-1}$.

Also, the summation above can be simplified using the binomial theorem: $$ \sum_{k=0}^{n-1} \binom{n-1}{k} (p/2)^k (1-p)^{n-1-k} = (p/2 + (1-p))^{n-1} = (1-p/2)^{n-1}, $$ so your formula simplifies to $2(1-p/2)^{n-1}$, and the corrected formula to $2(1-p/2)^{n-1} - (1-p)^{n-1}$.

We can also get this simplified formula directly. The probability of having a given ingoing edge is $p/2$, so the probability that there are no ingoing edges is $(1-p/2)^{n-1}$ (all $n-1$ edges are either outgoing or missing). Similarly, the probability that there are no outgoing edges is $(1-p/2)^{n-1}$, but when we add these, we should subtract the overlap. The overlap is $(1-p)^{n-1}$: the probability there are no edges at all.

$\endgroup$

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.