Design of on-line algorithms using hitting times

Random walks are well known for playing a crucial role in the design of ran domized off-line as well as on-line algorithms. In this work we prove some basic identities for ergodic Markov chains (e.g., an interesting characteri zation of reversibility in Markov chains is obtained in terms of first pass age times). Besides providing new insight into random walks on weighted gra phs, we show how these identities give us a way of designing competitive ra ndomized on-line algorithms for certain well-known problems.