The spectral gap of sparse random digraphs
The spectral gap of sparse random digraphs
复制标题
稀疏随机有向图的谱间隙
DOI：
10.1214/20-aihp1090
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Simon Coste
中科院分区：
文献类型：
--
作者：
Simon Coste
转移矩阵P的第二大特征值与马尔可夫链的许多性质有关，特别是它向平稳分布的收敛速度。本文给出了给定度序列的随机有向图上简单随机游动的转移矩阵P的第二特征值的一个渐近上界。这是第一个关于稀疏不可逆马氏链的谱间隙的渐近行为与一个未知的平稳分布。我们的结果的直接后果是一个推广的著名的弗里德曼定理，无向正则图。我们的结果是基于Bordenave（2015）引入的跟踪方法的变体。
The second largest eigenvalue of a transition matrix $P$ has connections with many properties of the underlying Markov chain, and especially its convergence rate towards the stationary distribution. In this paper, we give an asymptotic upper bound for the second eigenvalue when $P$ is the transition matrix of the simple random walk over a random directed graph with given degree sequence. This is the first result concerning the asymptotic behavior of the spectral gap for sparse non-reversible Markov chains with an unknown stationary distribution. An immediate consequence of our result is a generalization of the well-known Friedman theorem, for undirected regular graphs. Our result is based on a variation of the trace method introduced by Bordenave (2015).