When Does Memory Speed-up Mixing?

被引：0

作者：

Apers, Simon ^{[1
]}

Sarlette, Alain ^{[2
,3
]}

Ticozzi, Francesco ^{[4
,5
]}

机构：

[1] Univ Ghent, Dept Elect & Informat Syst, Technol Pk 914, B-9052 Zwijnaared Ghent, Belgium

[2] Univ Ghent, Ghent, Belgium

[3] INRIA Paris, QUANTIC Lab, Rue Simone Iff 2, F-75012 Paris, France

[4] Univ Padua, Dipartimento Ingn Informaz, Via Gradenigo 6-B, I-35131 Padua, Italy

[5] Dartmouth Coll, Dept Phys & Astron, 3127 Wilder, Hanover, NH 03755 USA

来源：

2017 IEEE 56TH ANNUAL CONFERENCE ON DECISION AND CONTROL (CDC) | 2017年

关键词：

MARKOV-CHAINS; RANDOM-WALKS; ALGORITHM; TIME;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We investigate under which conditions a higherorder Markov chain, or more generally a Markov chain on an extended state space, can mix faster than a standard Markov chain on a graph of interest. We find that, depending on the constraints on the dynamics, two very different scenarios can emerge: under strict invariance of the target marginal and for general initialization of the lifted chain no speedup is possible; on the other hand, if these requirements are both relaxed, the lifted dynamics can achieve mixing in a time that corresponds to the diameter of the graph, which is optimal.

引用

页数：6

共 22 条

[1] Non-backtracking random walks mix faster [J].

Alon, Noga ;

Benjamini, Itai ;

Lubetzky, Eyal ;

Sodin, Sasha .

COMMUNICATIONS IN CONTEMPORARY MATHEMATICS, 2007, 9 (04) :585-603

[2]

[Anonymous], 1995, Reversible markov chains and random walks on graphs

[3]

[Anonymous], 2009, American Mathematical Soc.

[4]

Bernard P., 1999, Lectures on probability theory and statistics, V1717, P93

[5]

Diaconis P, 2000, ANN APPL PROBAB, V10, P726

[6] 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

[7]

Diaconis P., 2013, Annales de la Facult des sciences de Toulouse: Mathmatiques Ser. 6, V22, P573, DOI [10.5802/afst.1383, DOI 10.5802/AFST.1383]

[8] A RANDOM POLYNOMIAL-TIME ALGORITHM FOR APPROXIMATING THE VOLUME OF CONVEX-BODIES [J].

DYER, M ;

FRIEZE, A ;

KANNAN, R .

JOURNAL OF THE ACM, 1991, 38 (01) :1-17

[9]

Feng Chen, 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P275, DOI 10.1145/301250.301315

[10] Non-reversible Monte Carlo simulations of spin models [J].

Fernandes, Heitor C. M. ;

Weigel, Martin .

COMPUTER PHYSICS COMMUNICATIONS, 2011, 182 (09) :1856-1859

← 1 2 3 →