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

HAL
open science

# Hitting and cover times of the star graph and the sun graph

François Castella, Bruno Sericola

► To cite this version:

François Castella, Bruno Sericola. Hitting and cover times of the star graph and the sun graph. Centre Inria de l'Université de Rennes. 2025, pp.29. hal-05161555

HAL Id: hal-05161555

https://inria.hal.science/hal-05161555v1

Submitted on 14 Jul 2025

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.

Public Domain
# Hitting and cover times of the star graph and the sun graph

François Castella* and Bruno Sericola†

July 14, 2025

## Abstract

We consider the moments and the distribution of the hitting times and cover time of the star graph composed of $m$ arms each of length $n$. We obtain recurrence relations for the distribution and the moments of all order of both the hitting times of the leaves and the cover times for various initial states. We use the recurrence relations on the moments to analyze the asymptotic behavior of the cover times distribution when the number $m$ of arms, which may depend on the length $n$ of each arm, tends to infinity when $n$ tends to infinity. We call this new graph, composed of an infinite number of arms each of infinite length, the sun graph.

Keywords: Random walk; Hitting time; Cover time; Star graph; Sun graph.

## 1 Introduction

Random walks are widely used in applied mathematics, physics and computer science and much attention is devoted to the analysis of performance measures of random walks in graphs. Examples of such performance measures are the cover time which is the time needed to visit at least once all the nodes of the graph, or the hitting time of a particular subset of nodes which is the time needed to reach one node of the subset. Many applications of random walks on graphs are proposed in [1] as for instance the analysis of electrical networks which are detailed in [7]. Very interesting surveys on random walks on graphs are [2] and [13] while [14] additionally contains many applications in both computer science and networks. In telecommunication systems random walks are used to explore the network or to collect information. 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 [12].

It has been shown in [9] and [8] 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, for which each vertex has the same number of neighbors, it is at most $2n^2$, see [8]. In [3] the authors consider an extension of the cover time called the marking time defined as follows. When the random walk reaches node $i$, a coin is flipped and with probability $p_i$ the node $i$ is marked. The marking time is then the time needed by the walk to mark all its nodes. They give general formulas for the expected marking time of a random walk and provide asymptotics when the $p_i$'s are small. In [10], 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))$. The cover time of a discrete-time homogenous Markov chain is analyzed in [19] where general formulae for its distribution and its moments are considered with applications to particular finite graphs. The expected hitting times on the lollipop graph, which consists of a complete graph connected with a path graph, has been obtained in [5] where the authors prove that this graph achieves the maximum expected hitting time among all the $n$-vertex graphs when its clique represents

<footnote>*François Castella is with IRMAR, university of Rennes</footnote>

<footnote>†Bruno Sericola is with Inria center at university of Rennes</footnote>
2/3 of the total graph. A detailed analysis of the hitting times on this particular graph has been proposed in [6], where the authors consider the distribution, the moments and their asymptotic behavior when the number of nodes tend to infinity. Expected cover times of the star graph with different arms lengths are obtained in [15] using again the analogy with the electric networks. Nevertheless this approach only deals with expected values of hitting and cover times.

In this paper, we consider hitting times and cover times of the star graph and the sun graph. The star graph is composed of $m$ arms each of length $n$. The sun graph is an asymptotic version of the star graph which consists in an infinite number of arms each of infinite length. More precisely, we consider a star graph with $m_n$ arms each of length $n$ and we analyze the asymptotic behavior of the cover time of this graph when $m_n$ tends to infinity with $n$. This is why we call this infinite star graph the sun graph. An example of a star graph is proposed in Figure 1 and the sun graph is depicted in Figure 3. In section 2, we review the main results obtained in [19] which give general expressions for the moments and the distribution of the hitting and cover time of a Markov chain. These results will be used for the analysis of the star graph and the sun graph. We also describe the Markov chain representing the random walk on the star graph. We analyze in section 3 the hitting times of the leaves in the star graph and we show that its distribution is nothing but the hitting time of the state $n$ in the path graph which can be seen as a star graph with a single arm, see Figure 2. The hitting and cover times of the path graph have been analyzed in detail in [20]. Section 4 is devoted to the study of the cover time in the star graph. In section 4.1 we propose a simple way to compute recursively the distribution of the cover time. The moments of the cover time are obtained in section 4.2, where we first give the moments of the hitting times of a subset of leaves, which are needed to obtain the moments of the cover time. We propose a simple algorithm to compute them recursively. The asymptotic analysis of the star graph, which we call the sun graph, is provided in section 5. The number $m_n$ of arms is a function of the length $n$ of each arm and tends to infinity when $n$ tends to infinity. We obtain the asymptotic behavior of the hitting and cover times moments which are used to get the cover time distrubution of the sun graph, that is the asymptotic dustribution of the star graph. Section 6 concludes the paper.

# 2 Basic results and star graph

The basic results provided in the next section have been obtained mainly obtained in [19] for the analysis of the cover of a general Markov chain.

## 2.1 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$, that is

$$T_{\{j\}} = \inf\{n \geq 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$, that is

$$C_A = \inf\{n \geq 0 \mid A \subseteq \{X_0, \dots, X_n\}\}. \qquad (1)$$

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$, that is

$$T_A = \inf\{n \geq 0 \mid X_n \in A\}. \qquad (2)$$

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 and by $I$ the identity matrix, their dimensions 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 [18],

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

Summing (3) over all $j \in A$, we obtain, observing that $P_{A^c,A} \mathbb{1} = (I - P_{A^c}) \mathbb{1}$,

$$ \mathbb{P}\{T_A = \ell | X_0 = i\} = (P_{A^c}^{\ell-1} P_{A^c,A} \mathbb{1})_i = (P_{A^c}^{\ell-1} (I - P_{A^c}) \mathbb{1})_i. \quad (4) $$

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

$$ \mathbb{P}\{X_{T_A} = j | 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}. \quad (5) $$

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

$$ \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, \quad (6) $$

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

and from (3),

$$ \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 (8) $$

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 distribution of cover time $C = C_S$ 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\}, $$

where for any subset of states A, the cover time $C_A$ of subset A is defined in (1) and its distribution is given by the next theorem.

**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 (9) $$
**Proof.** See [19].

■

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\}}). \quad (10) $$

**Proof.** See [19].

■

## 2.2 Random walk on the star graph

We consider in this section the random walk on the star graph with $m$ equal arms each with length $n$. We denote this Markov chain by $X = \{X_k, k \in \mathbb{N}\}$. Its state space is then

$$ S = \{0\} \cup \{(a, \ell) \mid a = 1, \dots, m \text{ and } \ell = 1, \dots, n\}. $$

State 0 is the center of the star. The first component $a$ represents the arm number and the second one $\ell$ represents the level within the arm. The number of states of $S$ is equal to $mn+1$. An example of this Markov chain is represented in Figure 1 for $m=3$ and $n=4$. We first consider in the following the hitting time of the leaves which is the time needed by the Markov chain to reach the subset of states $\{(1, n), \dots, (m, n)\}$. In a second step we consider the cover time of the star graph which is the time needed by the Markov chain to reach all the states of $S$.

We analyze both the distribution and the moments of these random variables, together with their asymptotic behavior when $n$ goes to infinity.

## 3 Hitting time of the leaves

We consider the hitting time of the leaves in the star graph, that is the time needed to reach subset $S_n = \{(1, n), \dots, (m, n)\}$. According to (2), this hitting time is denoted by $T_{S_n} = \inf\{k \ge 0 \mid X_k \in S_n\}$. We introduce the following natural partition of the state space $S$ which consists of grouping together states at the same level within the star graph.

$$ S = S_0 \cup S_1 \cup \dots \cup S_n $$

where $S_0 = \{0\}$, state 0 being the center of the star and for $\ell = 1, \dots, n$, subset $S_\ell$ contains all the states at level $\ell$ in the different arms, that is

$$ S_{\ell} = \{(1, \ell), \dots, (m, \ell)\}. $$
<figure><img src="image_2.png" /><figcaption>Figure 1: Transition probabilities of the star graph.</figcaption></figure>

The number of states of $S$ is equal to $mn + 1$. The transition probability matrix of $X$ is denoted by $P$ and is represented below, using this partition, for $m = 3$ and $n = 4$ which corresponds to the graph of Figure 1.

$$ P = \begin{pmatrix}
0 & 1/3 & 1/3 & 1/3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 \\
0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 \\
0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 \\
0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 \\
0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 1/2 \\
0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
\end{pmatrix} $$
As suggested by the example above, we decompose matrix $P$ through the partition $S_0, S_1, \dots, S_n$ of the state space $S$ as follows.

$$ P = \begin{pmatrix} 0 & \frac{1}{m} \mathbf{1}^{\top} & 0 & 0 & \dots & 0 & 0 \\ \frac{1}{2} \mathbf{1} & 0 & \frac{1}{2} I & 0 & \dots & \dots & 0 \\ 0 & \frac{1}{2} I & 0 & \frac{1}{2} I & 0 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \dots & 0 & \frac{1}{2} I & 0 & \frac{1}{2} I \\ 0 & 0 & \dots & \dots & 0 & I & 0 \end{pmatrix}, \quad (11) $$

where $\top$ denotes the transpose operator.

To avoid dealing with special cases, state 0 will also be denoted as $(a, 0)$, for any value of $a = 1, \dots, m$.

It is easily checked that Markov chain $X$ is strongly lumpable with respect to the partition $S_0, S_1, \dots, S_n$ of the state space $S$, see for instance [11] or [16] or [17] on state aggregation of Markov chains. Indeed, matrix $P$ satisfies the following property. For every pair of elements $i, j \in \{0, 1, \dots, n\}$, the probability $P_{(a,i),S_j} := \sum_{b=1}^m P_{(a,i),(b,j)}$ has the same value for every $a \in \{1, \dots, m\}$. This property is easily checked on matrix $P$ with the corresponding partition. Indeed, it means that each submatrix of matrix $P$ associated with the partition is a stochastic matrix, square or not, up to a constant. It means, see for instance [11] or [16] or [17], that the process $Y = \{Y_k, k \in \mathbb{N}\}$ defined by

$$ Y_k = i \iff X_k \in S_i $$

is a Markov chain on the state space $\{0, 1, \dots, n\}$. The graph of the Markov chain $Y$ is the path graph represented in Figure 2. Its transition probability matrix is denoted by $\hat{P}$ and its non zero transition probabilities are given by

$$ \begin{cases} \hat{P}_{0,1} = 1 \text{ and } \hat{P}_{i,i+1} = 1/2 \text{ for } i = 1, \dots, n-1 \\ \hat{P}_{n,n-1} = 1 \text{ and } \hat{P}_{i,i-1} = 1/2 \text{ for } i = 1, \dots, n-1. \end{cases} $$

It follows that the hitting time $T_{S_n}$ of subset $S_n$ on the star graph has the same distribution as the hitting

<figure><img src="image_3.png" /><figcaption>Figure 2: Transition probabilities of the Markov chain $Y$ corresponding to the path graph.</figcaption></figure>

time $T_n$ of state $n$ on the path graph, where

$$ T_n = \inf\{k \ge 0 \mid Y_k = n\}. \quad (12) $$

Observe that, following definition (2), this hitting time should be denoted by $T_{\{n\}}$, but for sake of simplicity we denote it by $T_n$. The hitting times on the path graph have been analyzed in details in [20] and thus all
the results of [20] apply to the analysis of the hitting time $T_{S_n}$. These results are used in the next section to analyze the cover time of the star graph. The distributions of $T_{S_n}$ and $T_n$ are thus given, for every $(a, i) \in S$ and $k \ge 1$, by

$$ \mathbb{P}_{(a,i)}\{T_{S_n} = k\} = \left( P_{S \setminus S_n}^{k-1} (I - P_{S \setminus S_n}) \mathbf{1} \right)_{(a,i)} = (R^{k-1}(I-R)\mathbf{1})_i = \mathbb{P}_i\{T_n = k\}, \quad (13) $$

where the matrix $R$ is obtained from matrix $\hat{P}$ by deleting its last row and its last column corresponding to state $n$. Its non zero entries are thus given by

$$ \begin{cases} R_{0,1} = 1 \text{ and } R_{i,i+1} = 1/2 \text{ for } i = 1, \dots, n-2 \\ R_{i,i-1} = 1/2 \text{ for } i = 1, \dots, n-1. \end{cases} $$

Observe that the distribution of $T_{S_n}$ has the same value for every initial arm number $a = 1, \dots, m$. A simple algorithm to compute these distributions has been proposed in [20].

# 4 Cover time of the star graph

The cover time $C$ of the star graph is the time needed by Markov chain $X$ to reach all the states of $S$. The shape of the star graph implies that the cover time is also the time needed by Markov chain $X$ to reach all the leaves, that is all the states of $S_n$.

The Markov chain indeed needs to reach every individual state within $S_n$, rather than just any state within the set $S_n$. This stricter condition means that lumpability, where states are grouped together and treated as equivalent, cannot be applied here, except when we will use hitting times of subsets $S_\ell$.

## 4.1 Distribution of the cover time

The distribution of the cover time for the star graph is the time needed to reach all the states of the Markov chain $X$. It is given recursively by the following theorem. For every $a = 1, \dots, m$, we introduce the notation

$$ \Gamma(a) = \{(1, n), \dots, (a, n)\}. \quad (14) $$

This set contains the leaves of arms $1, \dots, a$. We then have $S_n = \Gamma(m)$ and $S_n \setminus \{(m, n)\} = \Gamma(m-1)$. Observe that the time needed to reach all the states of $S$ is also the time needed to reach all the leaves of the star graph, that is the time needed to reach subset $S_n$. It follows that, for every $k \ge 0$ and $(a, i) \in S \setminus S_n$, we have

$$ \mathbb{P}_{(a,i)}\{C = k\} = \mathbb{P}_{(a,i)}\{C_{S_n} = k\}. \quad (15) $$

Moreover, recall that that the distribution of the hitting time $T_n$, simply denoted by $T_n$ and which is defined by (12), satisfies (13) and has been obtained in [20]. These observations lead to the following theorem.

**Theorem 3** For every $(a, i) \in S \setminus S_n$, that is $a = 1, \dots, m$ and $i = 0, 1, \dots, n-1$, we have $\mathbb{P}_{(a,i)}\{C = k\} = 0$ if $0 \le k < n - i + 2(m-1)n$ and

$$ \mathbb{P}_{(a,i)}\{C = k\} = \sum_{h=n-i}^{k-2(m-1)n} \mathbb{P}_{(m,n)}\{C_{\Gamma(m-1)} = k-h\} \mathbb{P}_i\{T_n = h\} \quad \text{if } k \ge n - i + 2(m-1)n, $$

where the non zero values of $\mathbb{P}_{(m,n)}\{C_{\Gamma(m-1)} = k\}$ are obtained recursively, for $a = 3, \dots, n$, by

$$ \begin{cases} \mathbb{P}_{(2,n)}\{C_{\Gamma(1)} = k\} = \mathbb{P}_{(2,n)}\{T_{\{(1,n)\}} = k\}, & \text{for } k \ge 2n \\ \\ \mathbb{P}_{(a,n)}\{C_{\Gamma(a-1)} = k\} = \sum_{h=2n}^{k-2(a-2)n} \mathbb{P}_{(a-1,n)}\{C_{\Gamma(a-2)} = k-h\} \mathbb{P}_{(a,n)}\{T_{\Gamma(a-1)} = h\}, & \text{for } k \ge 2(a-1)n. \end{cases} $$
**Proof.** The shape of the star graph, see for instance figure 1, implies that, when the initial state is state $(a, i)$, the minimum number of transitions to reach all the states of $S$ is equal to $n - i + 2(m - 1)n$. We thus have

$$ \mathbb{P}_{(a,i)}\{C=k\} = 0 \quad \text{if} \quad 0 \le k < n - i + 2(m - 1)n. $$

We suppose now that $k \ge n - i + 2(m - 1)n$. We thus have, using relation (9) with $A = S_n$ and relation (15), for every $(a, i) \in S \setminus S_n$,

$$ \mathbb{P}_{(a,i)}\{C=k\} = \mathbb{P}_{(a,i)}\{C_{S_n} = k\} = \sum_{h=1}^{k-2(m-1)n} \sum_{b=1}^{m} \left( P_{S\setminus S_n}^{h-1} P_{S\setminus S_n, S_n} \right)_{(a,i),(b,n)} \mathbb{P}_{(b,n)}\{C_{S_n\setminus\{(b,n)\}} = k-h\}, $$

where we used the fact that $\mathbb{P}_{(b,n)}\{C_{S_n\setminus\{(b,n)\}} = k - h\} = 0$ for $h > k - 2(m - 1)n$.

Observe that the symmetry of the star graph implies that the probability $\mathbb{P}_{(b,n)}\{C_{S_n\setminus\{(b,n)\}} = k - h\}$ has the same value for every $b = 1, \dots, m$. By taking $b = m$, we get for $k \ge n - i + 2(m - 1)n$,

$$ \mathbb{P}_{(a,i)}\{C=k\} = \sum_{h=1}^{k-2(m-1)n} \mathbb{P}_{(m,n)}\{C_{S_n\setminus\{(m,n)\}} = k-h\} \sum_{j=1}^{m} \left( P_{S\setminus S_n}^{h-1} P_{S\setminus S_n, S_n} \right)_{(a,i),(j,n)}. $$

Using relations (3) and (4), this yields

$$ \mathbb{P}_{(a,i)}\{C=k\} = \sum_{h=1}^{k-2(m-1)n} \mathbb{P}_{(m,n)}\{C_{S_n\setminus\{(m,n)\}} = k-h\} \left( P_{S\setminus S_n}^{h-1} (I - P_{S\setminus S_n})1 \right)_{(a,i)}. $$

Relation (13) leads to

$$ \begin{aligned} \mathbb{P}_{(a,i)}\{C=k\} &= \sum_{h=1}^{k-2(m-1)n} \mathbb{P}_{(m,n)}\{C_{S_n\setminus\{(m,n)\}} = k-h\} (R^{h-1}(I-R)1)_i \\ &= \sum_{h=n-i}^{k-2(m-1)n} \mathbb{P}_{(m,n)}\{C_{S_n\setminus\{(m,n)\}} = k-h\} \mathbb{P}_i\{T_n = h\}, \end{aligned} $$

where this last sum is for $h \ge n - i$ because $\mathbb{P}_i\{T_n = h\} = 0$ for $h < n - i$. Observe that the distribution of the cover time $C$ has the same value for every initial arm number $a = 1, \dots, m$. In this last expression the distribution of $T_n$ is known and an algorithm to compute it can be found in [20].

It now remains to analyze the distribution of $C_{S_n\setminus\{(m,n)\}}$ given that the initial state is the leaf state $(m, n)$. In other words, we have to compute $\mathbb{P}_{(m,n)}\{C_{S_n\setminus\{(m,n)\}} = k\}$, for every $k \ge 2(m - 1)n$.

By definition of the sets $\Gamma(a)$ in (14), we have $S_n = \Gamma(m)$, $S_n \setminus \{(m, n)\} = \Gamma(m - 1)$ and thus

$$ \mathbb{P}_{(m,n)}\{C_{S_n\setminus\{(m,n)\}} = k\} = \mathbb{P}_{(m,n)}\{C_{\Gamma(m-1)} = k\}. $$

Applying relation (9) with $A = \Gamma(a)$, we obtain, for every $a = 3, \dots, m$, $\mathbb{P}_{(a,n)}\{C_{\Gamma(a-1)} = k\} = 0$ if $0 \le k < 2(a - 1)n$ and for $k \ge 2(a - 1)n$,

$$ \mathbb{P}_{(a,n)}\{C_{\Gamma(a-1)} = k\} = \sum_{h=1}^{k-2(a-2)n} \sum_{j=1}^{a-1} \left( P_{S\setminus\Gamma(a-1)}^{h-1} P_{S\setminus\Gamma(a-1), \Gamma(a-1)} \right)_{(a,n),(j,n)} \mathbb{P}_{(j,n)}\{C_{\Gamma(a-1)\setminus\{(j,n)\}} = k-h\}, $$

where we used the fact that $\mathbb{P}_{(j,n)}\{C_{\Gamma(a-1)\setminus\{(j,n)\}} = k - h\} = 0$ for $h > k - 2(a - 2)n$.

The symmetry of the star graph implies that the probability $\mathbb{P}_{(j,n)}\{C_{\Gamma(a-1)\setminus\{(j,n)\}} = k - h\}$ has the same value for every $(j, n) \in \Gamma(a - 1)$. So we can write, for every $k \ge 2(a - 1)n$ and $a = 3, \dots, m$,

$$ \mathbb{P}_{(a,n)}\{C_{\Gamma(a-1)} = k\} = \sum_{h=1}^{k-2(a-2)n} \mathbb{P}_{(a-1,n)}\{C_{\Gamma(a-2)} = k-h\} \sum_{j=1}^{a-1} \left( P_{S\setminus\Gamma(a-1)}^{h-1} P_{S\setminus\Gamma(a-1), \Gamma(a-1)} \right)_{(a,n),(j,n)}. $$
Using relations (3) and (4), we obtain for every $a = 3, \dots, m$ and $k \ge 2(a-1)n$,

$$ 
\begin{aligned}
\mathbb{P}_{(a,n)}\{C_{\Gamma(a-1)} = k\} &= \sum_{h=1}^{k-2(a-2)n} \mathbb{P}_{(a-1,n)}\{C_{\Gamma(a-2)} = k-h\} \left(P_{S\setminus\Gamma(a-1)}^{h-1}(I - P_{S\setminus\Gamma(a-1)})\mathbb{1}\right)_{(a,n)} \\
&= \sum_{h=2n}^{k-2(a-2)n} \mathbb{P}_{(a-1,n)}\{C_{\Gamma(a-2)} = k-h\} \mathbb{P}_{(a,n)}\{T_{\Gamma(a-1)} = h\}.
\end{aligned}
$$

Indeed, the time needed to reach subset $\Gamma(a-1)$, starting from state $(a, n)$, is greater than or equal to $2n$. The recurrence relation starts with the value $a=2$, which gives, for $k \ge 2n$

$$ \mathbb{P}_{(2,n)}\{C_{\Gamma(1)} = k\} = \mathbb{P}_{(2,n)}\{C_{\{(1,n)\}} = k\} = \mathbb{P}_{(2,n)}\{T_{\{(1,n)\}} = k\}, $$

which completes the proof.

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

This theorem shows that the distribution of the cover time can be easily computed if both distributions of $T_{\Gamma(a-1)}$ and $T_n$ are known. Recall that $T_{\Gamma(a-1)}$ is defined on Markov chain $X$ by (2) with $A = \Gamma(a-1)$ and $T_n$ is defined on Markov chain $Y$ by (12). The distribution $T_n$ has been obtained in [20] on the path graph. Concerning the distribution of $T_{\Gamma(a-1)}$, for $a = 2, \dots, m$ on Markov chain $X$, we cannot use the argument of lumpability because Markov chain $X$ is not strongly lumpable with respect to the partition $S_0, S_1, \dots, S_{n-1}, S_n \setminus \Gamma(a-1)$. So we cannot use Markov chain $Y$ to calculate the probabilities $\mathbb{P}_{(a,n)}\{T_{\Gamma(a-1)} = k\}$. We can proceed as follows on Markov chain $X$. Recall first that

$$ \mathbb{P}_{(a,n)}\{T_{\Gamma(a-1)} = k\} = \left(P_{S\setminus\Gamma(a-1)}^{k-1}(I - P_{S\setminus\Gamma(a-1)})\mathbb{1}\right)_{(a,n)}. $$

We introduce the column vector $U^{(k)}$ defined by

$$ U^{(k)} = P_{S\setminus\Gamma(a-1)}^{k-1}(I - P_{S\setminus\Gamma(a-1)})\mathbb{1}. \qquad (16) $$

We decompose this vector using the partition $S_0, S_1, \dots, S_{n-1}, S_n \setminus \Gamma(a-1)$ of the subset $S \setminus \Gamma(a-1)$. We thus write

$$ U^{(k)} = (U_0(k), U_1(k), \dots, U_{n-1}(k), U_n(k)), $$

where $U_0(k)$ has dimension 1, $U_i(k)$ has dimension $m$ for $i = 1, \dots, n-1$ and $U_n(k)$ has dimension $m-a+1$. For $k=1$, we have $U^{(1)} = (I - P_{S\setminus\Gamma(a-1)})\mathbb{1}$ that is

$$ U_0^{(1)} = 0, U_1^{(1)} = \dots = U_{n-2}^{(1)} = 0, U_{n-1}^{(1)} = (1/2, \dots, 1/2, 0, \dots, 0) \text{ and } U_n^{(1)} = 0. $$

Observe that column vector $U_{n-1}^{(1)}$ has $a-1$ components equal to $1/2$ and $m-a+1$ components equal to 0. We introduce the $(m, m-a+1)$ matrix $B$ defined by

$$ B = \begin{pmatrix} 0 \\ I \end{pmatrix} $$

in which 0 is the $(a-1, m-a+1)$ null matrix and $I$ is, here, the $m-a+1$ dimensional identity matrix. Matrix $B/2$ (resp. $B^\top$) contains the transition probabilities from states of $S_{n-1}$ (resp. $S_n \setminus \Gamma(a-1)$) to states of $S_n \setminus \Gamma(a-1)$ (resp. $S_{n-1}$). Using relation (16) and the decomposition of matrix $P_{S\setminus\Gamma(a-1)}$ which is as in (11) but with $B/2$ in the last column instead of $I/2$ and with $B^\top$ in the last row instead of $I$, we obtain

$$ 
\left\{
\begin{aligned}
U_0(k) &= \frac{1}{m} \mathbb{1}^\top U_1(k-1) \\
U_i(k) &= \frac{1}{2} U_{i-1}(k-1) + \frac{1}{2} U_{i+1}(k-1) \\
U_{n-1}(k) &= \frac{1}{2} U_{n-2}(k-1) + \frac{1}{2} B U_n(k-1) \\
U_n(k) &= B^\top U_{n-1}(k-1).
\end{aligned}
\right.
$$
We analyze in the next section all the moments of the cover time.

## 4.2 Moments of the cover time

The moments of the cover time for a general Markov chain are given by relation (10). Applying this relation, with $A = S_n$ and $i = 0$, we obtain for $r \ge 1$,

$$ \mathbb{E}_0(C^r) = \mathbb{E}_0(C_{S_n}^r) = \mathbb{E}_0(T_{S_n}^r) + \sum_{a=1}^{m} \sum_{h=1}^{r} \binom{r}{h} \mathbb{E}_{(a,n)}(C_{S_n \setminus \{(a,n)\}}^h) \mathbb{E}_0(T_{S_n}^{r-h} 1_{\{X_{T_{S_n}} = (a,n)\}}). $$

The symmetry of the star graph implies that $\mathbb{E}_{(a,n)}(C_{S_n \setminus \{(a,n)\}}^h)$ has the same value for every $a = 1, \dots, m$. By taking $a = m$, $\mathbb{E}_{(a,n)}(C_{S_n \setminus \{(a,n)\}}^h) = \mathbb{E}_{(m,n)}(C_{S_n \setminus \{(m,n)\}}^h)$. It follows that

$$ \begin{aligned} \mathbb{E}_0(C_{S_n}^r) &= \mathbb{E}_0(T_{S_n}^r) + \sum_{h=1}^r \binom{r}{h} \mathbb{E}_{(m,n)}(C_{S_n \setminus \{(m,n)\}}^h) \sum_{a=1}^m \mathbb{E}_0(T_{S_n}^{r-h} 1_{\{X_{T_{S_n}} = (a,n)\}}) \\ &= \mathbb{E}_0(T_{S_n}^r) + \sum_{h=1}^r \binom{r}{h} \mathbb{E}_{(m,n)}(C_{S_n \setminus \{(m,n)\}}^h) \mathbb{E}_0(T_{S_n}^{r-h}). \end{aligned} $$

Relation 13 tells us that the hitting time $T_{S_n}$ on Markov chain $X$ and the hitting time $T_n$ on Markov chain $Y$ have the same distribution. Thus we have, since $S_n \setminus \{(m,n)\} = \Gamma(m-1)$,

$$ \mathbb{E}_0(C^r) = \mathbb{E}_0(T_n^r) + \sum_{h=1}^{r} \binom{r}{h} \mathbb{E}_{(m,n)}(C_{\Gamma(m-1)}^h) \mathbb{E}_0(T_n^{r-h}). \quad (17) $$

The moments of $T_n$ have been obtained in [20]. We thus concentrate our attention on the analysis of the cover time of subset $\Gamma(m-1)$ when the initial state is state $(m, n)$. The moments of this cover time are obtained from the moments of the cover time of subset $\Gamma(m-2)$, and so on, as follows. Using again relation (10), with $A = \Gamma(a-1)$ and initial state $(a, n)$, and using the symmetry of the star graph, we obtain for $r \ge 1$ and $a = 3, \dots, m$

$$ \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^r) = \mathbb{E}_{(a,n)}(T_{\Gamma(a-1)}^r) + \sum_{h=1}^{r} \binom{r}{h} \mathbb{E}_{(a-1,n)}(C_{\Gamma(a-2)}^h) \mathbb{E}_{(a,n)}(T_{\Gamma(a-1)}^{r-h}) \quad (18) $$

with initial value

$$ \mathbb{E}_{(2,n)}(C_{\Gamma(1)}^r) = \mathbb{E}_{(2,n)}(C_{(1,n)}^r) = \mathbb{E}_{(2,n)}(T_{(1,n)}^r) = \mathbb{E}_{(2,n)}(T_{\Gamma(1)}^r). $$

Observe that extracting the term $\mathbb{E}_{(a-1,n)}(C_{\Gamma(a-2)}^r)$ in the right hand side of (18), we easily get, for $r \ge 1$ and $a = 2, \dots, m$

$$ \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^r) = \sum_{k=2}^{a} \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^r) + \sum_{h=1}^{r-1} \binom{r}{h} \sum_{k=3}^{a} \mathbb{E}_{(k-1,n)}(C_{\Gamma(k-2)}^h) \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^{r-h}). \quad (19) $$

In order to calculate these moments recursively, we need to evaluate the moments of the hitting times $\mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^r)$, for $r \ge 1$ and $k = 2, \dots, m$. These moments are the moments of the hitting time of the subset of leaves $\Gamma(k-1)$ when the initial state is leave $(k, n)$. They are analyzed in the following section.
### 4.2.1 Moments of the hitting times of a subset of leaves

To analyze these moments we use the following partition of the state space

$$S = M_0 \cup M_1 \cdots \cup M_m,$$

where $M_0 = \{0\}$, state 0 being the center of the star and $M_k$ contains the states of the $k$th arm of the star, that is

$$M_k = \{(k, 1), \dots, (k, n)\}.$$

The transition probability matrix $P$ of $X$ is represented below using this partition for $m = 3$ and $n = 4$ according to the graph of Figure 1.

$$P = \begin{pmatrix}
0 & 1/3 & 0 & 0 & 0 & 1/3 & 0 & 0 & 0 & 1/3 & 0 & 0 & 0 \\
1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
\end{pmatrix} . \quad (20)$$

As suggested by this example, we decompose matrix $P$ through the partition $M_0, M_1, \dots, M_m$ of the state space $S$ as follows.

$$P = \begin{pmatrix}
0 & \frac{1}{m}c & \frac{1}{m}c & \cdots & \frac{1}{m}c & \frac{1}{m}c \\
\frac{1}{2}c^{\top} & H & 0 & \cdots & \cdots & 0 \\
\frac{1}{2}c^{\top} & 0 & H & 0 & \cdots & 0 \\
\vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\
\frac{1}{2}c^{\top} & 0 & \cdots & 0 & H & 0 \\
\frac{1}{2}c^{\top} & 0 & \cdots & \cdots & 0 & H
\end{pmatrix}, \quad (21)$$

where $\top$ denotes the transpose operator, $c$ is the unit row vector defined by $c = (1, 0, \dots, 0)$ whose dimension is $n$ and $H$ is the $(n, n)$ matrix whose non zero entries are given by

$$H_{i,i+1} = 1/2 \text{ for } i = 1, \dots, n-1, H_{i,i-1} = 1/2 \text{ for } i = 2, \dots, n-1 \text{ and } H_{n,n-1} = 1.$$

The hitting time $T_{\Gamma(k-1)}$ is the time needed by Markov chain $X$ to reach the subset of states $\Gamma(k-1) = \{(1, n), \dots, (k-1, n)\}$. The general result obtained in Theorem 1 of [6] implies that for every $k = 2, \dots, m$ and $r \ge 1$, we have

$$\mathbb{E}_{(k,n)} (T_{\Gamma(k-1)}^r) = \sum_{\ell=1}^{r} c_{r,\ell} ((I - P_{S\setminus\Gamma(k-1)})^{-\ell} 1)_{(k,n)}, \quad (22)$$
where, for every $\ell = 1, \dots, r$, the coefficients $c_{r,\ell}$ are given by

$$c_{r,\ell} = (-1)^r \sum_{j=1}^{\ell} (-1)^j \binom{\ell}{j} j^r.$$

The matrix $P_{S\setminus\Gamma(k-1)}$ is the submatrix obtained from matrix $P$ given in (21) by deleting all the rows and columns corresponding to states of $\Gamma(k-1)$. If we consider the example of matrix $P$ given by (20) for $m=3$ and $n=4$, when $k=3$ the matrix $P_{S\setminus\Gamma(2)}$ is obtained by deleting the rows and columns corresponding to states $(1, n)$ and $(2, n)$, that is

$$P_{S\setminus\Gamma(2)} = \begin{pmatrix}
0 & 1/3 & 0 & 0 & 1/3 & 0 & 0 & 1/3 & 0 & 0 & 0 \\
1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
\end{pmatrix}.$$

More generally, matrix $P_{S\setminus\Gamma(k-1)}$ can be written through the partition

$$M_0, M_1 \setminus \{(1, n)\}, \dots, M_{k-1} \setminus \{(k-1, n)\}, M_k, \dots, M_m \quad (23)$$

of the state space $S$ as follows.

$$P_{S\setminus\Gamma(k-1)} = \begin{pmatrix}
0 & \frac{1}{m}c_1 & \cdots & \frac{1}{m}c_1 & \frac{1}{m}c_1 & \cdots & \frac{1}{m}c_1 \\
\frac{1}{2}c_1^\top & Q & \cdots & 0 & 0 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
\frac{1}{2}c_1^\top & 0 & \cdots & Q & 0 & \cdots & 0 \\
\frac{1}{2}c_1^\top & 0 & \cdots & 0 & H & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
\frac{1}{2}c_1^\top & 0 & \cdots & 0 & 0 & \cdots & H
\end{pmatrix}, \quad (24)$$

where, as usual, $\top$ denotes the transpose operator, $c_1$ is the unit row vector defined by $c_1 = (1, 0, \dots, 0)$ whose dimension is $n-1$ and $Q$ is the $(n-1, n-1)$ matrix whose non zero entries are given by

$$Q_{i,i+1} = 1/2 \text{ for } i = 1, \dots, n-2, Q_{i,i-1} = 1/2 \text{ for } i = 2, \dots, n-1.$$

The number of matrices $Q$ in the diagonal is equal to $k-1$ and the number of matrices $H$ in the diagonal is equal $m-k+1$. From relation (22), we need to evaluate the quantities $((I - P_{S\setminus\Gamma(k-1)})^{-\ell}1)_{(k,n)}$ for every
ℓ ≥ 1 and k = 2 , . . . , m . We introduce the notation W ( ℓ $^{)}$( n ) = ( I − P$_{S}$$_{\Gamma}$$_{(}$$_{k}$$_{−}$$_{1)}$ ) − ℓ 1 . This column vector can be decomposed through the partition (23) as

$$
\mathcal{W}^{(\ell)}(n) = (w_0^{(\ell)}(n), U_1^{(\ell)}(n), \dots, U_{k-1}^{(\ell)}(n), V_k^{(\ell)}(n), \dots, V_m^{(\ell)}(n))
$$

where w ( ℓ ) 0 ( n ) is a scalar, U ( ℓ ) 1 ( n ) , . . . , U ( ℓ ) k − 1 ( n ) are column vectors of dimension n − 1 and V ( ℓ ) k ( n ) , . . . , V ( ℓ ) m ( n ) are column vectors of dimension n . By definition of W ( ℓ $^{)}$( n ) , we have W (0) ( n ) = 1 and, for ℓ ≥ 1 , W ( ℓ $^{)}$( n ) = ( I − P$_{S}$$_{\Gamma}$$_{(}$$_{k}$$_{−}$$_{1)}$ ) − 1 W ( ℓ − 1 $^{)}$( n ) . This can be written as

$$
\mathcal{W}^{(\ell)}(n) - P_{S \setminus \Gamma(k-1)} \mathcal{W}^{(\ell)}(n) = \mathcal{W}^{(\ell-1)}(n)
$$

or equivalently, using representation (24) of matrix P$_{S}$$_{\Gamma}$$_{(}$$_{k}$$_{−}$$_{1)}$ ,

$$
\left\{
\begin{array}{l}
w_0^{(\ell)}(n) - \frac{1}{m} c_1 \sum_{j=1}^{k-1} U_j^{(\ell)}(n) - \frac{1}{m} c \sum_{j=k}^{m} V_j^{(\ell)}(n) = w_0^{(\ell-1)}(n) \\
\\
U_j^{(\ell)}(n) - \frac{1}{2} c_1^\top w_0^{(\ell)}(n) - Q U_j^{(\ell)}(n) = U_j^{(\ell-1)}(n), \text{ for } j = 1, \dots, k-1 \\
\\
V_j^{(\ell)}(n) - \frac{1}{2} c^\top w_0^{(\ell)}(n) - H V_j^{(\ell)}(n) = V_j^{(\ell-1)}(n), \text{ for } j = k, \dots, m.
\end{array}
\right.
\tag{25}
$$

Since U (0) j ( n ) = 1 for every j = 1 , . . . , k − 1 and V (0) j ( n ) = 1 for every j = k , . . . , m , we deduce recursively that for every ℓ ≥ 0, we have

$$
U_1^{(\ell)}(n) = \dots = U_{k-1}^{(\ell)}(n) \quad \text{and} \quad V_k^{(\ell)}(n) = \dots = V_m^{(\ell)}(n).
$$

To simplify the notation we write U ( ℓ $^{)}$( n ) = U ( ℓ ) 1 ( n ) = · · · = U ( ℓ ) k − 1 ( n ) and V ( ℓ $^{)}$( n ) = V ( ℓ ) k ( n ) = · · · = V ( ℓ ) m ( n ) with U ( ℓ $^{)}$( n ) = ( u ( ℓ ) 1 ( n ) , . . . , u ( ℓ ) k − 1 ( n ) ) and V ( ℓ $^{)}$( n ) = ( v ( ℓ ) 1 ( n ) , . . . , v ( ℓ ) k ( n ) ) . Observe that all the entries w ( ℓ ) 0 ( n ) , u ( ℓ ) i ( n ) for i = 1 , . . . , n − 1 and v ( ℓ ) i ( n ) for i = 1 , . . . , n also depend on the parameters k and m , even if they are skipped in the notation to simplify the writing. With these notations, relation (22) can be written, for every k = 2 , . . . , m and r ≥ 1, as

$$
\mathbb{E}_{(k,n)} (T_{\Gamma(k-1)}^r) = \sum_{\ell=1}^{r} c_{r,\ell} \left( (I - P_{S\setminus\Gamma(k-1)})^{-\ell} 1 \right)_{(k,n)} = \sum_{\ell=1}^{r} c_{r,\ell} v_n^{(\ell)}(n). \quad (26)
$$

Recall that the quantities v ( ℓ ) n ( n ) also depend on both k and m . They are obtained recursively by the following theorem.

Theorem 4 For every n ≥ 1 , ℓ ≥ 1 , m ≥ 2 and k = 2 , . . . , m , we have

$$
\begin{align*}
w_0^{(\ell)}(n) &= \frac{mn}{k-1} w_0^{(\ell-1)}(n) + 2 \sum_{j=1}^{n-1} (n-j) u_j^{(\ell-1)}(n) + n \left( \frac{m}{k-1} - 1 \right) \left( 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right) \\
u_i^{(\ell)}(n) &= \frac{(n-i)w_0^{(\ell)}(n)}{n} + \frac{2i}{n} \sum_{j=1}^{n-1} (n-j) u_j^{(\ell-1)}(n) - 2 \sum_{j=1}^{i-1} (i-j) u_j^{(\ell-1)}(n), \quad \text{for } i=1, \dots, n-1 \\
v_i^{(\ell)}(n) &= w_0^{(\ell)}(n) + i \left( 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right) - 2 \sum_{j=1}^{i-1} (i-j) v_j^{(\ell-1)}(n), \quad \text{for } i=1, \dots, n
\end{align*}
$$

with initial values w (0) 0 ( n ) = 1 , u (0) i ( n ) = 1 for i = 0 , . . . , n − 1 and v (0) i ( n ) = 1 for i = 0 , . . . , n .
**Proof.** Since $U^{(\ell)}(n) = U_1^{(\ell)}(n) = \cdots = U_{k-1}^{(\ell)}(n)$ and $V^{(\ell)}(n) = V_k^{(\ell)}(n) = \cdots = V_m^{(\ell)}(n)$ with $U^{(\ell)}(n) = (u_1^{(\ell)}(n), \dots, u_{n-1}^{(\ell)}(n))$ and $V^{(\ell)}(n) = (v_1^{(\ell)}(n), \dots, v_n^{(\ell)}(n))$ the linear system (25) can be written as

$$w_0^{(\ell)}(n) - \frac{k-1}{m} u_1^{(\ell)}(n) - \frac{m-k+1}{m} v_1^{(\ell)}(n) = w_0^{(\ell-1)}(n). \quad (27)$$

$$ \left\{ \begin{array}{l} u_1^{(\ell)}(n) - \frac{1}{2}w_0^{(\ell)}(n) - \frac{1}{2}u_2^{(\ell)}(n) = u_1^{(\ell-1)}(n) \\[1em] u_i^{(\ell)}(n) - \frac{1}{2}u_{i-1}^{(\ell)}(n) - \frac{1}{2}u_{i+1}^{(\ell)}(n) = u_i^{(\ell-1)}(n), \text{ for } i=2, \dots, n-2 \\[1em] u_{n-1}^{(\ell)}(n) - \frac{1}{2}u_{n-2}^{(\ell)}(n) = u_{n-1}^{(\ell-1)}(n). \end{array} \right. \quad (28) $$

$$ \left\{ \begin{array}{l} v_1^{(\ell)}(n) - \frac{1}{2}w_0^{(\ell)}(n) - \frac{1}{2}v_2^{(\ell)}(n) = v_1^{(\ell-1)}(n) \\[1em] v_i^{(\ell)}(n) - \frac{1}{2}v_{i-1}^{(\ell)}(n) - \frac{1}{2}v_{i+1}^{(\ell)}(n) = v_i^{(\ell-1)}(n), \text{ for } i=2, \dots, n-1 \\[1em] v_n^{(\ell)}(n) - v_{n-1}^{(\ell)}(n) = v_n^{(\ell-1)}(n). \end{array} \right. \quad (29) $$

Using Lemma 11 in appendix A with $\theta_0 = w_0^{(\ell)}(n)$ and $\theta_i = u_i^{(\ell-1)}(n)$ for $i = 1, \dots, n-1$, the solution to the linear system (28) is

$$u_i^{(\ell)}(n) = \frac{(n-i)w_0^{(\ell)}(n)}{n} + \frac{2i}{n} \sum_{j=1}^{n-1} (n-j)u_j^{(\ell-1)}(n) - 2 \sum_{j=1}^{i-1} (i-j)u_j^{(\ell-1)}(n), \quad \text{for } i=1, \dots, n-1.$$

In the same way, using Lemma 12 with $\theta_0 = w_0^{(\ell)}(n)$ and $\theta_i = u_i^{(\ell-1)}(n)$ for $i = 1, \dots, n$, the solution of linear system (29) is

$$v_i^{(\ell)}(n) = w_0^{(\ell)}(n) + i \left( 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right) - 2 \sum_{j=1}^{i-1} (i-j) v_j^{(\ell-1)}(n).$$

Putting these solutions with index $i=1$ in relation (27) leads to

$$ \begin{aligned} w_0^{(\ell)}(n) &= w_0^{(\ell-1)}(n) + \frac{k-1}{m} u_1^{(\ell)}(n) + \frac{m-k+1}{m} v_1^{(\ell)}(n) \\ &= w_0^{(\ell-1)}(n) + \frac{k-1}{m} \left[ \frac{(n-1)w_0^{(\ell)}(n)}{n} + \frac{2}{n} \sum_{j=1}^{n-1} (n-j)u_j^{(\ell-1)}(n) \right] \\ &\quad + \frac{m-k+1}{m} \left[ w_0^{(\ell)}(n) + 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right]. \end{aligned} $$

This yields

$$w_0^{(\ell)}(n) = \frac{mn}{k-1} w_0^{(\ell-1)}(n) + 2 \sum_{j=1}^{n-1} (n-j) u_j^{(\ell-1)}(n) + n \left( \frac{m}{k-1} - 1 \right) \left( 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right)$$

which completes the proof. ■
The formal expressions of the first four moments $\mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^r)$ which are given by relation (26) are the following.

$$
\left.
\begin{aligned}
\mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}) &= v_n^{(1)}(n) = \frac{2mn^2}{k-1} \\
\mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^2) &= -v_n^{(1)}(n) + 2v_n^{(2)}(n) = \frac{8m^2n^4}{(k-1)^2} - \frac{4mn^2(2n^2+1)}{3(k-1)} \\
\mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^3) &= v_n^{(1)}(n) - 6v_n^{(2)}(n) + 6v_n^{(3)}(n) \\
&= \frac{48m^3n^6}{(k-1)^3} - \frac{16m^2n^4(2n^2+1)}{(k-1)^2} + \frac{8mn^2(4n^4+10n^2+1)}{15(k-1)} \\
\mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^4) &= -v_n^{(1)}(n) + 14v_n^{(2)}(n) - 36v_n^{(3)}(n) + 24v_n^{(4)}(n) \\
&= \frac{384m^4n^8}{(k-1)^4} - \frac{192m^3n^6(2n^2+1)}{(k-1)^3} + \frac{32m^2n^4(2n^2+3)(6n^2+1)}{5(k-1)^2} \\
&\qquad - \frac{16mn^2(8n^6+56n^4+42n^2-1)}{105(k-1)}.
\end{aligned}
\right\}
\quad (30)
$$

We give in the next section the formal expressions of the first three moments of the cover time of the star graph when the initial state is state 0.

### 4.2.2 First three moments of the cover time

The evaluation of the moments of the cover time is based on relations (19) and (17). The first three moments are given by the following theorem. Observe that the first moment, that is the expected cover time, has already been obtained in Palacios [15]. The proof proposed here is different and is needed to get expressions of the other moments. We first introduce for every $\ell \ge 1$ the harmonic series $h_\ell$ defined by

$$h_{\ell} = \sum_{j=1}^{\ell} \frac{1}{j}.$$

**Theorem 5** For every $n \ge 1$ and $m \ge 2$, we have

$$
\begin{aligned}
\mathbb{E}_0(C) &= (2mh_m - 1)n^2 \\
\mathbb{E}_0(C^2) &= \frac{n^2(5n^2 - 2)}{3} + \frac{4mn^2(n^2 - 1)h_{m-1}}{3} + 8m^2n^4 \sum_{k=1}^{m-1} \frac{h_k}{k} \\
\mathbb{E}_0(C^3) &= \frac{n^2(61n^4 - 50n^2 + 4)}{15} + \left( \frac{62mn^6}{15} - \frac{8mn^4}{3} + \frac{8mn^2}{15} \right) h_{m-1} - 8m^2n^4(n^2 + 2) \sum_{k=1}^{m-1} \frac{h_k}{k} \\
&\quad + 48m^3n^6 \left( h_{m-1} \sum_{k=1}^{m-1} \frac{h_k}{k} - \sum_{k=1}^{m-1} \frac{h_k^2}{k} + \sum_{k=1}^{m-1} \frac{h_k}{k^2} \right).
\end{aligned}
$$

**Proof.** From (19) with $r = 1$ and (30), we have for $a = 2, \dots, m$,

$$\mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}) = \sum_{k=2}^{a} \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}) = 2mn^2 \sum_{k=2}^{a} \frac{1}{a-1} = 2mn^2h_{a-1}. \quad (31)$$
It has been shown in [20] that $\mathbb{E}_0(T_n) = n^2$ and thus using (17) and (30), we obtain,

$$ \mathbb{E}_0(C) = n^2 + \mathbb{E}_{(m,n)}(C_{\Gamma(m-1)}) = n^2 + 2mn^2h_{m-1} = (2mh_m - 1)n^2, $$

which is the result obtained in [15].

For the second moment, we use (19) with $r = 2$. We then have for $a = 2, \dots, m$,

$$ \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^2) = \sum_{k=2}^{a} \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^2) + 2 \sum_{k=3}^{a} \mathbb{E}_{(k-1,n)}(C_{\Gamma(k-2)}) \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}). $$

Using (30) and (31), we obtain

$$ \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^2) = \frac{8m^2n^4}{(k-1)^2} - \frac{4mn^2(2n^2+1)}{3(k-1)} $$

and

$$ \mathbb{E}_{(k-1,n)}(C_{\Gamma(k-2)}) \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}) = 4mn^2h_{k-2} \frac{2mn^2}{k-1} = \frac{4m^2n^4h_{k-2}}{k-1}. $$

This yields, for $a = 2, \dots, m$

$$ \begin{aligned} \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^2) &= -\frac{4mn^2(2n^2+1)}{3} \sum_{k=2}^{a} \frac{1}{k-1} + 8m^2n^4 \sum_{k=2}^{a} \frac{1}{(k-1)^2} + 8m^2n^4 \sum_{k=3}^{a} \frac{h_{k-2}}{k-1} \\ &= -\frac{4mn^2(2n^2+1)}{3} h_{a-1} + 8m^2n^4 \left( \sum_{k=2}^{a-1} \frac{h_{k-1}}{k} + \sum_{k=1}^{a-1} \frac{1}{k^2} \right). \end{aligned} $$

Observing that

$$ \sum_{k=2}^{a-1} \frac{h_{k-1}}{k} + \sum_{k=1}^{a-1} \frac{1}{k^2} = \sum_{k=1}^{a-1} \frac{h_k}{k}, $$

we get

$$ \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^2) = -\frac{4mn^2(2n^2+1)}{3}h_{a-1} + 8m^2n^4 \sum_{k=1}^{a-1} \frac{h_k}{k}. \quad (32) $$

From [20], we have $\mathbb{E}_0(T_n^2) = n^2(5n^2 - 2)/3$ and thus relation (17) with $r = 2$ becomes

$$ \begin{aligned} \mathbb{E}_0(C^2) &= \frac{n^2(5n^2 - 2)}{3} + 4n^4(mh_m - 1) + \mathbb{E}_{(m,n)}(C_{S_n \setminus \{(m,n)\}}^2) \\ &= \frac{n^2(5n^2 - 2)}{3} + 4n^4(mh_m - 1) - \frac{4mn^2(2n^2 + 1)}{3}h_{m-1} + 8m^2n^4 \sum_{k=1}^{m-1} \frac{h_k}{k} \\ &= \frac{n^2(5n^2 - 2)}{3} + \frac{4mn^2(n^2 - 1)h_{m-1}}{3} + 8m^2n^4 \sum_{k=1}^{m-1} \frac{h_k}{k}. \end{aligned} $$

For the third moment, we use (19) with $r = 3$. We then have for $a = 2, \dots, m$,

$$ \begin{aligned} \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^3) = \sum_{k=2}^{a} \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^3) + 3 \sum_{k=3}^{a} \mathbb{E}_{(k-1,n)}(C_{\Gamma(k-2)}) \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^2) \\ + 3 \sum_{k=3}^{a} \mathbb{E}_{(k-1,n)}(C_{\Gamma(k-2)}^2) \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}). \end{aligned} \quad (33) $$
Using (30), (31) and (32), we have

$$ \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^3) = \frac{48m^3n^6}{(k-1)^3} - \frac{16m^2n^4(2n^2+1)}{(k-1)^2} + \frac{8mn^2(4n^4+10n^2+1)}{15(k-1)} $$

$$ \begin{aligned} \mathbb{E}_{(k-1,n)}(C_{\Gamma(k-2)}) \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^2) &= 2mn^2h_{k-2} \left( \frac{8m^2n^4}{(k-1)^2} - \frac{4mn^2(2n^2+1)}{3(k-1)} \right) \\ &= 16m^3n^6 \frac{h_{k-2}}{(k-1)^2} - \frac{8m^2n^4(2n^2+1)h_{k-2}}{3(k-1)} \end{aligned} $$

and

$$ \begin{aligned} \mathbb{E}_{(k-1,n)}(C_{\Gamma(k-2)}^2) \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}) &= \left( -\frac{4mn^2(2n^2+1)}{3}h_{k-2} + 8m^2n^4 \sum_{\ell=1}^{k-2} \frac{h_\ell}{\ell} \right) \frac{2mn^2}{k-1} \\ &= \frac{16m^3n^6}{k-1} \sum_{\ell=1}^{k-2} \frac{h_\ell}{\ell} - \frac{8m^2n^4(2n^2+1)h_{k-2}}{3(k-1)}. \end{aligned} $$

Putting these three relations in (33), we obtain

$$ \begin{aligned} \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^3) &= 48m^3n^6 \sum_{k=1}^{a-1} \frac{1}{k^3} - 16m^2n^4(2n^2+1) \sum_{k=1}^{a-1} \frac{1}{k^2} + \frac{8mn^2(4n^4+10n^2+1)}{15} h_{a-1} \\ &\quad + 48m^3n^6 \sum_{k=2}^{a-1} \frac{h_{k-1}}{k^2} - 16m^2n^4(2n^2+1) \sum_{k=2}^{a-1} \frac{h_{k-1}}{k} + 48m^3n^6 \sum_{k=2}^{a-1} \frac{1}{k} \sum_{\ell=1}^{k-1} \frac{h_\ell}{\ell} \\ &= 48m^3n^6 \sum_{k=1}^{a-1} \frac{h_k}{k^2} - 16m^2n^4(2n^2+1) \sum_{k=1}^{a-1} \frac{h_k}{k} + \frac{8mn^2(4n^4+10n^2+1)}{15} h_{a-1} \\ &\quad + 48m^3n^6 \left( h_{a-1} \sum_{k=1}^{a-2} \frac{h_k}{k} - \sum_{k=1}^{a-2} \frac{h_k^2}{k} \right). \end{aligned} $$

From [20], we have $\mathbb{E}_0(T_n^3) = n^2(61n^4 - 50n^2 + 4)/15$ and thus relation (17) with $r=3$ becomes

$$ \begin{aligned} \mathbb{E}_0(C^3) &= \frac{n^2(61n^4 - 50n^2 + 4)}{15} + 3\mathbb{E}_{(m,n)}(C_{\Gamma(m-1)}) \frac{n^2(5n^2 - 2)}{3} + 3\mathbb{E}_{(m,n)}(C_{\Gamma(m-1)}^2) n^2 \\ &\quad + \mathbb{E}_{(m,n)}(C_{\Gamma(m-1)}^3) \\ &= \frac{n^2(61n^4 - 50n^2 + 4)}{15} + 2mn^4(5n^2 - 2)h_{m-1} - 4mn^4(2n^2 + 1)h_{m-1} + 24m^2n^6 \sum_{k=1}^{m-1} \frac{h_k}{k} \\ &\quad + 48m^3n^6 \sum_{k=1}^{m-1} \frac{h_k}{k^2} - 16m^2n^4(2n^2 + 1) \sum_{k=1}^{m-1} \frac{h_k}{k} + \frac{8mn^2(4n^4 + 10n^2 + 1)}{15} h_{m-1} \\ &\quad + 48m^3n^6 \left( h_{m-1} \sum_{k=1}^{m-2} \frac{h_k}{k} - \sum_{k=1}^{m-2} \frac{h_k^2}{k} \right) \\ &= \frac{n^2(61n^4 - 50n^2 + 4)}{15} + \left( \frac{62mn^6}{15} - \frac{8mn^4}{3} + \frac{8mn^2}{15} \right) h_{m-1} - 8m^2n^4(n^2 + 2) \sum_{k=1}^{m-1} \frac{h_k}{k} \\ &\quad + 48m^3n^6 \left( h_{m-1} \sum_{k=1}^{m-1} \frac{h_k}{k} - \sum_{k=1}^{m-1} \frac{h_k^2}{k} + \sum_{k=1}^{m-1} \frac{h_k^3}{k^2} \right), \end{aligned} $$
which completes the proof.

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

Obviously we could obtain explicit expressions of all the moments of the cover time but these expressions quickly become quite long and, at first glance, do not have a simple form. We propose in the next section a simple numerical algorithm to compute all the moments $\mathbb{E}_0(C^r)$ of the cover time.

### 4.2.3 Algorithm to compute the moments of the cover time

To compute the moments $\mathbb{E}_0(C^r)$ of the cover time we first need to compute the values of $v_n^{(\ell)}(n)$ given recursively by Theorem 4, and use them to compute $\mathbb{E}_{(a,n)}(T_{\Gamma(a-1)}^r)$ from relation (26). These values are then inserted in (19) to obtain recursively $\mathbb{E}_{(m,n)}(C_{\Gamma(m-1)}^r)$ which are in turn used in relation (17) given that the terms $\mathbb{E}_0(T_n)$ have already been obtained in [20]. The algorithm is described below.

We first introduce the following notation for every $r \ge 1$ and $k = 2, \dots, m$,

$$ \mathrm{ET}(r, k) = \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^r), \quad \mathrm{EC}(r, k) = \mathbb{E}_{(k,n)}(C_{\Gamma(k-1)}^r). $$

**input** : $n, m, r_{\max}$

**output** : $\mathbb{E}_0(C^r)$ for $r = 1, \dots, r_{\max}$

**for** $k = 2$ **to** $m$ **do**

$$ w_0^{(0)}(n) = 1, u_i^{(0)}(n) = 1 \text{ for } i = 1, \dots, n-1, v_i^{(0)}(n) = 1 \text{ for } i = 1, \dots, n $$

**for** $\ell = 1$ **to** $r_{\max}$ **do** compute $w_0^{(\ell)}(n), u_i^{(\ell)}(n), v_i^{(\ell)}(n)$ from Theorem 4 **endfor**

**for** $r = 1$ **to** $r_{\max}$ **do** compute $\mathrm{ET}(r, k) = \sum_{\ell=1}^{r} c_{r,\ell} v_n^{(\ell)}(n)$ **endfor**

**endfor**

**for** $a = 2$ **to** $m$ **do**

**for** $r = 1$ **to** $r_{\max}$ **do** $\mathrm{EC}(r, a) = \sum_{k=2}^{a} \mathrm{ET}(r, k) + \sum_{h=1}^{r-1} \binom{r}{h} \sum_{k=3}^{a} \mathrm{EC}(h, k-1)\mathrm{ET}(r-h, k)$ **endfor**

**endfor**

**for** $r = 1$ **to** $r_{\max}$ **do** $\mathbb{E}_0(C^r) = \mathbb{E}_0(T_n^r) + \sum_{h=1}^{r} \binom{r}{h} \mathrm{EC}(h, m)\mathbb{E}_0(T_n^{r-h})$ **endfor**

<caption>Table 1: Algorithm computing the moments $\mathbb{E}_0(C^r)$ for $r = 1, \dots, r_{\max}$ of the cover time of the star graph with $m$ arms each of length $n$.</caption>

## 5 Asymptotic analysis of the star graph : the sun graph

We consider in this section the asymptotic behavior of the cover time of the star graph, when both the number of arms and the length of each arm tend to infinity. More precisely we suppose that $m$ is a function of $n$ which tends to infinity with $n$. To take into account this dependence, we denote by $m_n$ the number of arms. The infinite graph thus defined is called the sun graph and depicted on Figure 3.

We suppose in this section that the number $m_n$ of arms satisfies

$$ \lim_{n \to \infty} m_n = \infty. $$

The limiting behavior of the quantities $v_n^{(\ell)}(n) = ((I - P_{S \setminus \Gamma(k-1)})^{-\ell}1)_{(k,n)}$ which will be used from (26) to get the limiting behavior of the hitting time moments $\mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^r)$ are given by the following theorem.
<figure><img src="image_6.png" /><figcaption>Figure 3: The sun graph : an infinite number of arms each of infinite length.</figcaption></figure>

**Theorem 6** For every $\ell \ge 1$ and $k = 2, \dots, m_n$, we have

$$w_0^{(\ell)}(n) = \frac{2^\ell m_n^\ell n^{2\ell}}{(k-1)^\ell} + \frac{m_n^\ell n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_\ell(n, k),$$

$$u_i^{(\ell)}(n) = \frac{2^\ell m_n^\ell n^{2\ell}}{(k-1)^\ell} - \frac{2^\ell i m_n^\ell n^{2\ell-1}}{(k-1)^\ell} + m_n^\ell n^{2\ell} \varepsilon_\ell(n, k, i), \text{ for } i = 1, \dots, n-1$$

$$v_i^{(\ell)}(n) = \frac{2^\ell m_n^\ell n^{2\ell}}{(k-1)^\ell} + \frac{m_n^\ell n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_\ell(n, k, i), \text{ for } i = 1, \dots, n$$

where $\varepsilon_\ell(n, k)$ and $\varepsilon_\ell(n, k, i)$ denote any function which goes to zero as $n$ goes to infinity uniformly in $i$ and $k$, in the sense that

$$\max_{k=2, \dots, m_n} |\varepsilon_\ell(n, k)| \underset{n \to \infty}{\longrightarrow} 0 \quad \text{and} \quad \max_{k=2, \dots, m_n} \max_{i=1, \dots, n} |\varepsilon_\ell(n, k, i)| \underset{n \to \infty}{\longrightarrow} 0.$$

**Proof.** Recall that for $\ell = 0$, we have $w_0^{(0)}(n) = u_i^{(0)}(n) = v_i^{(0)}(n) = 1$. We proceed by induction. The result is true for $\ell = 1$. Indeed, from Theorem 4, we have

$$w_0^{(1)}(n) = \frac{2m_n n^2}{k-1} - n^2 = \frac{2m_n n^2}{k-1} + m_n n^2 \varepsilon_1(n, k)$$

$$u_i^{(1)}(n) = \frac{2m_n n^2}{k-1} - \frac{2im_n n}{k-1} - n^2 + 2in - i^2 = \frac{2m_n n^2}{k-1} - \frac{2im_n n}{k-1} + m_n n^2 \varepsilon_1(n, k, i)$$

$$v_i^{(1)}(n) = \frac{2m_n n^2}{k-1} - n^2 + 2in - i^2 = \frac{2m_n n^2}{k-1} + m_n n^2 \varepsilon_1(n, k, i),$$

with

$$\max_{k=2, \dots, m_n} |\varepsilon_1(n, k)| = \frac{1}{m_n} \underset{n \to \infty}{\longrightarrow} 0 \quad \text{and} \quad \max_{k=2, \dots, m_n} \max_{i=1, \dots, n} |\varepsilon_1(n, k, i)| = \frac{(n-1)^2}{m_n n^2} \underset{n \to \infty}{\longrightarrow} 0.$$
Suppose now that the result is true for integer $\ell - 1$ that is, suppose that

$$
\begin{align*}
w_0^{(\ell-1)}(n) &= \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} + \frac{m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-2}} \varepsilon_{\ell-1}(n, k), \\
u_i^{(\ell-1)}(n) &= \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} - \frac{2^{\ell-1} i m_n^{\ell-1} n^{2\ell-3}}{(k-1)^{\ell-1}} + m_n^{\ell-1} n^{2\ell-2} \varepsilon_{\ell-1}(n, k, i), \quad \text{for } i=1, \dots, n-1 \\
v_i^{(\ell-1)}(n) &= \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} + \frac{m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-2}} \varepsilon_{\ell-1}(n, k, i), \quad \text{for } i=1, \dots, n
\end{align*}
$$

with

$$
\max_{k=2,...,m_n} |\varepsilon_{\ell-1}(n,k)| \xrightarrow{n \to \infty} 0 \quad \text{and} \quad \max_{k=2,...,m_n} \max_{i=1,...,n} |\varepsilon_{\ell-1}(n,k,i)| \xrightarrow{n \to \infty} 0.
$$

We analyze separately the main terms occuring in the relations of Theorem 4, when $m$ is replaced by $m_n$.
Concerning the expression of $w_0^{(\ell)}(n)$ in Theorem 4 we have, using the induction hypothesis,

$$
\frac{m_n n}{k-1} w_0^{(\ell-1)}(n) = \frac{2^{\ell-1} m_n^{\ell} n^{2\ell-1}}{(k-1)^{\ell}} + \frac{m_n^{\ell} n^{2\ell-1}}{(k-1)^{\ell-1}} \varepsilon_{\ell-1}(n,k) = \frac{m_n^{\ell} n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_{\ell}(n,k),
$$

where

$$
\varepsilon_{\ell}(n, k) = \frac{2^{\ell-1}}{n(k-1)} + \frac{\varepsilon_{\ell-1}(n, k)}{n}
$$

satisfies

$$
\max_{k=2,...,m_n} |\varepsilon_{\ell}(n,k)| \xrightarrow{n \to \infty} 0.
$$

$$
\begin{align*}
2 \sum_{j=1}^{n-1} (n-j) u_j^{(\ell-1)}(n) &= 2 \sum_{j=1}^{n-1} (n-j) \left( \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} - \frac{2^{\ell-1} j m_n^{\ell-1} n^{2\ell-3}}{(k-1)^{\ell-1}} + m_n^{\ell-1} n^{2\ell-2} \varepsilon_{\ell-1}(n,k,j) \right) \\
&= \frac{2^{\ell-1} n(n-1) m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} - \left( n^2(n-1) - \frac{(n-1)n(2n-1)}{3} \right) \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-3}}{(k-1)^{\ell-1}} \\
&\quad + 2 m_n^{\ell-1} n^{2\ell-2} \sum_{j=1}^{n-1} (n-j) \varepsilon_{\ell-1}(n,k,j) \\
&= \frac{2^{\ell} m_n^{\ell-1} n^{2\ell}}{3(k-1)^{\ell-1}} + \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-1}}{(k-1)^{\ell-1}} + \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-2}}{3(k-1)^{\ell-1}} + 2 m_n^{\ell-1} n^{2\ell-2} \sum_{j=1}^{n-1} (n-j) \varepsilon_{\ell-1}(n,k,j) \\
&= \frac{m_n^{\ell} n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_{\ell}(n,k),
\end{align*}
$$

where

$$
\varepsilon_{\ell}(n, k) = \frac{2^{\ell}}{3m_n} + \frac{2^{\ell-1}}{m_n n} + \frac{2^{\ell-1}}{3m_n n^2} + \frac{2}{m_n n^2} \sum_{j=1}^{n-1} (n-j) \varepsilon_{\ell-1}(n, k, j)
$$

satisfies

$$
\max_{k=2,...,m_n} |\varepsilon_{\ell}(n,k)| \le \frac{2^{\ell}}{3m_n} + \frac{2^{\ell-1}}{m_n n} + \frac{2^{\ell-1}}{3m_n n^2} + \max_{k=2,...,m_n} \max_{j=1,...,n} |\varepsilon_{\ell-1}(n,k,j)| \frac{n-1}{m_n n} \xrightarrow{n \to \infty} 0.
$$
A similar calculus on the third term of $w_0^{(\ell)}(n)$ in Theorem 4 leads to

$$
\begin{align*}
& n \left( \frac{m_n}{k-1} - 1 \right) \left( 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right) \\
&= \left( \frac{m_n}{k-1} - 1 \right) 2 \sum_{j=1}^{n} \left( \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-1}}{(k-1)^{\ell-1}} + \frac{m_n^{\ell-1} n^{2\ell-1}}{(k-1)^{\ell-2}} \varepsilon_{\ell-1}(n, k, j) \right) \\
&\quad - \left( \frac{m_n}{k-1} - 1 \right) \left( \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-1}}{(k-1)^{\ell-1}} + \frac{m_n^{\ell-1} n^{2\ell-1}}{(k-1)^{\ell-2}} \varepsilon_{\ell-1}(n, k) \right) \\
&= \frac{2^\ell m_n^\ell n^{2\ell}}{(k-1)^\ell} + \frac{m_n^\ell n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_\ell(n, k),
\end{align*}
$$

where

$$
\varepsilon_{\ell}(n, k) = -\frac{2^{\ell}}{m_n} - \frac{2^{\ell-1}}{(k-1)n} + \frac{2^{\ell-1}}{m_n n} + \frac{(m_n - (k-1))}{m_n n} \left( 2 \sum_{j=1}^{n-1} \varepsilon_{\ell-1}(n, k, j) - \varepsilon_{\ell-1}(n, k) \right)
$$

satisfies

$$
\max_{k=2,...,m_n} |\varepsilon_{\ell}(n,k)| \le \frac{2^{\ell}}{m_n} + \frac{2^{\ell-1}}{n} + \frac{2^{\ell-1}}{m_n n} + 2 \max_{k=2,...,m_n} \max_{j=1,...,n} |\varepsilon_{\ell-1}(n,k,j)| + \frac{1}{n} \max_{k=2,...,m_n} |\varepsilon_{\ell-1}(n,k)| \underset{n \to \infty}{\longrightarrow} 0.
$$

Putting together these intermediate results, we get

$$
\begin{align*}
w_0^{(\ell)}(n) &= \frac{m_n n}{k-1} w_0^{(\ell-1)}(n) + 2 \sum_{j=1}^{n-1} (n-j) u_j^{(\ell-1)}(n) + n \left( \frac{m_n}{k-1} - 1 \right) \left( 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right) \\
&= \frac{2^\ell m_n^\ell n^{2\ell}}{(k-1)^\ell} + \frac{m_n^\ell n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_\ell(n,k),
\end{align*}
$$

where $\varepsilon_\ell(n, k)$ satisfies

$$
\max_{k=2,...,m_n} |\varepsilon_{\ell}(n,k)| \xrightarrow{n \to \infty} 0.
$$

Consider now the expression of $u_i^{(\ell)}(n)$ in Theorem 4. The first two terms of this expression have already been detailed above. Using the induction hypothesis, the third one writes as we did above

$$
\begin{align*}
2 \sum_{j=1}^{i-1} (i-j) u_j^{(\ell-1)}(n) &= 2 \sum_{j=1}^{i-1} (i-j) \left( \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} - \frac{2^{\ell-1} j m_n^{\ell-1} n^{2\ell-3}}{(k-1)^{\ell-1}} + m_n^{\ell-1} n^{2\ell-2} \varepsilon_\ell(n,k,j) \right) \\
&= \frac{2^{\ell-1} i (i-1) m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} - \left( i^2 (i-1) - \frac{(i-1) i (2i-1)}{3} \right) \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-3}}{(k-1)^{\ell-1}} \\
&\quad + 2 m_n^{\ell-1} n^{2\ell-2} \sum_{j=1}^{i-1} (i-j) \varepsilon_\ell(n,k,j) \\
&= m_n^\ell n^{2\ell} \varepsilon_\ell(n,k,i),
\end{align*}
$$

where $\varepsilon_\ell(n, k, i)$ satisfies

$$
|\varepsilon_{\ell}(n, k, i)| = \left| \frac{2^{\ell-1}i(i-1)}{(k-1)^{\ell-1}m_n n^2} \right| + \left| \frac{2^{\ell-1}(i^3 - i)}{3(k-1)^{\ell-1}m_n n^3} \right| + \frac{2}{m_n n^2} \left| \sum_{j=1}^{i-1} (i-j)\varepsilon_{\ell-1}(n, k, j) \right|.
$$
By taking the max over $k = 2, \dots, m_n$ and $i = 1, \dots, n$, we obtain

$$ \max_{k=2,\dots,m_n} \max_{i=1,\dots,n} |\varepsilon_{\ell}(n,k,i)| \underset{n \to \infty}{\longrightarrow} 0. $$

This leads to

$$ \begin{aligned} u_i^{(\ell)}(n) &= \frac{(n-i)w_0^{(\ell)}(n)}{n} + \frac{2i}{n} \sum_{j=1}^{n-1} (n-j)u_j^{(\ell-1)}(n) - 2 \sum_{j=1}^{i-1} (i-j)u_j^{(\ell-1)}(n) \\ &= \frac{2^\ell m_n^\ell n^{2\ell}}{(k-1)^\ell} - \frac{2^\ell i m_n^\ell n^{2\ell-1}}{(k-1)^\ell} + m_n^\ell n^{2\ell} \varepsilon_\ell^{(u)}(n,k,i) \end{aligned} $$

where $\varepsilon_\ell(n, k, i)$ satisfies

$$ \max_{k=2,\dots,m_n} \max_{i=1,\dots,n} |\varepsilon_{\ell}(n,k,i)| \underset{n \to \infty}{\longrightarrow} 0. $$

Finally, consider the expression of $v_i^{(\ell)}(n)$ in Theorem 4. The first term $w_0^{(\ell)}(n)$ of this expression has already been detailed above. Using the induction hypothesis, the second one writes with the same arguments used above

$$ \begin{aligned} &i \left( 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right) \\ &= 2i \sum_{j=1}^{n} \left( \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} + \frac{m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-2}} \varepsilon_{\ell-1}(n,k,j) \right) - \frac{2^{\ell-1} i m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} - \frac{i m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-2}} \varepsilon_{\ell-1}(n,k) \\ &= \frac{2^\ell i m_n^{\ell-1} n^{2\ell-1}}{(k-1)^{\ell-1}} + \frac{2i m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-2}} \sum_{j=1}^{n} \varepsilon_{\ell-1}(n,k,j) - \frac{2^{\ell-1} i m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} - \frac{i m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-2}} \varepsilon_{\ell-1}(n,k) \\ &= \frac{m_n^\ell n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_\ell^{(v)}(n,k,i) \end{aligned} $$

where

$$ \varepsilon_{\ell}(n,k,i) = \frac{2^{\ell}i}{m_n n} + \frac{2i(k-1)}{m_n n^2} \sum_{j=1}^{n} \varepsilon_{\ell-1}(n,k,j) - \frac{2^{\ell-1}i}{m_n n^2} - \frac{i(k-1)}{m_n n^2} \varepsilon_{\ell-1}(n,k) $$

satisfies

$$ \max_{k=2,\dots,m_n} \max_{i=1,\dots,n} |\varepsilon_{\ell}(n,k,i)| \underset{n \to \infty}{\longrightarrow} 0. $$

In the same way, the third term of the expression of $v_i^{(\ell)}(n)$ in Theorem 4 writes

$$ \begin{aligned} 2 \sum_{j=1}^{i} (i-j) v_j^{(\ell-1)}(n) &= 2 \sum_{j=1}^{i} (i-j) \left( \frac{2^{\ell-1} m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} + \frac{m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-2}} \varepsilon_{\ell-1}(n,k,j) \right) \\ &= \frac{2^{\ell-1} i (i-1) m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-1}} + \frac{2 m_n^{\ell-1} n^{2\ell-2}}{(k-1)^{\ell-2}} \sum_{j=1}^{i} (i-j) \varepsilon_{\ell-1}(n,k,j) \\ &= \frac{m_n^\ell n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_\ell(n,k,i) \end{aligned} $$

with

$$ \max_{k=2,\dots,m_n} \max_{i=1,\dots,n} |\varepsilon_{\ell}(n,k,i)| \underset{n \to \infty}{\longrightarrow} 0. $$
Putting together these intermediate results, we get

$$ 
\begin{aligned}
v_i^{(\ell)}(n) &= w_0^{(\ell)}(n) + i \left( 2 \sum_{j=1}^{n} v_j^{(\ell-1)}(n) - v_n^{(\ell-1)}(n) \right) - 2 \sum_{j=1}^{i-1} (i-j) v_j^{(\ell-1)}(n) \\
&= \frac{2^\ell m_n^\ell n^{2\ell}}{(k-1)^\ell} + \frac{m_n^\ell n^{2\ell}}{(k-1)^{\ell-1}} \varepsilon_\ell(n, k, i)
\end{aligned}
$$

with

$$ \max_{k=2,...,m_n} \max_{i=1,...,n} |\varepsilon_\ell(n, k, i)| \xrightarrow{n \to \infty} 0. $$

This completes the proof.

We are now in position to prove the theorem giving the moments of the cover time of any subset of arms starting from a fixed leave. We first need the following lemma which gives the asymptotic behavior of the quantities $\varphi_{j,a}$ and $\psi_{j,a}^{(\ell)}$ defined recursively, for $a \ge 2$ by $\varphi_{1,a} = h_{a-1}$ and for $j \ge 2$ and $\ell \ge 1$,

$$ \varphi_{j,a} = \sum_{k=2}^{a-1} \frac{\varphi_{j-1,k}}{k} \quad \text{and} \quad \psi_{j,a}^{(\ell)} = \sum_{k=2}^{a-1} \frac{\varphi_{j,k}}{k^\ell}. $$

Observe that we have $\varphi_{j,a} = \psi_{j-1,a}^{(1)}$.

**Lemma 7** For every $j \ge 1$, $\ell \ge 2$, we have

$$ \varphi_{j,a} \underset{a \to \infty}{\sim} \frac{\ln^j(a)}{j!} \quad \text{and} \quad \lim_{a \to \infty} \psi_{j,a}^{(\ell)} = \sum_{k=2}^{\infty} \frac{\varphi_{j,k}}{k^\ell} < \infty. $$

**Proof.** We first proceed by induction. We have by definition

$$ \varphi_{1,a} = h_{a-1} \underset{a \to \infty}{\sim} \ln(a). $$

Suppose that

$$ \varphi_{j-1,k} \underset{k \to \infty}{\sim} \frac{\ln^{j-1}(k)}{(j-1)!}. $$

The Bertrand series $\sum_k \ln^{j-1}(k)/k$ diverges. Using the fact that the function $\ln^{j-1}(x)/x$ is decreasing for $x > e^{j-1}$, we obtain

$$ \frac{1}{(j-1)!} \sum_{k=2}^{a-1} \frac{\ln^{j-1}(k)}{k} \underset{a \to \infty}{\sim} \frac{1}{(j-1)!} \int_1^a \frac{\ln^{j-1}(x)}{x} dx = \frac{\ln^j(a)}{j!}. $$

We then have

$$ \varphi_{j,a} = \sum_{k=2}^{a-1} \frac{\varphi_{j-1,k}}{k} \underset{a \to \infty}{\sim} \frac{\ln^j(a)}{j!}. $$

Consider now the term $\psi_{j,a}^{(\ell)}$. For $\ell \ge 2$, the Bertrand series $\sum_k \ln^j(k)/k^\ell$ converges and since

$$ \frac{\varphi_{j,k}}{k^\ell} \underset{k \to \infty}{\sim} \frac{\ln^j(k)}{j!k^\ell}. $$

we have

$$ \lim_{a \to \infty} \psi_{j,a}^{(\ell)} = \sum_{k=2}^{\infty} \frac{\varphi_{j,k}}{k^\ell} < \infty, $$

which completes the proof.
**Theorem 8** For every $r \ge 1$ and $a = 2, \dots, m_n$, we have

$$ \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^r) = 2^r r! m_n^r n^{2r} \varphi_{r,a}(1 + \varepsilon_r(n,a)). \quad (34) $$

with $\varepsilon_r(n, a) \to 0$ when both $n$ and $a$ tend to $\infty$ and $\varepsilon_r(n) = \max_{a=2,\dots,m_n} \varepsilon_r(n, a) \to 0$ when $n$ tends to $\infty$. In particular, we have

$$ \mathbb{E}_{(m_n, n)}(C^r) \underset{n \to \infty}{\sim} 2^r m_n^r n^{2r} \ln^r(m_n). $$

**Proof.** Using relation (26) and Theorem 6, we have, since $c_{r,r} = r!$,

$$ \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^r) = 2^r r! m_n^r n^{2r} \left( \frac{1}{(k-1)^r} + \frac{\varepsilon_r(n,k)}{(k-1)^{r-1}} \right), $$

with $\varepsilon_r(n) = \max_{k=2,\dots,m_n} \varepsilon_r(n, k) \to 0$ when $n$ tends to $\infty$. We then have

$$ \begin{aligned} \sum_{k=2}^{a} \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^r) &= 2^r r! m_n^r n^{2r} \sum_{k=2}^{a} \frac{1}{(k-1)^r} + 2^r r! m_n^r n^{2r} \sum_{k=2}^{a} \frac{\varepsilon_r(n,k)}{(k-1)^{r-1}} \\ &= 2^r r! m_n^r n^{2r} \left( \sum_{k=1}^{a-1} \frac{1}{k^r} + \varepsilon_r(n) \sum_{k=1}^{a-1} \frac{1}{k^{r-1}} \right). \end{aligned} $$

For $\ell, a \ge 2$ we introduce the truncated Riemann converging series

$$ \zeta_{\ell,a} = \sum_{k=1}^{a-1} \frac{1}{k^{\ell}}. $$

We now proceed by induction on $r$. The relation (34) is true for $r = 1$. Indeed, in that case we have from relation (31)

$$ \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^r) = 2m_n n^2 h_{a-1}, $$

which is exactly the right hand side of (34) with $r = 1$ and $\varepsilon_1(n, a) = 0$.

For $r = 2$ we obtain,

$$ \sum_{k=2}^{a} \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^2) = 8m_n^2 n^4 \left( \sum_{k=1}^{a-1} \frac{1}{k^2} + \varepsilon_2(n) \sum_{k=1}^{a-1} \frac{1}{k} \right) = 8m_n^2 n^4 (\zeta_{2,a} + \varepsilon_2(n)h_{a-1}). $$

Furthermore, since $\varepsilon_1(n, k) = 0$, we have

$$ \mathbb{E}_{(k-1,n)}(C_{\Gamma(k-2)}^r) \mathbb{E}_{(k,n)}(T_{\Gamma(k-1)}^r) = 2mn^2h_{k-2} \frac{2mn^2}{k-1} = \frac{4m^2n^4h_{k-2}}{k-1}. $$

It follows from relation (19) that

$$ \begin{aligned} \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^2) &= 8m^2 n^4 (\zeta_{2,a} + \varepsilon_2(n)h_{a-1}) + 8m_n^2 n^4 \sum_{k=2}^{a-1} \frac{h_{k-1}}{k} \\ &= 8m^2 n^4 (\zeta_{2,a} + h_{a-1}\varepsilon_2(n) + \varphi_{2,a}) \\ &= 8m^2 n^4 \varphi_{2,a} \left( 1 + \frac{\zeta_{2,a}}{\varphi_{2,a}} + \frac{h_{a-1}}{\varphi_{2,a}} \varepsilon_2(n) \right). \end{aligned} $$

From Lemma 7, both $\zeta_{2,a}/\varphi_{2,a}$ and $h_{a-1}/\varphi_{2,a}$ tend to 0 when $a$ tends to $\infty$, we thus have

$$ \mathbb{E}_{(a,n)}(C_{\Gamma(a-1)}^2) = 8m^2 n^4 \varphi_{2,a} (1 + \varepsilon_2(n, a)). $$
Suppose that the relation (34) is true until integer $r-1$, that is suppose that, for $j=1,...,r-1$, we have

$$ \mathbb{E}_{(a,n)} (C_{\Gamma(a-1)}^j) = 2^j j! m_n^j n^{2j} \varphi_{j,a} (1 + \varepsilon_j(n, a)) $$

with $\varepsilon_j(n,a) \to 0$ when both $n$ and $a$ tend to $\infty$ and $\varepsilon_j(n) = \max_{a=2,...,m_n} \varepsilon_j(n,a) \to 0$ when $n$ tends to $\infty$.

We then have, for $r \ge 3$, from (19) by extracting the term $j = r-1$, because $\varepsilon_1(n,a) = 0$ and using the induction hypothesis,

$$ \begin{aligned} \mathbb{E}_{(a,n)} (C_{\Gamma(a-1)}^r) &= \sum_{k=2}^{a} \mathbb{E}_{(k,n)} (T_{\Gamma(k-1)}^r) + \sum_{j=1}^{r-1} \binom{r}{j} \sum_{k=3}^{a} \mathbb{E}_{(k-1,n)} (C_{\Gamma(k-2)}^j) \mathbb{E}_{(k,n)} (T_{\Gamma(k-1)}^{r-j}) \\ &= 2^r r! m_n^r n^{2r} (\zeta_{r,a} + \varepsilon_r(n) \zeta_{r-1,a}) \\ &\quad + 2^r r! m_n^r n^{2r} \sum_{j=1}^{r-2} \sum_{k=2}^{a-1} \varphi_{j,k} [1 + \varepsilon_j(n,k)] \left[ \frac{1}{k^{r-j}} + \frac{\varepsilon_{r-j}(n,k)}{k^{r-j-1}} \right] \\ &\quad + 2^r r! m_n^r n^{2r} \sum_{k=2}^{a-1} \varphi_{r-1,k} [1 + \varepsilon_{r-1}(n,k)] \frac{1}{k}, \end{aligned} $$

where we used the relation $\mathbb{E}_{(k,n)} (T_{\Gamma(k-1)}) = 2m_n n^2/(k-1)$. It follows that

$$ \begin{aligned} \mathbb{E}_{(a,n)} (C_{\Gamma(a-1)}^r) &= 2^r r! m_n^r n^{2r} \left( \zeta_{r,a} + \varepsilon_r(n) \zeta_{r-1,a} + \sum_{j=1}^{r-2} \sum_{k=2}^{a-1} \frac{\varphi_{j,k}}{k^{r-j}} + \sum_{j=1}^{r-2} \sum_{k=2}^{a-1} \frac{\varphi_{j,k} \varepsilon_j(n,k)}{k^{r-j}} \right. \\ & \qquad \left. + \sum_{j=1}^{r-2} \sum_{k=2}^{a-1} \frac{\varphi_{j,k} \varepsilon_{r-j}(n,k)}{k^{r-j-1}} + \sum_{j=1}^{r-2} \sum_{k=2}^{a-1} \frac{\varphi_{j,k} \varepsilon_j(n,k) \varepsilon_{r-j}(n,k)}{k^{r-j-1}} + \sum_{k=2}^{a-1} \frac{\varphi_{r-1,k}}{k} + \sum_{k=2}^{a-1} \frac{\varepsilon_{r-1}(n,k)}{k} \right). \end{aligned} $$

We then get

$$ \begin{aligned} \mathbb{E}_{(a,n)} (C_{\Gamma(a-1)}^r) &= 2^r r! m_n^r n^{2r} \varphi_{r,a} \left( \frac{\zeta_{r,a}}{\varphi_{r,a}} + \varepsilon_r(n) \frac{\zeta_{r-1,a}}{\varphi_{r,a}} + \sum_{j=1}^{r-2} \frac{\psi_{j,a}^{(r-j)}}{\varphi_{r,a}} + \sum_{j=1}^{r-2} \varepsilon_j(n) \frac{\psi_{j,a}^{(r-j)}}{\varphi_{r,a}} \right. \\ & \qquad \left. + \sum_{j=1}^{r-2} \varepsilon_{r-j}(n) \frac{\psi_{j,a}^{(r-j-1)}}{\varphi_{r,a}} + \sum_{j=1}^{r-2} \varepsilon_j(n) \varepsilon_{r-j}(n) \frac{\psi_{j,a}^{(r-j-1)}}{\varphi_{r,a}} + 1 + \varepsilon_{r-1}(n) \frac{h_{a-1}-1}{\varphi_{r,a}} \right). \end{aligned} $$

Since $r \ge 3$, from Lemma 7 all the following terms tend to 0 when $a$ tends to $\infty$, that is

$$ \frac{\zeta_{r,a}}{\varphi_{r,a}}; \frac{\zeta_{r-1,a}}{\varphi_{r,a}}; \frac{\psi_{j,a}^{(r-j)}}{\varphi_{r,a}} \text{ for } j=1, \dots, r-2; \frac{\psi_{j,a}^{(r-j-1)}}{\varphi_{r,a}} \text{ for } j=1, \dots, r-3 \text{ and } \frac{h_{a-1}-1}{\varphi_{r,a}}. $$

When $j = r-2$ we have, using again Lemma 7,

$$ \frac{\psi_{j,a}^{(r-j-1)}}{\varphi_{r,a}} = \frac{\psi_{r-2,a}^{(1)}}{\varphi_{r,a}} = \frac{\varphi_{r-1,a}}{\varphi_{r,a}} \to 0 \text{ when } a \text{ tends to } \infty. $$

This proves relation (34). By taking $a = m_n$ in (34), we obtain the desired result since

$$ \varphi_{r,m_n} \underset{n \to \infty}{\sim} \frac{\ln^r(m_n)}{r!}. $$

This completes the proof.

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

The result of Theorem 8 can now be used in relation (17) to get the moments of the cover time of the sun graph when the initial state is the center of the graph, that is state 0.
**Theorem 9** for every $r \ge 0$, we have

$$ \lim_{n \to \infty} \mathbb{E}_0 \left( \left[ \frac{C}{2m_n n^2 \ln(m_n)} \right]^r \right) = 1. $$

**Proof.** Since $m$ is depending on $n$, relation (17) can be written as

$$ \mathbb{E}_0 (C^r) = \mathbb{E}_0 (T_n^r) + \sum_{h=1}^{r} \binom{r}{h} \mathbb{E}_{(m_n, n)} (C^h) \mathbb{E}_0 (T_n^{r-h}). \quad (35) $$

Observe that this relation uses the moments of the hitting time $T_n$ of state $n$ in the path graph starting from state 0 as shown in Figure 2. These moments have been analyzed in details in [20], where we obtained

$$ \lim_{n \to \infty} \mathbb{E}_0 \left( \left[ \frac{T_n}{n^2} \right]^r \right) = \frac{2^r r! |E_{2r}|}{(2r)!}, \quad (36) $$

where $|E_{2r}|$ are absolute values of the even Euler numbers. The odd Euler numbers are equal to 0 and the first even ones are

$$ E_0 = 1, E_2 = -1, E_4 = 5, E_6 = -61, E_8 = 1385, E_{10} = -50521, E_{12} = 2702765, E_{14} = -199360981. $$

Dividing each term of (35) by $2m_n n^2 \ln(m_n)$ and taking the limit when $n$ tends to infinity, we get using relation (36) and Theorem 8,

$$ \lim_{n \to \infty} \mathbb{E}_0 \left( \left[ \frac{T_n}{2m_n n^2 \ln(m_n)} \right]^{r-h} \right) = 0, \text{ for } h = 1, \dots, r-1, $$

$$ \lim_{n \to \infty} \mathbb{E}_{(m_n, n)} \left( \left[ \frac{C}{2m_n n^2 \ln(m_n)} \right]^h \right) = 1, \text{ for every } h \ge 1. $$

It follows that the only non zero limiting term is the one corresponding to $h = r$. We thus get for every $r \ge 0$,

$$ \lim_{n \to \infty} \mathbb{E}_0 \left( \left[ \frac{C}{2m_n n^2 \ln(m_n)} \right]^r \right) = 1, $$

which completes the proof.

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

We can now determine the limiting behavior of the distribution of the cover time of the sun graph.

**Theorem 10** For all $t \in \mathbb{R} \setminus \{1\}$, we have,

$$ \lim_{n \to \infty} \mathbb{P} \left\{ \frac{C}{2m_n n^2 \ln(n)} > t \right\} = \begin{cases} 1 & \text{if } t < 1 \\ 0 & \text{if } t > 1. \end{cases} $$

**Proof.** From Theorem 9, we have for every $r \ge 0$,

$$ \lim_{n \to \infty} \mathbb{E}_0 \left( \left[ \frac{C}{2m_n n^2 \ln(n)} \right]^r \right) = 1. $$

Let $Z$ be the constant random variable defined by $Z = 1$. For every $r \ge 0$, we have $\mathbb{E}(Z^r) = 1$. Thus the power series $\sum_{r \ge 0} \mathbb{E}(Z^r)x^r/r!$ has a positive radius (equal to $+\infty$). This implies, from Theorem 30.1 of [4], that the random variable $Z$ is uniquely determined by its moments. It follows from Theorem 30.2 of [4] that

$$ \frac{C}{2m_n n^2 \ln(n)} \xrightarrow{\mathcal{L}} Z = 1, \text{ as } n \to \infty. $$

This means that

$$ \lim_{n \to \infty} \mathbb{P} \left\{ \frac{C}{2m_n n^2 \ln(n)} > t \right\} = \begin{cases} 1 & \text{if } t < 1 \\ 0 & \text{if } t > 1, \end{cases} $$

which completes the proof.

<figure><img src="image_9.png" /></figure>
Observe that, since the limit $Z = 1$ is constant, we also have the convergence in probability of the random variable $C/(2m_n n^2 \ln(n))$ to $Z = 1$, that is, for any $\epsilon > 0$

$$ \lim_{n \to \infty} \mathbb{P} \left\{ \left| \frac{C}{2m_n n^2 \ln(n)} - 1 \right| > \epsilon \right\} = 0. $$

# 6 Conclusion

We considered in this paper both the distribution and the moments of the hitting and cover times on the star graph. We obtained recurrence relations for all order moments and for the distribution of these random variables. We used these relations to analyze the asymptotic behavior of the cover time distribution when the number of arms and their lengths tend to infinity. We call this limiting graph the sun graph. We observed that the cover time divided by its expectation converge in distribution. Further research will consist in analyzing more general graphs to see if this convergence still occurs. A first step will be to analyze other particular graphs such as the barbell graph obtained by connecting two copies of a complete graph by a bridge or the tadpole graph obtained by joining a cycle graph to a path graph.

# A Two lemmas

These two lemmas are used in the proof of Theorem 4

**Lemma 11** For every $n \ge 2$ and fixed $\theta_0, \theta_1, \dots, \theta_{l-1}$, the unique solution to the linear system

$$ \left\{ \begin{array}{l} x_1 - \frac{1}{2}\theta_0 - \frac{1}{2}x_2 = \theta_1 \\ x_i - \frac{1}{2}x_{i-1} - \frac{1}{2}x_{i+1} = \theta_i, \quad \text{for } i = 2, \dots, n-2 \\ x_{n-1} - \frac{1}{2}x_{n-2} = \theta_{n-1} \end{array} \right. $$

is given, for $i = 1, \dots, n-1$, by

$$ x_i = \frac{(n-i)\theta_0}{n} + \frac{2i}{n} \sum_{j=1}^{n-1} (n-j)\theta_j - 2 \sum_{j=1}^{i-1} (i-j)\theta_j. $$

**Proof.** Using the fact that $x_i = x_i/2 + x_{i/2}$ and introducing the differences $z_i = x_i - x_{i-1}$, with $x_0 = x_n = 0$, we get

$$ z_1 - z_2 = 2a_1 + a_0 \text{ and } z_i - z_{i+1} = 2a_i, \quad i = 2, \dots, n-1. $$

We then have

$$ z_1 - z_i = \sum_{j=1}^{i-1} (z_j - z_{j+1}) = a_0 + 2 \sum_{j=1}^{i-1} \theta_j $$

which gives, since $z_1 = x_1$,

$$ z_i = x_1 - \theta_0 - 2 \sum_{j=1}^{i-1} \theta_j, \quad i = 2, \dots, n. $$

Summing the $z_j$'s leads to

$$ x_i = \sum_{j=1}^{i} z_j = ix_1 - (i-1)\theta_0 - 2 \sum_{k=1}^{i-1} \sum_{j=1}^{k} \theta_j. $$
Since $x_n = 0$ we obtain

$$x_1 = \frac{(n-1)\theta_0}{n} + \frac{2}{n} \sum_{k=1}^{n-1} \sum_{j=1}^{k} \theta_j$$

and thus, for every $i = 1, \dots, n-1$,

$$x_i = \frac{(n-i)\theta_0}{n} + \frac{2i}{n} \sum_{k=1}^{n-1} \sum_{j=1}^{k} \theta_j - 2 \sum_{k=1}^{i-1} \sum_{j=1}^{k} \theta_j = \frac{(n-i)\theta_0}{n} + \frac{2i}{n} \sum_{j=1}^{n-1} (n-j)\theta_j - 2 \sum_{j=1}^{i-1} (i-j)\theta_j,$$

which completes the proof.

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

**Lemma 12** For every $n \ge 2$ and fixed $\theta_0, \theta_1, \dots, \theta_n$, the unique solution to the linear system

$$\left\{ \begin{array}{l} x_1 - \frac{1}{2}\theta_0 - \frac{1}{2}x_2 = \theta_1 \\ x_i - \frac{1}{2}x_{i-1} - \frac{1}{2}x_{i+1} = \theta_i, \quad \text{for } i = 2, \dots, n-1 \\ x_n - x_{n-1} = \theta_n \end{array} \right.$$

is given, for $i = 1, \dots, n$, by

$$x_i = \theta_0 + i \left( 2 \sum_{j=1}^{n} \theta_j - \theta_n \right) - 2 \sum_{j=1}^{i-1} (i-j) \theta_j.$$

**Proof.** Using the fact that $x_i = x_i/2 + x_i/2$ and introducing the differences $z_i = x_i - x_{i-1}$, with $x_0 = 0$, we get

$$z_1 - z_2 = 2\theta_1 + \theta_0, \quad z_i - z_{i+1} = 2\theta_i, \quad i = 2, \dots, n-1, \text{ and } z_n = \theta_n.$$

We then have

$$z_1 - z_i = \sum_{j=1}^{i-1} (z_j - z_{j+1}) = \theta_0 + 2 \sum_{j=1}^{i-1} \theta_j$$

which gives, since $z_1 = x_1$,

$$z_i = x_1 - \theta_0 - 2 \sum_{j=1}^{i-1} \theta_j, \quad i = 2, \dots, n.$$

Since $z_n = \theta_n$, we have

$$x_1 = \theta_0 + 2 \sum_{j=1}^{n-1} \theta_j + \theta_n = \theta_0 + 2 \sum_{j=1}^{n} \theta_j - \theta_n.$$

Summing the $z_j$'s leads to

$$x_i = \sum_{j=1}^{i} z_j = i x_1 - (i-1)\theta_0 - 2 \sum_{k=1}^{i-1} \sum_{j=1}^{k} \theta_j,$$

that is, for every $i = 1, \dots, \ell$,

$$x_i = \theta_0 + i \left( 2 \sum_{k=1}^{\ell} \theta_k - \theta_n \right) - 2 \sum_{k=1}^{i-1} \sum_{j=1}^{k} \theta_j,$$

which completes the proof.

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

[1] D. Aldous. *Applications of random walks on finite graphs*. preprint. https://www.google.com/search?client=firefox-b-d&q=Applications+of+random+walks+on+graphs, 1989.

[2] 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.

[3] 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)*, Moscow, Russia, Berlin, June 2000. Springer Verlag.

[4] P. Billingsley. *Probability and Measure*. Series in probability and mathematical statistics. Wiley, New York, third edition, 1995.

[5] G. Brightwell and P. Winkler. Maximum hitting time for random walks on graphs. *Random Structures and Algorithms*, 1(3):263–276, 1990.

[6] F. Castella and B. Sericola. Hitting times on the lollipop graph. *Probability in the Engineering and Informational Sciences*, pages 1–34, 2025.

[7] P. G. Doyle and J. L. Snell. *Random Walks and Electrical Networks*. The carus mathematical monographs. Mathematical Assoc. of America, Washington, DC, 1984.

[8] U. Feige. A tight lower bound on the cover time for random walks on graphs. *Random Structures and Algorithms*, 6(4):433–438, 1995.

[9] U. Feige. A tight upper bound on the cover time for random walks on graphs. *Random Structures and Algorithms*, 6(1):51–54, 1995.

[10] S. Ikeda, I. Kubo, and M. Yamashita. The hitting and cover times of random walks on finite graphs using local degree information. *Theoretical Computer Science*, 410(1):94–100, 2009.

[11] J.G. Kemeny and J.L. Snell. *Finite Markov Chains*. Springer, New York-Heidelberg-Berlin, 1976.

[12] 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):619–628, 2011. Special issue on Complex Networks.

[13] L. Lovász. *Random Walks on Graphs: A Survey*. Combinatorics, Paul Erdős is Eighty, volume 2. János Bolyai Mathematical Society, Keszthely, Hungary, 1996.

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

[15] J. L. Palacios. Cover times for the stars. *Math. Sci.*, 19:103–107, 1994.

[16] G. Rubino and B. Sericola. On weak lumpability in Markov chains. *Journal of Applied Probability*, 26:446–457, 1989.

[17] G. Rubino and B. Sericola. A finite characterization of weak lumpable Markov processes. part I: The discrete time case. *Stochastic Processes and their Applications*, 38:195–204, 1991.

[18] B. Sericola. *Markov Chains. Theory, Algorithms and Applications*. Applied stochastic methods series. Wiley, Hoboken, NJ, USA, 2013.

[19] B. Sericola. On cover times of Markov chains. *Stochastic Models*, 40(4):685–727, 2024.

[20] B. Sericola. Hitting and cover times of the path graph. Technical report, Centre Inria de l'université de Rennes, March 2025.