馬可夫鏈趨向穩定分佈時間之研究(I)

Abstract

離散型的馬可夫鏈(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現象。