没有合适的资源？快使用搜索试试~ 我知道了~

首页Markov Chains and Mixing Times

Markov Chains and Mixing Times

Markov

Chains

需积分: 10 17 下载量 140 浏览量更新于2023-06-17 1 收藏 6.45MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

387页

Markov Chains and Mixing Times David A. Levin Yuval Peres Elizabeth L. Wilmer

资源详情

资源推荐

Markov Chains and Mixing Times

David A. Levin

Yuval Peres

Elizabeth L. Wilmer

University of Oregon

E-mail address: dlevin@uoregon.edu

URL: http://www.uoregon.edu/~dlevin

Microsoft Research, University of Washington and UC Berkeley

E-mail address: peres@microsoft.com

URL: http://research.microsoft.com/~peres/

Oberlin College

E-mail address: elizabeth.wilmer@oberlin.edu

URL: http://www.oberlin.edu/math/faculty/wilmer.html

Contents

Preface xi

Overview xii

For the Reader xiii

For the Instructor xiv

For the Expert xvi

Acknowledgements xvii

Part I: Basic Methods and Examples 1

Chapter 1. Introduction to Finite Markov Chains 3

1.1. Finite Mar kov Chains 3

1.2. Random Mapping Representation 6

1.3. Irreducibility and Aperiodicity 8

1.4. Random Walks on Graphs 9

1.5. Stationary Distributions 10

1.6. Reversibility and Time Reversals 14

1.7. Classifying the States of a Markov Chain* 16

Exercises 18

Notes 20

Chapter 2. Classical (and Useful) Markov Chains 21

2.1. Gambler’s Ruin 21

2.2. Coupon Collecting 22

2.3. The Hypercube and the Ehrenfest Urn Model 23

2.4. The P´olya Urn Model 25

2.5. Birth-and-Death Chains 26

2.6. Random Walks on Groups 27

2.7. Random Walks on Z and Reﬂection Principles 30

Exercises 34

Notes 35

Chapter 3. Markov Chain Monte Carlo: Metropolis and Glauber Chains 37

3.1. Introduction 37

3.2. Metropolis Chains 37

3.3. Glauber Dynamics 40

Exercises 44

Notes 44

Chapter 4. Introduction to Markov Chain Mixing 47

4.1. Total Variation Distance 47

vi CONTENTS

4.2. Coupling and Total Variation Distance 49

4.3. The Convergence Theorem 52

4.4. Standardizing Distance from Stationar ity 53

4.5. Mixing Time 55

4.6. Mixing and Time Reversal 55

4.7. Ergodic Theorem* 58

Exercises 59

Notes 60

Chapter 5. Coupling 63

5.1. Deﬁnition 63

5.2. Bounding Total Variation Distance 64

5.3. Examples 65

5.4. Grand Couplings 70

Exercises 73

Notes 74

Chapter 6. Strong Stationary Times 75

6.1. Top-to-Random Shuﬄe 75

6.2. Deﬁnitions 76

6.3. Achieving Equilibrium 77

6.4. Strong Stationary Times and Bo unding Distance 78

6.5. Examples 80

6.6. Stationary Times and Cesaro Mixing Time* 83

Exercises 84

Notes 85

Chapter 7. Lower B ounds on Mixing Times 87

7.1. Counting and Diameter Bounds 87

7.2. Bottleneck Ratio 88

7.3. Distinguishing Statistics 92

7.4. Examples 96

Exercises 98

Notes 98

Chapter 8. The Symmetric Group and Shuﬄing Cards 99

8.1. The Symmetric Group 99

8.2. Random Tra ns positions 101

8.3. Riﬄe Shuﬄes 106

Exercises 109

Notes 111

Chapter 9. Random Walks on Networks 115

9.1. Networks and Reversible Markov Chains 115

9.2. Harmonic Functions 116

9.3. Voltages and Current Flows 117

9.4. Eﬀective Resista nce 118

9.5. Escape Pro babilities on a Square 123

Exercises 124

Notes 125

CONTENTS vii

Chapter 10. Hitting Times 127

10.1. Deﬁnition 127

10.2. Random Targ e t Times 128

10.3. Commute Time 130

10.4. Hitting Times for the Torus 133

10.5. Bounding Mixing Times via Hitting Times 134

10.6. Mixing for the Walk on Two Glued Graphs 138

Exercises 139

Notes 141

Chapter 11. Cover Times 143

11.1. Cover Times 143

11.2. The Matthews Method 143

11.3. Applications of the Matthews Method 147

Exercises 151

Notes 152

Chapter 12. Eigenvalues 153

12.1. The Spectral Representation of a Reversible Transition Matrix 153

12.2. The Relaxation Time 154

12.3. Eigenvalues and Eigenfunctions of Some Simple Random Walks 156

12.4. Product Chains 160

12.5. An ℓ

Bound 163

12.6. Time Averages 165

Exercises 167

Notes 168

Part II: The Plot Thickens 169

Chapter 13. Eigenfunctions and Comparison of Chains 171

13.1. Bounds on Spectral Gap via Contractions 171

13.2. Wilson’s Method for Lower Bounds 172

13.3. The Dirichlet Form and the Bottleneck Ratio 175

13.4. Simple Comparison of Markov Chains 179

13.5. The Path Method 182

13.6. Expander Graphs* 185

Exercises 187

Notes 187

Chapter 14. The Transportation Metric and Path Coupling 189

14.1. The Transportation Metric 189

14.2. Path Coupling 191

14.3. Fast Mixing for Colorings 193

14.4. Approximate Counting 195

Exercises 198

Notes 199

Chapter 15. The Ising Model 201

15.1. Fast Mixing at High Temperature 201

15.2. The Complete Graph 203

剩余386页未读，继续阅读

Markov Chains and Monte–Carlo Simulation.pdf

Markov chains – are a fundamental class of stochastic models for sequences of non–independent random variables, i.e. of random variables possessing a specific dependency structure. – have numerous ...

Markov Chains and Stochastic Stability compiled ver

Haggstrom O. Finite Markov chains and algorithmic applications

Haggstrom O Finite Markov chains and algorithmic applications CUP 2002 125s）；随机过程

markov chains

马尔科夫链（Markov chains）是一种数学模型，它描述了在给定过去状态的情况下，未来状态的概率分布只与当前状态有关，与过去状态无关。马尔科夫链的本质在于其具有马尔科夫性质，即无记忆性。在马尔科夫链中，...

Let { Xn } n > o be a Markov chain . Which of the following are Markov chains ? 1. Xm + r for r ≥0. 2. X2m for m ≥0. 请用中文回答并解释上述问题

第一个问题中，{ Xm + r } r ≥0 不是一个马尔可夫链，因为在给定 Xm 的条件下，Xm + r 的条件分布与之前的状态 X0, X1, ..., Xm-1 有关，不满足马尔可夫性质。第二个问题中，{ X2m } m ≥0 是一个马尔可夫链，...

Customers arrive at a two-server station in accordance with a Poisson process having rate r. Upon arriving, they join a single queue. Whenever a server completes a service, the person first in line enters service. The service times of server A are exponential with rate u1, and the service times of server B are exponential with rate u2, where u1+u2>r. An arrival finding both servers free is equally likely to go to either one. Define an appropriate continuous-time Markov chain for this model and find the limiting probabilities.

好的，我们可以将这个问题模型化为一个连续时间马尔科夫链。在这个模型中，我们可以定义四个状态：A表示服务员A正在服务，B表示服务员B正在服务，C表示客户正在排队，D表示两个服务员都闲着。根据给定的条件，我们...

Customers arrive at a two-server station in accordance with a Poisson process having rate r. Upon arriving, they join a single queue. Whenever a server completes a service, the person first in line enters service. The service times of server A are exponential with rate x, and the service times of server B are exponential with rate y, where x+y>r. An arrival finding both servers free is equally likely to go to either one. Define an appropriate continuous-time Markov chain for this model and find the limiting probabilities.

好的，我们可以为这个模型定义一个连续时间马尔科夫链。我们设 $0,1,2$ 分别表示服务器 A，B，和队列中的状态。我们假设当前时刻有 $n$ 个人在队列中，那么系统的状态就是 $(i,n)$，其中 $i\in\{0,1,2\}$ 表示服务器...

LSTM-Markov

LSTM-Markov是什么？ LSTM-Markov是一种结合了LSTM和马尔可夫模型的混合模型，它可以用于序列数据的建模和预测。LSTM用于捕捉序列中的长期依赖关系，而马尔可夫模型则用于建模序列中的短期依赖关系。LSTM-Markov...

Markov Random Fields

Markov Random Fields (MRFs), also known as Markov networks, are probabilistic graphical models used to represent complex random systems. They are commonly used in computer vision, image processing, ...

Structured Relation Discovery using Generative Models

This can be achieved through various techniques, such as recurrent neural networks (RNNs), Markov chains, and probabilistic graphical models. These models are trained on a large corpus of text, and ...

code of zero-state Markov switching model

In this example, we first simulate some data where `y` is the response variable and `z` is the zero-state Markov switching variable. We then fit a zero-state Markov switching model using `msmFit()` ...

yqing77

粉丝: 4
资源: 19

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

Markov Chains and Mixing Times

Markov Chains and Monte–Carlo Simulation.pdf

Markov Chains and Stochastic Stability compiled ver

Haggstrom O. Finite Markov chains and algorithmic applications

markov chains

Let { Xn } n > o be a Markov chain . Which of the following are Markov chains ? 1. Xm + r for r ≥0. 2. X2m for m ≥0. 请用中文回答并解释上述问题

What is a Markov Chain?

Dynamic event-triggered control for discrete Markov jump systems

用mcmc方法生成markov链 的MATLAB代码

《Markov模型》教案

matlab的markov链模型

markov链是的遍历

分析双层Markov链表示的状态转移模型和由隐Markov模型表示的状态转移模型的优劣和区别

markov跳变系统难点

用mcmc的MH方法生成markov链的MATLAB代码

LSTM-Markov

Markov Random Fields

Structured Relation Discovery using Generative Models

code of zero-state Markov switching model

会员权益专享

最新资源

用mcmc方法生成markov链的MATLAB代码