有限馬可夫鏈的對數索柏列夫常數

Abstract

一副撲克牌要洗牌幾次其機率分佈才會接近均勻分佈。數學上，這個問題是屬於有限馬可夫鏈收斂速度的計量分析。在其他的領域裡也有相似的問題，其中包含了統計物理學、計算機科學和生物學。在這篇論文裡，我們討論lP距離和超皺縮性之間的關係，並介紹兩個與收斂速度相關的常數－譜間隙和對數索柏列夫常數。

我們的目標是要準確地計算出對數索柏列夫常數，其中最主要的結果就是在循環體上簡單隨機運動的對數索柏列夫常數。另外，透過馬可夫鏈的崩塌，我們也得到兩種在直線上隨機運動的對數索柏列夫常數。最後，我們考慮狀態空間為三個點的馬可夫鏈並求得部分的對數索柏列夫常數。

How many times a deck of cards needed to be shuffled in order to get close to the uniform distribution. Mathematically, this question falls in the realm of the quantitative study of the convergence of finite Markov chains. Similar convergence rate questions for finite Markov chains are important in many fields including statistical physics, computer science, biology and more. In this dissertation, we discuss the relation between the lP-distance and the hypercontractivity. To bound the convergence rate, we introduced two well-known constants, the spectral gap and the logarithmic Sobolev constant.

Our goal is to compute the logarithmic Sobolev constant for nontrivial models. Diverse tricks in use include the comparison technique and the collapse of Markov chains. One of the main work concerns the simple random walk on the n cycle. For n even, the obtained logarithmic Sobolev constant is equal to half the spectral gap. For n odd, the ratio between the logarithmic Sobolev constant and the spectral gap is not uniform.

Ideally, if the collapse of a chain preserves the spectral gap and the original chain has the logarithmic Sobolev constant equal to a half of the spectral gap, then the logarithmic Sobolev constant of the collapsed chain is known and equal to half the spectral gap. We successfully apply this idea to collapsing even cycles to two different sticks. Throughout this thesis, examples are introduced to illustrate theoretical results. In the last section, we study some three-point Markov chains with introduced techniques.