Random Walks with "Back Buttons"

Madhu Sudan

Associate Professor, EECS Department

Massachusetts Institute of Technology

In this talk, we will introduce the notion of "backoff processes'', an idealized stochastic model of browsing on the world-wide web. This model incorporates both hyperlink traversals and use of the "back button.'' With some probability the next state of the process is generated by a distribution over out-edges from the current state, as in a traditional Markov chain. With the remaining probability, however, the next state is generated by clicking on the back button, and returning to the state from which the current state was entered. Repeated clicks on the back button require access to increasingly distant history. Backoff processes have fascinating similarities to and differences from Markov chains. In particular, they include the class of finite Markov chains as a special case, but are included within the class of denumerable Markov chains. Backoff processes always have a limit distribution, like (irreducible, aperiodic) Markov chains. Unlike Markov chains, the limit distribution may depend on the start state. Further this distribution can be computed by an efficient algorithm. In this talk, we will describe some of the mathematical questions and algorithmic answers associated with backoff processes. Joint work with Ron Fagin, Anna Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld and Andrew Tomkins.