Ergodicity Coefficients for Higher-Order Stochastic Processes

DOI10.1137/19M1285214zbMATH Open1483.60105arXiv1907.04841MaRDI QIDQ5037573FDOQ5037573

Authors: Francesco Tudisco, Dario Fasino 

Publication date: 1 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: The use of higher-order stochastic processes such as nonlinear Markov chains or vertex-reinforced random walks is significantly growing in recent years as they are much better at modeling high dimensional data and nonlinear dynamics in numerous application settings. In many cases of practical interest, these processes are identified with a stochastic tensor and their stationary distribution is a tensor $Z$-eigenvector. However, fundamental questions such as the convergence of the process towards a limiting distribution and the uniqueness of such a limit are still not well understood and are the subject of rich recent literature. Ergodicity coefficients for stochastic matrices provide a valuable and widely used tool to analyze the long-term behavior of standard, first-order, Markov processes. In this work, we extend an important class of ergodicity coefficients to the setting of stochastic tensors. We show that the proposed higher-order ergodicity coefficients provide new explicit formulas that (a) guarantee the uniqueness of Perron $Z$-eigenvectors of stochastic tensors, (b) provide bounds on the sensitivity of such eigenvectors with respect to changes in the tensor and (c) ensure the convergence of different types of higher-order stochastic processes governed by cubical stochastic tensors. Moreover, we illustrate the advantages of the proposed ergodicity coefficients on several example application settings, including the analysis of PageRank vectors for triangle-based random walks and the convergence of lazy higher-order random walks.

Full work available at URL: https://arxiv.org/abs/1907.04841

Recommendations

• scientific article
• Coefficients of ergodicity for stochastically monotone Markov chains
• High-order ergodicity of a complex harmonic process
• Coefficients of ergodicity for Markov chains with uncertain parameters
• Exponential ergodicity for a class of non-Markovian stochastic processes
• scientific article; zbMATH DE number 809400
• Ergodicity coefficient and perturbation bounds for continuous-time Markov chains
• Ergodic properties of generalized Ornstein-Uhlenbeck processes
• scientific article; zbMATH DE number 2156209

zbMATH Keywords

nonnegative tensorsvertex-reinforced random walk\(Z\)-eigenvectorergodicity coefficienthigher-order Markov chainmultilinear PageRankstochastic tensorsspacey random walk

Mathematics Subject Classification ID

Numerical analysis or methods applied to Markov chains (65C40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Numerical computation of matrix norms, conditioning, scaling (65F35) Numerical solutions to stochastic differential and integral equations (65C30)

Cites Work

• Spectral redemption in clustering sparse networks
• The mixture transition distribution model for high-order Markov chains and non-Gaussian time series
• Title not available (Why is that?)
• Estimation and Modelling Repeated Patterns in High Order Markov Chains with the Mixture Transition Distribution Model
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• Nonlinear Markov processes and kinetic equations.
• Most Tensor Problems Are NP-Hard
• Perron-Frobenius theorem for nonnegative multilinear forms and extensions
• Ergodicity coefficients defined by vector norms
• Shifted power method for computing tensor eigenpairs
• Extensions of Jentzsch's Theorem
• Perron-Frobenius theorem for nonnegative tensors
• D-eigenvalues of diffusion kurtosis tensors
• Non-negative matrices and Markov chains. 2nd ed
• Vertex-reinforced random walks and a conjecture of Pemantle
• Convergence of a second order Markov chain
• Tensor decompositions for learning latent variable models
• An elementary proof of the Birkhoff-Hopf theorem
• On the limiting probability distribution of a transition probability tensor
• Title not available (Why is that?)
• On the uniqueness and non-uniqueness of the positive \(\mathcal Z\)-eigenvector for transition probability tensors
• Stationary probability vectors of higher-order Markov chains
• The perturbation bound for the Perron vector of a transition probability tensor
• On the uniqueness of the positive Z-eigenvector for nonnegative tensors
• Vertex-reinforced random walk
• A note on certain ergodicity coefficients
• Block tensor unfoldings
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• The contractivity of cone-preserving multilinear mappings
• Multilinear PageRank
• Tensor Analysis
• Random walks and diffusion on networks
• Three Hypergraph Eigenvector Centralities
• Ergodicity of $p$-majorizing nonlinear Markov operators on the finite dimensional space
• Perturbation of the stationary distribution measured by ergodicity coefficients
• The Spacey Random Walk: A Stochastic Process for Higher-Order Data
• The uniqueness of multilinear PageRank vectors
• Extrapolation methods for fixed‐point multilinear PageRank computations
• Markov chains with memory, tensor formulation, and the dynamics of power iteration
• Fluctuations of the empirical measure of freezing Markov chains
• Convergence of a transition probability tensor of a higher-order Markov chain to the stationary probability vector
• The Perron--Frobenius Theorem for Multihomogeneous Mappings
• A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps
• Perron-based algorithms for the multilinear PageRank
• Non-backtracking PageRank
• A framework for second-order eigenvector centralities and clustering coefficients

Cited In (9)

• Second order Markov chains with finite vectors known stationary
• The Relation Between a Tensor and Its Associated Semi-Symmetric Form
• On the tensor spectral \(\mathbf{p}\)-norm and its higher order power method
• Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors
• Hitting times for second-order random walks
• Improved uniqueness conditions of solution for multilinear pagerank and its application
• Nonlocal pagerank
• New uniqueness conditions for the stationary probability matrix of transition probability tensors
• Multi-linear pseudo-PageRank for hypergraph partitioning

This page was built for publication: Ergodicity Coefficients for Higher-Order Stochastic Processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5037573)