%0 Journal Article %1 tetali1999design %A Tetali, Prasad %D 1999 %I Society for Industrial & Applied Mathematics (SIAM) %J SIAM J. Comput. %K Markov_chain cat_and_mouse_game effective_resistance electrical_networks hitting_times resistance_distance %N 4 %P 1232--1246 %R 10.1137/s0097539798335511 %T Design of On-Line Algorithms Using Hitting Times %U http://dx.doi.org/10.1137/S0097539798335511 %V 28 %X 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.

@article{tetali1999design, 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.}, added-at = {2016-09-17T08:56:00.000+0200}, author = {Tetali, Prasad}, biburl = {https://www.bibsonomy.org/bibtex/2fd2f028e8b13639d103013dc60f0e156/peter.ralph}, doi = {10.1137/s0097539798335511}, interhash = {724778efbd0930e1311120935738dde2}, intrahash = {fd2f028e8b13639d103013dc60f0e156}, journal = {{SIAM} J. Comput.}, keywords = {Markov_chain cat_and_mouse_game effective_resistance electrical_networks hitting_times resistance_distance}, month = jan, number = 4, pages = {1232--1246}, publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})}, timestamp = {2016-09-17T08:56:00.000+0200}, title = {Design of On-Line Algorithms Using Hitting Times}, url = {http://dx.doi.org/10.1137/S0097539798335511}, volume = 28, year = 1999 }