Abstract
Random walks are well known for playing a crucial role in the design of randomized
off-line as well as on-line algorithms. In this work we prove some basic identities for ergodic Markov
chains (e.g., an interesting characterization of reversibility in Markov chains is obtained in terms of
first passage times). Besides providing new insight into random walks on weighted graphs, we show
how these identities give us a way of designing competitive randomized on-line algorithms for certain
well-known problems.
Users
Please
log in to take part in the discussion (add own reviews or comments).