Effective resistance of random trees (Q2389604)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Effective resistance of random trees |
scientific article |
Statements
Effective resistance of random trees (English)
0 references
17 July 2009
0 references
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.
0 references
random trees
0 references
electrical networks
0 references
Efron--Stein inequality
0 references