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.