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 条

[1] SHUFFLING CARDS AND STOPPING-TIMES [J].

ALDOUS, D ;

DIACONIS, P .

AMERICAN MATHEMATICAL MONTHLY, 1986, 93 (05) :333-348

[2]

[Anonymous], THESIS

[3]

[Anonymous], 2009, American Mathematical Soc.

[4] A FUNCTIONAL LIMIT THEOREM FOR DEPENDENT SEQUENCES WITH INFINITE VARIANCE STABLE LIMITS [J].

Basrak, Bojan ;

Krizmanic, Danijel ;

Segers, Johan .

ANNALS OF PROBABILITY, 2012, 40 (05) :2008-2033

[5] Regularly varying multivariate time series [J].

Basrak, Bojan ;

Segers, Johan .

STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2009, 119 (04) :1055-1080

[6]

Basu R., 2015, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA'15, P1774

[7] The cutoff phenomenon for ergodic Markov processes [J].

Chen, Guan-Yu ;

Saloff-Coste, Laurent .

ELECTRONIC JOURNAL OF PROBABILITY, 2008, 13 :26-78

[8] Computing cutoff times of birth and death chains [J].

Chen, Guan-Yu ;

Saloff-Coste, Laurent .

ELECTRONIC JOURNAL OF PROBABILITY, 2015, 20 :1-47

[9]

Connor SB, 2010, ALEA-LAT AM J PROBAB, V7, P65

[10] The cutoff phenomenon in finite Markov chains [J].

Diaconis, P .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1996, 93 (04) :1659-1664

← 1 2 3 4 →