Approximating inter-point distances in directed Bernoulli graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908909170589696 |
|---|---|
| author | Barbour, A. D. Reinert, Gesine |
| author_facet | Barbour, A. D. Reinert, Gesine |
| contents | 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'$ can be computed along paths that are directed from $v$ to $v'$, or along paths that are directed from $v'$ 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{DG}(n,p,θ)$, obtained as a natural extension of the Bernoulli random graph $\mathcal{G}(n,p)$ by assigning directions to the edges independently, bidirectional with probability $θ$, and either of the two possible choices of single direction with probability $\frac12(1-θ)$. The approximation involves two independent copies of a trivariate limiting random vector $(W^*_1,W^*_2,W_3)$ associated with a $3$-type Bienaymé--Galton--Watson process. The approximation error is shown to be typically of order $O(n^{-1/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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22828 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Approximating inter-point distances in directed Bernoulli graphs Barbour, A. D. Reinert, Gesine Probability 05C80 (Primary) 60C05, 60J85 (Secondary) 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'$ can be computed along paths that are directed from $v$ to $v'$, or along paths that are directed from $v'$ 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{DG}(n,p,θ)$, obtained as a natural extension of the Bernoulli random graph $\mathcal{G}(n,p)$ by assigning directions to the edges independently, bidirectional with probability $θ$, and either of the two possible choices of single direction with probability $\frac12(1-θ)$. The approximation involves two independent copies of a trivariate limiting random vector $(W^*_1,W^*_2,W_3)$ associated with a $3$-type Bienaymé--Galton--Watson process. The approximation error is shown to be typically of order $O(n^{-1/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)$. |
| title | Approximating inter-point distances in directed Bernoulli graphs |
| topic | Probability 05C80 (Primary) 60C05, 60J85 (Secondary) |
| url | https://arxiv.org/abs/2603.22828 |