Full metadata record
DC FieldValueLanguage
dc.contributor.author陳冠宇en_US
dc.contributor.authorGuan-Yu Chenen_US
dc.contributor.author許元春en_US
dc.contributor.authorYuan-Chung Sheuen_US
dc.date.accessioned2014-12-12T02:52:09Z-
dc.date.available2014-12-12T02:52:09Z-
dc.date.issued2006en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT008922519en_US
dc.identifier.urihttp://hdl.handle.net/11536/78135-
dc.description.abstract一副撲克牌要洗牌幾次其機率分佈才會接近均勻分佈。數學上,這個問題是屬於有限馬可夫鏈收斂速度的計量分析。在其他的領域裡也有相似的問題,其中包含了統計物理學、計算機科學和生物學。在這篇論文裡,我們討論lP距離和超皺縮性之間的關係,並介紹兩個與收斂速度相關的常數-譜間隙和對數索柏列夫常數。 我們的目標是要準確地計算出對數索柏列夫常數,其中最主要的結果就是在循環體上簡單隨機運動的對數索柏列夫常數。另外,透過馬可夫鏈的崩塌,我們也得到兩種在直線上隨機運動的對數索柏列夫常數。最後,我們考慮狀態空間為三個點的馬可夫鏈並求得部分的對數索柏列夫常數。zh_TW
dc.description.abstractHow 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.en_US
dc.language.isoen_USen_US
dc.subject馬可夫鏈zh_TW
dc.subject混合時間zh_TW
dc.subject譜間隙zh_TW
dc.subject索柏列夫不等式zh_TW
dc.subject對數索柏列夫常數zh_TW
dc.subject彭加略不等式zh_TW
dc.subjectMarkov chainen_US
dc.subjectmixing timeen_US
dc.subjectspectral gapen_US
dc.subjectSobolev inequalityen_US
dc.subjectlogarithmic Sobolev constanten_US
dc.subjectPoincare inequalityen_US
dc.title有限馬可夫鏈的對數索柏列夫常數zh_TW
dc.titleThe logarithmic Sobolev constant on finite Markov chainsen_US
dc.typeThesisen_US
dc.contributor.department應用數學系所zh_TW
Appears in Collections:Thesis


Files in This Item:

  1. 251901.pdf