馬可夫鏈的熵收斂

Abstract

馬可夫鏈蒙地卡羅方法(MCMC method)是最常被用來模擬機率分佈的方法之一。舉例來說，一個被觀察到的自然現象有很多種不確定的狀態，每個狀態都有其對應之發生機率。經量化後，該現象的狀態平均值是我們有興趣的問題之一。然而，因為狀態空間過於龐大，直接計算平均值是不可行的。根據蒙地卡羅方法的理論，一個特選的馬可夫鏈被用來代替其穩定分佈進行取樣。而取樣的方法就是不斷的模擬該馬可夫鏈直到其機率分佈已經足夠接近穩定分佈。運用蒙地卡羅方法時，最直接的問題就是何時該停止馬可夫鏈的模擬。數學上，這個問題就是要找尋一個正確的停止時間使的停止時的機率分佈和穩定分佈的差異很小。 這個三年期計畫，目的是要解決一連串與馬可夫鏈密切相關的問題。其中包括了spectral gap、log-Sobolev constant、Lp-mixing time和entropy cutoff。最終的目標是要探討自然界中的cutoff現象。

The Markov chain Monte Carlo method (MCMC for short) is a strategy used in sampling probability distributions. In practice, one is interested in the expectation of a function f defined on a set S according to a probability π on S. Mostly, it is impossible to determine the mean value of a function with a direction computation because the state space S can be very large and the probability π might be available only up to proposition, while the normalizing constant is never computable at all. From the perspective of MCMC method, a Markov chain Xn with stationary distribution π is simulated and the value f(Xn) is considered as a representative for π(f). The qualitative analysis of Markov chain ensures that, under mild conditions, f(Xn) converges to π(f) (in any possible sense) as n tends to infinity. A natural question arises: When (a time T) to stop the simulation so that the value f(XT) is close to its limit? T is known as the mixing time for Xn and solving this issue falls on the quantitative analysis of Markov chains. In the three-year project, we plan to solve a series of problems related to the mixing time T, which include the spectral gap and the log-Sobolev constant, the sup-Lp-mixing time, the entropy cutoff and the cutoff for random graphs. Each of them has a close connection to the others and all of them are of special interests both in theory and in practice. In the long run, we plan to explore the cutoff phenomenon on any physical model.