Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-26T21:28:12.538Z Has data issue: false hasContentIssue false
  • English
  • Français

COMMUTE TIMES AND THE EFFECTIVE RESISTANCES OF RANDOM TREES

Published online by Cambridge University Press:  14 July 2009

Fahimah Al-Awadhi ,
Mokhtar Konsowa  and
Zainab Najeh
Fahimah Al-Awadhi
Affiliation:
Department of Statistics and OR, Kuwait University, Safat, Kuwait, 13060 E-mail: [email protected]
Mokhtar Konsowa
Affiliation:
Department of Statistics and OR, Kuwait University, Safat, Kuwait, 13060 E-mail: [email protected]
Zainab Najeh
Affiliation:
Department of Statistics and OR, Kuwait University, Safat, Kuwait, 13060 E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article we study the commute and hitting times of simple random walks on spherically symmetric random trees in which every vertex of level n has outdegree 1 with probability 1−qn and outdegree 2 with probability qn. Our argument relies on the link between the commute times and the effective resistances of the associated electric networks when 1 unit of resistance is assigned to each edge of the tree.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 23 , Issue 4 , October 2009 , pp. 649 - 660
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Aldous, D. & Fill, J. (2002). Reversible Markov chains and random walks on graphs. Preprint. Available from http://www.stat.berkeley.edu/~aldous/book.html.Google Scholar
2.Chandra, A., Reghavan, P., Ruzzo, W., Smolensky, R., & Tiwari, P. (1989). The electrical resistance of a graph captures its commute and cover times. Proceedings of the annual ACM symposium on the theory of computing, pp. 574–586.CrossRefGoogle Scholar
3.Doyle, P. & Snell, J. (1984). Random walks and electric networks. The Carus Mathematical Monographs. Washington, DC: Mathematical Association of America.CrossRefGoogle Scholar
4.Feller, W. (1968). An introduction to probability theory and its applications, Vol. I, 2nd ed.New York: Wiley.Google Scholar
5.Knopp, K. (1956). Infinite sequences and series. New York: Dover Publications.Google Scholar
6.Konsowa, M. (2006). Random walks on finite graphs. Journal of Statistical Theory and Its Applications 5(4): 373–380.Google Scholar
7.Lovász, L. (1993). Random walks on graphs. Bolyai Society, Mathematical Studies 2: 1–46.Google Scholar