1981年，Kemeny[4]考慮在連通圖G上做簡單隨機漫步，且有轉移機率矩陣P與平穩分佈π = (π_1,...,π_n)。Kemeny得到的第一個主要結果是:數值∑_(j=1)^n H_(ij)π_j與i無關，其中H_(ij)代表從點i出發第一次到點j的平均步數。這個數值在後來的文獻中被稱為Kemeny常數，並以K(P)表示。在[4]的第二個主要結果中，作者證明:可以透過選擇適當的g向量和β向量，經由n×n矩陣(I−P+gβ^T)^(−1)導出G的Kemeny常數。在本文中，我們首先提供這兩個結果更簡潔的證明。然後我們用這兩個結果來計算一些特殊圖的Kemeny常數，包括完全圖、完全二分圖、路徑圖和超立方體圖。;In [4] Kemeny consider a simple random walk on a connected graph G with transition probability matrix P and stationary distribution π = (π_1, . . . , π_n). The first key result of [4] is that Kemeny proved the value ∑_(j=1)^n H_(ij)π_j is independent of i, where H_(ij) is the mean hitting time to node j starting from i. This value was later called the Kemeny’s constant in the literature and denoted by K(P). The second key result of [4] is that Kemeny proved that K(P) can be derived via an n×n matrix matrix (I−P+gβ^T)^(−1) by choosing appropriate vectors g and β. In this thesis, first we give these two results a more condensed proof. We then use them to compute Kemeny’s constants of some special graphs, including complete graphs, complete bipartite graphs, paths and hypercubes.
