Burnside過程的Mixing Time估計

Abstract

Mixing Time 是一個描述馬可夫鏈收歛到平衡狀態的重要量。已經有許多關於估計Mixing Time的方法，譬如Coupling與Hilbert空間中分析技巧的應用。過去十五年，L. Goldgerg與M. Jerrum兩位計算機專家提出一個重要的馬可夫過程，稱為Burnside過程，作為計算Polya cycle index polynomial的一個重要數值方法。特別的D. Aldous與P. Diaconis估計了Bose-Einstein這個特殊的Burnside過程的Mixing Time。本文探討更一般的Burnside過程及它的Mixing Time。

Mixing time is the crucial time for a Markov chain converging to its equilibrium. Several tools have been developed to analyze this important quantity, such as analytic techniques in Hilbert space, and coupling methodology. In the last decade, computer theorists Goldberg and Jerrum purposed a special Markov chain, called Burnside process which is an important probability model for counting Polya's cycle index polynomial. In particular, D. Aldous 2001 and P. Diaconis 2005 discuss the mixing time of Bose-Einstein Markov chain. However, we still know little about the Burnside process. Hence, in this article we want to discuss mixing times for general Burnside processes.