Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T10:47:59.605Z 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: falawadi@kuc01.kuniv.edu.kw
Mokhtar Konsowa
Affiliation:
Department of Statistics and OR, Kuwait University, Safat, Kuwait, 13060 E-mail: konsowa@kuc01.kuniv.edu.kw
Zainab Najeh
Affiliation:
Department of Statistics and OR, Kuwait University, Safat, Kuwait, 13060 E-mail: zainab-najeh@hotmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

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

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