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.

Review text

The authors consider a binary tree of height \(n\) and investigate the effective resistance \(R_n\) and conductance \(C_n\) between its root and leaves. 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 at infinity. It is shown that \(\text{E} R_n = n \text{E} X_e - ( \text{Var} (X_e)/ \text{E} X_e ) \ln n + O(1)\) and \(\text{Var} (R_n) = O(1)\). Moreover, they establish sub--Gaussian tail bounds for \(R_n\). Some possible extensions to supercritical Galton--Watson trees are also discussed.

Recommendations

Cites work

Cited in

(12)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389604)