On the principal eigenvectors of random Markov matrices
Jacob Calvert, Frank den Hollander, Dana Randall · 2025
Read On the principal eigenvectors of random Markov matrices by Jacob Calvert, Frank den Hollander, Dana Randall (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-2505-01608.txt.
Introduction
Jacob Calvert, Frank den Hollander, and Dana Randall analyze the steady-state distribution of random walks on randomly weighted complete networks. That distribution is the principal left eigenvector of a random Markov matrix, an object with no known explicit form. Spectra of such matrices are well studied; the eigenvectors are not.
The authors place random weights on vertices and edges of the complete directed graph. Their main result compares the continuous-time walk's invariant distribution with weights inversely proportional to vertex weights. The distance between them shrinks to zero as the graph grows, under a mild moment condition, even with heavy-tailed vertex weights. A discrete-time companion result answers a question from earlier literature: that distribution becomes asymptotically uniform.
Catalog record
| CREATOR | Jacob Calvert, Frank den Hollander, Dana Randall |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01608
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the principal eigenvectors of random Markov matrices Jacob Calvert, Frank den Hollander, Dana Randall Abstract . We analyze the invariant distributions of continuous-time and discrete-time random walks on randomly weighted complete digraphs. These distributions correspond to the principal left eigenvectors of the associated random Markov generators and kernels, viewed as random matrices. While much is known about the spectra of these matrices, relatively little is known about the principal left eigenvectors, which are delicate random objects for which no explicit form is known. We consider a broad class of such matrices obtained by associating random weights to the vertices and edges of the complete digraph. Our main result concerns the total variation distance between the invariant distribution of the continuous-time random walk and the distribution that is inversely proportional to the vertex weights. It states that, if the edge weights are i.i.d. with a finite p p -th moment for some p > 4 p>4 , then this distance a.s. converges to zero as the number of vertices grows large, even when the vertex weights are heavy-tailed. We further answer a question of Bordenave, Caputo, and Chafaï by showing that, despite the dependence of the entries in the corresponding Markov kernel, its invariant distribution is asymptotically uniform a.s., so long as the edge weights have a finite second moment. 1. Introduction and main result Background. Diverse physical and computational processes motivate the study of random Markov matrices, including both the infinitesimal generators of continuous-time Markov chains and the stochastic kernels of discrete-time Markov chains. A natural model of a random Markov generator Q is (1) Q=A-D, where A is an n\times n random matrix of non-negative weights that are i.i.d. (except possibly for the symmetry A=A^{\top} ), and D=\mathrm{diag}(A1) is the diagonal matrix of the row sums of A , ensuring that Q has row sums equal to zero [ BCC14 ] . 1 1 1 For a 1\times n vector v , we use \mathrm{diag}(v) to denote the n\times n matrix with v along the diagonal and all off-diagonal entries of 0 . For an n\times n matrix M , we use \mathrm{diag}(M) to denote the 1\times n vector (M_{i,i})_{i\in[n]} . A closely related model is the random Markov kernel that results from normalizing the rows of A instead: (2) P=D^{-1}A. The Markov matrices in Eqs. 1 and 2 commonly arise from the adjacency matrices A of graphs, in which case the diagonal entries of D are the vertex degrees and L=-Q is the combinatorial Laplacian [ MPL17 ] . In this case, A is symmetric when the underlying graph is undirected. In general, A is the weighted adjacency matrix of a directed graph. Most results about random Markov matrices concern their spectra [ Cha10 , BCC10 , BCC11 , BCC12 , BCC14 , Ngu14 , Jun18 , CH22 , CO24 ] . In physical contexts, these spectra provide insight into the relaxation of glassy systems [ BR88 ] , the resonances of electrical networks [ Fyo99 , SMFL03 ] , and other features of the diverse classical and quantum systems that Markov matrices model [ Tim09 , Hor09 , BCSZ09 , TYL+21 , NDH23 ] . By comparison, relatively little is known about their principal left eigenvectors, which are invariant distributions \pi_{Q} and \pi_{P} of the corresponding continuous-time and discrete-time Markov chains. These eigenvectors relate to the behavior of important algorithms, like PageRank, which ranks the nodes in a graph in terms of the invariant distribution of a random walk running on it [ CLOC17 , HvdHL25 ] . By definition, the invariant distributions solve the matrix equations \pi_{Q}\,Q=0\quad\text{and}\quad\pi_{P}\,P=\pi_{P}. When the matrix A in Eqs. 1 and 2 is primitive, the Perron–Frobenius theorem implies that \pi_{Q} and \pi_{P} exist and are unique. In the special case when A is also Eulerian, or “balanced” [ MPL17 ] , meaning that A1=A^{\top}1 (i.e., each row sum equals the corresponding column sum), \pi_{Q} and \pi_{P} are simply proportional to the row sums of A . This enables the direct characterization of the principal left eigenvectors of symmetric random Markov matrices. For example, if the upper-triangular entries of A=A^{\top} are i.i.d. with finite second moment, then a maximal version of the strong law of large numbers (when applied to the row sums) implies that (3) \|\pi_{P}-u\|_{\mathrm{TV}}=o(1)\quad\mathrm{a.s.}, where u=(\frac{1}{n},\dots,\frac{1}{n}) is the uniform distribution and \|\nu\|_{\mathrm{TV}}=\frac{1}{2}\sum_{i\in[n]}|\nu(i)| denotes the total variation norm [ BCC10 , Proposition 1.5] . In general, however, the principal left eigenvector is a “delicate random object with no explicit expression” [ BCS19 ] . Indeed, with M denoting Q or P , the Markov chain tree theorem states that \pi_{M}(i)\propto\sum_{\mathcal{T}_{i}}\prod_{(j,k)\in\mathcal{T}_{i}}M_{j,k}, where the sum ranges over spanning trees \mathcal{T}_{i} of the complete digraph rooted at vertex i [ LR83 ] . The complexity of this expression gives a sense of the challenge that the characterization of \pi_{M} generally poses. Goal. The main purpose of this paper is to show that, although \pi_{Q} is generally a complicated function of the transition rates, for a broad class of random Markov generators it is closely approximated by a simple function of the exit rates q_{i}=|Q_{i,i}|=\sum_{j:\,j\neq i}Q_{i,j}. Regarding \pi_{P} , we extend Eq. 3 to the general case of non-symmetric adjacency matrices A , thereby addressing several related questions and claims in the literature. Model. We study the Markov matrices Q and P in Eqs. 1 and 2 arising from an n\times n random weighted adjacency matrix A with entries A_{i,j}=\theta_{i}X_{i,j},\quad i,j\in[n], where (\theta_{i})_{i\geq 1}\in(0,\infty)^{\mathbb{N}} is a (possibly random) sequence of vertex weights and (X_{i,j})_{i,j\geq 1} is an infinite array of i.i.d. directed edge weights with non-degenerate law \mathcal{L} supported on [0,\infty) . 2 2 2 This (non-unique) parameterization of adjacency matrices is common in stochastic thermodynamics and chemical kinetics, where the logarithms of \theta_{i} and X_{i,j} represent the well depths and effective barrier heights in the energy landscape of a non-equilibrium system [ OGH20 ] . Note that the vertex weights do not affect P , nor the closely related kernel \widehat{Q} defined by \widehat{Q}=\widehat{D}^{-1}\widehat{A} in terms of \widehat{A}=A-\mathrm{diag}(\mathrm{diag}(A)) and \widehat{D}=\mathrm{diag}(\widehat{A}1) . We will not study \widehat{Q} for its own sake. Rather, its analysis will be key to proving our main result concerning \pi_{Q} . Although \mathcal{L} may have an atom at 0 , the edge weight X_{i,j} is positive with some probability p\in(0,1) . It follows that both A and \widehat{A} are primitive for all sufficiently large n a.s., because the same is true of the adjacency matrix of the directed Erdős–Rényi random graph \mathcal{D}(n,p) with and without self-loops. For ease of reference, we collect some standard yet important consequences of this observation in the following remark. Remark 1.1 . For the rest of the paper, we will work on the event that A and \widehat{A} are primitive, which holds for all sufficiently large n a.s. On this event, the Markov matrices Q , P , and \widehat{Q} are well-defined and irreducible, and hence the corresponding invariant distributions \pi_{Q} , \pi_{P} , and \pi_{\widehat{Q}} exist and are unique. Additionally, the kernels P and \widehat{Q} are aperiodic. Figure 1. Comparison of distributions in Theorem 1.2 for edge weight law \mathcal{L}=\mathrm{Exp}(1) . Plotted are the scaled \pi_{Q} probabilities in descending order with corresponding values of