Achieving limiting distributions for Markov chains using back buttons |
| |
Authors: | Feuerverger Andrey Rosenthal Jeffrey S. |
| |
Affiliation: | (1) Department of Statistics, University of Toronto, Toronto, Ontario, Canada, M5S 3G3 |
| |
Abstract: | 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. |
| |
Keywords: | back button backoff process World Wide Web BACKMET algorithm Metropolis-Hastings algorithm |
本文献已被 SpringerLink 等数据库收录! |
|