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
    0 references
    0 references
    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
    0 references

    Identifiers