×

zbMATH — the first resource for mathematics

Effective resistance of random trees. (English) Zbl 1176.60068
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.

MSC:
60J45 Probabilistic potential theory
31C20 Discrete potential theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Addario-Berry, L. and Reed, B. A. (2009). Minima in branching random walks. Ann. Probab. · Zbl 1196.60142 · doi:10.1214/08-AOP428
[2] Athreya, K. B. and Ney, P. E. (1972). Branching Processes . Springer, Berlin. · Zbl 0259.60002
[3] Barndorff-Nielsen, O. E. (1994). A note on electrical networks and the inverse Gaussian distribution. Adv. in Appl. Probab. 26 63-67. JSTOR: · Zbl 0792.60015 · doi:10.2307/1427579 · links.jstor.org
[4] Barndorff-Nielsen, O. E. and Koudou, A. E. (1998). Trees with random conductivities and the (reciprocal) inverse Gaussian distribution. Adv. in Appl. Probab. 30 409-424. · Zbl 0912.60017 · doi:10.1239/aap/1035228076
[5] Benjamini, I. and Rossignol, R. (2008). Submean variance bound for effective resistance on random electric networks. Comm. Math. Phys. 280 445-462. · Zbl 1207.82024 · doi:10.1007/s00220-008-0476-7
[6] Benjamini, I., Kalai, G. and Schramm, O. (2003). First passage percolation has sublinear distance variance. Ann. Probab. 31 1970-1978. · Zbl 1087.60070 · doi:10.1214/aop/1068646373 · euclid:aop/1068646373
[7] Boucheron, S., Bousquet, O., Lugosi, G. and Massart, P. (2005). Moment inequalities for functions of independent random variables. Ann. Probab. 33 514-560. · Zbl 1074.60018 · doi:10.1214/009117904000000856
[8] de Bruijn, N. G. (1981). Asymptotic Methods in Analysis , 3rd ed. Dover Publications, New York. · Zbl 0556.41021
[9] Doyle, P. G. and Snell, J. L. (1984). Random Walks and Electric Networks. Carus Mathematical Monographs 22 . Mathematical Association of America, Washington, DC. · Zbl 0583.60065
[10] Efron, B. and Stein, C. (1981). The jackknife estimate of variance. Ann. Statist. 9 586-596. · Zbl 0481.62035 · doi:10.1214/aos/1176345462
[11] Falik, D. and Samorodnitsky, A. (2007). Edge-isoperimetric inequalities and influences. Combin. Probab. Comput. 16 693-712. · Zbl 1134.05309 · doi:10.1017/S0963548306008340
[12] Flajolet, P. and Odlyzko, A. (1982). The average height of binary trees and other simple trees. J. Comput. System Sci. 25 171-213. · Zbl 0499.68027 · doi:10.1016/0022-0000(82)90004-6
[13] Lyons, R. (1990). Random walks and percolation on trees. Ann. Probab. 18 931-958. · Zbl 0714.60089 · doi:10.1214/aop/1176990730
[14] Lyons, R. and Pemantle, R. (1992). Random walk in a random environment and first-passage percolation on trees. Ann. Probab. 20 125-136. · Zbl 0766.60091 · doi:10.1214/aop/1176989540
[15] Lyons, R. and Peres, Y. (2006). Probability on Trees and Networks . Cambridge Univ. Press, Cambridge.
[16] Lyons, R., Pemantle, R. and Peres, Y. (1997). Unsolved problems concerning random walks on trees. In Classical and Modern Branching Processes ( Minneapolis, MN , 1994). The IMA Volumes in Mathematics and Its Applications 84 223-237. Springer, New York. · Zbl 0867.60067
[17] Pemantle, R. (1988). Phase transition in reinforced random walk and RWRE on trees. Ann. Probab. 16 1229-1241. · Zbl 0648.60077 · doi:10.1214/aop/1176991687
[18] Peres, Y. (1999). Probability on trees: An introductory climb. In Lectures on Probability Theory and Statistics ( Saint-Flour , 1997). Lecture Notes in Mathematics 1717 193-280. Springer, Berlin. · Zbl 0957.60001
[19] Soardi, P. M. (1994). Potential Theory on Infinite Networks. Lecture Notes in Mathematics 1590 . Springer, Berlin. · Zbl 0818.31001 · doi:10.1007/BFb0073995
[20] Steele, J. M. (1986). An Efron-Stein inequality for nonsymmetric statistics. Ann. Statist. 14 753-758. · Zbl 0604.62017 · doi:10.1214/aos/1176349952
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.