SMILE

Stochastic Models for the Inference of Life Evolution

Positive association of the oriented percolation cluster in randomly oriented graphs

Bienvenu, F.

arXiv:1711.08815

2017

Consider any fixed graph whose edges have been randomly and independently oriented, and write \(\{S \leadsto i\}\) to indicate that there is an oriented path going from a vertex \(s \in S\) to vertex \(i\). Narayanan (2016) proved that for any set \(S\) and any two vertices \(i\) and \(j\), \(\{S \leadsto i\}\) and \(\{S \leadsto j\}\) are positively correlated. His proof relies on the Ahlswede-Daykin inequality, a rather advanced tool of probabilistic combinatorics. In this short note, I give an elementary proof of the following, stronger result: writing \(V\) for the vertex set of the graph, for any source set \(S\), the events \(\{S \leadsto i\}\), \(i \in V\), are positively associated -- meaning that the expectation of the product of increasing functionals of the family \(\{S \leadsto i\}\) for \(i \in V\) is greater than the product of their expectations. To show how this result can be used in concrete calculations, I also detail the example of percolation from the leaves of the randomly oriented complete binary tree of height \(n\). Positive association makes it possible to use the Stein--Chen method to find conditions for the size of the percolation cluster to be Poissonian in the limit as \(n\) goes to infinity.

Bibtex

@article{Bienvenu2017PercoRandomlyOriented,
author = {Bienvenu, Fran{\c{c}}ois},
title = {Positive association of the oriented percolation cluster in randomly oriented graphs},
journal = {arXiv:1711.08815},
eprint = {arXiv:1711.08815},
year = {2017},
url = {https://arxiv.org/pdf/1711.08815}
}

Link to the article

View the PDF.