馬可夫鏈上的覆蓋時間

Abstract

本文考慮的是在有限狀態空間Ι上、離散時間的馬可夫鏈。所謂「覆蓋時間」是指馬可夫鏈經過Ι中每一個狀態所需的最小時間。我們概略敘述了平均覆蓋時間的上下界最近的發展，並且特別對一些簡單的圖上的隨機散步導出其平均覆蓋時間的確切公式。

We consider a discrete-time Markov Chain X, taking values in a finite state space I. The cover time C is the minimal time when the Markov chain X visits every state in I. We survey the recent development for bounds of the mean cover times of random walks on some simple graphs.