Effective resistance of random trees

Abstract

We investigate the effective resistance $R_n$ and conductance $C_n$ 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 $r_e=2^d{X}_e$ where the $X_e$ are i.i.d. positive random variables bounded away from zero and infinity. It is shown that $\mathbf{E}{R}_n=n\mathbf{E}{X}_e-(\mathrm{Var}(X_e)/\mathbf{E}{X}_e)\ln n+O(1)$ and $\mathrm{Var}(R_n)=O(1)$. Moreover, we establish sub-Gaussian tail bounds for $R_n$. We also discuss some possible extensions to supercritical Galton--Watson trees.

Published in at http://dx.doi.org/10.1214/08-AAP572 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Minima in branching random walks
• Moment inequalities for functions of independent random variables