馬可夫鏈的熵收斂

Abstract

該專題計畫的研究主要有兩個方向。其中一個是一維有限圖上的特徵值，另一個是生死鏈的收斂時間。針對第一個研究方向，我們提出了一個演算法來估計每一個特徵值。該演算法具有指數型的收斂速度，且收斂率與有限圖的長度無關。因此，運用該演算法將所有的特徵值計算出來，所需的運算量大致上是有限圖長度的平方。另外，我們也推導出了一個譜間隙(最小非零特徵值)的理論下界。並證明了在某些例子上，該下界的某個常數倍同時也是譜間隙的上界。針對第二個研究方向，我們成功地推導出生死鏈的收斂時間。值得一題的是，收斂時間的序(order)是僅由生率與死率組成的公式。配合第一個方向的研究結果，我們可以準確地決定出該生死鏈是否具有相變現象(cutoff phenomenon)。

There are two goals in this grant. The first is to consider the spectrum of one-dimensional finite graphs with vertex set V. An iterative scheme is proposed to compute any eigenvalue with exponential convergence rate and independent of the size of V, say |V|. This allows us to determine the whole spectrum within order |V|^2 computations. As an application of the mathematical framework, we obtain a lower bound on the spectral gap, which is proved to be of the exact order on some examples. Secondly, we consider the total variation mixing time for birth and death chains. In continuous time case, we successfully bound the mixing time via a formula expressed by the birth and death rates. Combined with the result on the spectral gap, the formula provides a simple criterion on the determination of total variation cutoff. As a consequence of a comparison between the continuous and discrete time chains, we may extend the above results to lazy discrete time cases and obtain a precise connection on the cutoff time and window.