Time Dependent Biased Random Walks
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
We study the biased random walk where at each step of a random walk a
"controller" can, with a certain small probability, move the walk to an
arbitrary neighbour. This model was introduced by Azar et al. [STOC'1992]; we
extend their work to the time dependent setting and consider cover times of
this walk. We obtain new bounds on the cover and hitting times. Azar et al.
conjectured that the controller can increase the stationary probability of a
vertex from
Description
Keywords
Journal Title
Conference Name
Journal ISSN
1549-6333