The cutoff phenomenon for random birth and death chains

被引：3
作者：
Smith, Aaron [1 ]
机构：
[1] Univ Ottawa, Dept Math & Stat, 585 King Edward Dr, Ottawa, ON K1N 7N5, Canada
来源：
RANDOM STRUCTURES & ALGORITHMS | 2017年 / 50卷 / 02期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Markov chains mixing times; cutoff phenomenon; birth and death chain; random matrix; MARKOV-CHAINS; TIMES; MATRICES; MODEL;
D O I：
10.1002/rsa.20693
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
For any distribution on [n]={1,2,...,n}, we study elements drawn at random from the set A of tridiagonal stochastic matrices K satisfying (i)K[i,j]=(j)K[j,i] for all i,j[n]. These matrices correspond to birth and death chains with stationary distribution . We analyze an algorithm for sampling from A and use results from this analysis to draw conclusions about the Markov chains corresponding to typical elements of A. Our main interest is in determining when certain sequences of random birth and death chains exhibit the cutoff phenomenon. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 287-321, 2017
引用
收藏
页码：287 / 321
页数：35
相关论文
共 36 条
[11]  
Diaconis P., 1990, Random Structures & Algorithms, V1, P51, DOI [10.1002/rsa.3240010105, DOI 10.1002/RSA.3240010105]
[12]  
Diaconis P., 2008, ANN APPL PROBAB, V333, P33
[13]   Random doubly stochastic tridiagonal matrices [J].
Diaconis, Persi ;
Wood, Philip Matchett .
RANDOM STRUCTURES & ALGORITHMS, 2013, 42 (04) :403-437
[14]   Total variation cutoff in birth-and-death chains [J].
Ding, Jian ;
Lubetzky, Eyal ;
Peres, Yuval .
PROBABILITY THEORY AND RELATED FIELDS, 2010, 146 (1-2) :61-85
[15]  
Dou C, 1996, ANN PROBAB, V24, P987
[16]  
Dyer Martin., 2004, Proceedings of RANDOM, P149
[17]  
ErdosP, 1961, Magyar Tud. Akad. Mat. Kutato Int. Kozl, V6, P215
[18]   A survey of results on random random walks on finite groups [J].
Hildebrand, Martin .
PROBABILITY SURVEYS, 2005, 2 :33-63
[19]   MEAN PASSAGE TIMES FOR TRIDIAGONAL TRANSITION MATRICES AND A 2-PARAMETER EHRENFEST URN MODEL [J].
KRAFFT, O ;
SCHAEFER, M .
JOURNAL OF APPLIED PROBABILITY, 1993, 30 (04) :964-970
[20]  
Kuske R, 2000, SIAM J APPL MATH, V61, P1308
1234