We investigate the effective resistance Rn and conductance Cn between the root and leaves of a binary tree of height n. In this electrical network, the resistance of each edge e at distance d from the root is defined by re=2dXe where the Xe are i.i.d. positive random variables bounded away from zero and infinity. It is shown that ERn=nEXe−(Var (Xe)/EXe)ln n+O(1) and Var (Rn)=O(1). Moreover, we establish sub-Gaussian tail bounds for Rn. We also discuss some possible extensions to supercritical Galton–Watson trees.
Publié le : 2009-06-15
Classification:
Random trees,
electrical networks,
Efron–Stein inequality,
60J45,
31C20
@article{1245071020,
author = {Addario-Berry, Louigi and Broutin, Nicolas and Lugosi, G\'abor},
title = {Effective resistance of random trees},
journal = {Ann. Appl. Probab.},
volume = {19},
number = {1},
year = {2009},
pages = { 1092-1107},
language = {en},
url = {http://dml.mathdoc.fr/item/1245071020}
}
Addario-Berry, Louigi; Broutin, Nicolas; Lugosi, Gábor. Effective resistance of random trees. Ann. Appl. Probab., Tome 19 (2009) no. 1, pp. 1092-1107. http://gdmltest.u-ga.fr/item/1245071020/