A Generalized Cover Time for Random Walks on Graphs

Cyril Banderier () and Robert P. Dobrow ()
Additional contact information
Cyril Banderier: INRIA (Rocquencourt), Algorithms Project
Robert P. Dobrow: Clarkson University

A chapter in Formal Power Series and Algebraic Combinatorics, 2000, pp 113-124 from Springer

Abstract: Abstract Given a random walk on a graph, the cover time is the first time (number of steps) that every vertex has been hit (covered) by the walk. Define the marking time for the walk as follows. When the walk reaches vertex vi, a coin is flipped and with probability pi the vertex is marked (or colored). We study the time that every vertex is marked. (When all the pi’s are equal to 1, this gives the usual cover time problem.) General formulas are given for the marking time of a graph. Connections are made with the generalized coupon collector’s problem. Asymptotics for small p i ’s are given. Techniques used include combinatorics of random walks, theory of determinants, analysis and probabilistic considerations.

Keywords: Random Walk; Stationary Distribution; Complete Graph; Regular Graph; Outgoing Edge (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-04166-6_10

Ordering information: This item can be ordered from
http://www.springer.com/9783662041666

DOI: 10.1007/978-3-662-04166-6_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().