2015/05/08 by Zhiyi Chi, Chi, Zhiyi
Mathematics · #05C80 #60B20 #Adjacency matrix #Advanced Algebra and Geometry #Combinatorics #Discrete mathematics #Distribution (mathematics) #Eigenvalues and eigenvectors #FOS: Mathematics #Graph #Markov Chains and Monte Carlo Methods #Markov chain #Mathematical analysis #Mathematics #Matrix (chemical analysis) #Physics #Probability (math.PR) #Quantum mechanics #Random Matrices and Applications #Random matrix #Spectral gap #Stationary distribution #Statistics #math.PR #msc:05C80 #msc:60B20
paper · pdf · doi:10.48550/arxiv.1505.02086
openalex publication_date 2015/05/08 · arxiv created 2015/09/08 · arxiv updated 2015/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Random sampling of large Markov matrices with a tunable spectral gap, a nonuniform stationary distribution, and a nondegenerate limiting empirical spectral distribution (ESD) is useful. Fix c>0 and p>0. Let An be the adjacency matrix of a random graph following G(n, p/n), known as the Erdős-Rényi distribution. Add c/n to each entry of An and then normalize its rows. It is shown that the resulting Markov matrix has the desired properties. Its ESD weakly converges in probability to a symmetric nondegenerate distribution, and its extremal eigenvalues, other than 1, fall in [-1/√(1+c/k),-b]∪ [b,1/√(1+c/k)] for any 0< b < 1/√(1+c), where k = \lfloor p \rfloor + 1. Thus, for p∈ (0,1), the spectral gap tends to 1-1/√(1+c).