Approximating inter-point distances in directed Bernoulli graphs

In directed random graphs, in which edges can be assigned to have one of two directions, or perhaps both, the distance between two vertices $v$ and $v^{\mathrm{\prime }}$ can be computed along paths that are directed from $v$ to $v^{\mathrm{\prime }}$, or along paths that are directed from $v^{\mathrm{\prime }}$ to $v$. These two distances are in general dependent. Here, we approximate their joint distribution in the setting of the directed Bernoulli random graph $\mathcal{D}\mathcal{G}(n,p,\theta )$, obtained as a natural extension of the Bernoulli random graph $\mathcal{G}(n,p)$ by assigning directions to the edges independently, bidirectional with probability $\theta$, and either of the two possible choices of single direction with probability $\frac{1}{2}(1-\theta )$. The approximation involves two independent copies of a trivariate limiting random vector $(W_1^{\ast },W_2^{\ast },W_3)$ associated with a $3$-type Bienaymé–Galton–Watson process. The approximation error is shown to be typically of order $O(n^{-1\mathrm{/}2}\log n)$; this asymptotic order is likely to be optimal, even for the corresponding approximation in the Bernoulli random graph $\mathcal{G}(n,p)$.