# In-degree and out-degree distributions of a directed graph

For an undirected random graph with n nodes and probability p that any node u connects to any node v (apart from node u, i.e. no self-loops), the degree distribution is the binomial:

$$p_k = {n-1 \choose k} p^k (1-p)^{n-k-1}$$

However, what if the graph is random but directed? Are the in-degree and out-degree distributions the same as the above? Intuitively it feels like this is the case, but how do I show it?

As long as edges are independently generated, we still get a binomial distribution for the in-degree and out-degree.

Specifically, there's two ways we can try to generate a random directed graph:

• For each ordered pair $$(u,v)$$ with $$u \ne v$$, add a directed edge from $$u$$ to $$v$$ with probability $$p$$. Then the in-degree and out-degree of a vertex have the same binomial distribution for essentially the same reason. Say we're considering the in-degree of a vertex $$v$$. Then there are $$n-1$$ potential directed edges $$(u,v)$$ that could contribute: one for each possible $$u$$. Each of them exists independently with probability $$p$$, and their total number is the in-degree. That's exactly what the binomial distribution is for: the probability of in-degree $$k$$ is $$\binom{n-1}{k} p^k (1-p)^{n-1-k}.$$
• For each unordered pair $$\{u,v\}$$, with $$u \ne v$$, add an edge between $$u$$ and $$v$$ with probability $$q$$, and direct it in one of the two possible directions with probability $$\frac12$$. This avoids having edges going in both directions between $$u$$ and $$v$$, which may or may not be something you want. Anyway, in this setup, the in-degree and out-degree are binomial: the probability of in-degree $$k$$ is $$\binom{n-1}{k}(\tfrac q2)^k (1 - \tfrac q2)^{n-1-k}.$$

The formula $$\binom{n-1}{k} p^k (1-p)^{n-1-k}$$ for random graphs does not come out of nowhere: we have $$\binom{n-1}{k}$$ ways to pick $$k$$ potential edges out of a vertex, $$p^k$$ probability that all of them are present, and $$(1-p)^{n-1-k}$$ probability that all the others are absent. As long as we can do the same in the directed case (which we can), the same formula holds.