可逆馬可夫過程的L2切割時間

Abstract

馬可夫過程的切割現象是一個劇烈的相變行為。隨著距離函數的不同，馬可夫過程所表現出的相變行為也會有很大的差異。以全變量（total variation）為例，如果K是有限馬可夫鏈的轉置矩陣、μ是初始分佈、π是穩定分佈，則該隨機過程的機率分佈與穩定分佈之間的全變量（亦即

μKm-π

TV）是一個隨著時間遞減的函數。所謂的全變量切割現象就是指該距離函數的劇烈相變：在一開始的某段時間內，全變量會維持在幾乎是最大值。接著該距離函數會在極短的時間內遞減的很小，最後指數地收斂至0。該距離函數產生劇烈相變的時間就是全變量的切割時間。綜觀馬可夫過程的計量分析，最令人驚訝的發現之一就是大多數的模型都有切割現象。 這個專題計畫考慮可逆馬可夫過程的L2切割。根據算子理論的結果，可逆馬可夫過程的機率分佈和穩定分佈之間的L2距離是可以表示成一個特徵值和特徵向量的函數。對於有限群上的馬可夫過程，我們大致上已經能夠掌握L2切割存在性的判定方法以及L2切割時間的計算方式。這個計畫的主要目的就是要落實這些方法，並運用已知的結果來推導一般性的理論，進而針對幾個較複雜的模型進行計算。

Markov processes that present a cutoff show a sharp phase transition. Such a phenomenon can appear in a very different way among different distances. In the case of total variation, if K is the transition matrix of a finite Markov chain with stationary distribution π and initial distribution μ, then the total variation

μKm-π

TV, as a function of time, is non-increasing. A total variation cutoff is such a phenomenon that the distance

μKm-π

TV holds at almost its maximum for a while, then goes down in a relatively short time to a small value and converges to 0 exponentially fast. One of the most striking observations in the quantitative study of Markov processes is that many models present such a phase transition. In this project, we shall focus on the L2 cutoff for reversible Markov processes. It is known that the L2 distance can be represented as a function of the spectral information (eigenvalues and eigenfunctions) using the spectral decomposition. At this moment, we are able to deal with the L2-cutoff for reversible random walks on finite groups. Our aim here is to generalize this criterion to any ergodic Markov process and apply theoretic results to some typical but nontrivial models.