Effective resistance of random trees

Details Effective resistance of random trees Effective resistance of random trees

2008-01-12

arxiv.org/abs/0801.1909v2

Annals of Applied Probability 2009, Vol. 19, No. 3, 1092-1107

Mathematics

Probability

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

Scientific paper

10.1214/08-AAP572

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^dX_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-(\operatorname {\mathbf{Var}}(X_e)/\mathbf{E}X_e)\ln n+O(1)$ and $\operatorname {\mathbf{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.

Affiliated with

Also associated with

No associations

Rating

Effective resistance of random trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Effective resistance of random trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Effective resistance of random trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-605995