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

m a t h b f E R_{n} = n m a t h b f E X_{e} - (o p e r a t o r n a m e m a t h b f V a r (X_{e}) / m a t h b f E X_{e}) l n n + O (1)

and

o p e r a t o r n a m e m a t h b f V a r (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.

Recommendations

Cites Work

Cited In (8)

This page was built for publication: Effective resistance of random trees