# On cover times of Markov chains

Bruno Sericola

► To cite this version:

Bruno Sericola. On cover times of Markov chains. Inria Rennes - Bretagne Atlantique. 2022, pp.32. hal-03837323

HAL Id: hal-03837323

https://inria.hal.science/hal-03837323

Submitted on 2 Nov 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# On cover times of Markov chains

Bruno Sericola *

November 2, 2022

## Abstract

We consider the cover time of a discrete-time homogenous Markov chain, that is the time needed by the Markov chain to visit all its states. We analyze both the distribution and the moments of the cover time and we are interested in exact results instead of asymptotic values of the mean cover time which are generally considered in the literature. We first obtain several general results on the hitting time and the cover time of a subset of the state space both in terms of distribution and moments. These results are then applied to particular graphs namely the generalized cycle graph, the complete graph and the generalized path graph. They lead to recurrence or analytic relations for the distribution and the mean value of their cover times.

Keywords: Markov chain; Hitting time; Cover time; Cycle graph; Complete graph; Path graph.

## 1 Introduction

The cover time of a Markov chain is the time needed by the Markov chain to visit all its states. This random variable as well as the more classical hitting times or return times are quite important in many areas of distributed systems and networks. For instance, visiting all the nodes of such systems allows the user to collect information about the performance or the reliability of the system. These visits can be made using random walks which are a particular case of Markov chains since the transition probabilities from a given node are uniformly distributed among the number of its neighbours but they can also be made using general transition probability matrices. Obviously the visiting time of all the nodes is a critical performance measure. For instance, in the context of graph theory for social networks, a notion of centrality has been used to assess the relative importance of nodes in a given network topology and a novel form of centrality based on the second order moments of return times in random walks was proposed in [6].

Several papers have already been written on both the hitting time and cover time and most of these papers deal with the particular case of random walks and consider moreover only asymptotic values of the means of these random variables. Very interesting surveys on random walks on graphs are proposed in [7] and [1], while [8] additionally contains many applications in both computer science and networks. It is shown in [4] and [3] that the expected cover time in a random walk with $n$ states is at least $(1-o(1))n\ln(n)$ and at most $(4/27+o(1))n^3$. In the case of a regular graph, it is at most $2n^2$, see [4]. In [2] the authors consider an extension of the cover time called the marking time defined as follows. When the random walk reaches state $i$, a coin is flipped and with probability $p_i$ the state $i$ is marked. The marking time is then the time needed by the walk to mark all its states. They give general formulas for the expected marking time of a random walk and provide asymptotics when the $p_i$'s are small. In [5], the authors first prove that for any transition probability matrix, both the expected hitting time and the expected cover time of the path graph is $\Omega(n^2)$. They also prove that for some particular Markov chains called degree-biased random walks, the expected hitting time is $O(n^2)$ and the expected cover time is $O(n^2 \ln(n))$.

In this paper, we consider both the distribution and the moments of the cover time of a discrete-time homogeneous Markov chain and we are interested in exact results instead of asymptotic values of the mean

<footnote>*Bruno Sericola is with Inria, Univ. Rennes, CNRS, IRISA</footnote>
cover time which are generally considered in the literature. In section 2, we analyze the hitting time and the cover time of a subset of the state space both in terms of distribution and moments. We then apply these results to several particular graphs. In section 3, we consider the generalized cycle graph and we provide an analytic expression of the mean hitting time. When the transition probabilities are identical from each state, we provide simple algorithms based on recursive expressions to compute the mean cover time as well as its distribution. Section 4 is devoted to the analysis of the cover time of the random walk on the complete graph, with and without self-loops. In both cases, we give analytic expressions for the cover time distribution and for its mean value. In section 5, we deal with the case of the path graph with general transition probability matrix. We provide an explicit expression of the mean cover time while its distribution is obtained using a simple recurrence relation. Section 6 concludes the paper.

## 2 Basic results

Consider a homogeneous discrete-time Markov chain $X = \{X_n, n \in \mathbb{N}\}$ over a finite state space $S$. We denote by $P$ the transition probability matrix of $X$. We suppose that $X$ is irreducible and, for every $j \in S$, we define the hitting time $T_{\{j\}}$ of state $j$ as the first instant at which state $j$ is reached by the Markov chain $X$, i.e.

$$T_{\{j\}} = \inf\{n \ge 0 \mid X_n = j\}.$$

The irreducibility of $X$ implies that, for every $j \in S$, $T_{\{j\}}$ is finite almost surely. Let $A$ be a non empty subset of states of $S$. We denote by $C_A$ the cover time of subset $A$, defined by the time needed to reach all the states of $A$, i.e.

$$C_A = \inf\{n \ge 0 \mid A \subseteq \{X_0, \dots, X_n\}\}.$$

The cover time of the Markov chain $X$, which is the time needed to reach all the states of $S$, is simply denoted by $C$ and is given by $C = C_S$. We introduce the random variable $T_A$ representing the hitting time of subset $A$, i.e.

$$T_A = \inf\{n \ge 0 \mid X_n \in A\}.$$

The complementary subset of $A$ in $S$, $S \setminus A$, is denoted simply by $A^c$. The partition $\{A, A^c\}$ of $S$ induces a decomposition of $P$ into four submatrices as

$$P = \begin{pmatrix} P_A & P_{A,A^c} \\ P_{A^c,A} & P_{A^c} \end{pmatrix},$$

where matrix $P_A$ (resp. $P_{A^c}$) contains the transition probabilities between states of $A$ (resp. $A^c$) and matrix $P_{A,A^c}$ (resp. $P_{A^c,A}$) contains the transition probabilities from states of $A$ (resp. $A^c$) to states of $A^c$ (resp. $A$). We also denote by $\mathbb{1}$ the column vector with all its entries equal to 1, its dimension being specified by the context. With these notations, we have, for all $i \in A^c$, $j \in A$ and $\ell \ge 1$, see for instance [10],

$$\mathbb{P}\{T_A = \ell, X_{T_A} = j \mid X_0 = i\} = (P_{A^c}^{\ell-1} P_{A^c,A})_{i,j}. \qquad (1)$$

Summing (1) over all $j \in A$, we obtain

$$\mathbb{P}\{T_A = \ell \mid X_0 = i\} = (P_{A^c}^{\ell-1} P_{A^c,A} \mathbb{1})_i. \qquad (2)$$

Summing (1) over all $\ell \ge 1$, we obtain

$$\mathbb{P}\{X_{T_A} = j \mid X_0 = i\} = \sum_{\ell=1}^{\infty} (P_{A^c}^{\ell-1} P_{A^c,A})_{i,j} = ((I - P_{A^c})^{-1} P_{A^c,A})_{i,j}. \qquad (3)$$

Since $(I - P_{A^c})^{-1} P_{A^c,A} \mathbb{1} = \mathbb{1}$, we have, from (2),

$$\mathbb{E}(T_A | X_0 = i) = \sum_{\ell=1}^{\infty} \ell (P_{A^c}^{\ell-1} P_{A^c,A} \mathbb{1})_i = ((I - P_{A^c})^{-1} \mathbb{1})_i, \qquad (4)$$
$$ \mathbb{E}(T_A^2 | X_0 = i) = \sum_{\ell=1}^{\infty} \ell^2 (P_{A^c}^{\ell-1} P_{A^c, A} \mathbf{1})_i = ((I + P_A)(I - P_{A^c})^{-2} \mathbf{1})_i \quad (5) $$

and from (1),

$$ \mathbb{E}(T_A 1_{\{X_{T_A}=j\}} | X_0 = i) = \sum_{\ell=1}^{\infty} \ell (P_{A^c}^{\ell-1} P_{A^c, A})_{i,j} = ((I - P_{A^c})^{-2} P_{A^c, A})_{i,j}. \quad (6) $$

Using these results, the following theorem gives a recursive expression of the distribution of $C_A$. For any event $u$ and for any random variable $U$, we introduce the notation $\mathbb{P}_i\{u\} = \mathbb{P}\{u | X_0 = i\}$ and $\mathbb{E}_i(U) = \mathbb{E}(U | X_0 = i)$. Note that, for every $j \in S$, we have $C_{\{j\}} = T_{\{j\}}$. Moreover, for every $k \ge 0$ and for every $i \in A$, with $|A| \ge 2$, we have, by definition of $C_A$,

$$ \mathbb{P}_i\{C_A = k\} = \mathbb{P}_i\{C_{A\setminus\{i\}} = k\}. $$

We thus only need to consider the case where the initial state belongs to the subset $A^c$. If $\alpha$ denotes the initial distribution of $X$, we get

$$ \mathbb{P}\{C_A = k\} = \sum_{i \in S} \alpha_i \mathbb{P}_i\{C_A = k\} = \sum_{i \in A} \alpha_i \mathbb{P}_i\{C_{A\setminus\{i\}} = k\} + \sum_{i \in A^c} \alpha_i \mathbb{P}_i\{C_A = k\}. $$

The cover time $C$ of the Markov chain is then given by

$$ \mathbb{P}\{C = k\} = \sum_{i \in S} \alpha_i \mathbb{P}_i\{C = k\} = \sum_{i \in S} \alpha_i \mathbb{P}_i\{C_{S\setminus\{i\}} = k\}. $$

**Theorem 1** For every $A \subset S$ such that $|A| \ge 2$, $i \in A^c$ and $k \ge 0$, we have

$$ \mathbb{P}_i\{C_A = k\} = \begin{cases} 0 & \text{if } 0 \le k < |A| \\ \sum_{h=1}^{k-|A|+1} \sum_{j \in A} (P_{A^c}^{h-1} P_{A^c, A})_{i,j} \mathbb{P}_j\{C_{A\setminus\{j\}} = k-h\} & \text{if } k \ge |A|. \end{cases} \quad (7) $$

**Proof.** Since $i \in A^c$, the time needed to reach all the states of $A$ from state $i$ is at least equal to $|A|$, so we have $\mathbb{P}_i\{C_A = k\} = 0$ for $k < |A|$. For every $i \in A^c$ and $k \ge |A|$, we have, conditioning on the values of $T_A$ and $X_{T_A}$,

$$ \begin{align*} \mathbb{P}_i\{C_A = k\} &= \sum_{h=1}^{k} \sum_{j \in A} \mathbb{P}_i\{C_A = k \mid T_A = h, X_{T_A} = j\} \mathbb{P}_i\{T_A = h, X_{T_A} = j\} \\ &= \sum_{h=1}^{k} \sum_{j \in A} \mathbb{P}_i\{C_A = k \mid T_A = h, X_{T_A} = j\} (P_{A^c}^{h-1} P_{A^c, A})_{i,j} \quad \text{using (1)} \\ &= \sum_{h=1}^{k} \sum_{j \in A} \mathbb{P}_j\{C_{A\setminus\{j\}} = k-h\} (P_{A^c}^{h-1} P_{A^c, A})_{i,j} \\ &= \sum_{h=1}^{k-|A|+1} \sum_{j \in A} \mathbb{P}_j\{C_{A\setminus\{j\}} = k-h\} (P_{A^c}^{h-1} P_{A^c, A})_{i,j}, \end{align*} $$

where the third equality uses the Markov and the homogeneity properties of $X$.
For every $\ell \ge 1$, the $\ell$-th order moment of the cover time of subset A starting from state $i$ is given by the following corollary.

**Corollary 2** For every $A \subset S$ such that $|A| \ge 2$, $\ell \ge 1$ and $i \in A^c$, we have

$$ \mathbb{E}_i(C_A^\ell) = \mathbb{E}_i(T_A^\ell) + \sum_{j \in A} \sum_{m=1}^{\ell} \binom{\ell}{m} \mathbb{E}_j(C_{A\setminus\{j\}}^m) \mathbb{E}_i(T_A^{\ell-m} 1_{\{X_{T_A}=j\}}). $$

**Proof.** From Theorem 1, we get for $\ell \ge 1$ and $i \in A^c$

$$ \begin{aligned} \mathbb{E}_i(C_A^\ell) &= \sum_{k=|A|}^{\infty} k^\ell \mathbb{P}_i\{C_A = k\} \\ &= \sum_{k=|A|}^{\infty} k^\ell \sum_{h=1}^{k-|A|+1} \sum_{j \in A} \mathbb{P}_j\{C_{A\setminus\{j\}} = k-h\} (P_{A^c}^{h-1} P_{A^c,A})_{i,j}. \end{aligned} $$

Exchanging the order of summations leads to

$$ \begin{aligned} \mathbb{E}_i(C_A^\ell) &= \sum_{j \in A} \sum_{h=1}^{\infty} \sum_{k=h+|A|-1}^{\infty} k^\ell \mathbb{P}_j\{C_{A\setminus\{j\}} = k-h\} (P_{A^c}^{h-1} P_{A^c,A})_{i,j} \\ &= \sum_{j \in A} \sum_{h=1}^{\infty} \sum_{k=|A|-1}^{\infty} (k+h)^\ell \mathbb{P}_j\{C_{A\setminus\{j\}} = k\} (P_{A^c}^{h-1} P_{A^c,A})_{i,j}. \end{aligned} $$

Developing the term $(k+h)^\ell$ gives

$$ \begin{aligned} \mathbb{E}_i(C_A^\ell) &= \sum_{j \in A} \sum_{h=1}^{\infty} \sum_{k=|A|-1}^{\infty} \sum_{m=0}^{\ell} \binom{\ell}{m} k^m h^{\ell-m} \mathbb{P}_j\{C_{A\setminus\{j\}} = k\} (P_{A^c}^{h-1} P_{A^c,A})_{i,j} \\ &= \sum_{j \in A} \sum_{h=1}^{\infty} \sum_{m=0}^{\ell} \binom{\ell}{m} \mathbb{E}_j(C_{A\setminus\{j\}}^m) h^{\ell-m} (P_{A^c}^{h-1} P_{A^c,A})_{i,j} \\ &= \sum_{j \in A} \sum_{m=0}^{\ell} \binom{\ell}{m} \mathbb{E}_j(C_{A\setminus\{j\}}^m) \sum_{h=1}^{\infty} h^{\ell-m} (P_{A^c}^{h-1} P_{A^c,A})_{i,j} \\ &= \sum_{j \in A} \sum_{m=0}^{\ell} \binom{\ell}{m} \mathbb{E}_j(C_{A\setminus\{j\}}^m) \mathbb{E}_i(T_A^{\ell-m} 1_{\{X_{T_A}=j\}}), \end{aligned} $$

where this last equality follows from relations (1) and (6). Extracting the term $m=0$ leads to

$$ \mathbb{E}_i(C_A^\ell) = \mathbb{E}_i(T_A^\ell) + \sum_{j \in A} \sum_{m=1}^{\ell} \binom{\ell}{m} \mathbb{E}_j(C_{A\setminus\{j\}}^m) \mathbb{E}_i(T_A^{\ell-m} 1_{\{X_{T_A}=j\}}), $$

which completes the proof.

Taking $\ell = 1$ in Corollary 2, we get, using (3) and (4), the mean cover time of subset A, i.e.

$$ \mathbb{E}_i(C_A) = ((I - P_{A^c})^{-1} 1)_i + \sum_{j \in A} ((I - P_{A^c})^{-1} P_{A^c,A})_{i,j} \mathbb{E}_j(C_{A\setminus\{j\}}). \quad (8) $$
Taking $\ell = 2$ in Corollary 2, we get, using (3), (5) and (6), the second moment of the cover time of subset A, i.e.

$$ \mathbb{E}_i(C_A^2) = ((I + P_{A^c})(I - P_{A^c})^{-2}1)_i + 2 \sum_{j \in A} \mathbb{E}_j(C_{A \setminus \{j\}}) ((I - P_{A^c})^{-2}P_{A^c,A})_{i,j} \\ + \sum_{j \in A} \mathbb{E}_j(C_{A \setminus \{j\}}^2) ((I - P_{A^c})^{-1}P_{A^c,A})_{i,j}. \qquad (9) $$

It is easily checked that, in practice, the direct use of Theorem 1 and Corollary 2 leads to algorithms having an exponential complexity $O(2^n)$ for a general n-states Markov chain, i.e. when $|S| = n$. That is why in the following sections, we show how to apply these results to particular graphs of Markov chains.

# 3 The generalized n-cycle graph

We consider in this section a Markov chain on the state space $S = \{0, 1, \dots, n-1\}$, $n \ge 2$, with transition probability matrix P. Its non zero transition probabilities are given by

$$ \left\{ \begin{array}{rcll} P_{n-1,0} = p_{n-1}, & P_{i,i+1} = p_i & \text{for } i = 0, \dots, n-2 \\ P_{0,n-1} = q_0, & P_{i,i-1} = q_i & \text{for } i = 1, \dots, n-1 \\ P_{i,i} = r_i & & \text{for } i = 0, \dots, n-1, \end{array} \right. $$

where $p_i, q_i \in [0, 1]$, $r_i \in [0, 1)$ with $p_i + q_i + r_i = 1$, for $i = 0, \dots, n-1$. We call the graph of this Markov chain the generalized n-cycle graph because for $p_i = q_i = 1/2$ and $r_i = 0$, we obtain the well-known random walk called the n-cycle graph without loops and for $p_i = q_i = r_i = 1/3$, we obtain the well-known random walk called the n-cycle graph with loops. In order to simplify the writing, we introduce the notation $\theta_i = q_i/p_i$ when $p_i \neq 0$.

## 3.1 Mean cover time of the generalized n-cycle graph

We consider in this subsection the mean hitting time and mean cover time of the subset of states $\{i + 1, \dots, n - 1\}$ of the generalized n-cycle graph when the initial state is state i, for all $i = 0, \dots, n - 2$.

**Theorem 3** For every $i = 0, \dots, n-2$, if $p_\ell \neq 0$ for $\ell = 0, \dots, i$, we have

$$ \mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = \sum_{k=0}^{i} \frac{1}{p_k} \left[ \prod_{m=k+1}^{i} \theta_m - \left( \sum_{\ell=k}^{i} \prod_{m=k+1}^{\ell} \theta_m \right) \frac{\prod_{m=0}^{i} \theta_m}{1 + \sum_{\ell=0}^{i} \prod_{m=0}^{\ell} \theta_m} \right]. \qquad (10) $$

**Proof.** From relation (4), we have, for every $i = 0, \dots, n-2$,

$$ \mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = ((I - P_{\{0, \dots, i\}})^{-1}1)_i. $$

The column vector $v = (v_0, \dots, v_i)$ defined by $v = (I - P_{\{0, \dots, i\}})^{-1}1$ is the unique solution to the linear system

$$ (I - P_{\{0, \dots, i\}})v = 1 $$

and we are looking for an expression of $v_i = \mathbb{E}_i(T_{\{i+1, \dots, n-1\}})$. This linear system can be written as

$$ \left\{ \begin{array}{rcll} (1 - r_0)v_0 - p_0v_1 & = & 1 & \\ -q_\ell v_{\ell-1} + (1 - r_\ell)v_\ell - p_\ell v_{\ell+1} & = & 1, & \text{for } \ell = 1, \dots, i-1 \\ -q_i v_{i-1} + (1 - r_i)v_i & = & 1. & \end{array} \right. \qquad (11) $$
We suppose that $p_\ell \neq 0$, for $\ell = 0, \dots, i$. Defining $v_{-1} = v_{i+1} = 0$ and $z_\ell = v_\ell - v_{\ell+1}$ and observing that $1 - r_\ell = p_\ell + q_\ell$, we get, for $\ell = 0, \dots, i$,

$$z_{\ell} = \frac{1}{p_{\ell}} + \frac{q_{\ell}}{p_{\ell}} z_{\ell-1},$$

which leads, since $z_{-1} = -v_0$ and $\theta_\ell = q_\ell/p_\ell$, to

$$z_{\ell} = \sum_{k=0}^{\ell} \frac{1}{p_k} \prod_{m=k+1}^{\ell} \theta_m - v_0 \prod_{m=0}^{\ell} \theta_m. \qquad (12)$$

Summing relation (12) for $\ell = 0$ to $i$, we obtain, since $v_{i+1} = 0$,

$$\sum_{\ell=0}^{i} z_i = v_0 = \frac{\sum_{\ell=0}^{i} \sum_{k=0}^{\ell} \frac{1}{p_k} \prod_{m=k+1}^{\ell} \theta_m}{1 + \sum_{\ell=0}^{i} \prod_{m=0}^{\ell} \theta_m}.$$

Replacing $v_0$ by its value in relation (12) in which we set $\ell = i$, we get

$$v_i = z_i = \sum_{k=0}^{i} \frac{1}{p_k} \prod_{m=k+1}^{i} \theta_m - \left( \sum_{\ell=0}^{i} \sum_{k=0}^{\ell} \frac{1}{p_k} \prod_{m=k+1}^{\ell} \theta_m \right) \left( \frac{\prod_{m=0}^{i} \theta_m}{1 + \sum_{\ell=0}^{i} \prod_{m=0}^{\ell} \theta_m} \right) \\ = \sum_{k=0}^{i} \frac{1}{p_k} \left[ \prod_{m=k+1}^{i} \theta_m - \left( \sum_{\ell=k}^{i} \prod_{m=k+1}^{\ell} \theta_m \right) \left( \frac{\prod_{m=0}^{i} \theta_m}{1 + \sum_{\ell=0}^{i} \prod_{m=0}^{\ell} \theta_m} \right) \right],$$

which completes the proof.

<figure><img src="image_2.png" /></figure>

This relation leads to the following particular results for all $i = 0, \dots, n-2$.

* If $q_i = 0$, which means that $\theta_i = 0$, we get as expected

$$\mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = 1/p_i.$$

* If $p_\ell = 0$, for all $\ell = 0, \dots, i$ then we have $1 - r_\ell = q_\ell$ and the linear system (11) writes $v_0 = 1/q_0$ and $v_\ell - v_{\ell-1} = 1/q_\ell$, which leads as expected to

$$\mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = \sum_{\ell=0}^{i} \frac{1}{q_\ell}.$$

* If $q_\ell/p_\ell = \theta$ with $p_\ell \neq 0$, for all $\ell = 0, \dots, i$, then we have $\theta_\ell = \theta$, for all $\ell = 0, \dots, i$ and we obtain

$$\mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = \begin{cases} \sum_{k=0}^{i} \frac{1}{p_k} \left( \frac{\theta^{i-k} - \theta^{i+1}}{1 - \theta^{i+2}} \right) & \text{if } \theta \neq 1 \\ \frac{1}{i+2} \sum_{k=0}^{i} \frac{k+1}{p_k} & \text{if } \theta = 1. \end{cases}$$
• If $p_{\ell} = p \neq 0$ and $q_{\ell} = q$, for all $\ell = 0, \dots, i$, then we have $\theta_{\ell} = \theta = q/p$, for all $\ell = 0, \dots, i$ and we obtain

$$ \mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = \begin{cases} \frac{1}{p} \left( \frac{1}{1-\theta} - \frac{(i+2)\theta^{i+1}}{1-\theta^{i+2}} \right) & \text{if } \theta \neq 1 \\ \frac{i+1}{2p} & \text{if } \theta = 1. \end{cases} $$

All the other particular cases can be easily obtained from the linear system (11).

In order to obtain the mean cover time of subset $\{i+1, \dots, n-1\}$ when the initial state is state $i$, we need the following lemma. For every $i=0, \dots, n-2$, we introduce the matrix $W^{(i)}$ defined by

$$ W^{(i)} = (I - P_{\{0, \dots, i\}})^{-1} P_{\{0, \dots, i\}, \{i+1, \dots, n-1\}}. $$

The rows of matrix $W^{(i)}$ are numbered from 0 to $i$ and its columns are numbered from $i+1$ to $n-1$. For $\ell = 0, \dots, i$ and $j = i+1, \dots, n-1$, we denote by $W_{\ell,j}^{(i)}$, the entry $(\ell, j)$ of $W^{(i)}$.

**Lemma 4** For every $i=0, \dots, n-2$, $\ell=0, \dots, i$ and $j=i+2, \dots, n-2$, we have $W_{\ell,j}^{(i)} = 0$ and, if $p_{\ell} \neq 0$ for $\ell=0, \dots, i$,

$$ W_{\ell, i+1}^{(i)} = 1 - \frac{\sum_{h=\ell}^{i} \prod_{m=0}^{h} \theta_m}{1 + \sum_{h=0}^{i} \prod_{m=0}^{h} \theta_m} \quad \text{and} \quad W_{\ell, n-1}^{(i)} = 1 - W_{\ell, i+1}^{(i)} = \frac{\sum_{h=\ell}^{i} \prod_{m=0}^{h} \theta_m}{1 + \sum_{h=0}^{i} \prod_{m=0}^{h} \theta_m}. $$

**Proof.** We introduce the notation $H^{(i)} = P_{\{0, \dots, i\}, \{i+1, \dots, n-1\}}$ with the same numbering of rows and columns as matrix $W^{(i)}$. The non zero entries of matrix $H^{(i)}$ are $H_{i, i+1}^{(i)} = p_i$ and $H_{0, n-1}^{(i)} = q_0$. It follows that the non zero entries of matrix $W^{(i)}$ are in its first and last columns. These entries are $W_{\ell, i+1}^{(i)}$ and $W_{\ell, n-1}^{(i)}$, for $\ell = 0, \dots, i$. Moreover since matrix $W^{(i)}$ is a (non square) stochastic matrix, we have $W_{\ell, i+1}^{(i)} + W_{\ell, n-1}^{(i)} = 1$. So it suffices to evaluate the entries $W_{\ell, i+1}^{(i)}$, for $\ell = 0, \dots, i$. Consider the column vector $v$ defined by $v = (v_0, \dots, v_i)$ with $v_{\ell} = W_{\ell, i+1}^{(i)}$. It is the unique solution to the system

$$ (I - P_{\{0, \dots, i\}})v = h, $$

where $h$ is the first column of matrix $H^{(i)}$, i.e. $h = (0, \dots, 0, p_i)$. This system can then be written as

$$ \left\{ \begin{array}{l} (1-r_0)v_0 - p_0v_1 = 0 \\ -q_{\ell}v_{\ell-1} + (1-r_{\ell})v_{\ell} - p_{\ell}v_{\ell+1} = 0 \quad \text{for } \ell = 1, \dots, i-1 \\ -q_i v_{i-1} + (1-r_i)v_i = p_i. \end{array} \right. \qquad (13) $$

We suppose that $p_{\ell} \neq 0$ for $\ell = 0, \dots, i$ and we recall that $\theta_{\ell} = q_{\ell}/p_{\ell}$. Defining $v_{-1} = v_{i+1} = 0$ and $z_{\ell} = v_{\ell} - v_{\ell+1}$ and observing that $1 - r_{\ell} = p_{\ell} + q_{\ell}$, we get $z_{\ell} = \theta_{\ell}z_{\ell-1}$, for $\ell = 0, \dots, i-1$ and $z_i = \theta_i z_{i-1} + 1$. Since $v_{-1} = 0$ which gives $z_{-1} = -v_0$, this leads to

$$ \left\{ \begin{array}{l} z_{\ell} = -v_0 \prod_{m=0}^{\ell} \theta_m, \quad \text{for } \ell = 0, \dots, i-1 \\ z_i = 1 - v_0 \prod_{m=0}^{i} \theta_m. \end{array} \right. $$
Summing these relations from 0 to i, we obtain, since $v_{i+1} = 0$,

$$ \sum_{h=0}^{i} z_h = v_0 = \frac{1}{1 + \sum_{h=0}^{i} \prod_{m=0}^{h} \theta_m} $$

In the same way, we have, for $\ell = 0, \dots, i$,

$$ \sum_{h=\ell}^{i} z_h = v_\ell = 1 - \frac{\sum_{h=\ell}^{i} \prod_{m=0}^{h} \theta_m}{1 + \sum_{h=0}^{i} \prod_{m=0}^{h} \theta_m}, $$

which completes the proof.

<figure><img src="image_3.png" /></figure>

Observe that if $p_i = 0$ then the linear system (13) simply gives $v_0 = \dots = v_i = 0$ which means that $W_{\ell, i+1}^{(i)} = 0$ and $W_{\ell, n-1}^{(i)} = 1$, for all $\ell = 0, \dots, i$.

Dealing with cover times when the $p_i$ and the $q_i$ are as general as possible is very tricky due to the complex expression of $\mathbb{E}_i(T_{\{i+1, \dots, n-1\}})$ in Theorem 3. This point is thus postponed to further research.

In the following theorem we consider the case where $p_\ell = p$ and $q_\ell = q$, for all $\ell = 0, \dots, n-1$. We then have $\theta_\ell = \theta = q/p$, for all $\ell = 0, \dots, n-1$. As we saw in the fourth previous item, we have in this case

$$ \mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = \frac{1}{p} \left( \frac{1}{1-\theta} - \frac{(i+2)\theta^{i+1}}{1-\theta^{i+2}} \right). $$

In order to simplify the notation, we define for every $i = 0, \dots, n-2$, the functions

$$ f_i(\theta) = \frac{1}{1-\theta} - \frac{(i+2)\theta^{i+1}}{1-\theta^{i+2}} = p \mathbb{E}_i(T_{\{i+1, \dots, n-1\}}). \quad (14) $$

In the same way, using Lemma 4 with $\ell = i$ and $\theta_m = \theta$, we obtain

$$ W_{i, i+1}^{(i)} = \begin{cases} \frac{1 - \theta^{i+1}}{1 - \theta^{i+2}} & \text{if } \theta \neq 1 \\ \frac{i+1}{i+2} & \text{if } \theta = 1 \quad \text{and} \quad W_{i, n-1}^{(i)} = 1 - W_{i, i+1}^{(i)}. \\ 0 & \text{if } p = 0 \end{cases} \quad (15) $$

We are now able to evaluate the mean cover time of subset $\{i+1, \dots, n-1\}$ when the initial state is state i.

**Theorem 5** For every $i = 0, \dots, n-2$, when $p_\ell = p$ and $q_\ell = q$, for all $\ell = 0, \dots, n-1$, we have

$$ \mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = \begin{cases} \frac{h_i(\theta)}{p} & \text{if } \theta \neq 1 \\ \frac{(n+i)(n-i-1)}{4p} & \text{if } \theta = 1 \\ \frac{n-1}{q} & \text{if } p=0. \end{cases} $$

where the functions $h_i$ are given recursively for $i = 0, \dots, n-2$, by $h_{n-1} = 0$ which is the null function and

$$ h_i(\theta) = f_i(\theta) + \frac{1 - \theta^{i+1}}{1 - \theta^{i+2}} h_{i+1}(\theta) + \theta^i \frac{1 - \theta}{1 - \theta^{i+2}} h_{i+1}(1/\theta). $$
**Proof.** We first suppose that $\theta \neq 1$. Using equation (8) and relations (14) and (15), we have, for $i = 0, \dots, n-2$ and by taking $A = \{i+1, \dots, n-1\}$,

$$
\begin{align*}
\mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) &= \mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) + \sum_{j=i+1}^{n-1} W_{i,j}^{(i)} \mathbb{E}_j(C_{\{i+1, \dots, n-1\} \setminus \{j\}}) \\
&= \mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) + W_{i,i+1}^{(i)} \mathbb{E}_{i+1}(C_{\{i+2, \dots, n-1\}}) + W_{i,n-1}^{(i)} \mathbb{E}_{n-1}(C_{\{i+1, \dots, n-2\}}) \\
&= \frac{f_i(\theta)}{p} + \frac{1 - \theta^{i+1}}{1 - \theta^{i+2}} \mathbb{E}_{i+1}(C_{\{i+2, \dots, n-1\}}) + \left(1 - \frac{1 - \theta^{i+1}}{1 - \theta^{i+2}}\right) \mathbb{E}_{n-1}(C_{\{i+1, \dots, n-2\}}).
\end{align*}
$$

For $i = 0, \dots, n-2$, we define $g_i(p, q) = \mathbb{E}_i(C_{\{i+1, \dots, n-1\}})$. By symmetry, it is easily checked that we have $\mathbb{E}_{n-1}(C_{\{i, \dots, n-2\}}) = g_i(q, p)$. It follows that

$$
g_i(p, q) = \frac{f_i(\theta)}{p} + \frac{1 - \theta^{i+1}}{1 - \theta^{i+2}} g_{i+1}(p, q) + \left(1 - \frac{1 - \theta^{i+1}}{1 - \theta^{i+2}}\right) g_{i+1}(q, p).
$$

Defining $h_i(p, q) = pg_i(p, q)$, we obtain $pg_{i+1}(q, p) = h_{i+1}(q, p)/\theta$ and thus

$$
h_i(p, q) = f_i(\theta) + \frac{1 - \theta^{i+1}}{1 - \theta^{i+2}} h_{i+1}(p, q) + \frac{\theta^i (1 - \theta)}{1 - \theta^{i+2}} h_{i+1}(q, p).
$$

Since $h_{n-2}(p, q) = pg_{n-2}(p, q) = p \mathbb{E}_{n-2}(C_{\{n-1\}}) = p \mathbb{E}_{n-2}(T_{\{n-1\}}) = f_{n-2}(\theta)$, we define $h_{n-1}(p, q) = 0$, for all $p, q$. This initial value of the recursion implies that the function $h_i(p, q)$ only depends on the fraction $\theta = q/p$. We thus redefine functions $h_i$ as $h_i(\theta) = h_i(p, q)$ and we have $h_i(1/\theta) = h_i(q, p)$. It follows that, for $i = 0, \dots, n-2$,

$$
h_i(\theta) = f_i(\theta) + \frac{1 - \theta^{i+1}}{1 - \theta^{i+2}} h_{i+1}(\theta) + \frac{\theta^i (1 - \theta)}{1 - \theta^{i+2}} h_{i+1}(1/\theta),
$$

with $h_{n-1} = 0$, the null function.

In the case where $\theta = 1$, i.e. when $p = q$, we have $\mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = (i+1)/2p$ and thus

$$
\mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = \frac{i+1}{2p} + W_{i,i+1}^{(i)} \mathbb{E}_{i+1}(C_{\{i+2, \dots, n-1\}}) + (1 - W_{i,i+1}^{(i)}) \mathbb{E}_{n-1}(C_{\{i+1, \dots, n-2\}}).
$$

Since $p=q$, we have by symmetry, $\mathbb{E}_{i+1}(C_{\{i+2, \dots, n-1\}}) = \mathbb{E}_{n-1}(C_{\{i+1, \dots, n-2\}})$, which leads to

$$
\mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = \frac{i+1}{2p} + \mathbb{E}_{i+1}(C_{\{i+2, \dots, n-1\}}),
$$

that is

$$
\mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = \frac{i+1}{2p} + \frac{i+2}{2p} + \dots + \frac{n-1}{2p} = \frac{(n+i)(n-i-1)}{4p}.
$$

If $p=0$ we easily get $\mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = \mathbb{E}_i(T_{i+1}) = (n-1)/q$, which completes the proof.

<figure><img src="image_4.png" /></figure>

**Corollary 6** For every $n \ge 2$, we have

$$
\mathbb{E}(C) = \mathbb{E}_0(C_{\{1, \dots, n-1\}}) =
\begin{cases}
\frac{h_0(\theta)}{p} & \text{if } \theta \neq 1 \\
\\
\frac{n(n-1)}{4p} & \text{if } \theta = 1 \\
\\
\frac{n-1}{q} & \text{if } p=0.
\end{cases}
$$
**Proof.** Again, by symmetry, we have for every $i = 0, \dots, n-1$, $\mathbb{E}(C) = \mathbb{E}_i(C_{S\setminus\{i\}})$. Taking $i = 0$ in Theorem 5, we get the result. ■

Note that when $\theta = 1$ with $p = q = 1/2$ (resp. with $p = q = 1/3$) we get the well-known result of the classical $n$-cycle graph without self-loops that is $\mathbb{E}(C) = n(n-1)/2$ (resp. with self-loops that is $\mathbb{E}(C) = 3n(n-1)/4$).

For $\theta \neq 1$, the algorithm to compute the mean cover time $\mathbb{E}(C)$ is described in Table 1.

**input :** $n \ge 2$, $p, q \in (0, 1)$ with $p+q \le 1$

**output :** $\mathbb{E}(C)$

$$\theta = q/p$$

$$h_{n-2}(\theta) = \frac{1}{1-\theta} - \frac{n\theta^{n-1}}{1-\theta^n}; h_{n-2}(1/\theta) = -\frac{\theta}{1-\theta} + \frac{n\theta}{1-\theta^n}$$

**for** $i = n-3$ **downto** 0 **do**

$$f_i(\theta) = \frac{1}{1-\theta} - \frac{(i+2)\theta^{i+1}}{1-\theta^{i+2}}; f_i(1/\theta) = -\frac{\theta}{1-\theta} + \frac{(i+2)\theta}{1-\theta^{i+2}}$$

$$h_i(\theta) = f_i(\theta) + \frac{1-\theta^{i+1}}{1-\theta^{i+2}}h_{i+1}(\theta) + \frac{\theta^i(1-\theta)}{1-\theta^{i+2}}h_{i+1}(1/\theta)$$

$$h_i(1/\theta) = f_i(1/\theta) + \frac{\theta(1-\theta^{i+1})}{1-\theta^{i+2}}h_{i+1}(1/\theta) + \frac{\theta(1-\theta)}{1-\theta^{i+2}}h_{i+1}(\theta)$$

**endfor**

$$\mathbb{E}(C) = h_0(\theta)/p$$

<caption>Table 1: Algorithm computing the mean cover time of the generalized $n$-cycle graph.</caption>

## 3.2 Cover time distribution of the generalized $n$-cycle graph

We consider first in this subsection the cover time distribution of the subset of states $\{i+1, \dots, n-1\}$ of the generalized $n$-cycle graph for which $p_\ell = p$ and $q_\ell = q$, for all $\ell = 0, \dots, n-1$, i.e. $\theta_\ell = \theta = q/p$, when the initial state is state $i$. Then by taking $i = 0$ we deduce, by symmetry, the cover time distribution for every initial distribution.

To simplify the writing, we introduce the matrix $(i+1) \times (n-i-1)$ matrix $H^{(i)}(h)$ defined for every $i = 0, \dots, n-2$ and $h \ge 0$, by

$$H^{(i)}(h) = P_{\{0, \dots, i\}}^{h} P_{\{0, \dots, i\}, \{i+1, \dots, n-1\}}$$

When $i = 0, \dots, n-3$, the only non zero entries of matrix $H^{(i)}(0) = P_{\{0, \dots, i\}, \{i+1, \dots, n-1\}}$ are $H_{i,i+1}^{(i)}(0) = p$ and $H_{0,n-1}^{(i)}(0) = q$. When $i = n-2$, the matrix $H^{(n-2)}(0) = P_{\{0, \dots, n-2\}, \{n-1\}}$ has a single column. Its non zero entries are $H_{0,n-1}^{(n-2)}(0) = q$ and $H_{n-2,n-1}^{(n-2)}(0) = p$.

It follows that matrix $H^{(i)}(h)$ has only 2 non-zero columns which are column $i+1$ and column $n-1$ and obviously a single one when $i = n-2$. For every $h \ge 0$ and $i = 0, \dots, n-2$, we denote column $i+1$ of $H^{(i)}(h)$ by $v^{(i)}(h) = (v_0^{(i)}(h), \dots, v_i^{(i)}(h))$ and column $n-1$ of $H^{(i)}(h)$ by $w^{(i)}(h) = (w_0^{(i)}(h), \dots, w_i^{(i)}(h))$. Their initial values are $v^{(i)}(0) = (0, \dots, 0, p)$ and $w^{(i)}(0) = (q, 0, \dots, 0)$.

Using these remarks and notations, we have from Theorem 1, by taking $A = \{i+1, \dots, n-1\}$, for every
i = 0, ..., n - 3 and k ≥ n - i - 1,

$$
\begin{align*}
\mathbb{P}_i\{C_{i+1, \dots, n-1} = k\} &= \sum_{h=1}^{k-n+i+2} \sum_{j=i+1}^{n-1} H_{i,j}^{(i)}(h-1)\mathbb{P}_j\{C_{i+1, \dots, n-1} \setminus \{j\} = k-h\} \\
&= \sum_{h=1}^{k-n+i+2} \left( H_{i,i+1}^{(i)}(h-1)\mathbb{P}_{i+1}\{C_{i+2, \dots, n-1} = k-h\} + H_{i,n-1}^{(i)}(h-1)\mathbb{P}_{n-1}\{C_{i+1, \dots, n-2} = k-h\} \right) \\
&= \sum_{h=1}^{k-n+i+2} \left( v_i^{(i)}(h-1)\mathbb{P}_{i+1}\{C_{i+2, \dots, n-1} = k-h\} + w_i^{(i)}(h-1)\mathbb{P}_{n-1}\{C_{i+1, \dots, n-2} = k-h\} \right) \\
&= \sum_{h=0}^{k-n+i+1} \left( v_i^{(i)}(h)\mathbb{P}_{i+1}\{C_{i+2, \dots, n-1} = k-h-1\} + w_i^{(i)}(h)\mathbb{P}_{n-1}\{C_{i+1, \dots, n-2} = k-h-1\} \right).
\end{align*}
$$

Let us now introduce the notation $f_i(p, q, k) = \mathbb{P}_i\{C_{i+1, \dots, n-1} = k\}$. Note that using the symmetry of the Markov chain, the cover time distribution of subset $\{i+1, \dots, n-2\}$ starting from state $n-1$ is equal to the cover time distribution of subset $\{i+2, \dots, n-1\}$ starting from state $i+1$ and interchanging the roles of $p$ and $q$, that is

$$
\mathbb{P}_{n-1}\{C_{i+1, \dots, n-2} = k - h - 1\} = f_{i+1}(q, p, k - h - 1).
$$

We thus have, for every $i = 0, \dots, n-3$ and $k \ge n-i-1$,

$$
f_i(p, q, k) = \sum_{h=0}^{k-n+i+1} \left( v_i^{(i)}(h) f_{i+1}(p, q, k-h-1) + w_i^{(i)}(h) f_{i+1}(q, p, k-h-1) \right). \quad (16)
$$

3.2.1 Computation of vectors $v_i^{(i)}(h)$ and $w_i^{(i)}(h)$

When $i = 0, \dots, n-3$, the column vector $v^{(i)}(h)$ (resp. $w^{(i)}(h)$) being the first (resp. the last) column of matrix $H^{(i)}(h)$, we have

$$
v^{(i)}(h) = P_{\{0, \dots, i\}}^{h} v^{(i)}(0) \text{ and } w^{(i)}(h) = P_{\{0, \dots, i\}}^{h} w^{(i)}(0),
$$

where we recall that $v^{(i)}(0) = (0, \dots, 0, p)$ and $w^{(i)}(0) = (q, 0, \dots, 0)$. We thus have

$$
v^{(i)}(h) = P_{\{0, \dots, i\}} v^{(i)}(h-1) \text{ and } w^{(i)}(h) = P_{\{0, \dots, i\}} w^{(i)}(h-1).
$$

When $i = n-2$, since matrix $H^{(n-2)}(h)$ is a column vector, we have $H^{(n-2)}(0) = v^{(n-2)}(0) + w^{(n-2)}(0)$ and thus $H^{(n-2)}(h) = v^{(n-2)}(h) + w^{(n-2)}(h)$. The algorithm to compute either $v_i^{(i)}(h)$ or $w_i^{(i)}(h)$ is the same. It is quite simple and shown in Table 2, where vector $x(p, q, \ell)$ can be either vector $v_i^{(i)}(\ell)$ or $w_i^{(i)}(\ell)$.

input : n ≥ 3, p, q ∈ (0, 1) with p + q ≤ 1, i = 1, ..., n − 2, h, x(p, q, 0) = (x₀(p, q, 0), ..., xᵢ(p, q, 0))

output : x(p, q, ℓ) = (x₀(p, q, ℓ), ..., xᵢ(p, q, ℓ)) for ℓ = 1, ..., h

r = 1 - (p + q)

for ℓ = 1 to h do

$$
x_0(p, q, \ell) = r x_0(p, q, \ell - 1) + p x_1(p, q, \ell - 1)
$$

for m = 1 to i - 1 do

$$
x_m(p, q, \ell) = q x_{m-1}(p, q, \ell-1) + r x_m(p, q, \ell-1) + p x_{m+1}(p, q, \ell-1)
$$

endfor

$$
x_i(\ell) = q x_{i-1}(p, q, \ell - 1) + r x_i(p, q, \ell - 1)
$$

endfor
Table 2: Algorithm computing the values $v_i^{(i)}(h)$ and $w_i^{(i)}(h)$. When $i = 1, \dots, n-3$, by taking $x(p, q, 0) = v_i^{(i)}(0)$ (resp. $x(p, q, 0) = w_i^{(i)}(0)$), the algorithm provides $v_i^{(i)}(h)$ (resp. $w_i^{(i)}(h)$), for $\ell = 1, \dots, h$. When $i = n-2$, by taking $x(p, q, 0) = v^{(n-2)}(0)+w^{(n-2)}(0)$, the algorithm provides $x(p, q, \ell) = v^{(n-2)}(\ell)+w^{(n-2)}(\ell)$, for $\ell = 1, \dots, h$.

Note that the case where $i = 0$, is not taken into account by the algorithm described in Table 2 because in this case we simply have $(P_{\{0\}})^h = r^h$, that is $v_0^{(0)}(h) = pr^h$ and $w_0^{(0)}(h) = qr^h$.

### 3.2.2 Computation of the cover time distribution of the generalized n-cycle graph

The computation of the cover time distribution is based on relation (16). Indeed, for every $k \ge 0$ it is given by

$$ \mathbb{P}\{C = k\} = f_0(p, q, k). $$

Observe that in relation (16), the values $v_i^{(i)}(h)$ and $w_i^{(i)}(h)$ obviously depend on $p$ and $q$ and since we need both $f_i(p, q, k)$ and $f_i(q, p, k)$, we must specify this dependence. Relation (16) becomes

$$ \left\{ \begin{aligned} f_i(p, q, k) &= \sum_{h=0}^{k-n+i+1} \left( v_i^{(i)}(p, q, h) f_{i+1}(p, q, k-h-1) + w_i^{(i)}(p, q, h) f_{i+1}(q, p, k-h-1) \right), \\ f_i(q, p, k) &= \sum_{h=0}^{k-n+i+1} \left( v_i^{(i)}(q, p, h) f_{i+1}(q, p, k-h-1) + w_i^{(i)}(q, p, h) f_{i+1}(p, q, k-h-1) \right). \end{aligned} \right. \quad (17) $$

In order to get $f_0(p, q, k)$, the starting point of relation (17) is the computation of $f_{n-2}(p, q, \ell)$ and $f_{n-2}(q, p, \ell)$. The value of $f_{n-2}(p, q, \ell)$ is given, using relation (2), by

$$ f_{n-2}(p, q, \ell) = \mathbb{P}_{n-2}\{C_{\{n-1\}} = \ell\} = \mathbb{P}_{n-2}\{T_{\{n-1\}} = \ell\} = \left( P_{\{0,...,n-2\}}^{\ell-1} P_{\{0,...,n-2\},\{n-1\}} \right)_{n-2}, $$

so $f_{n-2}(p, q, \ell)$ is provided by the algorithm of Table 2, by taking $i = n-2$ and $x(p, q, 0) = v^{(n-2)}(p, q, 0) + w^{(n-2)}(p, q, 0) = (q, 0, \dots, 0, p)$. In the same way, the value of $f_{n-2}(q, p, \ell)$ is provided by the algorithm of Table 2, by taking $i = n-2$ and $x(q, p, 0) = (p, 0, \dots, 0, q)$.

The following algorithm provides $\mathbb{P}\{C = k\} = f_0(p, q, k)$ for $k = n-1, \dots, K$. Observe that we have $\mathbb{P}\{C = k\} = 0$, for $k = 0, \dots, n-2$.

**input**: $n \ge 3$, $K \ge n-1$, $p, q \in (0, 1)$ with $p+q \le 1$

**output**: $f_0(p, q, k)$ for $k = n-1, \dots, K$

$r = 1 - (p+q)$

**for** $k = 1$ **to** $K-n+2$ **do**

Compute $f_{n-2}(p, q, k) = x_{n-2}(p, q, k)$ from algorithm of Table 2,

with $i = n-2$ and $x(p, q, 0) = (q, 0, \dots, 0, p)$

Compute $f_{n-2}(q, p, k) = x_{n-2}(q, p, k)$ from algorithm of Table 2,

with $i = n-2$ and $x(q, p, 0) = (p, 0, \dots, 0, q)$

**endfor**

**for** $i = n-3$ **downto** 0 **do**

**for** $h = 0$ **to** $K-n$ **do**

Compute $v_i^{(i)}(p, q, h) = x_i(p, q, h)$ from algorithm of Table 2, with $x(p, q, 0) = (0, \dots, 0, p)$

Compute $w_i^{(i)}(p, q, h) = x_i(p, q, h)$ from algorithm of Table 2, with $x(p, q, 0) = (q, 0, \dots, 0)$

Compute $v_i^{(i)}(q, p, k) = x_i(q, p, k)$ from algorithm of Table 2, with $x(q, p, 0) = (0, \dots, 0, q)$

Compute $w_i^{(i)}(q, p, h) = x_i(q, p, h)$ from algorithm of Table 2, with $x(q, p, 0) = (p, 0, \dots, 0)$

**endfor**

**for** $k = n-i-1$ **to** $K-i$ **do**
$$f_i(p, q, k) = \sum_{h=0}^{k-n+i+1} \left( v_i^{(i)}(p, q, h) f_{i+1}(p, q, k-h-1) + w_i^{(i)}(p, q, h) f_{i+1}(q, p, k-h-1) \right) \\ f_i(q, p, k) = \sum_{h=0}^{k-n+i+1} \left( v_i^{(i)}(q, p, h) f_{i+1}(q, p, k-h-1) + w_i^{(i)}(q, p, h) f_{i+1}(p, q, k-h-1) \right)$$

endfor
endfor

<caption>Table 3: Algorithm computing the distribution $\mathbb{P}\{C = k\} = f_0(p, q, k)$, for $k = n - 1, \dots, K$.</caption>

# 4 The complete graph

## 4.1 The complete graph with self-loops

A random walk on the complete graph with self-loops is a Markov chain on the state space $S = \{0, 1, \dots, n-1\}$, $n \ge 2$, with transition probability matrix $P$ given, for every $u, v \in S$, by $P_{u,v} = 1/n$.

### 4.1.1 Mean cover time of the complete graph with self-loops

By symmetry, we have for any initial distribution,

$$\mathbb{E}(C) = \mathbb{E}_i(C_{S\setminus\{i\}}) = \mathbb{E}_0(C_{\{1, \dots, n-1\}}).$$

For every $n \ge 1$, we denote by $h_n$ the harmonic sum, i.e.

$$h_n = \sum_{k=1}^{n} \frac{1}{k}.$$

**Theorem 7** For every $i = 0, \dots, n-2$, we have

$$\mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = \frac{n}{n - (i + 1)} \quad \text{and} \quad \mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = nh_{n-(i+1)}.$$

**Proof.** The matrix $P$ having all its entries equal to $1/n$, we have for every $i = 0, \dots, n-2$ and $u, v \in \{0, 1, \dots, i\}$,

$$(I - P_{\{0,1,\dots,i\}})_{u,v}^{-1} = \begin{cases} \frac{1}{n - (i + 1)} & \text{if } u \neq v \\ \frac{n - i}{n - (i + 1)} & \text{if } u = v. \end{cases}$$

We thus get from relation (4),

$$\mathbb{E}_i(T_{\{i+1, \dots, n-1\}}) = \left( (I - P_{\{0,1,\dots,i\}})^{-1} 1 \right)_i = \sum_{j=0}^{i} (I - P_{\{0,1,\dots,i\}})_{i,j}^{-1} = \frac{n}{n - (i + 1)}, \quad (18)$$

and, for every $j \in \{i+1, \dots, n-1\}$,

$$((I - P_{\{0,1,\dots,i\}})^{-1} P_{\{0,1,\dots,i\}, \{i+1,\dots,n-1\}})_{i,j} = \frac{1}{n - (i + 1)}.$$

Putting this result into equation (8), we obtain

$$\mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = \frac{n}{n - (i + 1)} + \frac{1}{n - (i + 1)} \sum_{j=i+1}^{n-1} \mathbb{E}_j(C_{\{i+1, \dots, n-1\} \setminus \{j\}}).$$
By symmetry all the terms in the sum have the same value, so we get

$$ \mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = \frac{n}{n-(i+1)} + \mathbb{E}_{i+1}(C_{\{i+2, \dots, n-1\}}). $$

From relation (18) with $i = n - 2$, we have

$$ \mathbb{E}_{n-2}(C_{\{n-1\}}) = \mathbb{E}_{n-2}(T_{\{n-1\}}) = n. $$

We then obtain recursively,

$$ \mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = n \sum_{\ell=i+1}^{n-1} \frac{n}{n-(i+1)} = nh_{n-(i+1)}, $$

which completes the proof.

Again, by symmetry, taking $i = 0$ in Theorem 7, we get

$$ \mathbb{E}(C) = nh_{n-1}. $$

### 4.1.2 Cover time distribution of the complete graph with self-loops

By symmetry, we also have for any initial distribution and for every $i \in S$,

$$ \mathbb{P}\{C = k\} = \mathbb{P}_i\{C_{S\setminus\{i\}} = k\} = \mathbb{P}_0\{C_{\{1, \dots, n-1\}} = k\}. $$

**Lemma 8** For every $i = 0, \dots, n-3$, we have

$$ \mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = \begin{cases} 0 & \text{if } 0 \le k < n-(i+1) \\ \frac{n-(i+1)}{n} \sum_{h=n-(i+2)}^{k-1} \left(\frac{i+1}{n}\right)^{k-h-1} \mathbb{P}_{i+1}\{C_{\{i+2, \dots, n-1\}} = h\} & \text{if } k \ge n-(i+1). \end{cases} $$

**Proof.** Applying relation (7) to subset $A = \{i+1, \dots, n-1\}$, we have $\mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = 0$ for $0 \le k < n-(i+1)$ and for $k \ge n-(i+1)$

$$ \mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = \sum_{h=1}^{k-n+i+2} \sum_{j=i+1}^{n-1} \left( P_{\{0, \dots, i\}}^{h-1} P_{\{0, \dots, i\}, \{i+1, \dots, n-1\}} \right)_{i,j} \mathbb{P}_j\{C_{\{i+1, \dots, n-1\} \setminus \{j\}} = k-h\}. $$

It is easily checked that for every $u \in \{0, \dots, i\}$, $v \in \{i+1, \dots, n-1\}$ and $h \ge 1$, we have

$$ \left( P_{\{0, \dots, i\}}^{h-1} P_{\{0, \dots, i\}, \{i+1, \dots, n-1\}} \right)_{u,v} = \frac{(i+1)^{h-1}}{n^h}. \qquad (19) $$

Moreover, by symmetry, $\mathbb{P}_j\{C_{\{i+1, \dots, n-1\} \setminus \{j\}} = k-h\}$ has the same value for every $j \in \{i+1, \dots, n-1\}$. We thus get, for $k \ge n-(i+1)$,

$$ \begin{aligned} \mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} &= \sum_{h=1}^{k-n+i+2} \sum_{j=i+1}^{n-1} \frac{(i+1)^{h-1}}{n^h} \mathbb{P}_{i+1}\{C_{\{i+2, \dots, n-1\}} = k-h\} \\ &= \frac{n-(i+1)}{n} \sum_{h=1}^{k-n+i+2} \left(\frac{i+1}{n}\right)^{h-1} \mathbb{P}_{i+1}\{C_{\{i+2, \dots, n-1\}} = k-h\} \\ &= \frac{n-(i+1)}{n} \sum_{h=n-(i+2)}^{k-1} \left(\frac{i+1}{n}\right)^{k-h-1} \mathbb{P}_{i+1}\{C_{\{i+2, \dots, n-1\}} = h\}, \end{aligned} $$

which completes the proof.
The following theorem gives an explicit formula for the distribution of the cover time of subset {$i + 1, \dots, n - 1$} when starting in state $i$. In order to prove this theorem, we first need the following lemma.

**Lemma 9** For every $m \ge 0$ and $x \in \mathbb{R}$, we have

$$ \sum_{j=0}^{m} (-1)^j \binom{m+1}{j} (x-j)^m = (m+1-x)^m. $$

**Proof.** We use the following result which is proved in [9]. For every $m \ge 0$ and $x \in \mathbb{R}$,

$$ \sum_{j=0}^{m} (-1)^j \binom{m}{j} (x-j)^m = m!. \qquad (20) $$

Using this relation and the fact that $\binom{m+1}{j} = \binom{m}{j} + \binom{m}{j-1}$, we get

$$ \begin{aligned} \sum_{j=0}^{m} (-1)^j \binom{m+1}{j} (x-j)^m &= \sum_{j=0}^{m} (-1)^j \binom{m}{j} (x-j)^m + \sum_{j=1}^{m} (-1)^j \binom{m}{j-1} (x-j)^m \\ &= m! - \sum_{j=0}^{m-1} (-1)^j \binom{m}{j} (x-j-1)^m \\ &= m! - \sum_{j=0}^{m} (-1)^j \binom{m}{j} (x-1-j)^m + (-1)^m (x-m-1)^m \\ &= (m+1-x)^m, \end{aligned} $$

where the second and the fourth equalities are due to relation (20).

**Theorem 10** For every $i = 0, \dots, n-2$, we have $\mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = 0$ for $0 \le k < n - (i+1)$ and for $k \ge n - (i+1)$,

$$ \mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = \frac{n-(i+1)}{n} \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} \left(\frac{n-(j+1)}{n}\right)^{k-1}. \qquad (21) $$

**Proof.** Clearly we have $\mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = 0$ for $0 \le k < n - (i+1)$. For $k \ge n - (i+1)$, the proof is made by recurrence. For $i = n - 2$, we have for $k \ge 0$,

$$ \mathbb{P}_{n-2}\{C_{\{n-1\}} = k\} = \mathbb{P}_{n-2}\{T_{\{n-1\}} = k\}. $$

We have $\mathbb{P}_{n-2}\{T_{\{n-1\}} = 0\} = 0$ and for $k \ge 1$, we obtain from (2) and (19)

$$ \mathbb{P}_{n-2}\{T_{\{n-1\}} = k\} = \left( P_{\{0, \dots, n-2\}}^{k-1} P_{\{0, \dots, n-2\}, \{n-1\}} \right)_{n-2} = \frac{(n-1)^{k-1}}{n^k}, $$

which is exactly relation (21) for $i = n - 2$.

Suppose relation (21) is true for index $i + 1 \le n - 2$, i.e. suppose that

$$ \mathbb{P}_{i+1}\{C_{\{i+2, \dots, n-1\}} = k\} = \frac{n-(i+2)}{n} \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+3)}{j} \left(\frac{n-(j+1)}{n}\right)^{k-1}. $$
From Lemma 8, we get for $k \ge n - (i + 1)$,

$$
\begin{align*}
\mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} &= \frac{n-(i+1)}{n} \sum_{h=n-(i+2)}^{k-1} \left(\frac{i+1}{n}\right)^{k-h-1} \frac{n-(i+2)}{n} \\
&\quad \times \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+3)}{j} \left(\frac{n-(j+1)}{n}\right)^{h-1} \\
&= \frac{(n-(i+1))(n-(i+2))(i+1)^{k-2}}{n^k} \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+3)}{j} \\
&\quad \times \sum_{h=n-(i+2)}^{k-1} \left(\frac{n-(j+1)}{i+1}\right)^{h-1} \\
&= \frac{(n-(i+1))(n-(i+2))(i+1)^{k-2}}{n^k} \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+3)}{j} \\
&\quad \times \left(\frac{n-(j+1)}{i+1}\right)^{n-(i+3)} \frac{i+1}{n-(i+2)-j} \left(-1 + \left(\frac{n-(j+1)}{i+1}\right)^{k-n+i+2}\right).
\end{align*}
$$

Observing that

$$
\frac{n-(i+2)}{n-(i+2)-j} \binom{n-(i+3)}{j} = \binom{n-(i+2)}{j},
$$

we obtain

$$
\begin{align*}
\mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} &= \frac{(n-(i+1))(i+1)^{k-2}}{n^k} \left[ \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} \frac{(n-(j+1))^{n-(i+3)}}{(i+1)^{n-(i+4)}} \right. \\
&\qquad \left. + \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} \frac{(n-(j+1))^{k-1}}{(i+1)^{k-2}} \right] \\
&= \frac{(n-(i+1))}{n^k} \left[ \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} (n-(j+1))^{k-1} \right. \\
&\qquad \left. - (i+1)^{k-n+i+2} \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} (n-(j+1))^{n-(i+3)} \right].
\end{align*}
$$
Using Lemma 9 in the second sum for $m = n - (i + 3)$ and $x = n - 1$, we get

$$
\begin{align*}
\mathbb{P}_i\{C_{i+1, \dots, n-1} = k\} &= \frac{n-(i+1)}{n^k} \left[ \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} (n-(j+1))^{k-1} \right. \\
&\qquad \left. - (i+1)^{k-n+i+2} (-i-1)^{n-(i+3)} \right] \\
&= \frac{n-(i+1)}{n^k} \left[ \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} (n-(j+1))^{k-1} \right. \\
&\qquad \left. + (-1)^{n-(i+2)} (i+1)^{k-1} \right] \\
&= \frac{n-(i+1)}{n^k} \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} (n-(j+1))^{k-1},
\end{align*}
$$

which completes the proof.

<figure><img src="image_5.png" /></figure>

**Corollary 11** For every $i = 0, \dots, n-2$, we have

$$
\mathbb{P}_i\{C_{i+1, \dots, n-1} > k\} = \begin{cases} 1 & \text{if } 0 \le k < n - (i+1) \\ \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+1)}{j+1} \left(\frac{n-(j+1)}{n}\right)^k & \text{if } k \ge n - (i+1). \end{cases}
$$

**Proof.** The result is trivial for $k < n - (i + 1)$. For $k \ge n - (i + 1)$, we have

$$
\begin{align*}
\mathbb{P}_i\{C_{i+1, \dots, n-1} > k\} &= \sum_{h=k}^{\infty} \mathbb{P}_i\{C_{i+1, \dots, n-1} = h+1\} \\
&= \frac{n-(i+1)}{n} \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} \sum_{h=k}^{\infty} \left(\frac{n-(j+1)}{n}\right)^h \\
&= \frac{n-(i+1)}{n} \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} \frac{n}{j+1} \left(\frac{n-(j+1)}{n}\right)^k \\
&= \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} \frac{n-(i+1)}{j+1} \left(\frac{n-(j+1)}{n}\right)^k \\
&= \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+1)}{j+1} \left(\frac{n-(j+1)}{n}\right)^k,
\end{align*}
$$

which completes the proof.

<figure><img src="image_6.png" /></figure>

Note that the second expression of Corollary 11 is still valid for $k = n - (i + 2)$. Indeed, the variable
change $j := j - 1$ followed by the use of Lemma 9, with $m = n - (i + 2)$ and $x = n$, leads to

$$ 
\begin{aligned}
\sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+1)}{j+1} \left(\frac{n-(j+1)}{n}\right)^{n-(i+2)} &= - \sum_{j=1}^{n-(i+1)} (-1)^j \binom{n-(i+1)}{j} \left(\frac{n-j}{n}\right)^{n-(i+2)} \\
&= - \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+1)}{j} \left(\frac{n-j}{n}\right)^{n-(i+2)} + 1 - (-1)^{n-(i+1)} \left(\frac{i+1}{n}\right)^{n-(i+2)} \\
&= -(-1)^{n-(i+2)} \left(\frac{i+1}{n}\right)^{n-(i+2)} + 1 - (-1)^{n-(i+1)} \left(\frac{i+1}{n}\right)^{n-(i+2)} = 1.
\end{aligned}
$$

Taking $i = 0$ in Theorem 10, we obtain the cover time probability mass function given by

$$ \mathbb{P}\{C = k\} = \begin{cases} 0 & \text{if } 0 \le k < n-1 \\ \frac{n-1}{n} \sum_{j=0}^{n-2} (-1)^j \binom{n-2}{j} \left(\frac{n-(j+1)}{n}\right)^{k-1} & \text{if } k \ge n-1. \end{cases} $$

Taking $i = 0$ in Corollary 11, the complementary cumulative distribution function is given by

$$ \mathbb{P}\{C > k\} = \begin{cases} 1 & \text{if } 0 \le k < n-1 \\ \sum_{j=0}^{n-2} (-1)^j \binom{n-1}{j+1} \left(\frac{n-(j+1)}{n}\right)^k & \text{if } k \ge n-1. \end{cases} $$

## 4.2 The complete graph without self-loops

Random walk on the complete graph without self-loops is a Markov chain on the state space $S = \{0, 1, \dots, n-1\}$, $n \ge 2$, with transition probability matrix $P$ given, for every $u \ne v$, by $P_{u,v} = 1/(n-1)$ and $P_{u,u} = 0$.

### 4.2.1 Mean cover time of the complete graph without self-loops

By symmetry, we have for any initial distribution and for every $i \in S$,

$$ \mathbb{E}(C) = \mathbb{E}_i(C_{S\setminus\{i\}}) = \mathbb{E}_0(C_{\{1,\dots,n-1\}}). $$

**Lemma 12** For every $u, v \in \{0, \dots, i\}$ and $k \ge 0$, we have

$$ \left(P_{\{0, \dots, i\}}^{k}\right)_{u,v} = \begin{cases} \frac{i^k - (-1)^k}{(i+1)(n-1)^k} & \text{if } u \neq v \\ \frac{i^k + i(-1)^k}{(i+1)(n-1)^k} & \text{if } u = v. \end{cases} $$

**Proof.** The proof is made by recurrence. For $k = 0$ we clearly have $(P_{\{0, \dots, i\}}^0)_{u,v} = 1_{\{u=v\}}$. Suppose that the result is true for index $k - 1$, i.e. suppose that

$$ \left(P_{\{0, \dots, i\}}^{k-1}\right)_{u,v} = \begin{cases} \frac{i^{k-1} - (-1)^{k-1}}{(i+1)(n-1)^{k-1}} & \text{if } u \neq v \\ \frac{i^{k-1} + i(-1)^{k-1}}{(i+1)(n-1)^{k-1}} & \text{if } u = v. \end{cases} $$
We then have

$$
\begin{align*}
\left(P_{\{0,...,i\}}^k\right)_{u,v} &= \sum_{w=0}^{i} \left(P_{\{0,...,i\}}^{k-1}\right)_{u,w} \left(P_{\{0,...,i\}}\right)_{w,v} \\
&= \frac{1}{n-1} \sum_{w=0, w \neq v}^{i} \left(P_{\{0,...,i\}}^{k-1}\right)_{u,w} \\
&= \begin{cases}
\frac{1}{n-1} \left( \left(P_{\{0,...,i\}}^{k-1}\right)_{u,u} + \sum_{w=0, w \neq u, v}^{i} \left(P_{\{0,...,i\}}^{k-1}\right)_{u,w} \right) & \text{if } u \neq v \\
\frac{1}{n-1} \sum_{w=0, w \neq u}^{i} \left(P_{\{0,...,i\}}^{k-1}\right)_{u,w} & \text{if } u = v
\end{cases} \\
&= \begin{cases}
\frac{i^k - (-1)^k}{(i+1)(n-1)^k} & \text{if } u \neq v \\
\frac{i^k + i(-1)^k}{(i+1)(n-1)^k} & \text{if } u = v,
\end{cases}
\end{align*}
$$

which completes the proof.

**Theorem 13** For every $i = 0, \dots, n-2$, we have

$$
E_i(C_{\{i+1, \dots, n-1\}}) = (n-1)h_{n-(i+1)}.
$$

**Proof.** For every $u, v \in \{0, \dots, i\}$, we have from Lemma 12,

$$
\left((I - P_{\{0,...,i\}})^{-1}\right)_{u,v} = \sum_{k=0}^{\infty} \left(P_{\{0,...,i\}}^{k}\right)_{u,v} = \begin{cases} \frac{n-1}{n(n-(i+1))} & \text{if } u \neq v \\ \frac{(n-1)(n-i)}{n(n-(i+1))} & \text{if } u = v. \end{cases}
$$

We thus get, for every $u \in \{0, \dots, i\}$,

$$
\begin{align*}
\left( (I - P_{\{0, \dots, i\}})^{-1} 1 \right)_u &= \sum_{v=0}^{i} \left( (I - P_{\{0, \dots, i\}})^{-1} \right)_{u,v} \\
&= \frac{(n-1)(n-i)}{n(n-(i+1))} + \sum_{v=0, v \neq u}^{i} \frac{n-1}{n(n-(i+1))} \\
&= \frac{n-1}{n-(i+1)}.
\end{align*}
$$

For every $u \in \{0, \dots, i\}$ and $v \in \{i+1, \dots, n-1\}$, we have

$$
\left( (I - P_{\{0,...,i\}})^{-1} P_{\{0,...,i\}, \{i+1,...,n-1\}} \right)_{u,v} = \frac{1}{n-1} \left( (I - P_{\{0,...,i\}})^{-1} 1 \right)_{u} = \frac{1}{n-(i+1)}.
$$

Putting this result into relation (8), we obtain

$$
\mathbb{E}_i(C_{\{i+1, \dots, n-1\}}) = \frac{n-1}{n-(i+1)} + \frac{1}{n-(i+1)} \sum_{j=i+1}^{n-1} \mathbb{E}_j(C_{\{i+1, \dots, n-1\} \setminus \{j\}}).
$$
By symmetry, we have $E_j(C_{\{i+1,...,n-1\}\setminus\{j\}}) = E_{i+1}(C_{\{i+2,...,n-1\}})$, which leads to

$$ \mathbb{E}_i(C_{\{i+1,...,n-1\}}) = \frac{n-1}{n-(i+1)} + \mathbb{E}_{i+1}(C_{\{i+2,...,n-1\}}). $$

Since

$$ \mathbb{E}_{n-2}(C_{\{n-1\}}) = \mathbb{E}_{n-2}(T_{\{n-1\}}) = \left( \left( I - P_{A_{n-2}^c} \right)^{-1} 1 \right)_{n-2} = n-1, $$

we obtain, recursively,

$$ \mathbb{E}_i(C_{\{i+1,...,n-1\}}) = (n-1)h_{n-(i+1)}, $$

which completes the proof.

<figure><img src="image_7.png" /></figure>

By symmetry, taking $i=0$ in Theorem 13, we get

$$ E(C) = (n-1)h_{n-1}. $$

### 4.2.2 Cover time distribution of the complete graph without self-loops

Again, by symmetry, we have for any initial distribution and for every $i \in S$,

$$ P\{C = k\} = \mathbb{P}_i\{C_{S\setminus\{i\}} = k\} = \mathbb{P}_0\{C_{\{1,...,n-1\}} = k\}. $$

**Lemma 14** For every $i = 0, ..., n-3$, we have

$$ \mathbb{P}_i\{C_{\{i+1,...,n-1\}} = k\} = \begin{cases} 0 & \text{if } 0 \le k < n-(i+1) \\ \frac{n-(i+1)}{n-1} \sum_{h=n-(i+2)}^{k-1} \left(\frac{i}{n-1}\right)^{k-h-1} \mathbb{P}_{i+1}\{C_{\{i+2,...,n-1\}} = h\} & \text{if } k \ge n-(i+1) \end{cases} $$

**Proof.** Applying relation (7) to subset $A = \{i+1, ..., n-1\}$, we have $\mathbb{P}_i\{C_{\{i+1,...,n-1\}} = k\} = 0$ for $0 \le k < n-(i+1)$ and

$$ \mathbb{P}_i\{C_{\{i+1,...,n-1\}} = k\} = \sum_{h=1}^{k-n+i+2} \sum_{j=i+1}^{n-1} \left( P_{\{0,...,i\}}^{h-1} P_{\{0,...,i\}, \{i+1,...,n-1\}} \right)_{i,j} \mathbb{P}_j\{C_{\{i+1,...,n-1\}} \setminus j = k-h\}, $$

for $k \ge n-(i+1)$.

It is easily checked from Lemma 12 that for every $u \in \{0, ..., i\}$, $v \in \{i+1, ..., n-1\}$ and $h \ge 1$, we have

$$ \left( P_{\{0,...,i\}}^{h-1} P_{\{0,...,i\}, \{i+1,...,n-1\}} \right)_{u,v} = \frac{i^{h-1}}{(n-1)^h}. \qquad (22) $$

Moreover, by symmetry, $\mathbb{P}_j\{C_{\{i+1,...,n-1\}} \setminus j = k-h\}$ has the same value for every $j \in \{i+1, ..., n-1\}$. We thus get, for $k \ge n-(i+1)$,

$$ \begin{aligned} \mathbb{P}_i\{C_{\{i+1,...,n-1\}} = k\} &= \sum_{h=1}^{k-n+i+2} \sum_{j=i+1}^{n-1} \frac{i^{h-1}}{(n-1)^h} \mathbb{P}_{i+1}\{C_{\{i+2,...,n-1\}} = k-h\} \\ &= \frac{n-(i+1)}{n-1} \sum_{h=1}^{k-n+i+2} \left(\frac{i}{n-1}\right)^{h-1} \mathbb{P}_{i+1}\{C_{\{i+2,...,n-1\}} = k-h\} \\ &= \frac{n-(i+1)}{n-1} \sum_{h=n-(i+2)}^{k-1} \left(\frac{i}{n-1}\right)^{k-h-1} \mathbb{P}_{i+1}\{C_{\{i+2,...,n-1\}} = h\}, \end{aligned} $$

which completes the proof.

<figure><img src="image_8.png" /></figure>
The following theorem gives an explicit formula for the distribution of the cover time of subset {$i + 1, \dots, n - 1$}.

**Theorem 15** For every $i = 0, \dots, n-2$, we have $\mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = 0$ for $0 \le k < n - (i+1)$ and for $k \ge n - (i+1)$,

$$ \mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = \frac{n-(i+1)}{n-1} \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} \left(\frac{n-(j+2)}{n-1}\right)^{k-1}. \quad (23) $$

**Proof.** Clearly we have $\mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} = 0$ for $0 \le k < n - (i+1)$. For $k \ge n - (i+1)$, the proof is made by recurrence. For $i = n - 2$, we have for $k \ge 0$,

$$ \mathbb{P}_{n-2}\{C_{\{n-1\}} = k\} = \mathbb{P}_{n-2}\{T_{\{n-1\}} = k\}. $$

We have $\mathbb{P}_{n-2}\{T_{\{n-1\}} = 0\} = 0$ and for $k \ge 1$, we obtain from (2) and (22)

$$ \mathbb{P}_{n-2}\{T_{\{n-1\}} = k\} = \left( P_{\{0, \dots, n-2\}}^{k-1} P_{\{0, \dots, n-2\}, \{n-1\}} 1 \right)_{n-2} = \frac{(n-2)^{k-1}}{(n-1)^k}, $$

which is exactly relation (21) for $i = n - 2$.

Suppose relation (23) is true for index $i + 1 \le n - 2$, i.e. suppose that

$$ \mathbb{P}_{i+1}\{C_{\{i+2, \dots, n-1\}} = k\} = \frac{n-(i+2)}{n-1} \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+3)}{j} \left(\frac{n-(j+2)}{n-1}\right)^{k-1}. $$

From Lemma 14, we get for $k \ge n - (i + 1)$,

$$ \begin{aligned} \mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = k\} &= \frac{n-(i+1)}{n-1} \sum_{h=n-(i+2)}^{k-1} \left(\frac{i}{n-1}\right)^{k-h-1} \frac{n-(i+2)}{n-1} \\ & \quad \times \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+3)}{j} \left(\frac{n-(j+2)}{n-1}\right)^{h-1} \\ &= \frac{(n-(i+1))(n-(i+2))^{i(k-2)}}{(n-1)^k} \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+3)}{j} \\ & \quad \times \sum_{h=n-(i+2)}^{k-1} \left(\frac{n-(j+2)}{i}\right)^{h-1} \\ &= \frac{(n-(i+1))(n-(i+2))^{i(k-2)}}{(n-1)^k} \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+3)}{j} \\ & \quad \times \left(\frac{n-(j+2)}{i}\right)^{n-(i+3)} \frac{i}{n-(i+2)-j} \left(-1 + \left(\frac{n-(j+2)}{i}\right)^{k-n+i+2}\right). \end{aligned} $$

Observing that

$$ \frac{n-(i+2)}{n-(i+2)-j} \binom{n-(i+3)}{j} = \binom{n-(i+2)}{j}, $$
we obtain

$$
\begin{aligned}
\mathbb{P}_i\{C_{i+1, \dots, n-1} = k\} &= \frac{(n-(i+1))i^{k-2}}{(n-1)^k} \left[ \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} \frac{(n-(j+2))^{n-(i+3)}}{i^{n-(i+4)}} \right. \\
&\qquad \left. + \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} \frac{(n-(j+2))^{k-1}}{i^{k-2}} \right] \\
&= \frac{n-(i+1)}{(n-1)^k} \left[ \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} (n-(j+2))^{k-1} \right. \\
&\qquad \left. - i^{k-n+i+2} \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} (n-(j+2))^{n-(i+3)} \right].
\end{aligned}
$$

Using Lemma 9 in the second sum for $m = n - (i+3)$ and $x = n-1$, we get

$$
\begin{aligned}
\mathbb{P}_i\{C_{i+1, \dots, n-1} = k\} &= \frac{n-(i+1)}{(n-1)^k} \left[ \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} (n-(j+2))^{k-1} \right. \\
&\qquad \left. - i^{k-n+i+2} (-i)^{n-(i+3)} \right] \\
&= \frac{n-(i+1)}{(n-1)^k} \left[ \sum_{j=0}^{n-(i+3)} (-1)^j \binom{n-(i+2)}{j} (n-(j+2))^{k-1} \right. \\
&\qquad \left. + (-1)^{n-(i+2)} i^{k-1} \right] \\
&= \frac{n-(i+1)}{(n-1)^k} \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} (n-(j+2))^{k-1},
\end{aligned}
$$

which completes the proof.

<figure><img src="image_9.png" /></figure>

**Corollary 16** For every $i = 0, \dots, n-2$, we have

$$
\mathbb{P}_i\{C_{i+1, \dots, n-1} > k\} = \begin{cases} 1 & \text{if } 0 \le k < n-(i+1) \\ \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+1)}{j+1} \left(\frac{n-(j+2)}{n-1}\right)^k & \text{if } k \ge n-(i+1). \end{cases}
$$
**Proof.** The result is trivial for $k < n - (i + 1)$. For $k \ge n - (i + 1)$, we have

$$
\begin{align*}
\mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} > k\} &= \sum_{h=k}^{\infty} \mathbb{P}_i\{C_{\{i+1, \dots, n-1\}} = h+1\} \\
&= \frac{n-(i+1)}{n-1} \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} \sum_{h=k}^{\infty} \left(\frac{n-(j+2)}{n-1}\right)^h \\
&= \frac{n-(i+1)}{n-1} \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} \frac{n-1}{j+1} \left(\frac{n-(j+2)}{n-1}\right)^k \\
&= \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+2)}{j} \frac{n-(i+1)}{j+1} \left(\frac{n-(j+2)}{n-1}\right)^k \\
&= \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+1)}{j+1} \left(\frac{n-(j+2)}{n-1}\right)^k,
\end{align*}
$$

which completes the proof.

<figure><img src="image_10.png" /></figure>

Note that the second expression of Corollary 16 is still valid for $k = n - (i+2)$. Indeed, as we did in the section on the complete graph with self-loops, the use of Lemma 9, with $m = n - (i+2)$ and $x = n-1$, gives

$$
\begin{align*}
\sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+1)}{j+1} \left(\frac{n-(j+2)}{n-1}\right)^{n-(i+2)} &= - \sum_{j=1}^{n-(i+1)} (-1)^j \binom{n-(i+1)}{j} \left(\frac{n-(j+1)}{n-1}\right)^{n-(i+2)} \\
&= - \sum_{j=0}^{n-(i+2)} (-1)^j \binom{n-(i+1)}{j} \left(\frac{n-(j+1)}{n-1}\right)^{n-(i+2)} + 1 - (-1)^{n-(i+1)} \left(\frac{i}{n-1}\right)^{n-(i+2)} \\
&= -(-1)^{n-(i+2)} \left(\frac{i}{n-1}\right)^{n-(i+2)} + 1 - (-1)^{n-(i+1)} \left(\frac{i}{n-1}\right)^{n-(i+2)} = 1.
\end{align*}
$$

Taking $i=0$ in Theorem 10, we obtain the cover time probability mass function given by

$$
\mathbb{P}\{C = k\} = \begin{cases} 0 & \text{if } 0 \le k < n-1 \\ \sum_{j=0}^{n-2} (-1)^j \binom{n-2}{j} \left(\frac{n-(j+2)}{n-1}\right)^{k-1} & \text{if } k \ge n-1. \end{cases}
$$

Taking $i=0$ in Corollary 11, the complementary cumulative distribution function is given by

$$
\mathbb{P}\{C > k\} = \begin{cases} 1 & \text{if } 0 \le k < n-1 \\ \sum_{j=0}^{n-2} (-1)^j \binom{n-1}{j+1} \left(\frac{n-(j+2)}{n-1}\right)^k & \text{if } k \ge n-1. \end{cases}
$$

5 The generalized n-path graph

We consider in this section a Markov chain on the state space $S = \{1, \dots, n\}$, $n \ge 2$, with transition probability matrix $P$. Its non zero transition probabilities are given by

$$
\begin{cases}
P_{i,i+1} = p_i & \text{for } i = 1, \dots, n-1 \\
P_{i,i-1} = q_i & \text{for } i = 2, \dots, n \\
P_{i,i} = r_i & \text{for } i = 1, \dots, n,
\end{cases}
$$
where $p_i, q_i \in (0,1]$, $r_i \in [0,1)$ with $p_1 + r_1 = 1$, $p_i + q_i + r_i = 1$ for $i = 2, \dots, n-1$ and $r_n + q_n = 1$. We call this Markov chain the generalized n-path graph because when $p_i = q_i = 1/2$, for $i = 2, \dots, n-1$ and $p_1 = q_n = 1$ which means that $r_i = 0$, we obtain the well-known random walk called the n-path graph without loops and when $p_i = q_i = r_i = 1/3$, for $i = 2, \dots, n-1$ and $p_1 = r_1 = q_n = r_n = 1/2$ we obtain the well-known random walk called the n-path graph with loops.

## 5.1 Mean cover time of the generalized n-path graph

We consider in this subsection the mean cover time of the generalized n-path graph starting in state $i$, for every $i = 1, \dots, n$. We first consider the mean cover time of subset $\{i+1, \dots, n\}$ starting in state $i$.

**Lemma 17** For every $i = 1, \dots, n-1$, we have

$$ \mathbb{E}_i(T_{\{i+1, \dots, n\}}) = \sum_{k=1}^{i} \left( \prod_{m=k+1}^{i} \frac{q_m}{p_m} \right) \frac{1}{p_k}, $$

the product being equal to 1 when $k = i$.

**Proof.** From relation (4), we have, for every $i = 1, \dots, n-1$,

$$ \mathbb{E}_i(T_{\{i+1, \dots, n\}}) = ((I - P_{\{1, \dots, i\}})^{-1} 1)_i. $$

The column vector $V = (v_1, \dots, v_i)$ defined by $V = (I - P_{\{1, \dots, i\}})^{-1} 1$ is the unique solution to the linear system

$$ (I - P_{\{1, \dots, i\}})V = 1 $$

and we are looking for an expression of $v_i = \mathbb{E}_i(T_{\{i+1, \dots, n-1\}})$. This linear system can be written as

$$ \left\{ \begin{array}{l} (1 - r_1)v_1 - p_1v_2 = 1 \\ -q_\ell v_{\ell-1} + (1 - r_\ell)v_\ell - p_\ell v_{\ell+1} = 1, \text{ for } \ell = 2, \dots, i-1 \\ -q_i v_{i-1} + (1 - r_i)v_i = 1. \end{array} \right. \qquad (24) $$

Defining $v_{i+1} = 0$, $z_\ell = v_\ell - v_{\ell+1}$ for $\ell = 1, \dots, i$ and observing that $1 - r_1 = p_1$ and $1 - r_\ell = p_\ell + q_\ell$, for $\ell = 2, \dots, i$, we obtain

$$ z_1 = \frac{1}{p_1} \text{ and } z_\ell = \frac{1}{p_\ell} + \frac{q_\ell}{p_\ell} z_{\ell-1}, \text{ for } \ell = 2, \dots, i. $$

This leads, for $\ell = 1, \dots, i$, to

$$ z_\ell = \sum_{k=1}^{\ell} \left( \prod_{m=k+1}^{\ell} \frac{q_m}{p_m} \right) \frac{1}{p_k}, $$

the product being equal to 1 when $k = \ell$. Since $v_{i+1} = 0$, we have $v_i = z_i$, that is

$$ v_i = \sum_{k=1}^{i} \left( \prod_{m=k+1}^{i} \frac{q_m}{p_m} \right) \frac{1}{p_k}, $$

which completes the proof.

**Lemma 18** For every $i = 1, \dots, n-1$, we have

$$ \mathbb{E}_i(C_{\{i+1, \dots, n\}}) = \sum_{j=i}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k}, $$

the product being equal to 1 when $k = j$.
**Proof.** From relation (8) we have, for every $i = 1, \dots, n-1$,

$$ \mathbb{E}_i(C_{\{i+1, \dots, n\}}) = \mathbb{E}_i(T_{\{i+1, \dots, n\}}) + \sum_{j=i+1}^{n} \left( (I - P_{\{1, \dots, i\}})^{-1} P_{\{1, \dots, i\}, \{i+1, \dots, n\}} \right)_{i,j} \mathbb{E}_j(C_{\{i+1, \dots, n\} \setminus \{j\}}). $$

Observing that the only non zero entry of matrix $P_{\{1, \dots, i\}, \{i+1, \dots, n\}}$ is $(P_{\{1, \dots, i\}, \{i+1, \dots, n\}})_{i, i+1} = p_i$, we deduce that matrix $(I - P_{\{1, \dots, i\}})^{-1} P_{\{1, \dots, i\}, \{i+1, \dots, n\}}$ has only one non zero column which is column $i+1$. This matrix being a (non square) stochastic matrix, we have

$$ ((I - P_{\{1, \dots, i\}})^{-1} P_{\{1, \dots, i\}, \{i+1, \dots, n\}})_{i,j} = 1_{\{j=i+1\}}. $$

The previous equation thus becomes

$$ \mathbb{E}_i(C_{\{i+1, \dots, n\}}) = \mathbb{E}_i(T_{\{i+1, \dots, n\}}) + \mathbb{E}_{i+1}(C_{\{i+2, \dots, n\}}) $$

which leads, since $\mathbb{E}_{n-1}(C_{\{n\}}) = \mathbb{E}_{n-1}(T_{\{n\}})$, to

$$ \mathbb{E}_i(C_{\{i+1, \dots, n\}}) = \sum_{j=i}^{n-1} \mathbb{E}_j(T_{\{j+1, \dots, n\}}). $$

Using Lemma 17, we conclude that

$$ \mathbb{E}_i(C_{\{i+1, \dots, n\}}) = \sum_{j=i}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k}, $$

which completes the proof.

In the same way, we consider the mean cover time of subset $\{1, \dots, i-1\}$ starting in state $i$.

**Lemma 19** For every $i = 2, \dots, n$, we have

$$ \mathbb{E}_i(T_{\{1, \dots, i-1\}}) = \sum_{k=i}^{n} \left( \prod_{m=i}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k}, $$

the product being equal to 1 when $k = i$.

**Proof.** From relation (4), we have, for every $i = 2, \dots, n$,

$$ \mathbb{E}_i(T_{\{1, \dots, i-1\}}) = ((I - P_{\{i, \dots, n\}})^{-1} 1)_i. $$

The column vector $V = (v_i, \dots, v_n)$ defined by $V = (I - P_{\{i, \dots, n\}})^{-1} 1$ is the unique solution to the linear system

$$ (I - P_{\{i, \dots, n\}})V = 1 $$

and we are looking for an expression of $v_i = \mathbb{E}_i(T_{\{1, \dots, i-1\}})$. This linear system can be written as

$$ \left\{ \begin{array}{l} (1 - r_i)v_i - p_i v_{i+1} = 1 \\ \\ -q_{\ell}v_{\ell-1} + (1 - r_{\ell})v_{\ell} - p_{\ell}v_{\ell+1} = 1, \text{ for } \ell = i+1, \dots, n-1 \\ \\ -q_n v_{n-1} + (1 - r_n)v_n = 1. \end{array} \right. \qquad (25) $$
Defining $v_{i-1} = 0$, $z_\ell = v_\ell - v_{\ell-1}$, for $\ell = i, \dots, n$ and observing that $1 - r_n = q_n$ and $1 - r_\ell = p_\ell + q_\ell$, for $\ell = i, \dots, n-1$, we obtain

$$z_n = \frac{1}{q_n} \text{ and } z_\ell = \frac{1}{q_\ell} + \frac{p_\ell}{q_\ell} z_{\ell+1}, \text{ for } \ell = i, \dots, n-1.$$

This leads to, for $\ell = i, \dots, n$, to

$$z_\ell = \sum_{k=\ell}^{n} \left( \prod_{m=\ell}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k},$$

the product being equal to 1 when $k = \ell$. Since $v_{i-1} = 0$, we have $v_i = z_i$, that is

$$v_i = \sum_{k=i}^{n} \left( \prod_{m=i}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k},$$

which completes the proof.

<figure><img src="image_11.png" /></figure>

**Lemma 20** For every $i = 2, \dots, n$, we have

$$\mathbb{E}_i(C_{\{1, \dots, i-1\}}) = \sum_{j=2}^{i} \sum_{k=j}^{n} \left( \prod_{m=j}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k},$$

the product being equal to 1 when $k = j$.

**Proof.** From relation (8) we have, for every $i = 2, \dots, n$,

$$\mathbb{E}_i(C_{\{1, \dots, i-1\}}) = \mathbb{E}_i(T_{\{1, \dots, i-1\}}) + \sum_{j=1}^{i-1} \left( (I - P_{\{i, \dots, n\}})^{-1} P_{\{i, \dots, n\}, \{1, \dots, i-1\}} \right)_{i,j} \mathbb{E}_j(C_{\{1, \dots, i-1\} \setminus \{j\}}).$$

The same remark we did for the proof of Lemma 17 gives

$$((I - P_{\{i, \dots, n\}})^{-1} P_{\{i, \dots, n\}, \{1, \dots, i-1\}})_{i,j} = 1_{\{j=i-1\}}.$$

The previous equation thus becomes

$$\mathbb{E}_i(C_{\{1, \dots, i-1\}}) = \mathbb{E}_i(T_{\{1, \dots, i-1\}}) + \mathbb{E}_{i-1}(C_{\{1, \dots, i-2\}}).$$

which leads, since $\mathbb{E}_2(C_{\{1\}}) = \mathbb{E}_2(T_{\{1\}})$, to

$$\mathbb{E}_i(C_{\{1, \dots, i-1\}}) = \sum_{j=2}^{i} \mathbb{E}_j(T_{\{1, \dots, j-1\}}).$$

Using Lemma 19, we conclude that

$$\mathbb{E}_i(C_{\{1, \dots, i-1\}}) = \sum_{j=2}^{i} \sum_{k=j}^{n} \left( \prod_{m=j}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k}.$$

which completes the proof.

<figure><img src="image_12.png" /></figure>
Observe that the linear structure of the state space of the path graph implies that for every $a, i, b \in S$, when starting in state $i$ with $a < i < b$, the distribution of the cover time of subset $\{1, \dots, a, b, \dots, n\}$ is the same as that of the cover time of the global state space. More precisely, we have

$$ \mathbb{P}_i\{C_{\{1, \dots, a, b, \dots, n\}} = k\} = \mathbb{P}_i\{C_{S\setminus\{i\}} = k\} = \mathbb{P}_i\{C = k\}. \quad (26) $$

It follows in particular that the expectations (and all the moments) are equal, i.e.

$$ \mathbb{E}_i(C_{\{1, \dots, a, b, \dots, n\}}) = \mathbb{E}_i(C_{S\setminus\{i\}}) = \mathbb{E}_i(C), \text{ for every } a, i, b \text{ with } a < i < b. \quad (27) $$

In the same way, we have for every $a$, $\mathbb{P}_1\{C_{\{a, \dots, n\}} = k\} = \mathbb{P}_1\{C_{S\setminus\{1\}} = k\} = \mathbb{P}_1\{C = k\}$ and in the same way $\mathbb{P}_n\{C_{\{1, \dots, a\}} = k\} = \mathbb{P}_n\{C_{S\setminus\{n\}} = k\} = \mathbb{P}_n\{C = k\}$. This observation is used to prove the following results. We use in the following the convention that a sum of terms $\sum_a^b (...) \text{ is set to } 0$ when $a > b$,

**Theorem 21** For every $i = 1, \dots, n$, we have

$$ \mathbb{E}_i(C) = \sum_{j=i}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} + \frac{\sum_{j=1}^{i-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right)}{\sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right)} \sum_{j=2}^{n} \sum_{k=j}^{n} \left( \prod_{m=j}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k}. $$

**Proof.** Using again relation (8) we have, for every $i = 2, \dots, n-1$,

$$ \mathbb{E}_i(C_{S\setminus\{i\}}) = ((I - P_{\{i\}})^{-1} 1)_i + \sum_{j \in S \setminus \{i\}} \left( ((I - P_{\{i\}})^{-1} P_{\{i\}, S \setminus \{i\}}) \right)_{i,j} \mathbb{E}_j(C_{S \setminus \{i,j\}}). $$

Matrix $P_{\{i\}}$ is in fact a scalar which value is $r_i = 1 - p_i - q_i$ and matrix $P_{\{i\}, S \setminus \{i\}}$ is a row vector which non zero entries are $(P_{\{i\}, S \setminus \{i\}})_{i-1} = q_i$ and $(P_{\{i\}, S \setminus \{i\}})_{i+1} = p_i$. We thus have

$$ ((I - P_{\{i\}})^{-1} P_{\{i\}, S \setminus \{i\}})_{i, i-1} = \frac{q_i}{p_i + q_i} \quad \text{and} \quad ((I - P_{\{i\}})^{-1} P_{\{i\}, S \setminus \{i\}})_{i, i+1} = \frac{p_i}{p_i + q_i}, $$

the other entries being equal to 0. This leads to

$$ \mathbb{E}_i(C_{S\setminus\{i\}}) = \frac{1}{p_i + q_i} + \frac{q_i}{p_i + q_i} \mathbb{E}_{i-1}(C_{S\setminus\{i-1, i\}}) + \frac{p_i}{p_i + q_i} \mathbb{E}_{i+1}(C_{S\setminus\{i, i+1\}}). $$

Using relation (27) and the particular cases $i = 1$ and $i = n$, we obtain for every $i = 2, \dots, n-1$,

$$ \mathbb{E}_i(C) = \frac{1}{p_i + q_i} + \frac{q_i}{p_i + q_i} \mathbb{E}_{i-1}(C) + \frac{p_i}{p_i + q_i} \mathbb{E}_{i+1}(C). $$

Introducing the notation $z_i = E_i(C) - E_{i+1}(C)$, we get for every $i = 2, \dots, n-1$,

$$ z_i = \frac{1}{p_i} + \frac{q_i}{p_i} z_{i-1}, $$

which leads, for every $i = 2, \dots, n-1$, to

$$ z_i = \sum_{k=2}^{i} \left( \prod_{m=k+1}^{i} \frac{q_m}{p_m} \right) \frac{1}{p_k} + \left( \prod_{m=2}^{i} \frac{q_m}{p_m} \right) z_1, $$

the first product being equal to 1 when $k = i$. From Lemma 18 and 20, we have

$$ \mathbb{E}_1(C) = \sum_{j=1}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} \quad \text{and} \quad \mathbb{E}_n(C) = \sum_{j=2}^{n} \sum_{k=j}^{n} \left( \prod_{m=j}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k}. $$
It follows that

$$
\begin{align*}
E_1(C) - E_n(C) &= \sum_{j=1}^{n-1} z_j = \sum_{j=1}^{n-1} \sum_{k=2}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} + \sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) z_1 \\
&= \sum_{j=1}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} - \sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_1} + \sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) z_1 \\
&= E_1(C) - \sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_1} + \sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) z_1.
\end{align*}
$$

Using the expression of $E_n(C)$, we get the following expression of $z_1$ i.e.

$$
z_1 = \frac{1}{p_1} - \frac{E_n(C)}{\sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right)} = \frac{1}{p_1} - \frac{\sum_{j=2}^{n} \sum_{k=j}^{n} \left( \prod_{m=j}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k}}{\sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right)}.
$$

Writing now

$$
E_1(C) - E_i(C) = \sum_{j=1}^{i-1} z_j = \sum_{j=1}^{i-1} \sum_{k=2}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} + \sum_{j=1}^{i-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) z_1
$$

and using the previous expression of $E_1(C)$ and $z_1$, we obtain

$$
\begin{align*}
E_i(C) &= \sum_{j=1}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} - \sum_{j=1}^{n-1} \sum_{k=2}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} - \sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) z_1 \\
&= \sum_{j=1}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} + \sum_{j=1}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} + \sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_1} - \sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) z_1 \\
&= \sum_{j=i}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} + \left( \frac{1}{p_1} - z_1 \right) \sum_{j=1}^{i-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right) \\
&= \sum_{j=i}^{n-1} \sum_{k=1}^{j} \left( \prod_{m=k+1}^{j} \frac{q_m}{p_m} \right) \frac{1}{p_k} + \frac{\sum_{j=1}^{i-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right)}{\sum_{j=1}^{n-1} \left( \prod_{m=2}^{j} \frac{q_m}{p_m} \right)} \sum_{k=2}^{n} \sum_{j=k}^{n} \left( \prod_{m=j}^{k-1} \frac{p_m}{q_m} \right) \frac{1}{q_k},
\end{align*}
$$

which completes the proof.

We then apply this theorem in the following particular cases.
• If $p_{\ell} = p \neq 0$ and $q_{\ell} = q \neq 0$ then, introducing the notation $\theta = q/p$, we have, when $\theta \neq 1$,

$$
\begin{align*}
\mathbb{E}_i(C) &= \frac{1}{p} \sum_{j=i}^{n-1} \sum_{k=1}^{j} \theta^{j-k} + \frac{\sum_{j=1}^{i-1} \theta^{j-1}}{q \sum_{j=1}^{n-1} \theta^{j-1}} \sum_{k=2}^{n} \sum_{j=k}^{n} \left(\frac{1}{\theta}\right)^{k-j} \\
&= \frac{1}{p} \sum_{j=i}^{n-1} \frac{1-\theta^j}{1-\theta} + \frac{1-\theta^{i-1}}{q \left(\frac{1-\theta}{1-\theta}\right)} \sum_{j=2}^{n} \frac{1-(1/\theta)^{n-j+1}}{1-(1/\theta)} \\
&= \frac{1}{p(1-\theta)} \left(n-i-\theta^i \frac{1-\theta^{n-i}}{1-\theta}\right) + \frac{1-\theta^{i-1}}{q(1-\theta^{n-1})} \sum_{j=2}^{n} \frac{1-(1/\theta)^{n-j+1}}{1-(1/\theta)} \\
&= \frac{1}{p(1-\theta)} \left(n-i-\theta^i \frac{1-\theta^{n-i}}{1-\theta}\right) + \frac{1-\theta^{i-1}}{q(1-1/\theta)(1-\theta^{n-1})} \sum_{j=2}^{n} (1-(1/\theta)^{n-j+1}) \\
&= \frac{1}{p(1-\theta)} \left(n-i-\theta^i \frac{1-\theta^{n-i}}{1-\theta}\right) + \frac{1-\theta^{i-1}}{q(1-1/\theta)(1-\theta^{n-1})} \left(n-1-\frac{1}{\theta} \left(\frac{1-(1/\theta)^{n-1}}{1-1/\theta}\right)\right).
\end{align*}
$$

• If $p_{\ell} = q_{\ell} \in (0, 1/2]$ for all $\ell = 2, \dots, n-1$ then we have

$$
\begin{align*}
\mathbb{E}_i(C) &= \sum_{j=i}^{n-1} \sum_{k=1}^{j} \frac{1}{p_k} + \frac{i-1}{n-1} \sum_{j=2}^{n} \sum_{k=j}^{n} \frac{1}{q_k} \\
&= (n-i) \sum_{k=1}^{i-1} \frac{1}{p_k} + \sum_{k=i}^{n-1} \frac{n-k}{p_k} + \frac{i-1}{n-1} \sum_{k=2}^{n} \frac{k-1}{q_k} \\
&= (n-i) \sum_{k=1}^{i-1} \frac{1}{p_k} + \sum_{k=i}^{n-1} \frac{n-k}{p_k} + \frac{i-1}{n-1} \sum_{k=2}^{n-1} \frac{k-1}{p_k} + \frac{i-1}{q_n}
\end{align*}
$$

• If $p_{\ell} = q_{\ell} = p \in (0, 1/2]$ for all $\ell = 2, \dots, n-1$, we get

$$
\begin{align*}
\mathbb{E}_i(C) &= \frac{1}{p} \sum_{j=i}^{n-1} j + \frac{i-1}{p(n-1)} \sum_{j=2}^{n} n-j+1 \\
&= \frac{(n-1+i)(n-i)}{2p} + \frac{n(i-1)}{2p}.
\end{align*}
$$

5.2 Cover time distribution of the generalized n-path graph

We first consider the cover time distribution of subset $\{i+1, \dots, n\}$ when the initial state is state $i$. This distribution is obtained recursively by the following lemma.

**Lemma 22** For every $i = 1, \dots, n-2$, we have $\mathbb{P}_i\{C_{\{i+1, \dots, n\}} = k\} = 0$ for $0 \le k < n-i$ and for $k \ge n-i$,

$$
\mathbb{P}_i\{C_{\{i+1, \dots, n\}} = k\} = p_i \sum_{h=1}^{k-n+i+1} \binom{p_h^{h-1}}{1, \dots, i} \binom{1}{i, i} \mathbb{P}_{i+1}\{C_{\{i+2, \dots, n\}} = k-h\} \quad (28)
$$

with

$$
\mathbb{P}_{n-1}\{C_n = k\} = p_{n-1}\left(P_{1,...,n-1}^{h-1}\right)_{n-1,n-1}.
$$
For every $i = 3, \dots, n$, we have $\mathbb{P}_i\{C_{\{1,\dots,i-1\}} = k\} = 0$ for $0 \le k < i-1$ and for $k \ge i-1$,

$$ \mathbb{P}_i\{C_{\{1,\dots,i-1\}} = k\} = q_i \sum_{h=1}^{k-i+2} \left( P_{\{i,\dots,n\}}^{h-1} \right)_{i,i} \mathbb{P}_{i-1}\{C_{\{1,\dots,i-2\}} = k-h\} \quad (29) $$

with

$$ \mathbb{P}_2\{C_{\{1\}} = k\} = q_2 \left( P_{\{2,\dots,n\}}^{h-1} \right)_{2,2}. $$

**Proof.** From Theorem 1, we have $\mathbb{P}_i\{C_{\{i+1,\dots,n\}} = k\} = 0$ for $0 \le k < n-i$ and for $k \ge n-i$,

$$ \mathbb{P}_i\{C_{\{i+1,\dots,n\}} = k\} = \sum_{h=1}^{k-n+i+1} \sum_{j=i+1}^{n} \left( P_{\{1,\dots,i\}}^{h-1} P_{\{1,\dots,i\},\{i+1,\dots,n\}} \right)_{i,j} \mathbb{P}_j\{C_{\{i+1,\dots,n\}} \setminus \{j\} = k-h\}. $$

Observing that the only non zero entry of matrix $P_{\{1,\dots,i\},\{i+1,\dots,n\}}$ is entry $(i, i+1)$ which is equal to $p_i$, we have

$$ \left( P_{\{1,\dots,i\}}^{h-1} P_{\{1,\dots,i\},\{i+1,\dots,n\}} \right)_{i,j} = p_i (P_{\{1,\dots,i\}})_{i,i}^{h-1} 1_{\{j=i+1\}}. $$

It follows that for every $i = 1, \dots, n-2$,

$$ \mathbb{P}_i\{C_{\{i+1,\dots,n\}} = k\} = \sum_{h=1}^{k-n+i+1} p_i \left( P_{\{1,\dots,i\}}^{h-1} \right)_{i,i} \mathbb{P}_{i+1}\{C_{\{i+2,\dots,n\}} = k-h\}. $$

The initial value of this recurrence relation is obtained by taking $i = n-1$. When $i = n-1$ we obtain for $k \ge 1$ using relation (2),

$$ \mathbb{P}_{n-1}\{C_{\{n\}} = k\} = \left( P_{\{1,\dots,n-1\}}^{h-1} P_{\{1,\dots,n-1\},\{n\}} 1 \right)_i = p_{n-1} \left( P_{\{1,\dots,n-1\}}^{h-1} \right)_{n-1,n-1}. $$

In the same way, from Theorem 1, we have $\mathbb{P}_i\{C_{\{1,\dots,i-1\}} = k\} = 0$ for $0 \le k < i-1$ and for $k \ge i-1$,

$$ \mathbb{P}_i\{C_{\{1,\dots,i-1\}} = k\} = \sum_{h=1}^{k-i+2} \sum_{j=1}^{i-1} \left( P_{\{i,\dots,n\}}^{h-1} P_{\{1,\dots,i-1\},\{1,\dots,i-1\}} \right)_{i,j} \mathbb{P}_j\{C_{\{i+1,\dots,n\}} \setminus \{j\} = k-h\}. $$

The only non zero entry of matrix $P_{\{1,\dots,i-1\},\{1,\dots,i-1\}}$ is entry $(i, i-1)$ which is equal to $q_i$. We thus have

$$ \left( P_{\{i,\dots,n\}}^{h-1} P_{\{1,\dots,i-1\},\{1,\dots,i-1\}} \right)_{i,j} = q_i (P_{\{i,\dots,n\}})_{i,i}^{h-1} 1_{\{j=i-1\}}. $$

It follows that for every $i = 3, \dots, n$,

$$ \mathbb{P}_i\{C_{\{1,\dots,i-1\}} = k\} = q_i \sum_{h=1}^{k-i+2} \left( P_{\{i,\dots,n\}}^{h-1} \right)_{i,i} \mathbb{P}_{i-1}\{C_{\{1,\dots,i-2\}} = k-h\}. $$

The initial value of this recurrence relation is obtained by taking $i = 2$. When $i = 2$ we obtain for $k \ge 1$ using relation (2),

$$ \mathbb{P}_2\{C_{\{1\}} = k\} = \left( P_{\{2,\dots,n\}}^{h-1} P_{\{2,\dots,n\},\{1\}} 1 \right)_2 = q_2 \left( P_{\{2,\dots,n\}}^{h-1} \right)_{2,2}, $$

which completes the proof.

By taking $i = 1$ in relation (28), we are able to compute recursively $\mathbb{P}_1\{C = k\}$ starting from the value $\mathbb{P}_{n-1}\{C_{\{n\}} = k\}$. In the same way, by taking $i = n$ in relation (29), we are able to compute recursively $\mathbb{P}_n\{C = k\}$ starting from the value $\mathbb{P}_2\{C_{\{1\}} = k\}$. The computation of the values $(P_{\{1,\dots,i\}}^{h-1})_{i,i}$ and $(P_{\{i,\dots,n\}}^{h-1})_{i,i}$ can be easily done in the same way as previously in subsection 3.2.1.

The following theorem allows the computation of all the $\mathbb{P}_i\{C = k\}$.
**Theorem 23** For every $i = 2, \dots, n-1$, we have $\mathbb{P}_i\{C = k\} = 0$ for $0 \le k < n-1$ and for $k \ge n-1$,

$$ \mathbb{P}_i\{C = k\} = q_i \sum_{h=1}^{k-n+2} (1-p_i-q_i)^{h-1} \mathbb{P}_{i-1}\{C = k-h\} + p_i \sum_{h=1}^{k-n+2} (1-p_i-q_i)^{h-1} \mathbb{P}_{i+1}\{C = k-h\}. \quad (30) $$

**Proof.** Again, from Theorem 1, we have $\mathbb{P}_i\{C = k\} = \mathbb{P}_i\{C_{\{1,...,i-1,i+1,...,n\}} = k\} = 0$ for $0 \le k < n-1$ and for $k \ge n-1$,

$$ \mathbb{P}_i\{C_{\{1,...,i-1,i+1,...,n\}} = k\} = \sum_{h=1}^{k-n+2} \sum_{j=1, j \neq i}^{n} \left( P_{\{i\}}^{h-1} P_{\{i\}, \{1,...,i-1,i+1,...,n\}} \right)_{i,j} \mathbb{P}_j\{C_{\{1,...,i-1,i+1,...,n\} \setminus \{j\}} = k-h\}. $$

Observing that

$$ \left( P_{\{i\}}^{h-1} P_{\{i\}, \{1,...,i-1,i+1,...,n\}} \right)_{i,j} = (1-p_i-q_i)^{h-1} (q_i 1_{\{j=i-1\}} + p_i 1_{\{j=i+1\}}), $$

we get

$$ \mathbb{P}_i\{C_{\{1,...,i-1,i+1,...,n\}} = k\} = q_i \sum_{h=1}^{k-n+2} (1-p_i-q_i)^{h-1} \mathbb{P}_{i-1}\{C_{\{1,...,i-2,i+1,...,n\}} = k-h\} \\ + p_i \sum_{h=1}^{k-n+2} (1-p_i-q_i)^{h-1} \mathbb{P}_{i+1}\{C_{\{1,...,i-1,i+2,...,n\}} = k-h\}, $$

where the term $\mathbb{P}_{i-1}\{C_{\{1,...,i-2,i+1,...,n\}} = k-h\}$ is equal to $\mathbb{P}_1\{C_{\{3,...,n\}} = k-h\}$ when $i=2$ and the term $\mathbb{P}_{i+1}\{C_{\{1,...,i-1,i+2,...,n\}} = k-h\}$ is equal to $\mathbb{P}_n\{C_{\{1,...,n-2\}} = k-h\}$ when $i=n-1$. Using relation (26), we conclude that, for every $k \ge n-1$,

$$ \mathbb{P}_i\{C = k\} = q_i \sum_{h=1}^{k-n+2} (1-p_i-q_i)^{h-1} \mathbb{P}_{i-1}\{C = k-h\} + p_i \sum_{h=1}^{k-n+2} (1-p_i-q_i)^{h-1} \mathbb{P}_{i+1}\{C = k-h\}, $$

which completes the proof.

<figure><img src="image_13.png" /></figure>

It follows, using both Lemma 22 and Theorem 23, that we are able to compute easily the distribution of the cover time starting from any state $i$.

Observe that if we consider the path graph without self-loops, i.e. if $r_i = 1 - p_i - q_i = 0$ for every $i = 2, \dots, n-1$, we obtain simply, for

$$ \mathbb{P}_i\{C = k\} = q_i \mathbb{P}_{i-1}\{C = k-1\} + p_i \mathbb{P}_{i+1}\{C = k-1\}, $$

the initial and final values $\mathbb{P}_1\{C = k\}$ and $\mathbb{P}_n\{C = k\}$ being given by Lemma 22.

# 6 Conclusion

We considered in this paper both the distribution and the moments of the cover time of a Markov chain and we obtained recurrence relations for the cover time distribution of a subset of states and for its mean value. These results have been applied to particular graphs namely the generalized cycle graph, the complete graph and the generalized path graph leading to recurrence or analytic relations for the distribution and the mean value of their cover times. Further research will be to analyze other particular graphs such as the Lollipop graph, the Barbell graph or the Tadpole graph. Another issue could be the analysis of the generalized cycle graph when the $p_i$ and the $q_i$ are not constant.
References

[1] D. Aldous and J. A. Fill. *Reversible Markov Chains and Random Walks on Graphs*. Unfinished monograph. https://www.stat.berkeley.edu/aldous/RWG/book.pdf, 2002.

[2] C. Banderier and R. P. Dobrow. A generalized cover time for random walk on graphs. In *12th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC)*, 2000.

[3] U. Feige. A tight lower bound on the cover time for random walks on graphs. *Random Structures and Algorithms*, 6, 1995.

[4] U. Feige. A tight upper bound on the cover time for random walks on graphs. *Random Structures and Algorithms*, 6, 1995.

[5] S. Ikeda, I. Kubob, and M. Yamashita. The hitting and cover times of random walks on finite graphs using local degree information. *Theoretical Computer Science*, 410, 2009.

[6] A-M. Kermarrec, E. Le Merrer, B. Sericola, and G. Trédan. Second order centrality: distributed assessment of nodes importance in complex networks. *Computer Communications*, 34(5), 2011. Special issue on Complex Networks.

[7] L. Lovasz. *Random Walks on Graphs: A Survey*. Combinatorics, Paul Erdős is Eighty, volume 2. Keszthely (Hungary), 1996.

[8] R. Motowani and P. Raghavan. *Randomized Algorithms*. Cambridge University Press, New York, 1995.

[9] S. M. Ruiz. An algebraic identity leading to Wilson's theorem. *The Mathematical Gazette*, 80(489), 1996.

[10] B. Sericola. *Markov Chains. Theory, Algorithms and Applications*. Applied stochastic methods series. WILEY, 2013.