一維空間上馬可夫鏈的收斂門檻

Abstract

在馬可夫鏈蒙地卡羅的理論中，一個特別的馬可夫鏈被用來進行取樣，而取樣的方法就是不斷的模擬該馬可夫鏈直到其機率分佈已經足夠接近穩定分佈。蒙地卡羅方法被廣泛的應用在其他的科學領域，其中包含了統計物理學、資訊科學以及生物學。在運用蒙地卡羅方法時，最常碰到的問題就是何時該停止馬可夫鏈的模擬以及停止時的取樣其機率分佈是否適用。在數學上，這個問題就是要找尋一個正確的停止時間使的停止時的機率分佈和穩定分佈的差異很小。 在度量馬可夫鏈的機率分佈以及穩定分佈的機制中，最常被運用的是total variation、 separation、 entropy以及Lp-norm。在這個計畫裡，我們將著重在total variation以及L2距離的估計。Diaconis是第一個引進群表現論來研究L2距離的機率學家。他成功地運用這個方法計算出random transpositions的正確停止時間，以致於停止洗牌時一副牌排列組合的機率分佈接近均勻分佈。稍後，Chen和Saloff-Coste運用spectral theory推導出可逆馬可夫鏈L2收斂門檻時間的公式。這個計畫的目的就是希望簡化該公式在一維空間上馬可夫鏈的L2收斂時間。

In Markov chain Monte Carlo (MCMC for short) theory, a particular Makov chain is run for a very long time until its distribution is close enough to the equilibrium distribution. Such a method has wide applications in many other fields including computer science, statistic physics and biology. The common problem in using MCMC among these disciplines is when to stop the simulation and whether the samples at stop are ready for use. In mathematics, this falls to the problem of find the “right time” so that the distribution at stop is “close” enough to the equilibrium distribution. There have been many mechanics used to measure the difference between the distribution of a Markov chain and its stationarity. The most widely used include the total variation, separation distance, entropy, and the Lp-norm. In this project, we will consider mostly the L2-distance and spread to the total variation sometime. Diaconis is the pioneer who introduces the group representation theory to study random walks on finite groups. He successfully applies his method to find the stop time of random transposition card shuffling so that the card arrangements at stop are closed to uniform. Another criterion on the L2-mixing time of normal Markov chains has been developed by Chen and Saloff-Coste later using the spectral theory. We will apply such a method to birth and death chains or more generally to one-dimensional Markov processes. Our goal is to find a simple expression of the L2-threshold without too much spectral information, in particular the information of eigenfunctions.