pith. sign in

arxiv: 0801.1909 · v2 · submitted 2008-01-12 · 🧮 math.PR

Effective resistance of random trees

classification 🧮 math.PR
keywords mathbfresistanceeffectiveoperatornamerandomroottreesaway
0
0 comments X
read the original 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^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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.