EFFECTIVE RESISTANCE OF RANDOM TREES

• 成果类型: Article
• 署名作者: Addario-Berry, Louigi; Broutin, Nicolas; Lugosi, Gabor
• 署名单位: Universite de Montreal; Pompeu Fabra University; ICREA; Pompeu Fabra University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/08-AAP572
• 发表日期: 2009
• 页码: 1092-1107
• 关键词: inverse gaussian distribution; random-walk; percolation; variance; inequalities; networks

摘要

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 ER(n) = nEX(e) - (Var(X(e))/EX(e)) In n + O(1) and 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.