Small noise limits of Markov chains and the PageRank
Vivek S. Borkar, S. Sowmya, Raghavendra Tripathi · 2025
Read Small noise limits of Markov chains and the PageRank by Vivek S. Borkar, S. Sowmya, Raghavendra Tripathi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05137.txt.
Introduction
Vivek Borkar, Sowmya, and Raghavendra Tripathi wrote a 2025 paper on PageRank. In its classic form, PageRank is the steady-state spread of a Markov chain, a step-by-step random process, that has been nudged by a small change. As that nudge shrinks toward zero, the chain loses the trait that keeps it well behaved, so the limit is hard to handle head-on.
The authors turn to a known result, the Markov chain tree theorem, and use it to write down exact formulas for PageRank. The work brings out some results they call surprising. The formulas also hold for a much wider class of nudges, and one case inside that class is personalized PageRank, a form tuned to one user. The paper gives cases where even simpler formulas work. Readers who use PageRank gain exact forms where they once had only step-by-step computing.
Catalog record
| CREATOR | Vivek S. Borkar, S. Sowmya, Raghavendra Tripathi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-05137
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Small noise limits of Markov chains and the PageRank Vivek S. Borkar, S. Sowmya, Raghavendra Tripathi Abstract . We recall the classical formulation of PageRank as the stationary distribution of a singularly perturbed irreducible Markov chain that is not irreducible when the perturbation parameter goes to zero. Specifically, we use the Markov chain tree theorem to derive explicit expressions for the PageRank. This analysis leads to some surprising results. These results are then extended to a much more general class of perturbations that subsume personalized PageRank. We also give examples where even simpler formulas for PageRank are possible. 2020 Mathematics Subject Classification (Primary) 60F99, 05C99 (Secondary) 05C81, 05C90 1. Introduction Google’s PageRank algorithm for ranking web pages [ 5 ] has been an extensively studied topic since its inception. The early accounts [ 18 ] , [ 17 ] , though somewhat dated, give an excellent exposition. See [ 3 ] , [ 10 ] , [ 9 ] , [ 22 ] , [ 27 ] for more recent surveys. There are also other related research directions such as dynamic PageRank [ 7 ] , [ 23 ] and PageRank on random graphs [ 8 ] , [ 19 ] . See also [ 11 ] for a game theoretic formulation of PageRank where the Markov chain tree theorem plays a role as it does here. The literature on PageRank is immense and rich, particularly the schemes that build upon the basic framework of raw PageRank as originally defined. See [ 1 ] , [ 6 ] , [ 14 ] , [ 15 ] , [ 25 ] for other research directions. In this note, we address a novel issue, viz. the PageRank viewed with the lens of small noise limits for stationary distributions of singularly perturbed Markov chains. This leads to additional insights about PageRank, sometimes surprising. In the next section, we recall a key result from Markov chain theory, the Markov chain tree theorem, that facilitates our approach. In section 3, we present our main results. Section 4 gives a few concrete examples. Section 5 concludes with a brief discussion. 2. Markov chain preliminaries Here we recall some standard facts about finite-state Markov chains. Some good general references for this (and more) are [ 13 ] , [ 21 ] , [ 26 ] . A Markov chain (X_{n})_{n\geq 0} on a finite state space S:=\{1,2,\cdots,N\} is described by an n\times n transition matrix P such that P(i,j)=\mathbb{P}(X_{1}=j|X_{0}=i)=\mathbb{P}(X_{n+1}=j|X_{n}=i,X_{m},m<n). Let P^{n} denote the n -fold matrix product of P . It is easy to see that P^{n}(i,j)=\mathbb{P}(X_{n}=j|X_{0}=i) . Two states i and j are said to communicate if P^{n}(i,j)>0 and P^{m}(j,i)>0 for some n,m\in\mathbb{N} . It can be easily verified that communication is an equivalence relation. In particular, it partitions the state space into the so-called communicating classes plus possibly some transient states, i.e. states that do not belong to any communicating class. We say that the chain is reducible when it has more than one communicating class. Otherwise we say that it is irreducible . Let P be the N\times N transition matrix of a (possibly reducible) Markov chain on a finite state space S:=\{1,2,\cdots,N\} . When P is irreducible, it has a unique stationary distribution. That is, there exists a unique probability measure \pi on S (treated as a row vector) such that \pi P=\pi . The situation, however, is different for a reducible Markov chain. In particular, if P is reducible, then each closed communicating class supports a unique stationary distribution. These stationary distributions, after extending them to the whole state space by assigning zero probability to the remaining states, form the extreme points of the polytope of all stationary distributions. In particular, no stationary distribution assigns positive probability to a transient state. In the absence of a unique stationary distribution, a commonly employed technique for ‘selecting’ a stationary distribution is via the zero noise limit. The idea is as follows. Take an irreducible transition matrix Q=[[q(i,j)]]_{i,j\in S} on the same state space and let P_{\epsilon}\coloneqq(1-\epsilon)P+\epsilon Q . The choice of Q is usually dictated by the application. We shall see some examples of P and Q later. A standard choice for Q is \frac{1}{N}\textbf{1}\textbf{1}^{T} . For \epsilon>0 , P^{\epsilon} defines an irreducible transition matrix and hence admits a unique stationary distribution \pi^{\epsilon} . Letting \epsilon\to 0 in the equation \pi^{\epsilon}=\pi^{\epsilon}P_{\epsilon},\ \sum_{i\in S}\pi^{\epsilon}(i)=1, it is easy to see that any limit point of \pi_{\epsilon} as \epsilon\to 0 is a stationary distribution of P . In some cases in applications, one can show that \pi_{\epsilon} has a unique limit as \epsilon\to 0 , and this limiting distribution is then viewed as the ‘physical’ stationary distribution of P . This is called the small noise limit [ 12 ] . In general, the limit may be non-unique and may comprise of all possible stationary distributions of P . We encounter the latter situation later in this work. Next, we describe the Markov chain tree theorem (see e.g. [ 24 ] ) that gives an expression for the stationary distribution of an irreducible Markov chain in terms of the weights of its arborescences. Our treatment of the Markov chain tree theorem follows [ 2 ] . Consider an irreducible Markov chain on S with transition matrix \widetilde{P} . Define an arborescence as a directed spanning tree with at most one outgoing edge from each node. Then there is exactly one node in this tree with no outgoing edge, dubbed the ‘root’ of the arborescence. The weight of an arborescence A , denoted |A| , is the product of transition probabilities of the directed edges in A . For i\in S , let H(i) denote the set of arborescence rooted in i , with its weight defined as |H(i)|:=\sum_{A\in H(i)}|A| . The Markov chain tree theorem states the following. Theorem 2.1 (Markov chain tree theorem) . Let \widetilde{\pi} be the unique stationary distribution of an irreducible Markov chain on the finite state space S=\{1,\ldots,n\} with transition matrix \widetilde{P} . Then, \widetilde{\pi}(i)=\frac{|H(i)|}{\sum_{j}|H(j)|} for i\in S . In section 3, we use the Markov chain tree theorem to analyze the zero noise limit of the PageRank algorithm. We state our main result here. Theorem 2.2 . Let P be a reducible Markov chain on finite state space S=\{1,\ldots,n\} . Let C_{1},\ldots,C_{m} be the closed communicating classes of P . For k\in[m] , let \pi_{k} denote the unique stationary distribution of P supported on C_{k} . Let P_{\epsilon}\coloneqq(1-\epsilon)P+\epsilon\frac{1}{n}\textbf{1}\textbf{1}^{T} and let \pi^{(\epsilon)} denote the unique stationary distribution of P_{\epsilon} . Then, for every k\in[m] and v\in C_{k} , we have \lim_{\epsilon\to 0}\pi^{(\epsilon)}(v)=\frac{\pi_{k}(v)}{m}\;. In particular, we have \lim_{\epsilon\to 0}\pi^{(\epsilon)}(C_{k})=\frac{1}{m}\;, for every k\in[m] . In the context of the PageRank algorithm, the matrix P represents the transition matrix of the simple random walk on the web graph. The basic idea behind the PageRank algorithm is to rank the web pages according to the stationary distribution of P . However, the web graph has some small clusters and even some dangling nodes (i.e., absorbing states, equivalently, the states with no outgoing edge pointing to a different state) and therefore it has no unique stationary distribution. This necessitates the need for some regularization. As explained in