# Probability of an edge in directed random configuration graph

I am considering Bollobas' directed random configuration graph of size $$N$$, constructed by the following random algorithm:

1. Draw a sequence of $$N$$ node-degree pairs $$(j_1,k_1),...,(j_N,k_N)$$ independently from the degree distribution $$P$$. Accept the draw only if it is feasible, i.e. only if $$\sum_{n \in [N]}(j_n-k_n)=0$$.

2. For every node $$n$$, create $$j_n$$ in-stubs and $$k_n$$ out-stubs, where in-/out-stubs are open ended half-edges with an in-/out-arrow.

3. For any unpaired out-stub, select iteratively uniformly at random an unpaired in-stub and connect them.

Each such resulting pair of stubs forms a directed edge of the graph.

I am interested in the probabilities of an edge. My suggestion is:

Under this random matching approach, the probability that there is an edge from a node $$i$$ to a node $$l$$ is, with $$m$$ being the number of all edges: $$p_{il}=\frac{k_i \cdot j_l}{(2m-1)},$$ as node $$i$$ has $$k_i$$ out-stubs and $$j_l$$ in-stubs out of $$2m-1$$ (excluding of node $$i$$) attached to $$l$$ to which it could connect.

And similarly the probability that there is an edge from a node $$l$$ to $$i$$ is:$$p_{il}=\frac{j_i \cdot k_l}{(2m-1)}$$

Is this correct, or am I missing something?

## 1 Answer

We can choose a uniformly random matching in any order. So let's choose the $$k_i$$ edges out of node $$i$$ one at a time and see the probability none of them go to node $$l$$.

The first edge we choose has probability $$\frac{j_l}{m}$$ of going to $$l$$. If it doesn't, then the second edge has probability $$\frac{j_l}{m-1}$$. If that also doesn't happen, then the third edge has probability $$\frac{j_l}{m-2}$$, and so on. So the overall probability that none of the edges go to node $$l$$ is $$1-p_{il} = \left(1 - \frac{j_l}{m}\right)\left(1 - \frac{j_l}{m-1}\right) \dotsb \left(1 - \frac{j_l}{m-k_i+1}\right)$$ and the probability you want is the complement of this one.

Asymptotically, however, assuming $$k_i$$ and $$j_l$$ are small relative to $$m$$, the answer is in fact close to $$\frac{k_i \cdot j_l}{m}$$ which is what you have, except that $$m$$ and not $$2m-1$$ is the number of options for the first edge. (Unlike the undirected configuration model, here there are $$m$$ out-stubs and $$m$$ in-stubs, which we distinguish.)

Additionally, because there are $$k_i$$ edges with probability $$\frac{j_l}{m}$$ of going to $$l$$, then $$\frac{k_i j_l}{m}$$ edges is the expected number of edges from $$i$$ to $$l$$.

• So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =\frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =\frac{ k_i j_l} {m}$) – Alisat Jan 6 at 18:35
• The "neat" form is not the probability but the expected number of edges from $i$ to $l$. – Misha Lavrov Jan 6 at 20:10
• And for the undirected case, the formula you give is also the expectation, not the probability. – Misha Lavrov Jan 6 at 20:15
• The paper does not use the configuration mode. Instead, they define $p_{ij} = \frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model. – Misha Lavrov Jan 6 at 21:19
• Upon further reading, the paper does seem to claim that $\frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect. – Misha Lavrov Jan 6 at 21:48