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 条
[31]  
Peres Y., J THEOR PROBAB, V28, P1
[32]  
Propp JG, 1996, RANDOM STRUCT ALGOR, V9, P223, DOI 10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO
[33]  
2-O
[34]  
Resnick SI, 2007, SPRINGER SER OPER RE, P1, DOI 10.1007/978-0-387-45024-7
[35]  
Skorohod AV., 1956, Theory of Probability and Its Applications, V1, P261, DOI [DOI 10.1137/1101022, 10.1137/1101022]
[36]   Random random walks on Z(2)(d)* [J].
Wilson, DB .
PROBABILITY THEORY AND RELATED FIELDS, 1997, 108 (04) :441-457
1234