Achieving limiting distributions for Markov chains using back buttons
As a simple model for browsing the World Wide Web, we consider Markov chains with the option of moving "back" to the previous state. We develop an algorithm which uses back buttons to achieve essentially any limiting distribution on the state space. This corresponds to spending the desired total fraction of time at each web page. On finite state spaces, our algorithm always succeeds. On infinite state spaces the situation is more complicated, and is related to both the tail behaviour of the distributions, and the properties of convolution equations.
back button world wide web backoff process backmet algorithm metropolis-hastings algorithm