有限馬可夫鏈的log-Sobolev常數 - 陳冠宇; CHEN GUAN-YU (My University, 2010)
在馬可夫鏈蒙地卡羅的理論中，一個特別選定的馬可夫鏈被用來代替其穩定分佈進行取樣。而取樣的方法就是不斷的模擬該馬可夫鏈直到其機率分佈已經足夠接近穩定分佈。至今，蒙地卡羅方法已經被廣泛地應用在其他科學領域，其中包含了統計物理學、資訊科學以及生物學。運用蒙地卡羅方法時，最直接的問題就是何時該停止馬可夫鏈的模擬。數學上，這個問題就是要找尋一個正確的停止時間使的停止時的機率分佈和穩定分佈的差異很小。 在度量馬可夫鏈機率分佈以及穩定分佈的機制中，最常被運用的是total variation、 separation、 entropy以及Lp-norm。Gross在1975提出的log-Sobolev不等式是到目前為止研究Entropy以及Lp-norm的收斂速度最有效率的方法之一。但是運用該方法會牽涉到log-Sobolev常數的計算，而該常數的計算至今仍是非常困難。這個計畫的目的包含兩個部分：其一是為了決定出所有三點馬可夫鏈的log-Sobolev常數，而另一方面是要運用L. Miclo在2005年針對log-Sobolev常數的研究結果，發展出一套準確計算一維度馬可夫鏈log-Sobolev常數的演算法。

In Markov chain Monte Carlo (MCMC, for short) theory, a particular Markov chain is run for a very long time, say T, until its distribution is close enough to the stationarity. In practice, one is interested in the time T to stop the simulation and choose a random sample, and T is closely related to the mixing time. The most widely used in measuring the convergence rate of the MCMC method includes the total variation, separation, entropy, and the Lp-norm. In recent years, for models of statistical mechanics and of theoretical computer science and many others, there has been a flourishing of new mathematical ideas to rigorously control the time T. Since L. Gross introduced the concept of the logarithmic Sobolev (log-Sobolev, for short) inequality in 1975, there have been many people engaged in applying it to mathematical and physical models. The log-Sobolev inequality is useful in bounded the Lp-mxing time but, however, the exact computation of the related constant, the log-Sobolev constant, is only available in very few simple examples, such as two-point Markov chains. One goal of this project is to determine at least the exact order of the log-Sobolev constants for all three-point Markov chains. According to the property of the minimizers for the spectral gap and the log-Sobolev constant developed by L. Miclo in 2005, we attempts to develop an algorithm to compute the exact log-Sobolev constant for one-dimensional Markov chains.
Logarithmic Sobolev Constant of Finite Markov Chains
Keywords: 馬可夫鏈; 厄任菲司特甕; Markov chains; Ehrenfest chains