The full spectrum of random walks on complete finite d-ary trees

被引：0
作者：
Nestoridi, Evita [1 ]
Nguyen, Oanh [1 ,2 ]
机构：
[1] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
[2] Univ Illinois, Dept Math, Champaign, IL USA
来源：
ELECTRONIC JOURNAL OF PROBABILITY | 2021年 / 26卷
关键词：
random walk; spectrum; regular trees;
D O I：
10.1214/21-EJP608
中图分类号：
O21 [概率论与数理统计]; C8 [统计学];
学科分类号：
020208 ; 070103 ; 0714 ;
摘要：
In the present paper, we determine the full spectrum of the simple random walk on finite, complete d-ary trees. We also find an eigenbasis for the transition matrix. As an application, we apply our results to get a lower bound for the interchange process on complete, finite d-ary trees, which we conjecture to be sharp.
引用
收藏
页数：17
相关论文
共 25 条
  • [1] RANDOM-WALK COVERING OF SOME SPECIAL TREES
    ALDOUS, DJ
    [J]. JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1991, 157 (01) : 271 - 283
  • [2] Comparing with octopi
    Alon, Gil
    Kozma, Gady
    [J]. ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2020, 56 (04): : 2672 - 2685
  • [3] Functions of random walks on hyperplane arrangements
    Athanasiadis, Christos A.
    Diaconis, Persi
    [J]. ADVANCES IN APPLIED MATHEMATICS, 2010, 45 (03) : 410 - 437
  • [4] CHARACTERIZATION OF CUTOFF FOR REVERSIBLE MARKOV CHAINS
    Basu, Riddhipratim
    Hermon, Jonathan
    Peres, Yuval
    [J]. ANNALS OF PROBABILITY, 2017, 45 (03) : 1448 - 1487
  • [5] A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
    Bidigare, P
    Hanlon, P
    Rockmore, D
    [J]. DUKE MATHEMATICAL JOURNAL, 1999, 99 (01) : 135 - 174
  • [6] Brown KS, 1998, ANN PROBAB, V26, P1813
  • [7] Semigroups, rings, and Markov chains
    Brown, KS
    [J]. JOURNAL OF THEORETICAL PROBABILITY, 2000, 13 (03) : 871 - 938
  • [8] PROOF OF ALDOUS' SPECTRAL GAP CONJECTURE
    Caputo, Pietro
    Liggett, Thomas M.
    Richthammer, Thomas
    [J]. JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2010, 23 (03) : 831 - 851
  • [9] Computing cutoff times of birth and death chains
    Chen, Guan-Yu
    Saloff-Coste, Laurent
    [J]. ELECTRONIC JOURNAL OF PROBABILITY, 2015, 20 : 1 - 47
  • [10] Chen GY, 2013, ALEA-LAT AM J PROBAB, V10, P293
123