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?
Best Answer
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.