Abstract
We introduce backoff processes, an idealized stochastic model of browsing on the World Wide Web, which incorporates both hyperlink traversals and use of the “back button.” With some probability the next state 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 by a “forward step.” Repeated clicks on the back button require access to increasingly distant history. We show that this process has fascinating similarities to and differences from Markov chains. In particular, we prove that, like Markov chains, back-off processes always have a limit distribution, and we give algorithms to compute this distribution. Unlike Markov chains, the limit distribution may depend on the start state.
Introduction
Traditional models of web navigation, such as the Random Surfer model used in early PageRank algorithms, rely heavily on Markov chains. These models operate on the "memoryless" property: the probability of moving to a new page depends solely on the current page. However, real-world web browsing is rarely memoryless. Users frequently utilize the "back button" to return to previously visited content, an action that inherently requires the browser to maintain a history of the path taken.
This paper introduces backoff processes, a novel stochastic framework that extends Markov chains by incorporating a history stack. By modeling the back button as a fundamental transition type, the authors explore how memory-dependent behavior alters the long-term dynamics of random walks on a graph.
The Backoff Process Model
A backoff process is defined by three components: an underlying finite Markov chain $M$ (representing hyperlink structures), a vector of backoff probabilities $\alpha$ for each state, and a designated starting state $i$.
The core mechanism of the process is a history stack. At each discrete time step, the process performs one of two actions:
- Forward Step: With probability $1-\alpha$, the process chooses a new state based on the transition matrix $M$ and pushes this new state onto the stack.
- Backward Step: With probability $\alpha$, the process "pops" the current state from the stack, returning the user to the state immediately below it in the history.
This simple addition of a stack transforms the walk from a memoryless process into one where the future is dictated by the specific path used to reach the current state. Repeated back-button clicks allow a user to retreat deep into their browsing history, potentially returning all the way to their starting point.
Classification of Dynamics
The authors categorize backoff processes into three distinct regimes based on the "drift" or growth rate of the history stack:
- Ergodic: The history stack remains relatively small and frequently returns to the empty state (the starting point). In this regime, the process is highly influenced by its origin.
- Transient: The history stack grows indefinitely over time. The process "wanders off" into the graph, and the influence of the starting state eventually diminishes.
- Null: This represents the critical threshold between the ergodic and transient states.
To analyze these regimes, the authors employ potential functions and martingale tail inequalities, proving that despite the complexity of the history stack, every backoff process eventually settles into a Cesaro limit distribution (a long-term time-average of state occupancy).
Key Insights and Theoretical Departures
Start State Sensitivity
Perhaps the most significant finding is that backoff processes break a fundamental rule of irreducible finite Markov chains. In a standard Markov chain, the starting state is eventually forgotten, and the system converges to a unique stationary distribution. In backoff processes—specifically in the ergodic regime—the starting state permanently influences the limit distribution. Because the user frequently "backs up" to their origin, the "home base" remains a focal point of the distribution forever.
The Critical Threshold
In a simplified model where every state has the same backoff probability $\alpha$, a phase transition occurs at $\alpha = 1/2$. When the probability of going back is less than half, the stack grows (transient); when it is greater than half, the stack stays small (ergodic). This transition marks the point where the user's history becomes a permanent anchor versus a temporary trail.
Irrationality from Rationality
The authors demonstrate a surprising mathematical property in the transient case: even if all transition and backoff probabilities are rational numbers, the resulting limit probabilities can be irrational (for example, the roots of cubic equations). This distinguishes backoff processes from standard Markov chains, where rational inputs always yield rational stationary distributions, and necessitates the use of approximation algorithms for computation.
Computational Framework
The paper provides a robust algorithmic foundation for analyzing these processes. Central to their approach is the Hungarian matrix ($H = I - AMA^{-1}$), a construction that allows the researchers to solve for limit probabilities using linear systems in the ergodic and null cases. For the more complex transient cases, they provide a polynomial-time algorithm to approximate the limit distribution to within any desired error margin $\epsilon$ using semidefinite programming.
Conclusion and Future Work
While the backoff process is an idealized model—omitting modern features like multiple tabs or forward buttons—it represents a vital step toward more realistic models of web navigation. The proof that history-dependent processes still possess predictable limit distributions provides a theoretical safety net for researchers modeling complex user behaviors. Future work remains in extending these proofs to aperiodic null cases and incorporating more sophisticated human browsing nuances into the stochastic framework.
Summary updated