Probability of an edge in directed random configuration graph

Question

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?

Answer 1

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$.