Exponential bounds and stopping rules for MCMC and general Markov chains
Exponential bounds and stopping rules for MCMC and general Markov chains
复制标题
DOI：
10.1145/1190095.1190152
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
Ioannis Kontoyiannis;L. A. Lastras-Montaño;Sean P. Meyn
中科院分区：
文献类型：
--
作者：
Ioannis Kontoyiannis;L. A. Lastras-Montaño;Sean P. Meyn
我们开发明确的，一般的概率，经验样本平均值的马尔可夫链的函数在一般字母表将超过稳态平均值的函数由一个给定的量的范围。我们的界限结合了联合收割机简单的信息理论的想法，从优化技术和一些相当基本的工具，从分析。在一个方向，激励中心问题模拟，我们开发的一般类的“几何遍历”马尔可夫链的界限。这些界限采取了一种特别适合于模拟问题的形式，它们自然会导致一类新的采样标准。通过几个例子说明了这一点。在另一个方向，我们得到了一个新的约束的重要特殊类的Doeblin链，这个界是最佳的，在这个意义上说，在特殊情况下的独立和同分布的随机变量，它基本上减少到经典Hoeffding界。
We develop explicit, general bounds for the probability that the empirical sample averages of a function of a Markov chain on a general alphabet will exceed the steady-state mean of that function by a given amount. Our bounds combine simple information-theoretic ideas together with techniques from optimization and some fairly elementary tools from analysis. In one direction, motivated by central problems in simulation, we develop bounds for the general class of "geometrically ergodic" Markov chains. These bounds take a form that is particularly suited to simulation problems, and they naturally lead to a new class of sampling criteria. These are illustrated by several examples. In another direction, we obtain a new bound for the important special class of Doeblin chains; this bound is optimal, in the sense that in the special case of independent and identically distributed random variables it essentially reduces to the classical Hoeffding bound.