標題: 馬可夫鏈趨向穩定分佈時間之研究(I)
Times to Equilibriums for Markov Chains(I)
作者: 許元春
SHEU YUAN-CHUNG
交通大學應用數學系
關鍵字: 馬可夫鏈;穩定分布;趨向時間;Polya’s 理論;Burnside 過程;cut-off現象;Random Inversion
公開日期: 2005
摘要: 離散型的馬可夫鏈(Markov Chain)是最簡單也是最基本的一種隨機過程。它有豐富的理論結果及廣泛的應用。特別的,當馬可夫鏈是Ergodic時,其分佈(distribution)會隨著時間趨向穩定分佈(Stationary Distribution or Equilibrium)。一個自然且熱門的研究主題是:趨向穩定分佈的速度有多快? 最近十年,D. Aldous, P. Diaconis 和L. Saloff-Coste等著名的機率學家建立重要的不等式 (如log-Sobolev, Nash, Poincare 等)和mixing time 的重要關聯。我們於2003年時很技巧性的計算出simple random walk在n-cycle(n偶數時)上的log-Sobolev constant。當n是奇數時,經過一年多的努力我們有一些猜想及部分結果,但還需要時間及突破性的方法去證明我們的猜想。 Polya』s Theory 是組合學裡關於counting 的重要理論。計算機科學家Jerrum證明估計cycle index 的值是NP-complete。Burnside process的真正意涵就是利用MCMC來估計cycle index的值。我們將結合分析的手法及coupling的機率技巧探討一般Burnside process趨向穩定分佈的速度問題。 Cut-off現象是馬可夫鏈趨向穩定分佈一個令人驚奇的重要現象。我們相信一些重要的馬可鏈都應該有這cut-off現象。可惜到現在為止,只有很少數的馬可夫鏈被證明去有cut-off現象。在本計劃裡我們也將同時探討random inversion 的cut-off現象。
官方說明文件#: NSC94-2115-M009-010
URI: http://hdl.handle.net/11536/90300
https://www.grb.gov.tw/search/planDetail?id=1093400&docId=205895
Appears in Collections:Research Plans


Files in This Item:

  1. 942115M009010.PDF