# Hitting times on the lollipop graph

Bruno Sericola, François Castella

► To cite this version:

Bruno Sericola, François Castella. Hitting times on the lollipop graph. Centre Inria de l'université de Rennes. 2023, pp.1-27. [hal-04143403](https://hal.inria.fr/hal-04143403)

HAL Id: hal-04143403

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

Submitted on 27 Jun 2023

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>

Distributed under a Creative Commons Attribution 4.0 International License
# Hitting times on the lollipop graph

François Castella, Bruno Sericola

► To cite this version:

François Castella, Bruno Sericola. Hitting times on the lollipop graph. Centre Inria de l'université de Rennes. 2024, pp.1-30. hal-04143403v2

HAL Id: hal-04143403

https://inria.hal.science/hal-04143403v2

Submitted on 13 Dec 2024

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>
# Hitting times on the lollipop graph

François Castella* and Bruno Sericola†

June 27, 2023

## Abstract

We consider the moments and the distribution of hitting times on the lollipop graph which is the graph exhibiting the maximum expected hitting time among all the graphs having the same number of nodes. We obtain recurrence relations for the moments of all order and we use these relations to analyze the asymptotic behavior of the hitting time distribution when the number of nodes tends to infinity.

**Keywords**: Markov chain; Hitting times; Lollipop graph; Moments; Asymptotic analysis.

## 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 [2] as for instance the analysis of electrical networks which are detailed in [10]. Very interesting surveys on random walks on graphs are [3] and [16] while [17] 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 [15].

It has been shown in [12] and [11] 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 [11]. In [5] 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 [14], 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 homogeneous Markov chain is analyzed in [19] where both its distribution and its moments are considered with applications to particular graphs namely the generalized cycle graph, the complete graph and the generalized path graph.

We consider in this paper hitting times on the lollipop graph which consists of a complete graph (a clique) on $m$ vertices and a path graph on $n-m$ vertices. One end of the path graph is connected to one vertex, denoted by $m$, of the clique, and its other end is the target vertex $n$ for the hitting times. Such a graph has been denoted by $L_m^n$ for $n, m \in \mathbb{N}$, with $2 \le m \le n$. It is represented in Figure 1 for $m=8$ and $n=14$. Observe that when $m=n$ we obtain the well-known complete graph $K_n$. The expected hitting time of the

<footnote>*François Castella is with Univ. Rennes, Inria, CNRS, IRISA</footnote>

<footnote>†Bruno Sericola is with Inria, Univ. Rennes, CNRS, IRISA</footnote>
# Hitting times on the lollipop graph

François Castella* and Bruno Sericola†

December 12, 2024

## Abstract

We consider the moments and the distribution of hitting times on the lollipop graph which is the graph exhibiting the maximum expected hitting time among all the graphs having the same number of nodes. We obtain recurrence relations for the moments of all order and we use these relations to analyze the asymptotic behavior of the hitting time distribution when the number of nodes tends to infinity.

**Keywords**: Markov chain; Hitting times; Lollipop graph; Moments; Asymptotic analysis.

## 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 [2] as for instance the analysis of electrical networks which are detailed in [10]. Very interesting surveys on random walks on graphs are [3] and [16] while [17] 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 [15].

It has been shown in [12] and [11] 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 [11]. In [5] 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 [14], 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 both its distribution and its moments are considered with applications to particular graphs namely the generalized cycle graph, the complete graph and the generalized path graph.

In this paper we consider hitting times on the lollipop graph which consists of a complete graph (a clique) on $m$ vertices and a path graph on $n-m$ vertices. One end of the path graph is connected to one vertex, denoted by $m$, of the clique, and its other end is the target vertex $n$ for the hitting times. Such a graph has been denoted by $L_m^n$ for $n, m \in \mathbb{N}$, with $2 \le m \le n$. It is represented in Figure 1 for $m = 8$ and $n = 14$. Observe that when $m = n$ we obtain the well-known complete graph $K_n$. The expected hitting time of the

<footnote>*François Castella is with Univ. Rennes, Inria, CNRS, IRISA</footnote>

<footnote>†Bruno Sericola is with Inria, Univ. Rennes, CNRS, IRISA</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: The lollipop graph $L_8^{14}$</figcaption></figure>

path end node $n$, when starting from a node $i \in \{1, \dots, m-1\}$, has been obtained in [9] where the authors prove that the maximum expected hitting time among all the $n$-vertex graphs is obtained for the lollipop graph $L_m^n$ when $m = \lceil 2(n-1)/3 \rceil$. This major result is obviously quite important and shows that a detailed analysis of the lollipop graph is relevant.

This is the goal of our paper. In section 2, we give general formulas for the distribution and for all the moments of the hitting times in a general Markov chain. We use these results in section 3 to derive the mean and the variance of the hitting times on the lollipop graph. Our proof for obtaining the expected hitting times on the lollipop graph differs from the one of [9] but we need it to obtain higher order moments. We also obtain in section 3 the moment generating function of the hitting times and we propose a simple method to compute the convergence domain of this function which consists in evaluating the eigenvalues and in particular the spectral radius of the substochactic matrix arising in the distribution expression of the hitting time. We propose in section 4 a general recursive way to obtain all the moments of the hitting time $T_n$ of node $n$ and we use this recursion to obtain the asymptotic behavior of the distribution of $T_n$ when $n$ tends to infinity for various values of $m$. As a particular case we obtain that, when $m = \lceil 2(n-1)/3 \rceil$, the asymptotic distribution of $27T_n/(4n^3)$ is exponential with rate 1. Section 5 concludes the paper.

## 2 General 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 $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 $T_A$ the hitting time of subset $A$, defined by the time needed to reach $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$).
<figure><img src="image_2.png" /><figcaption>Figure 1: The lollipop graph $L_8^{14}$</figcaption></figure>

path end node $n$, when starting from a node $i \in \{1, \dots, m-1\}$, has been obtained in [9] where the authors prove that the maximum expected hitting time among all the $n$-vertex graphs is obtained for the lollipop graph $L_m^n$ when $m = \lceil 2(n-1)/3 \rceil$, with value $(4/27+o(1))n^3$. This major result is obviously quite important and shows that a detailed analysis of the lollipop graph is relevant.

This is the goal of our paper. The novelty of the proof techniques lies in the way we obtain detailed recurrence formulas for the calculation of all moments of the hitting times. These formulas then make it possible to exhibit the asymptotic behavior of all the moments. This phase is clearly the hardest to come by. From these asymptotic moments, we obtain the asymptotic distribution of the hitting times using a standard argument of complex analysis.

The paper is organised as follows. In section 2, we give general formulas for the distribution and for all the moments of the hitting times in a general Markov chain. We use these results in section 3 to derive the mean and the variance of the hitting times on the lollipop graph. Our proof for obtaining the expected hitting times on the lollipop graph differs from the one of [9] but we need it to obtain higher order moments. We also obtain in section 3 the moment generating function of the hitting times and we propose a simple method to compute the convergence domain of this function which consists in evaluating the eigenvalues and in particular the spectral radius of the substochactic matrix arising in the distribution expression of the hitting time. We propose in section 4 a general recursive way to obtain all the moments of the hitting time $T_n$ of node $n$ and we use this recursion to obtain the asymptotic behavior of the distribution of $T_n$ when $n$ tends to infinity for various values of $m$. As a particular case we obtain that, when $m = \lceil 2(n-1)/3 \rceil$, the asymptotic distribution of $27T_n/(4n^3)$ is exponential with rate 1. Section 5 concludes the paper.

## 2 General 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 $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 $T_A$ the hitting time of subset $A$, defined by the time needed to reach $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},$$
We also denote by 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$ and $k \ge 1$, see for instance [18],

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

The r-th moment of the hitting time of subset A starting from state $i \in A^c$ is then given by

$$ \mathbb{E}(T_A^r | X_0 = i) = \sum_{k=1}^{\infty} k^r (P_{A^c}^{k-1} P_{A^c, A} 1)_i. \qquad (2) $$

The following theorem gives a finite expression of this r-th moment which involves only the successive powers of matrix $(I - P_{A^c})^{-1}$.

**Theorem 1** For every $r \ge 1$, we have

$$ \mathbb{E}(T_A^r | X_0 = i) = \sum_{\ell=1}^{r} c_{r,\ell} ((I - P_{A^c})^{-\ell} 1)_i $$

where, for every $\ell = 1, \dots, r$,

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

**Proof.** For $r \ge 0$ and $x \in (0, 1]$, we introduce the notation $S_r(x) = \sum_{k=1}^{\infty} k^r x^{k-1} P_{A^c}^{k-1}$. We prove by recurrence that, for $r \ge 1$ we have

$$ S_r(x) = \sum_{\ell=1}^{r} c_{r,\ell} (I - xP_{A^c})^{-(\ell+1)} \quad \text{where } c_{r,\ell} = (-1)^r \sum_{j=1}^{\ell} (-1)^j \binom{\ell}{j} j^r. $$

The result is true for $r = 1$. Indeed, for $r = 1$ we have

$$ S_1(x) = \sum_{k=1}^{\infty} kx^{k-1} P_{A^c}^{k-1}, $$

which gives

$$ \int_0^x S_1(t) dt = \sum_{k=1}^{\infty} k \left( \int_0^x t^{k-1} dt \right) P_{A^c}^{k-1} = \sum_{k=1}^{\infty} x^k P_{A^c}^{k-1} = xS_0(x) = x(I - xP_{A^c})^{-1}. $$

By taking the derivative with respect to $x$, we get

$$ S_1(x) = (I - xP_{A^c})^{-1} + xP_{A^c}(I - xP_{A^c})^{-2} = (I - xP_{A^c} + xP_{A^c})(I - xP_{A^c})^{-2} = (I - xP_{A^c})^{-2}. $$

On the other hand, the equality is satisfied since $c_{1,1} = 1$.

Suppose that the relation is true for index $r-1$, i.e. suppose that

$$ S_{r-1}(x) = \sum_{\ell=1}^{r-1} c_{r-1,\ell} (I - xP_{A^c})^{-(\ell+1)} \quad \text{where } c_{r-1,\ell} = (-1)^{r-1} \sum_{j=1}^{\ell} (-1)^j \binom{\ell}{j} j^{r-1}. $$

We then have

$$ \int_0^x S_r(t) dt = \sum_{k=1}^{\infty} k^{r-1} x^k P_{A^c}^{k-1} = xS_{r-1}(x). $$
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 $\mathbf{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$ and $k \ge 1$, see for instance [18],

$$ \mathbb{P}\{T_A = k | X_0 = i\} = (P_{A^c}^{k-1} P_{A^c,A} \mathbf{1})_i. \qquad (1) $$

The r-th moment of the hitting time of subset A starting from state $i \in A^c$ is then given by

$$ \mathbb{E}(T_A^r | X_0 = i) = \sum_{k=1}^{\infty} k^r (P_{A^c}^{k-1} P_{A^c,A} \mathbf{1})_i. \qquad (2) $$

The following theorem gives a finite expression of this r-th moment which involves only the successive powers of matrix $(I - P_{A^c})^{-1}$.

**Theorem 1** For every $r \ge 1$, we have

$$ \mathbb{E}(T_A^r | X_0 = i) = \sum_{\ell=1}^{r} c_{r,\ell} ((I - P_{A^c})^{-\ell} \mathbf{1})_i $$

where, for every $\ell = 1, \dots, r$,

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

**Proof.** For $r \ge 0$ and $x \in (0, 1]$, we introduce the notation $G_r(x) = \sum_{k=1}^{\infty} k^r x^{k-1} P_{A^c}^{k-1}$. We prove by induction that, for $r \ge 1$ we have

$$ G_r(x) = \sum_{\ell=1}^{r} c_{r,\ell} (I - x P_{A^c})^{-(\ell+1)} \quad \text{where } c_{r,\ell} = (-1)^r \sum_{j=1}^{\ell} (-1)^j \binom{\ell}{j} j^r. $$

The result is true for $r = 1$. Indeed, for $r = 1$ we have

$$ G_1(x) = \sum_{k=1}^{\infty} k x^{k-1} P_{A^c}^{k-1}, $$

which gives

$$ \int_0^x G_1(t) dt = \sum_{k=1}^{\infty} k \left( \int_0^x t^{k-1} dt \right) P_{A^c}^{k-1} = \sum_{k=1}^{\infty} x^k P_{A^c}^{k-1} = x G_0(x) = x (I - x P_{A^c})^{-1}. $$

By taking the derivative with respect to $x$, we get

$$ G_1(x) = (I - x P_{A^c})^{-1} + x P_{A^c} (I - x P_{A^c})^{-2} = (I - x P_{A^c} + x P_{A^c}) (I - x P_{A^c})^{-2} = (I - x P_{A^c})^{-2}. $$

On the other hand, the equality is satisfied since $c_{1,1} = 1$.

Suppose that the relation is true for index $r-1$, i.e. suppose that

$$ G_{r-1}(x) = \sum_{\ell=1}^{r-1} c_{r-1,\ell} (I - x P_{A^c})^{-(\ell+1)} \quad \text{where } c_{r-1,\ell} = (-1)^{r-1} \sum_{j=1}^{\ell} (-1)^j \binom{\ell}{j} j^{r-1}. $$
By taking the derivative with respect to $x$, we get

$$S_r(x) = S_{r-1}(x) + xS'_{r-1}(x).$$

Using the recurrence hypothesis we obtain

$$S_r(x) = \sum_{\ell=1}^{r-1} c_{r-1,\ell} (I - xP_{A^c})^{-(\ell+1)} + xP_{A^c} \sum_{\ell=1}^{r-1} (\ell+1)c_{r-1,\ell} (I - xP_{A^c})^{-(\ell+2)}.$$

Observing that $xP_{A^c}(\ell+1)c_{r-1,\ell} = -(\ell+1)c_{r-1,\ell}(I - xP_{A^c}) + (\ell+1)c_{r-1,\ell}I$, we get

$$\begin{aligned}
S_r(x) &= \sum_{\ell=1}^{r-1} c_{r-1,\ell} (I - xP_{A^c})^{-(\ell+1)} - \sum_{\ell=1}^{r-1} (\ell+1)c_{r-1,\ell} (I - xP_{A^c})^{-(\ell+1)} + \sum_{\ell=1}^{r-1} (\ell+1)c_{r-1,\ell} (I - xP_{A^c})^{-(\ell+2)} \\
&= -\sum_{\ell=1}^{r-1} \ell c_{r-1,\ell} (I - xP_{A^c})^{-(\ell+1)} + \sum_{\ell=2}^{r} \ell c_{r-1,\ell-1} (I - xP_{A^c})^{-(\ell+1)} \\
&= -c_{r-1,1} (I - xP_{A^c})^{-2} + \sum_{\ell=2}^{r-1} \ell (c_{r-1,\ell-1} - c_{r-1,\ell}) (I - xP_{A^c})^{-(\ell+1)} + rc_{r-1,r-1} (I - xP_{A^c})^{-(r+1)}.
\end{aligned}$$

Note that $-c_{r-1,1} = (-1)^r = c_{r,1}$. Moreover since it is well-known that $c_{r-1,r-1} = (r-1)!$, we have $rc_{r-1,r-1} = r! = c_{r,r}$. Finally, for $\ell = 2, \dots, r-1$, we obtain

$$\begin{aligned}
\ell(c_{r-1,\ell-1} - c_{r-1,\ell}) &= \ell \left[ (-1)^{r-1} \sum_{j=1}^{\ell-1} (-1)^j \binom{\ell-1}{j} j^{r-1} - (-1)^{r-1} \sum_{j=1}^{\ell} (-1)^j \binom{\ell}{j} j^{r-1} \right] \\
&= (-1)^{r-1} \sum_{j=1}^{\ell-1} (-1)^j \ell \left[ \binom{\ell-1}{j} - \binom{\ell}{j} \right] j^{r-1} - (-1)^{r-1} (-1)^\ell \ell^r \\
&= (-1)^{r-1} \sum_{j=1}^{\ell-1} (-1)^j (-j) \binom{\ell}{j} j^{r-1} - (-1)^{r-1} (-1)^\ell \ell^r \\
&= (-1)^r \sum_{j=1}^{\ell-1} (-1)^j \binom{\ell}{j} j^r + (-1)^r (-1)^\ell \ell^r \\
&= c_{r,\ell}.
\end{aligned}$$

We thus recover

$$S_r(x) = \sum_{\ell=1}^{r} c_{r,\ell} (I - xP_{A^c})^{-(\ell+1)},$$

which completes the proof by recurrence. Using relation (2), we obtain

$$\mathbb{E}(T_A^r | X_0 = i) = (S_r(1)P_{A^c,A}1)_i = \sum_{\ell=1}^{r} c_{r,\ell} \left( (I - P_{A^c})^{-\ell} (I - P_{A^c})^{-1} P_{A^c,A}1 \right)_i.$$

Matrix $P$ being stochastic we have $(I - P_{A^c})^{-1} P_{A^c,A}1 = 1$, which completes the proof.

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

Taking $r = 1$ in Theorem 1, we get the expected hitting time of subset $A$, i.e.

$$\mathbb{E}(T_A | X_0 = i) = ((I - P_{A^c})^{-1}1)_i. \qquad (3)$$

Taking $r = 2$ in Theorem 1, we get the second order moment of $T_A$, i.e.

$$\mathbb{E}(T_A^2 | X_0 = i) = - \left( (I - P_{A^c})^{-1} 1 \right)_i + 2 \left( (I - P_{A^c})^{-2} 1 \right)_i. \qquad (4)$$

The following section is devoted to the analysis of the hitting times moments on the lollipop graph.
We then have

$$ \int_{0}^{x} G_{r}(t)dt = \sum_{k=1}^{\infty} k^{r-1}x^{k}P_{A^{c}}^{k-1} = xG_{r-1}(x). $$

By taking the derivative with respect to $x$, we get

$$ G_{r}(x) = G_{r-1}(x) + xG'_{r-1}(x). $$

Using the induction hypothesis we obtain

$$ G_{r}(x) = \sum_{\ell=1}^{r-1} c_{r-1,\ell} (I - xP_{A^{c}})^{-(\ell+1)} + xP_{A^{c}} \sum_{\ell=1}^{r-1} (\ell+1)c_{r-1,\ell} (I - xP_{A^{c}})^{-(\ell+2)}. $$

Observing that $xP_{A^{c}}(\ell+1)c_{r-1,\ell} = -(\ell+1)c_{r-1,\ell}(I-xP_{A^{c}}) + (\ell+1)c_{r-1,\ell}I$, we get

$$ \begin{aligned} G_{r}(x) &= \sum_{\ell=1}^{r-1} c_{r-1,\ell} (I - xP_{A^{c}})^{-(\ell+1)} - \sum_{\ell=1}^{r-1} (\ell+1)c_{r-1,\ell} (I - xP_{A^{c}})^{-(\ell+1)} + \sum_{\ell=1}^{r-1} (\ell+1)c_{r-1,\ell} (I - xP_{A^{c}})^{-(\ell+2)} \\ &= -\sum_{\ell=1}^{r-1} \ell c_{r-1,\ell} (I - xP_{A^{c}})^{-(\ell+1)} + \sum_{\ell=2}^{r} \ell c_{r-1,\ell-1} (I - xP_{A^{c}})^{-(\ell+1)} \\ &= -c_{r-1,1} (I - xP_{A^{c}})^{-2} + \sum_{\ell=2}^{r-1} \ell (c_{r-1,\ell-1} - c_{r-1,\ell}) (I - xP_{A^{c}})^{-(\ell+1)} + rc_{r-1,r-1} (I - xP_{A^{c}})^{-(r+1)}. \end{aligned} $$

Note that $-c_{r-1,1} = (-1)^{r+1} = c_{r,r}$. Moreover since it is well-known that $c_{r-1,r-1} = (r-1)!$, we have $rc_{r-1,r-1} = r! = c_{r,r}$. Finally, for $\ell = 2, \dots, r-1$, we obtain

$$ \begin{aligned} \ell(c_{r-1,\ell-1} - c_{r-1,\ell}) &= \ell \left[ (-1)^{r-1} \sum_{j=1}^{\ell-1} (-1)^j \binom{\ell-1}{j} j^{r-1} - (-1)^{r-1} \sum_{j=1}^{\ell} (-1)^j \binom{\ell}{j} j^{r-1} \right] \\ &= (-1)^{r-1} \sum_{j=1}^{\ell-1} (-1)^j \ell \left[ \binom{\ell-1}{j} - \binom{\ell}{j} \right] j^{r-1} - (-1)^{r-1} (-1)^\ell \ell^r \\ &= (-1)^{r-1} \sum_{j=1}^{\ell-1} (-1)^j (-j) \binom{\ell}{j} j^{r-1} - (-1)^{r-1} (-1)^\ell \ell^r \\ &= (-1)^r \sum_{j=1}^{\ell-1} (-1)^j \binom{\ell}{j} j^r + (-1)^r (-1)^\ell \ell^r \\ &= c_{r,\ell}. \end{aligned} $$

We thus recover

$$ G_{r}(x) = \sum_{\ell=1}^{r} c_{r,\ell} (I - xP_{A^{c}})^{-(\ell+1)}, $$

which completes the proof by induction. Using relation (2), we obtain

$$ \mathbb{E}(T_A^r | X_0 = i) = (G_r(1)P_{A^c,A}1)_i = \sum_{\ell=1}^{r} c_{r,\ell} \left( (I - P_{A^c})^{-\ell} (I - P_{A^c})^{-1} P_{A^c,A}1 \right)_i. $$

Matrix $P$ being stochastic we have $(I - P_{A^c})^{-1} P_{A^c,A}1 = 1$, which completes the proof. ■
### 3 The lollipop graph

Recall that for $n, m \in \mathbb{N}$, with $2 \le m < n$, the $n$-vertex lollipop graph, $L_m^n$, consists of a clique on $m$ vertices and a path graph on $n - m$ vertices. The $m$ vertices of the clique are numbered $1, \dots, m$ and the $n - m$ vertices of the path are numbered $m + 1, \dots, n$, vertex $m$ being the one joining the clique and the path as shown in Figure 1.

We consider a random walk on the vertices of a lollipop graph $L_m^n$, that is a Markov chain $X = \{X_k, k \in \mathbb{N}\}$, for which the transition probability from a state $i$ to each neighbor $j$ of $i$ occurs with equal probability. More precisely the state space of $X$ is the set $S = \{1, \dots, m-1, m, m+1, \dots, n\}$ with transition probability matrix $P$ which non zero entries are given by

$$ 
\left\{ 
\begin{array}{ll}
P_{i,j} = \frac{1}{m-1} & \text{for } i,j \in \{1, \dots, m-1\} \text{ and } i \neq j, \\
P_{i,m} = \frac{1}{m-1} & \text{for } i \in \{1, \dots, m-1\}, \\
P_{m,j} = \frac{1}{m} & \text{for } j \in \{1, \dots, m-1, m+1\}, \\
P_{i,i-1} = P_{i,i+1} = \frac{1}{2} & \text{for } i \in \{m+1, \dots, n-1\}, \\
P_{n,n-1} = 1. & 
\end{array}
\right. 
$$

For example, this matrix is represented below for $m = 5$ and $n = 9$.

$$ P = \begin{pmatrix}
0 & 1/4 & 1/4 & 1/4 & 1/4 & 0 & 0 & 0 & 0 \\
1/4 & 0 & 1/4 & 1/4 & 1/4 & 0 & 0 & 0 & 0 \\
1/4 & 1/4 & 0 & 1/4 & 1/4 & 0 & 0 & 0 & 0 \\
1/4 & 1/4 & 1/4 & 0 & 1/4 & 0 & 0 & 0 & 0 \\
1/5 & 1/5 & 1/5 & 1/5 & 0 & 1/5 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
\end{pmatrix} \quad (5) $$

The hitting time on the lollipop graph is the time needed to reach state $n$ when the initial state is state $i = 1, \dots, n-1$. According to the notation of the previous section, it is given by the random variable $T_n$. As usual, we use the convention that a sum of terms $\sum_a^b (...) = 0$ when $a > b$. Concerning the $r$-th moment of $T_n$, we will write $\mathbb{E}_i(T_n^r)$ for $\mathbb{E}(T_n^r | X_0 = i)$, $\mathbb{W}_i(T_n)$ for the variance $\mathbb{V}(T_n | X_0 = i)$ and for any event $E$, $\mathbb{P}_i(E)$ for $\mathbb{P}(E | X_0 = i)$.

#### 3.1 Mean hitting time

Using relation (3) with $A = \{n\}$, we obtain for $i = 1, \dots, n-1$,

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

Matrix $P_{\{1,...,n-1\}}$ is the submatrix obtained from $P$ by deleting row $n$ and column $n$. As suggested by the example above, we decompose matrix $P_{\{1,...,n-1\}}$ through the partition $\{1, \dots, m-1\}, \{m\}, \{m+1, \dots, n-1\}$
As a byproduct of Theorem 1, the reader may note that taking $r = 1$ in the Theorem we get the expected hitting time of subset A, i.e.

$$ \mathbb{E}(T_A | X_0 = i) = ((I - P_{A^c})^{-1} 1)_i, \qquad (3) $$

while taking $r = 2$ we get the second order moment of $T_A$, i.e.

$$ \mathbb{E}(T_A^2 | X_0 = i) = -((I - P_{A^c})^{-1} 1)_i + 2((I - P_{A^c})^{-2} 1)_i. \qquad (4) $$

In this spirit, the following section is devoted to the analysis of all moments of the hitting time on the lollipop graph.

## 3 The lollipop graph

Recall that for $n, m \in \mathbb{N}$, with $2 \le m < n$, the $n$-vertex lollipop graph, $L_m^n$, consists of a clique on $m$ vertices and a path graph on $n - m$ vertices. The $m$ vertices of the clique are numbered $1, \dots, m$ and the $n - m$ vertices of the path are numbered $m + 1, \dots, n$, vertex $m$ being the one joining the clique and the path as shown in Figure 1.

We consider a random walk on the vertices of a lollipop graph $L_m^n$, that is a Markov chain $X = \{X_k, k \in \mathbb{N}\}$, for which the transition probability from a state $i$ to each neighbor $j$ of $i$ occurs with equal probability. More precisely the state space of $X$ is the set $S = \{1, \dots, m-1, m, m+1, \dots, n\}$ with transition probability matrix $P$ which non zero entries are given by

$$ \left\{ \begin{array}{ll} P_{i,j} = \frac{1}{m-1} & \text{for } i,j \in \{1, \dots, m-1\} \text{ and } i \neq j, \\ \\ P_{i,m} = \frac{1}{m-1} & \text{for } i \in \{1, \dots, m-1\}, \\ \\ P_{m,j} = \frac{1}{m} & \text{for } j \in \{1, \dots, m-1, m+1\}, \\ \\ P_{i,i-1} = P_{i,i+1} = \frac{1}{2} & \text{for } i \in \{m+1, \dots, n-1\}, \\ \\ P_{n,n-1} = 1. & \end{array} \right. $$

For example, this matrix is represented below for $m = 5$ and $n = 9$.

$$ P = \begin{pmatrix} 0 & 1/4 & 1/4 & 1/4 & 1/4 & 0 & 0 & 0 & 0 \\ 1/4 & 0 & 1/4 & 1/4 & 1/4 & 0 & 0 & 0 & 0 \\ 1/4 & 1/4 & 0 & 1/4 & 1/4 & 0 & 0 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 0 & 1/4 & 0 & 0 & 0 & 0 \\ 1/5 & 1/5 & 1/5 & 1/5 & 0 & 1/5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}. \qquad (5) $$

The hitting time on the lollipop graph is the time needed to reach state $n$ when the initial state is state $i = 1, \dots, n-1$. According to the notation of the previous section, it is given by the random variable $T_n$. As usual, we use the convention that a sum of terms $\sum_a^b (...) = 0$ when $a > b$. Concerning the $r$-th moment of $T_n$, we will write $\mathbb{E}_i(T_n^r)$ for $\mathbb{E}(T_n^r | X_0 = i)$, $\mathbb{W}_i(T_n)$ for the variance $\mathbb{W}(T_n | X_0 = i)$ and for any event $E$, $\mathbb{P}_i(E)$ for $\mathbb{P}(E | X_0 = i)$.
of the set of states {$1, \dots, n-1$} as follows.

$$ P_{\{1, \dots, n-1\}} = \begin{pmatrix} Q & \frac{1}{m-1} \mathbb{1} & 0 \\ \frac{1}{m} \mathbb{1}^{\top} & 0 & \frac{1}{m} c^{\top} \\ 0 & \frac{1}{2} c & R \end{pmatrix}, \qquad (6) $$

where $\top$ denotes the transpose operator, $Q$ is the $(m-1, m-1)$ matrix given, for $i \neq j$, by $Q_{i,j} = 1/(m-1)$, $c$ is the unit column vector defined by $c = (1, 0, \dots, 0)^{\top}$ with dimension $n-m-1$ and $R$ is the $(n-m-1, n-m-1)$ matrix which non zero entries are given by $R_{i,i-1} = R_{i,i+1} = 1/2$ for $i = m+1, \dots, n-1$.

We then have the following explicit expression of the mean hitting time of state $n$ when starting from state $i$, with $i \neq n$. A part of this result has already been obtained in [9] when $i \in \{1, \dots, m-1\}$ using another proof. The proof used here is relevant because it is the starting point for the obtention of higher order moments for which we need in addition the mean hitting time of state $n$ when starting from state $i \in \{m, \dots, n-1\}$.

**Theorem 2** For every $n, m \in \mathbb{N}$, with $2 \le m \le n$ we have

$$ \mathbb{E}_i(T_n) = (n-m)(m^2 - 2m + n) + m - 1 \quad \text{for } i = 1, \dots, m-1 $$

$$ \mathbb{E}_i(T_n) = (n-m)(m^2 - 2m + n) - (i-m)(m^2 - 2m + i) \quad \text{for } i = m, \dots, n. $$

**Proof.** We introduce the column vector $V = (v_1, \dots, v_{n-1})^{\top}$ defined by $V = (I - P_{\{1, \dots, n-1\}})^{-1} \mathbb{1}$. We decompose vector $V$ following the partition used in (6), by writing

$$ V = \begin{pmatrix} V_1 \\ v_m \\ V_2 \end{pmatrix}, \quad \text{with} \quad V_1 = \begin{pmatrix} v_1 \\ \vdots \\ v_{m-1} \end{pmatrix} \quad \text{and} \quad V_2 = \begin{pmatrix} v_{m+1} \\ \vdots \\ v_{n-1} \end{pmatrix}. $$

We then have $\mathbb{E}_i(T_n) = v_i$ with

$$ V = (I - P_{\{1, \dots, n-1\}})^{-1} \mathbb{1} \iff (I - P_{\{1, \dots, n-1\}}) V = \mathbb{1} \iff \left\{ \begin{array}{l} V_1 - QV_1 - \frac{v_m}{m-1} \mathbb{1} = \mathbb{1} \\ v_m - \frac{1}{m} \mathbb{1}^{\top} V_1 - \frac{1}{m} c^{\top} V_2 = \mathbb{1} \\ V_2 - \frac{v_m}{2} c - R V_2 = \mathbb{1}. \end{array} \right. $$

Observing, by symmetry, that $\mathbb{E}_i(T_n)$ has the same value for every $i \in \{1, \dots, m-1\}$, we have $v_1 = \dots = v_{m-1}$. We denote this common value by $v$. We then have

$$ V_1 = v \mathbb{1}, \quad QV_1 = vQ \mathbb{1} = \frac{(m-2)v}{m-1} \mathbb{1}, \quad \mathbb{1}^{\top} V_1 = (m-1)v, \quad c^{\top} V_2 = v_{m+1}, $$

which leads to

$$ \left\{ \begin{array}{l} v_m = v - m + 1 \\ v_m - \frac{(m-1)v}{m} - \frac{v_{m+1}}{m} = 1 \\ v_i - \frac{1}{2}v_{i-1} - \frac{1}{2}v_{i+1} = 1, \text{ for } i = m+1, \dots, n-1, \end{array} \right. \qquad (7) $$
## 3.1 Mean hitting time

Using relation (3) with $A = \{n\}$, we obtain for $i = 1, \dots, n-1$,

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

Matrix $P_{\{1,...,n-1\}}$ is the submatrix obtained from $P$ by deleting row $n$ and column $n$. As suggested by the example above, we decompose matrix $P_{\{1,...,n-1\}}$ through the partition $\{1, \dots, m-1\}$, $\{m\}$, $\{m+1, \dots, n-1\}$ of the set of states $\{1, \dots, n-1\}$ as follows.

$$ P_{\{1,...,n-1\}} = \begin{pmatrix} Q & \frac{1}{m-1}1 & 0 \\ \frac{1}{m}1^{\top} & 0 & \frac{1}{m}c^{\top} \\ 0 & \frac{1}{2}c & R \end{pmatrix}, \qquad (6) $$

where $\top$ denotes the transpose operator, $Q$ is the $(m-1, m-1)$ matrix given, for $i \neq j$, by $Q_{i,j} = 1/(m-1)$, $c$ is the unit column vector defined by $c = (1, 0, \dots, 0)^{\top}$ with dimension $n-m-1$ and $R$ is the $(n-m-1, n-m-1)$ matrix, of which non zero entries are given by $R_{i,i-1} = R_{i,i+1} = 1/2$ for $i = m+1, \dots, n-1$.

We then have the following explicit expression of the mean hitting time of state $n$ when starting from state $i$, with $i \neq n$. A part of this result has already been obtained in [9] when $i \in \{1, \dots, m-1\}$ using another proof. The proof used here is relevant because it is the starting point for the obtention of higher order moments for which we need in addition the mean hitting time of state $n$ when starting from state $i \in \{m, \dots, n-1\}$.

**Theorem 2** For every $n, m \in \mathbb{N}$, with $2 \le m \le n$ we have

$$ \mathbb{E}_i(T_n) = (n-m)(m^2 - 2m + n) + m - 1 \quad \text{for } i = 1, \dots, m-1 $$

$$ \mathbb{E}_i(T_n) = (n-m)(m^2 - 2m + n) - (i-m)(m^2 - 2m + i) \quad \text{for } i = m, \dots, n. $$

**Proof.** We introduce the column vector $V = (v_1, \dots, v_{n-1})^{\top}$ defined by $V = (I - P_{\{1,...,n-1\}})^{-1}1$. We decompose vector $V$ following the partition used in (6), by writing

$$ V = \begin{pmatrix} V_1 \\ v_m \\ V_2 \end{pmatrix}, \quad \text{with} \quad V_1 = \begin{pmatrix} v_1 \\ \vdots \\ v_{m-1} \end{pmatrix} \quad \text{and} \quad V_2 = \begin{pmatrix} v_{m+1} \\ \vdots \\ v_{n-1} \end{pmatrix}. $$

We then have $\mathbb{E}_i(T_n) = v_i$ with

$$ V = (I - P_{\{1,...,n-1\}})^{-1}1 \iff (I - P_{\{1,...,n-1\}})V = 1 \iff \left\{ \begin{array}{l} V_1 - QV_1 - \frac{v_m}{m-1}1 = 1 \\ v_m - \frac{1}{m}1^{\top}V_1 - \frac{1}{m}c^{\top}V_2 = 1 \\ V_2 - \frac{v_m}{2}c - RV_2 = 1. \end{array} \right. $$

Observing, by symmetry, that $\mathbb{E}_i(T_n)$ has the same value for every $i \in \{1, \dots, m-1\}$, we have $v_1 = \dots = v_{m-1}$. We denote this common value by $v$. We then have

$$ V_1 = v1, \quad QV_1 = vQ1 = \frac{(m-2)v}{m-1}1, \quad 1^{\top}V_1 = (m-1)v, \quad c^{\top}V_2 = v_{m+1}, $$
where we have defined $v_n = \mathbb{E}_n(T_n) = 0$. Using the first relation of (7) in the second one of (7), we obtain $v_{m+1} = v - m^2$. Defining $z_i = v_i - v_{i+1}$ for $i = m, \dots, n-1$, the third relation of (7) gives $z_i = z_{i-1} + 2$, for $i = m+1, \dots, n-1$ with $z_m = v_m - v_{m+1} = v - m + 1 - (v - m^2) = m^2 - m + 1$. It follows that $z_{m+i} = z_m + 2i = m^2 - m + 1 + 2i$ and thus

$$v_m = \sum_{i=m}^{n-1} z_i = \sum_{i=0}^{n-m-1} z_{m+i} = (n-m)(m^2 - 2m + n).$$

We then get the value of $v$ using $v = v_m + m - 1$. In the same way, we have

$$v_m - v_{m+i} = \sum_{\ell=m}^{m+i-1} z_{\ell} = \sum_{\ell=0}^{i-1} z_{m+\ell} = i(m^2 - m + 1) + i(i - 1) = i(m^2 - m + i),$$

which gives for $i = 0, \dots, n-m$,

$$v_{m+i} = v_m - i(m^2 - m + i) = (n-m)(m^2 - 2m + n) - i(m^2 - m + i),$$

that is $v_i = (n-m)(m^2 - 2m + n) - (i-m)(m^2 - 2m + i)$, for $i = m, \dots, n$.

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

## 3.2 Variance of the hitting time

To evaluate the variance of the hitting time $T_n$, we first calculate the second order moment $\mathbb{E}(T_n^2)$. Using relation (4) with $A = \{n\}$, we obtain for $i = 1, \dots, n-1$,

$$\mathbb{E}_i(T_n^2) = -((I - P_{\{1,...,n-1\}})^{-1}1)_i + 2((I - P_{\{1,...,n-1\}})^{-2}1)_i.$$

**Theorem 3** For every $n, m \in \mathbb{N}$, with $2 \le m \le n$ we have, for $i = 1, \dots, m-1$

$$\mathbb{E}_i(T_n^2) = 2(n-m)[(m^2 - m + 1)v - m(m-1)] + (2m-3)v + 4 \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell$$

and for $i = m, \dots, n$

$$\mathbb{E}_i(T_n^2) = 2(n-i)[(m^2 - m + 1)v - m(m-1)] - v_i + 4 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell - \sum_{\ell=m+1}^{i-1} (i-\ell)v_\ell \right),$$

where the values of $v$ and $v_\ell$, which are given by Theorem 2, are $v = (n-m)(m^2 - 2m + n) + m - 1$ and $v_\ell = (n-m)(m^2 - 2m + n) - (\ell - m)(m^2 - 2m + \ell)$, for $\ell = m, \dots, n-1$.

**Proof.** The proof is close to the one of Theorem 2. We first introduce the column vectors $V = (v_1, \dots, v_{n-1})^\top$ and $W = (w_1, \dots, w_{n-1})^\top$ defined by

$$V = (I - P_{\{1,...,n-1\}})^{-1}1, \quad W = (I - P_{\{1,...,n-1\}})^{-2}1.$$

Vector $W$ is thus given by $W = (I - P_{\{1,...,n-1\}})^{-1}V$, where vector $V$ has been obtained in Theorem 2. As we did for vector $V$, we decompose vector $W$ following the partition used in (6), by writing

$$W = \begin{pmatrix} W_1 \\ w_m \\ W_2 \end{pmatrix}, \text{ with } W_1 = \begin{pmatrix} w_1 \\ \vdots \\ w_{m-1} \end{pmatrix} \text{ and } W_2 = \begin{pmatrix} w_{m+1} \\ \vdots \\ w_{n-1} \end{pmatrix}.$$
which leads to

$$ egin{cases} v_m = v - m + 1 \\ v_m - \frac{(m-1)v}{m} - \frac{v_{m+1}}{m} = 1 \\ v_i - \frac{1}{2}v_{i-1} - \frac{1}{2}v_{i+1} = 1, \text{ for } i = m+1, \dots, n-1, \end{cases} \quad (7) $$

where we have defined $v_n = \mathbb{E}_n(T_n) = 0$. Using the first relation of (7) in the second one of (7), we obtain $v_{m+1} = v - m^2$. Defining $z_i = v_i - v_{i+1}$ for $i = m, \dots, n-1$, the third relation of (7) gives $z_i = z_{i-1} + 2$, for $i = m+1, \dots, n-1$ with $z_m = v_m - v_{m+1} = v - m + 1 - (v - m^2) = m^2 - m + 1$. It follows that $z_{m+i} = z_m + 2i = m^2 - m + 1 + 2i$ and thus we obtain by telescoping

$$ v_m = \sum_{i=m}^{n-1} z_i = \sum_{i=0}^{n-m-1} z_{m+i} = (n-m)(m^2 - 2m + n). $$

We then get the value of $v$ using $v = v_m + m - 1$. In the same way, we have

$$ v_m - v_{m+i} = \sum_{\ell=m}^{m+i-1} z_{\ell} = \sum_{\ell=0}^{i-1} z_{m+\ell} = i(m^2 - m + 1) + i(i - 1) = i(m^2 - m + i), $$

which gives for $i = 0, \dots, n-m$,

$$ v_{m+i} = v_m - i(m^2 - m + i) = (n-m)(m^2 - 2m + n) - i(m^2 - m + i), $$

that is $v_i = (n-m)(m^2 - 2m + n) - (i-m)(m^2 - 2m + i)$, for $i = m, \dots, n$.

## 3.2 Variance of the hitting time

To evaluate the variance of the hitting time $T_n$, we first calculate the second order moment $\mathbb{E}(T_n^2)$. Using relation (4) with $A = \{n\}$, we obtain for $i = 1, \dots, n-1$,

$$ \mathbb{E}_i(T_n^2) = -((I - P_{\{1,...,n-1\}})^{-1}1)_i + 2((I - P_{\{1,...,n-1\}})^{-2}1)_i. $$

**Theorem 3** For every $n, m \in \mathbb{N}$, with $2 \le m \le n$ we have, for $i = 1, \dots, m-1$

$$ \mathbb{E}_i(T_n^2) = 2(n-m)[(m^2 - m + 1)v - m(m-1)] + (2m-3)v + 4 \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell $$

and for $i = m, \dots, n$

$$ \mathbb{E}_i(T_n^2) = 2(n-i)[(m^2 - m + 1)v - m(m-1)] - v_i + 4 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell - \sum_{\ell=m+1}^{i-1} (i-\ell)v_\ell \right), $$

where the values of $v$ and $v_\ell$, which are given by Theorem 2, are $v = (n-m)(m^2 - 2m + n) + m - 1$ and $v_\ell = (n-m)(m^2 - 2m + n) - (\ell - m)(m^2 - 2m + \ell)$, for $\ell = m, \dots, n-1$.

**Proof.** The proof is close to the one of Theorem 2. We first introduce the column vectors $V = (v_1, \dots, v_{n-1})^\top$ and $W = (w_1, \dots, w_{n-1})^\top$ defined by

$$ V = (I - P_{\{1,...,n-1\}})^{-1}1, \quad W = (I - P_{\{1,...,n-1\}})^{-2}1. $$
We first evaluate the vector W which is given by

$$ W = (I - P_{\{1,...,n-1\}})^{-1}V \iff (I - P_{\{1,...,n-1\}})W = V \iff \left\{ \begin{array}{l} W_1 - QW_1 - \frac{w_m}{m-1}1 = V_1 \\ w_m - \frac{1}{m}1^\top W_1 - \frac{1}{m}c^\top W_2 = v_m \\ W_2 - \frac{w_m}{2}c - RW_2 = V_2. \end{array} \right. $$

Observing, by symmetry, that $E_i(T_n^2)$ has the same value for every $i = 1, \dots, m-1$, we have $w_1 = \dots = w_{m-1}$. We denote this common value by $w$. We then have

$$ W_1 = w1, \quad QW_1 = wQ1 = \frac{(m-2)w}{m-1}1, \quad 1^\top W_1 = (m-1)w, \quad c^\top W_2 = w_{m+1}, $$

which leads to

$$ \left\{ \begin{array}{l} w - \frac{(m-2)w}{m-1} - \frac{w_m}{m-1} = v \\ w_m - \frac{(m-1)w}{m} - \frac{w_{m+1}}{m} = v_m \\ w_i - \frac{1}{2}w_{i-1} - \frac{1}{2}w_{i+1} = v_i, \text{ for } i = m+1, \dots, n-1, \end{array} \right. \qquad (8) $$

where we have defined $w_n = E_n(T_n^2) = 0$. The first relation of (8) gives $w_m = w - (m-1)v$. Using this result in the second relation of (8) and the fact that $v_m = v - (m-1)$, we obtain $w_{m+1} = w - m^2v + m(m-1)$.

Defining $z_i = w_i - w_{i+1}$ for $i = m, \dots, n-1$, the third relation of (8) gives $z_i = z_{i-1} + 2v_i$, for $i = m+1, \dots, n-1$ with $z_m = w_m - w_{m+1} = (m^2 - m + 1)v - m(m-1)$. It follows that

$$ z_{m+i} = z_m + 2 \sum_{\ell=1}^{i} v_{m+\ell} = (m^2 - m + 1)v - m(m-1) + 2 \sum_{\ell=m+1}^{m+i} v_{\ell}, $$

and thus

$$ w_m = \sum_{i=m}^{n-1} z_i = \sum_{i=0}^{n-m-1} z_{m+i} = (n-m)[(m^2 - m + 1)v - m(m-1)] + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell. $$

We then get the value of $w$ using $w = w_m + (m-1)v$. In the same way, we have

$$ w_m - w_{m+i} = \sum_{\ell=m}^{m+i-1} z_\ell = \sum_{\ell=0}^{i-1} z_{m+\ell} = i[(m^2 - m + 1)v - m(m-1)] + 2 \sum_{\ell=m+1}^{m+i-1} (m + i - \ell)v_\ell, $$

which gives for $i = 1, \dots, n-m$,

$$ \begin{aligned} w_{m+i} &= w_m - i[(m^2 - m + 1)v - m(m-1)] - 2 \sum_{\ell=m+1}^{m+i-1} (m + i - \ell)v_\ell \\ &= (n - m - i)[(m^2 - m + 1)v - m(m-1)] + 2 \left( \sum_{\ell=m+1}^{n-1} (n - \ell)v_\ell - \sum_{\ell=m+1}^{m+i-1} (m + i - \ell)v_\ell \right), \end{aligned} $$

that is, for $i = m+1, \dots, n$,

$$ w_i = (n - i)[(m^2 - m + 1)v - m(m - 1)] + 2 \left( \sum_{\ell=m+1}^{n-1} (n - \ell)v_\ell - \sum_{\ell=m+1}^{i-1} (i - \ell)v_\ell \right). \qquad (9) $$
Vector $W$ is thus given by $W = (I - P_{\{1,...,n-1\}})^{-1}V$, where vector $V$ has been obtained in Theorem 2. As we did for vector $V$, we decompose vector $W$ following the partition used in (6), by writing

$$W = \begin{pmatrix} W_1 \\ w_m \\ W_2 \end{pmatrix}, \text{ with } W_1 = \begin{pmatrix} w_1 \\ \vdots \\ w_{m-1} \end{pmatrix} \text{ and } W_2 = \begin{pmatrix} w_{m+1} \\ \vdots \\ w_{n-1} \end{pmatrix}.$$

We first evaluate the vector $W$ which is given by

$$W = (I - P_{\{1,...,n-1\}})^{-1}V \iff (I - P_{\{1,...,n-1\}})W = V \iff \left\{ \begin{array}{l} W_1 - QW_1 - \frac{w_m}{m-1}1 = V_1 \\ w_m - \frac{1}{m}1^\top W_1 - \frac{1}{m}c^\top W_2 = v_m \\ W_2 - \frac{w_m}{2}c - RW_2 = V_2. \end{array} \right.$$

Observing, by symmetry, that $E_i(T_n^2)$ has the same value for every $i = 1, ..., m-1$, we have $w_1 = \cdots = w_{m-1}$. We denote this common value by $w$. We then have

$$W_1 = w1, \quad QW_1 = wQ1 = \frac{(m-2)w}{m-1}1, \quad 1^\top W_1 = (m-1)w, \quad c^\top W_2 = w_{m+1},$$

which leads to

$$\left\{ \begin{array}{l} w - \frac{(m-2)w}{m-1} - \frac{w_m}{m-1} = v \\ w_m - \frac{(m-1)w}{m} - \frac{w_{m+1}}{m} = v_m \\ w_i - \frac{1}{2}w_{i-1} - \frac{1}{2}w_{i+1} = v_i, \text{ for } i = m+1, \dots, n-1, \end{array} \right. \qquad (8)$$

where we have defined $w_n = E_n(T_n^2) = 0$. The first relation of (8) gives $w_m = w - (m-1)v$. Using this result in the second relation of (8) and the fact that $v_m = v - (m-1)$, we obtain $w_{m+1} = w - m^2v + m(m-1)$.

Defining $z_i = w_i - w_{i+1}$ for $i = m, ..., n-1$, the third relation of (8) gives $z_i = z_{i-1} + 2v_i$, for $i = m+1, ..., n-1$ with $z_m = w_m - w_{m+1} = (m^2 - m + 1)v - m(m-1)$. It follows that

$$z_{m+i} = z_m + 2 \sum_{\ell=1}^{i} v_{m+\ell} = (m^2 - m + 1)v - m(m-1) + 2 \sum_{\ell=m+1}^{m+i} v_{\ell},$$

and thus

$$w_m = \sum_{i=m}^{n-1} z_i = \sum_{i=0}^{n-m-1} z_{m+i} = (n-m)[(m^2 - m + 1)v - m(m-1)] + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell.$$

We then get the value of $w$ using $w = w_m + (m-1)v$. In the same way, we have

$$w_m - w_{m+i} = \sum_{\ell=m}^{m+i-1} z_\ell = \sum_{\ell=0}^{i-1} z_{m+\ell} = i[(m^2 - m + 1)v - m(m-1)] + 2 \sum_{\ell=m+1}^{m+i-1} (m + i - \ell)v_\ell,$$

which gives for $i = 1, ..., n-m$,

$$\begin{aligned} w_{m+i} &= w_m - i[(m^2 - m + 1)v - m(m-1)] - 2 \sum_{\ell=m+1}^{m+i-1} (m + i - \ell)v_\ell \\ &= (n - m - i)[(m^2 - m + 1)v - m(m-1)] + 2 \left( \sum_{\ell=m+1}^{n-1} (n - \ell)v_\ell - \sum_{\ell=m+1}^{m+i-1} (m + i - \ell)v_\ell \right), \end{aligned}$$
Since $\mathbb{E}_i(T_n^2) = 2w_i - v_i$, we obtain for $i = 1, \dots, m-1$, $\mathbb{E}_i(T_n^2) = 2w - v = 2w_m + (2m-3)v$, that is

$$ \mathbb{E}_i(T_n^2) = 2(n-m)[(m^2 - m + 1)v - m(m-1)] + (2m-3)v + 4 \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell $$

and, for $i = m, \dots, n-1$,

$$ \mathbb{E}_i(T_n^2) = 2(n-i)[(m^2 - m + 1)v - m(m-1)] - v_i + 4 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell - \sum_{\ell=m+1}^{i-1} (i-\ell)v_\ell \right), $$

which completes the proof.

The variance of $T_n$, when the initial state is state $i$, is then given by $\mathbb{V}_i(T_n) = \mathbb{E}_i(T_n^2) - \mathbb{E}_i(T_n)^2$.

### 3.3 Moments generating function of the hitting time

Using relation (1), the probability mass function of $T_n$ is given, for every $k \ge 1$, by

$$ \mathbb{P}_i\{T_n = k\} = \left( P_{\{1,...,n-1\}}^{k-1} P_{\{1,...,n-1\},\{n\}} 1 \right)_i. $$

The column vector $B = (b_1, \dots, b_{n-1})^\top$ defined by $B = P_{\{1,...,n-1\},\{n\}} 1$ has all its entries equal to 0, except the last one i.e. its $(n-1)$-th entry which is equal to $1/2$. We then have for every $k \ge 1$,

$$ \mathbb{P}_i\{T_n = k\} = \left( P_{\{1,...,n-1\}}^{k-1} B \right)_i, $$

with $B = (0, \dots, 0, 1/2)^\top$. The matrix $P_{\{1,...,n-1\}}$ being an irreducible sub-stochastic matrix, its spectral radius $\rho_n$ satisfies $0 < \rho_n < 1$. The moment generating function of the hitting time $T_n$ when the initial state is state $i$ is given by the function

$$ M_i(t) = \mathbb{E}_i (e^{tT_n}) = \sum_{k=0}^{\infty} e^{tk} \mathbb{P}_i\{T_n = k\} = \sum_{k=1}^{\infty} e^{tk} \left( P_{\{1,...,n-1\}}^{k-1} B \right)_i = e^t \left( \sum_{k=0}^{\infty} (e^t P_{\{1,...,n-1\}})^k B \right)_i. $$

This series converges for all real numbers $t$ such that $e^t \rho_n < 1$, that is for all $t$ such that $t < -\ln(\rho_n)$. For these values of $t$, we obtain

$$ M_i(t) = e^t \left( (I - e^t P_{\{1,...,n-1\}})^{-1} B \right)_i. $$

An explicit expression of the moment generating function $M_i(t)$ is given by the following theorem.

**Theorem 4** For every $n, m \in \mathbb{N}$, with $2 \le m \le n$ and for all $t$ such that $t < -\ln(\rho_n)$ we have

$$ \begin{align} M_i(t) &= \frac{1}{\sum_{\ell=0}^{n-m+1} a_{n-m, \ell} e^{-\ell t}} & \text{for } i=1, \dots, m-1 \nonumber \\ M_i(t) &= \frac{\sum_{\ell=0}^{i-m+1} a_{i-m, \ell} e^{-\ell t}}{\sum_{\ell=0}^{n-m+1} a_{n-m, \ell} e^{-\ell t}} & \text{for } i=m, \dots, n, \tag{10} \end{align} $$
that is, for $i = m + 1, \dots, n$,

$$w_i = (n-i)[(m^2 - m + 1)v - m(m-1)] + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell - \sum_{\ell=m+1}^{i-1} (i-\ell)v_\ell \right). \quad (9)$$

Since $\mathbb{E}_i(T_n^2) = 2w_i - v_i$, we obtain for $i = 1, \dots, m-1$, $\mathbb{E}_i(T_n^2) = 2w - v = 2w_m + (2m-3)v$, that is

$$\mathbb{E}_i(T_n^2) = 2(n-m)[(m^2 - m + 1)v - m(m-1)] + (2m-3)v + 4 \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell$$

and, for $i = m, \dots, n-1$,

$$\mathbb{E}_i(T_n^2) = 2(n-i)[(m^2 - m + 1)v - m(m-1)] - v_i + 4 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell - \sum_{\ell=m+1}^{i-1} (i-\ell)v_\ell \right),$$

which completes the proof.

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

The variance of $T_n$, when the initial state is state $i$, is then given by $\mathbb{V}_i(T_n) = \mathbb{E}_i(T_n^2) - \mathbb{E}_i(T_n)^2$.

### 3.3 Moments generating function of the hitting time

Using relation (1), the probability mass function of $T_n$ is given, for every $k \ge 1$, by

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

The column vector $B = (b_1, \dots, b_{n-1})^\top$ defined by $B = P_{\{1, \dots, n-1\}, \{n\}} 1$ has all its entries equal to 0, except the last one i.e. its $(n-1)$-th entry which is equal to $1/2$. We then have for every $k \ge 1$,

$$\mathbb{P}_i\{T_n = k\} = \left( P_{\{1, \dots, n-1\}}^{k-1} B \right)_i,$$

with $B = (0, \dots, 0, 1/2)^\top$. The matrix $P_{\{1, \dots, n-1\}}$ being an irreducible sub-stochastic matrix, its spectral radius $\rho_n$ satisfies $0 < \rho_n < 1$. The moment generating function of the hitting time $T_n$ when the initial state is state $i$ is given by the function

$$M_i(t) = \mathbb{E}_i (e^{tT_n}) = \sum_{k=0}^{\infty} e^{tk} \mathbb{P}_i\{T_n = k\} = \sum_{k=1}^{\infty} e^{tk} \left( P_{\{1, \dots, n-1\}}^{k-1} B \right)_i = e^t \left( \sum_{k=0}^{\infty} (e^t P_{\{1, \dots, n-1\}})^k B \right)_i .$$

This series converges for all real numbers $t$ such that $e^t \rho_n < 1$, that is for all $t$ such that $t < -\ln(\rho_n)$. For these values of $t$, we obtain

$$M_i(t) = e^t \left( (I - e^t P_{\{1, \dots, n-1\}})^{-1} B \right)_i .$$

An explicit expression of the moment generating function $M_i(t)$ is given by the following theorem.

**Theorem 4** For every $n, m \in \mathbb{N}$, with $2 \le m \le n$ and for all $t$ such that $t < -\ln(\rho_n)$ we have

$$\begin{align}
M_i(t) &= \frac{1}{\sum_{\ell=0}^{n-m+1} a_{n-m, \ell} e^{-\ell t}} & \text{for } i=1, \dots, m-1 \nonumber \\
M_i(t) &= \frac{\sum_{\ell=0}^{i-m+1} a_{i-m, \ell} e^{-\ell t}}{\sum_{\ell=0}^{n-m+1} a_{n-m, \ell} e^{-\ell t}} & \text{for } i=m, \dots, n, \tag{10}
\end{align}$$
where the $a_{i,\ell}$ are given by

$$ a_{i,\ell} = \begin{cases} (-1)^{\frac{i-\ell+2}{2}} (m-2) 2^{\ell-1} \left[ \left( \frac{\frac{i+\ell-2}{2}}{\frac{i-\ell}{2}} \right) m + 2 \left( \frac{\frac{i+\ell-2}{2}}{\frac{i-\ell-2}{2}} \right) \right] & \text{if } i-\ell \text{ is even} \\ (-1)^{\frac{i-\ell+1}{2}} (m-1) 2^{\ell-2} \left[ \left( \frac{\frac{i+\ell-3}{2}}{\frac{i-\ell+1}{2}} \right) m + 2 \left( \frac{\frac{i+\ell-3}{2}}{\frac{i-\ell-1}{2}} \right) + 4 \left( \frac{\frac{i+\ell-1}{2}}{\frac{i-\ell-1}{2}} \right) \right] & \text{if } i-\ell \text{ is odd} \end{cases} $$

with the convention that $\binom{b}{a} = 0$ if $a \notin \{0, \dots, b-1\}$ and $\binom{b}{a} = 1$ for all $b < 0$.

**Proof.** We introduce the column vector $M(t) = (M_1(t), \dots, M_{n-1}(t))^{\top}$ defined by

$$ M(t) = e^t (I - e^t P_{\{1, \dots, n-1\}})^{-1} B. $$

As we did in the proofs of the previous theorems, we decompose vectors $M(t)$ and $B$ following the partition used in (6), by writing

$$ M(t) = \begin{pmatrix} M^{(1)}(t) \\ M_m(t) \\ M^{(2)}(t) \end{pmatrix}, \quad \text{with } M^{(1)}(t) = \begin{pmatrix} M_1(t) \\ \vdots \\ M_{m-1}(t) \end{pmatrix} \quad \text{and} \quad M^{(2)}(t) = \begin{pmatrix} M_{m+1}(t) \\ \vdots \\ M_{n-1}(t) \end{pmatrix}. $$

$$ B = \begin{pmatrix} B^{(1)} \\ 0 \\ B^{(2)} \end{pmatrix}, \quad \text{with } B^{(1)} = \begin{pmatrix} 0 \\ \vdots \\ 0 \end{pmatrix} \quad \text{and} \quad B^{(2)} = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1/2 \end{pmatrix}. $$

We then have

$$ M(t) = e^t (I - e^t P_{\{1, \dots, n-1\}})^{-1} B \iff (I - e^t P_{\{1, \dots, n-1\}}) M(t) = e^t B \quad \begin{cases} M^{(1)}(t) - e^t Q M^{(1)}(t) - \frac{e^t M_m(t)}{m-1} = 0 \\ M_m(t) - \frac{e^t}{m} \mathbf{1}^\top M^{(1)}(t) - \frac{e^t}{m} c^\top M^{(2)}(t) = 0 \\ M^{(2)}(t) - \frac{e^t M_m(t)}{2} c - e^t R M^{(2)}(t) = e^t B_2. \end{cases} $$

Observing, by symmetry, that $E_i (e^t T_n)$ has the same value for every $i \in \{1, \dots, m-1\}$, we have $M_1(t) = \dots = M_{m-1}(t)$. We denote this common value by $\mu(t)$. Hence

$$ M^{(1)}(t) = \mu(t)\mathbf{1}, \quad QM^{(1)}(t) = \mu(t)Q\mathbf{1} = \frac{(m-2)\mu(t)}{m-1}\mathbf{1}, \quad \mathbf{1}^\top M^{(1)}(t) = (m-1)\mu(t), \quad c^\top M^{(2)}(t) = M_{m+1}(t), $$

which leads to

$$ \left\{ \begin{aligned} & \mu(t) - \frac{(m-2)e^t \mu(t)}{m-1} - \frac{e^t M_m(t)}{m-1} = 0 \\ & M_m(t) - \frac{(m-1)e^t \mu(t)}{m} - \frac{e^t M_{m+1}(t)}{m} = 0 \\ & M_i(t) - \frac{e^t}{2} M_{i-1}(t) - \frac{e^t}{2} M_{i+1}(t) = 0, \text{ for } i = m+1, \dots, n-1, \end{aligned} \right. \quad (11) $$
where the $a_{i,l}$ are given by

$$ a_{i,l} = \begin{cases} (-1)^{\frac{i-\ell+2}{2}} (m-2) 2^{\ell-1} \left[ \left( \frac{\frac{i+\ell-2}{2}}{\frac{i-\ell}{2}} \right) m + 2 \left( \frac{\frac{i+\ell-2}{2}}{\frac{i-\ell-2}{2}} \right) \right] & \text{if } i-\ell \text{ is even} \\ (-1)^{\frac{i-\ell+1}{2}} (m-1) 2^{\ell-2} \left[ \left( \frac{\frac{i+\ell-3}{2}}{\frac{i-\ell+1}{2}} \right) m + 2 \left( \frac{\frac{i+\ell-3}{2}}{\frac{i-\ell-1}{2}} \right) + 4 \left( \frac{\frac{i+\ell-1}{2}}{\frac{i-\ell-1}{2}} \right) \right] & \text{if } i-\ell \text{ is odd} \end{cases} $$

with the convention that $\binom{b}{a} = 0$ if $a \notin \{0, \dots, b-1\}$ and $\binom{b}{a} = 1$ for all $b < 0$.

**Proof.** We introduce the column vector $M(t) = (M_1(t), \dots, M_{n-1}(t))^{\top}$ defined by

$$ M(t) = e^t (I - e^t P_{\{1, \dots, n-1\}})^{-1} B. $$

As we did in the proofs of the previous theorems, we decompose vectors $M(t)$ and $B$ following the partition used in (6), by writing

$$ M(t) = \begin{pmatrix} M^{(1)}(t) \\ M_m(t) \\ M^{(2)}(t) \end{pmatrix}, \quad \text{with } M^{(1)}(t) = \begin{pmatrix} M_1(t) \\ \vdots \\ M_{m-1}(t) \end{pmatrix} \quad \text{and} \quad M^{(2)}(t) = \begin{pmatrix} M_{m+1}(t) \\ \vdots \\ M_{n-1}(t) \end{pmatrix}. \\ \\ B = \begin{pmatrix} B^{(1)} \\ 0 \\ B^{(2)} \end{pmatrix}, \quad \text{with } B^{(1)} = \begin{pmatrix} 0 \\ \vdots \\ 0 \end{pmatrix} \quad \text{and} \quad B^{(2)} = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1/2 \end{pmatrix}. $$

We then have

$$ M(t) = e^t (I - e^t P_{\{1, \dots, n-1\}})^{-1} B \iff (I - e^t P_{\{1, \dots, n-1\}}) M(t) = e^t B \\ \iff \begin{cases} M^{(1)}(t) - e^t Q M^{(1)}(t) - \frac{e^t M_m(t)}{m-1} = 0 \\ M_m(t) - \frac{e^t}{m} \mathbf{1}^\top M^{(1)}(t) - \frac{e^t}{m} c^\top M^{(2)}(t) = 0 \\ M^{(2)}(t) - \frac{e^t M_m(t)}{2} c - e^t R M^{(2)}(t) = e^t B_2. \end{cases} $$

Observing, by symmetry, that $\mathbb{E}_i (e^t T_n)$ has the same value for every $i \in \{1, \dots, m-1\}$, we have $M_1(t) = \dots = M_{m-1}(t)$. We denote this common value by $\mu(t)$. Hence

$$ M^{(1)}(t) = \mu(t)\mathbf{1}, \quad QM^{(1)}(t) = \mu(t)Q\mathbf{1} = \frac{(m-2)\mu(t)}{m-1}\mathbf{1}, \quad \mathbf{1}^\top M^{(1)}(t) = (m-1)\mu(t), \quad c^\top M^{(2)}(t) = M_{m+1}(t), $$

which leads to

$$ \left\{ \begin{aligned} & \mu(t) - \frac{(m-2)e^t \mu(t)}{m-1} - \frac{e^t M_m(t)}{m-1} = 0 \\ & M_m(t) - \frac{(m-1)e^t \mu(t)}{m} - \frac{e^t M_{m+1}(t)}{m} = 0 \\ & M_i(t) - \frac{e^t}{2} M_{i-1}(t) - \frac{e^t}{2} M_{i+1}(t) = 0, \text{ for } i = m+1, \dots, n-1, \end{aligned} \right. \qquad (11) $$
where we have used the fact that $M_n(t) = \mathbb{E}_n (e^{tT_n}) = 1$. The first relation of (11) gives

$$M_m(t) = [(m-1)e^{-t} - (m-2)] \mu(t).$$

Using this result in the second relation of (11), we obtain $M_{m+1}(t) = me^{-t}M_m(t) - (m-1)\mu(t)$, that is

$$M_{m+1}(t) = [m(m-1)e^{-2t} - m(m-2)e^{-t} - (m-1)] \mu(t).$$

The third relation of (11) can be written as

$$M_i(t) = 2e^{-t}M_{i-1}(t) - M_{i-2}(t), \text{ for } i = m+2, \dots, n,$$

This second order recurrence relation together with the expressions of $M_m(t)$ and $M_{m+1}(t)$ implies that $M_{m+i}(t)$ can be written as

$$M_{m+i}(t) = \left[ \sum_{\ell=0}^{i+1} a_{i,\ell} e^{-\ell t} \right] \mu(t), \text{ for } i = 0, \dots, n-m. \quad (12)$$

We then must have for $i = 2, \dots, n-m$,

$$\sum_{\ell=0}^{i+1} a_{i,\ell} e^{-\ell t} = \sum_{\ell=0}^{i} 2a_{i-1,\ell} e^{-(\ell+1)t} - \sum_{\ell=0}^{i-1} a_{i-2,\ell} e^{-\ell t} = \sum_{\ell=1}^{i+1} 2a_{i-1,\ell-1} e^{-\ell t} - \sum_{\ell=0}^{i-1} a_{i-2,\ell} e^{-\ell t}.$$

It follows that the coefficients $a_{i,\ell}$ must satisfy, for $i = 2, \dots, n-m$,

$$\left\{ \begin{array}{l} a_{i,0} = -a_{i-2,0} \\ a_{i,\ell} = 2a_{i-1,\ell-1} - a_{i-2,\ell} \quad \text{for } \ell = 1, \dots, i-1 \\ a_{i,i} = 2a_{i-1,i-1} \\ a_{i,i+1} = 2a_{i-1,i} \end{array} \right.$$

with $a_{0,0} = -(m-2)$, $a_{0,1} = m-1$, $a_{1,0} = -(m-1)$, $a_{1,1} = -m(m-2)$ and $a_{1,2} = m(m-1)$. These initial values suggest that the coefficients $a_{i,\ell}$ can be expressed, for $i = 2, \dots, n-m$, as

$$a_{i,\ell} = \begin{cases} (-1)^{\frac{i-\ell+2}{2}} (m-2)a'_{i,\ell} & \text{if } i-\ell \text{ is even} \\ (-1)^{\frac{i-\ell+1}{2}} (m-1)a'_{i,\ell} & \text{if } i-\ell \text{ is odd,} \end{cases}$$

where

$$\left\{ \begin{array}{l} a'_{i,0} = a'_{i-2,0} \\ a'_{i,\ell} = 2a'_{i-1,\ell-1} + a_{i-2,\ell} \quad \text{for } \ell = 1, \dots, i-1 \\ a'_{i,i} = 2a'_{i-1,i-1} \\ a'_{i,i+1} = 2a'_{i-1,i} \end{array} \right. \qquad (13)$$

with $a'_{0,0} = 1$, $a'_{0,1} = 1$, $a'_{1,0} = 1$, $a_{1,1} = m$ and $a_{1,2} = m$. It is then easily checked that the following explicit expression of the $a'_{i,\ell}$ satisfies relations (13)

$$a'_{i,\ell} = \begin{cases} 2^{\ell-1} \left[ \left( \frac{i+\ell-2}{2} \right) m + 2 \left( \frac{i+\ell-2}{i-\ell-2} \right) \right] & \text{if } i-\ell \text{ is even} \\ 2^{\ell-2} \left[ \left( \frac{i+\ell-3}{2} \right) m + 2 \left( \frac{i+\ell-3}{i-\ell-1} \right) + 4 \left( \frac{i+\ell-1}{i-\ell-1} \right) \right] & \text{if } i-\ell \text{ is odd} \end{cases}$$

with the convention that $\binom{b}{a} = 0$ if $a \notin \{0, \dots, b-1\}$ and $\binom{b}{a} = 1$ for all $b < 0$.
where we have used the fact that $M_n(t) = \mathbb{E}_n (e^{tT_n}) = 1$. The first relation of (11) gives

$$M_m(t) = [(m-1)e^{-t} - (m-2)] \mu(t).$$

Using this result in the second relation of (11), we obtain $M_{m+1}(t) = me^{-t}M_m(t) - (m-1)\mu(t)$, that is

$$M_{m+1}(t) = [m(m-1)e^{-2t} - m(m-2)e^{-t} - (m-1)] \mu(t).$$

The third relation of (11) can be written as

$$M_i(t) = 2e^{-t}M_{i-1}(t) - M_{i-2}(t), \text{ for } i = m+2, \dots, n,$$

This second order recurrence relation together with the expressions of $M_m(t)$ and $M_{m+1}(t)$ implies that $M_{m+i}(t)$ can be written as

$$M_{m+i}(t) = \left[ \sum_{\ell=0}^{i+1} a_{i,\ell} e^{-\ell t} \right] \mu(t), \text{ for } i = 0, \dots, n-m. \qquad (12)$$

We then must have for $i = 2, \dots, n-m$,

$$\sum_{\ell=0}^{i+1} a_{i,\ell} e^{-\ell t} = \sum_{\ell=0}^{i} 2a_{i-1,\ell} e^{-(\ell+1)t} - \sum_{\ell=0}^{i-1} a_{i-2,\ell} e^{-\ell t} = \sum_{\ell=1}^{i+1} 2a_{i-1,\ell-1} e^{-\ell t} - \sum_{\ell=0}^{i-1} a_{i-2,\ell} e^{-\ell t}.$$

It follows that the coefficients $a_{i,\ell}$ must satisfy, for $i = 2, \dots, n-m$,

$$\left\{ \begin{array}{l} a_{i,0} = -a_{i-2,0} \\ a_{i,\ell} = 2a_{i-1,\ell-1} - a_{i-2,\ell} \quad \text{for } \ell = 1, \dots, i-1 \\ a_{i,i} = 2a_{i-1,i-1} \\ a_{i,i+1} = 2a_{i-1,i} \end{array} \right.$$

with $a_{0,0} = -(m-2)$, $a_{0,1} = m-1$, $a_{1,0} = -(m-1)$, $a_{1,1} = -m(m-2)$ and $a_{1,2} = m(m-1)$. These initial values suggest that the coefficients $a_{i,\ell}$ can be expressed, for $i = 2, \dots, n-m$, as

$$a_{i,\ell} = \begin{cases} (-1)^{\frac{i-\ell+2}{2}} (m-2)a'_{i,\ell} & \text{if } i-\ell \text{ is even} \\ (-1)^{\frac{i-\ell+1}{2}} (m-1)a'_{i,\ell} & \text{if } i-\ell \text{ is odd,} \end{cases}$$

where

$$\left\{ \begin{array}{l} a'_{i,0} = a'_{i-2,0} \\ a'_{i,\ell} = 2a'_{i-1,\ell-1} + a_{i-2,\ell} \quad \text{for } \ell = 1, \dots, i-1 \\ a'_{i,i} = 2a'_{i-1,i-1} \\ a'_{i,i+1} = 2a'_{i-1,i} \end{array} \right. \qquad (13)$$

with $a'_{0,0} = 1$, $a'_{0,1} = 1$, $a'_{1,0} = 1$, $a_{1,1} = m$ and $a_{1,2} = m$. It is then easily checked that the following explicit expression of the $a'_{i,\ell}$ satisfies relations (13)

$$a'_{i,\ell} = \begin{cases} 2^{\ell-1} \left[ \left( \frac{i+\ell-2}{2} \right) m + 2 \left( \frac{i+\ell-2}{i-\ell-2} \right) \right] & \text{if } i-\ell \text{ is even} \\ 2^{\ell-2} \left[ \left( \frac{i+\ell-3}{2} \right) m + 2 \left( \frac{i+\ell-3}{i-\ell-1} \right) + 4 \left( \frac{i+\ell-1}{i-\ell-1} \right) \right] & \text{if } i-\ell \text{ is odd} \end{cases}$$

with the convention that $\binom{b}{a} = 0$ if $a \notin \{0, \dots, b-1\}$ and $\binom{b}{a} = 1$ for all $b < 0$.
Since $M_n(t) = 1$ we get by taking $i = n - m$ in relation (12),

$$ \mu(t) = \frac{1}{\sum_{\ell=0}^{n-m+1} a_{n-m,\ell} e^{-\ell t}} \quad \text{and} \quad M_{m+i}(t) = \frac{\sum_{\ell=0}^{i+1} a_{i,\ell} e^{-\ell t}}{\sum_{\ell=0}^{n-m+1} a_{n-m,\ell} e^{-\ell t}}, \quad \text{for } i = 0, \dots, n-m $$

which can be written as

$$ M_i(t) = \frac{\sum_{\ell=0}^{i-m+1} a_{i-m,\ell} e^{-\ell t}}{\sum_{\ell=0}^{n-m+1} a_{n-m,\ell} e^{-\ell t}}, \quad \text{for } i = m, \dots, n. $$

This completes the proof.

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

Observe that, since $M_i(0) = 1$ for every $i = 1, \dots, n$, we have

$$ \sum_{\ell=0}^{i-m+1} a_{i-m,\ell} = 1, \quad \text{for all } i = m, \dots, n. $$

The moment generating function $M_i(t)$ is defined only for $t < -\ln(\rho_n)$ and it is well-known from the Perron-Frobenius theorem that $\rho_n$ is an eigenvalue of matrix $P_{\{1,...,n-1\}}$. That is why we study the eigenvalues of matrix $P_{\{1,...,n-1\}}$ in the following subsection.

## 3.4 Eigenvalues

We analyze in this section the eigenvalues of matrix $P_{\{1,...,n-1\}}$. For fixed $2 \le m \le n$ and $k = 1, \dots, n-1$ we consider submatrix $P_{\{1,...,k\}}$ of matrix $P$ which consists in removing the $n-1-k$ last lines and columns of matrix $P_{\{1,...,n-1\}}$. We denote by $R_k(x)$ the characteristic polynomial of matrix $P_{\{1,...,k\}}$ which is the determinant of matrix $xI - P_{\{1,...,k\}}$, that is

$$ R_k(x) = |xI - P_{\{1,...,k\}}|. $$

The following theorem gives the characteristic polynomial $R_k(x)$ of matrix $P_{\{1,...,k\}}$, for $k = 1, \dots, n-1$.

**Theorem 5** We have

$$ \begin{align*} R_k(x) &= \frac{(m-1)x - (k-1)}{m-1} \left( x + \frac{1}{m-1} \right)^{k-1}, \quad \text{for } k = 1, \dots, m-1 \\ R_m(x) &= \frac{m(m-1)x^2 - m(m-2)x - (m-1)}{m(m-1)} \left( x + \frac{1}{m-1} \right)^{m-2}, \\ R_{m+1}(x) &= xR_m(x) - \frac{1}{2m}R_{m-1}(x) \\ R_k(x) &= xR_{k-1}(x) - \frac{1}{4}R_{k-2}(x), \quad \text{for } k = m+2, \dots, n-1. \end{align*} $$

For $k = 1, \dots, n-m+1$, we have

$$ R_{m+k-2}(x) = S_k(x) \left( x + \frac{1}{m-1} \right)^{m-2}, $$
Since $M_n(t) = 1$ we get by taking $i = n - m$ in relation (12),

$$ \mu(t) = \frac{1}{\sum_{\ell=0}^{n-m+1} a_{n-m,\ell} e^{-\ell t}} \quad \text{and} \quad M_{m+i}(t) = \frac{\sum_{\ell=0}^{i+1} a_{i,\ell} e^{-\ell t}}{\sum_{\ell=0}^{n-m+1} a_{n-m,\ell} e^{-\ell t}}, \quad \text{for } i = 0, \dots, n-m $$

which can be written as

$$ M_i(t) = \frac{\sum_{\ell=0}^{i-m+1} a_{i-m,\ell} e^{-\ell t}}{\sum_{\ell=0}^{n-m+1} a_{n-m,\ell} e^{-\ell t}}, \quad \text{for } i = m, \dots, n. $$

This completes the proof.

Observe that, since $M_i(0) = 1$ for every $i = 1, \dots, n$, we have

$$ \sum_{\ell=0}^{i-m+1} a_{i-m,\ell} = 1, \quad \text{for all } i = m, \dots, n. $$

The moment generating function $M_i(t)$ is defined only for $t < -\ln(\rho_n)$ and it is well-known from the Perron-Frobenius theorem that $\rho_n$ is an eigenvalue of matrix $P_{\{1,...,n-1\}}$. That is why we study the eigenvalues of matrix $P_{\{1,...,n-1\}}$ in the following subsection.

## 3.4 Eigenvalues

We analyze in this section the eigenvalues of matrix $P_{\{1,...,n-1\}}$. For fixed $2 \le m \le n$ and $k = 1, \dots, n-1$ we consider submatrix $P_{\{1,...,k\}}$ of matrix $P$ which consists in removing the $n-1-k$ last lines and columns of matrix $P_{\{1,...,n-1\}}$. We denote by $R_k(x)$ the characteristic polynomial of matrix $P_{\{1,...,k\}}$ which is the determinant of matrix $xI - P_{\{1,...,k\}}$, that is

$$ R_k(x) = |xI - P_{\{1,...,k\}}|. $$

The following theorem gives the characteristic polynomial $R_k(x)$ of matrix $P_{\{1,...,k\}}$, for $k = 1, \dots, n-1$.

**Theorem 5** We have

$$ \begin{align*} R_k(x) &= \frac{(m-1)x - (k-1)}{m-1} \left( x + \frac{1}{m-1} \right)^{k-1}, \quad \text{for } k = 1, \dots, m-1 \\ R_m(x) &= \frac{m(m-1)x^2 - m(m-2)x - (m-1)}{m(m-1)} \left( x + \frac{1}{m-1} \right)^{m-2}, \\ R_{m+1}(x) &= xR_m(x) - \frac{1}{2m}R_{m-1}(x) \\ R_k(x) &= xR_{k-1}(x) - \frac{1}{4}R_{k-2}(x), \quad \text{for } k = m+2, \dots, n-1. \end{align*} $$

For $k = 1, \dots, n-m+1$, we have

$$ R_{m+k-2}(x) = S_k(x) \left( x + \frac{1}{m-1} \right)^{m-2}, $$
where the k-th order polynomial $S_k(x)$ has k distinct real roots which interlace with the k-1 distinct real roots of $S_{k-1}(x)$, for $k \ge 2$.

Matrix $P_{\{1,...,n-1\}}$ has $n-1$ real eigenvalues: $-1/(m-1)$ with multiplicity $m-2$ and $n-m+1$ other distinct real eigenvalues with multiplicity 1. All its eigenvalues belong to the interval $(-1, 1)$ with the greatest one which is its spectral radius $\rho_n$ belongs to the interval $[1/2, 1)$.

**Proof.** For every $k = 1, ..., m-1$ and $x \in \mathbb{R}$, the matrix $xI - P_{\{1,...,k\}}$ is given by $(xI - P_{\{1,...,k\}})_{i,i} = x$ and $(xI - P_{\{1,...,k\}})_{i,j} = -1/(m-1)$, for $i \neq j$. We also consider the $k \times k$ matrix $M(k, x)$ defined by $M_{1,1}(k, x) = -1/(m-1)$, $M_{i,i}(k, x) = x$, for $i \ge 2$ and $M_{i,j}(k, x) = -1/(m-1)$, for $i \neq j$.

The determinants $R_k(x)$ and $D_k(x)$ of matrices $xI - P_{\{1,...,k\}}$ and $M(k, x)$ respectively can then be written recursively, for $k \ge 2$ as

$$R_k(x) = xR_{k-1}(x) + \frac{k-1}{m-1}D_{k-1}(x)$$

$$D_k(x) = \frac{-1}{m-1}R_{k-1}(x) + \frac{k-1}{m-1}D_{k-1}(x),$$

Indeed, we performed the expansion of the determinants $R_k(x)$ and $D_k(x)$ using the first row. The first term is obtained from the expansion of the first column and the second term is obtained from the $k-1$ identical terms derived from the expansion of the second to the $(k-1)$-th column. The initial values of these relations are

$$R_2(x) = \left(x - \frac{1}{m-1}\right) \left(x + \frac{1}{m-1}\right) \text{ and } D_2(x) = -\frac{1}{m-1} \left(x + \frac{1}{m-1}\right).$$

It is easily checked by recurrence that the solution to these equations is given, for $k = 1, ..., m-1$, by

$$R_k(x) = \left(x - \frac{k-1}{m-1}\right) \left(x + \frac{1}{m-1}\right)^{k-1} \text{ and } D_k(x) = -\frac{1}{m-1} \left(x + \frac{1}{m-1}\right)^{k-1}.$$

We consider now the characteristic polynomial of matrix $P_{\{1,...,m\}}$. The matrix $xI - P_{\{1,...,m\}}$ is given by $(xI - P_{\{1,...,m\}})_{i,i} = x$, $(xI - P_{\{1,...,m\}})_{i,j} = -1/(m-1)$, for $i = 1, ..., m-1$ with $i \neq j$ and $(xI - P_{\{1,...,m\}})_{m,j} = -1/m$, for $j \neq m$. The characteristic polynomial $R_m(x)$ of matrix $P_{\{1,...,m\}}$ is then given by

$$R_m(x) = xR_{m-1}(x) + \frac{m-1}{m}D_{m-1}(x).$$

Here we performed the expansion of the determinants using the last row. The first term is obtained from the expansion of the last column and the second term is obtained from the $m-1$ identical terms derived from the expansion of the $(m-1)$-th column to the second column. Replacing $R_{m-1}(x)$ and $D_{m-1}(x)$ by their values obtained above, we get

$$R_m(x) = \frac{m(m-1)x^2 - m(m-2)x - (m-1)}{m(m-1)} \left(x + \frac{1}{m-1}\right)^{m-2}.$$

Concerning the characteristic polynomials $R_{m+1}(x), ..., R_{n-1}(x)$, we observe that (see (6) and the example (5)) the submatrix obtained from matrix $P_{\{1,...,n-1\}}$ by deleting its $m-1$ first rows and columns is a tridiagonal matrix. We thus easily get

$$R_{m+1}(x) = xR_m(x) - \frac{1}{2m}R_{m-1}(x)$$

and, for $k = m+2, ..., n-1$,

$$R_k(x) = xR_{k-1}(x) - \frac{1}{4}R_{k-2}(x).$$
where the k-th order polynomial $S_k(x)$ has k distinct real roots which interlace with the k-1 distinct real roots of $S_{k-1}(x)$, for $k \ge 2$.

Matrix $P_{\{1,...,n-1\}}$ has $n-1$ real eigenvalues: $-1/(m-1)$ with multiplicity $m-2$ and $n-m+1$ other distinct real eigenvalues with multiplicity 1. All its eigenvalues belong to the interval $(-1, 1)$ with the greatest one which is its spectral radius $\rho_n$ belongs to the interval $[1/2, 1)$.

**Proof.** For every $k = 1, ..., m-1$ and $x \in \mathbb{R}$, the matrix $xI - P_{\{1,...,k\}}$ is given by $(xI - P_{\{1,...,k\}})_{i,i} = x$ and $(xI - P_{\{1,...,k\}})_{i,j} = -1/(m-1)$, for $i \neq j$. We also consider the $k \times k$ matrix $M(k,x)$ defined by $M_{1,1}(k,x) = -1/(m-1)$, $M_{i,i}(k,x) = x$, for $i \ge 2$ and $M_{i,j}(k,x) = -1/(m-1)$, for $i \neq j$.

The determinants $R_k(x)$ and $D_k(x)$ of matrices $xI - P_{\{1,...,k\}}$ and $M(k,x)$ respectively can then be written recursively, for $k \ge 2$ as

$$R_k(x) = xR_{k-1}(x) + \frac{k-1}{m-1}D_{k-1}(x)$$

$$D_k(x) = \frac{-1}{m-1}R_{k-1}(x) + \frac{k-1}{m-1}D_{k-1}(x),$$

Indeed, we performed the expansion of the determinants $R_k(x)$ and $D_k(x)$ using the first row. The first term is obtained from the expansion of the first column and the second term is obtained from the $k-1$ identical terms derived from the expansion of the second to the $(k-1)$-th column. The initial values of these relations are

$$R_2(x) = \left(x - \frac{1}{m-1}\right) \left(x + \frac{1}{m-1}\right) \text{ and } D_2(x) = -\frac{1}{m-1} \left(x + \frac{1}{m-1}\right).$$

It is easily checked by induction that the solution to these equations is given, for $k = 1, ..., m-1$, by

$$R_k(x) = \left(x - \frac{k-1}{m-1}\right) \left(x + \frac{1}{m-1}\right)^{k-1} \text{ and } D_k(x) = -\frac{1}{m-1} \left(x + \frac{1}{m-1}\right)^{k-1}.$$

We consider now the characteristic polynomial of matrix $P_{\{1,...,m\}}$. The matrix $xI - P_{\{1,...,m\}}$ is given by $(xI - P_{\{1,...,m\}})_{i,i} = x$, $(xI - P_{\{1,...,m\}})_{i,j} = -1/(m-1)$, for $i = 1, ..., m-1$ with $i \neq j$ and $(xI - P_{\{1,...,m\}})_{m,j} = -1/m$, for $j \neq m$. The characteristic polynomial $R_m(x)$ of matrix $P_{\{1,...,m\}}$ is then given by

$$R_m(x) = xR_{m-1}(x) + \frac{m-1}{m}D_{m-1}(x).$$

Here we performed the expansion of the determinants using the last row. The first term is obtained from the expansion of the last column and the second term is obtained from the $m-1$ identical terms derived from the expansion of the $(m-1)$-th column to the second column. Replacing $R_{m-1}(x)$ and $D_{m-1}(x)$ by their values obtained above, we get

$$R_m(x) = \frac{m(m-1)x^2 - m(m-2)x - (m-1)}{m(m-1)} \left(x + \frac{1}{m-1}\right)^{m-2}.$$

Concerning the characteristic polynomials $R_{m+1}(x), ..., R_{n-1}(x)$, we observe that (see (6) and the example (5)) the submatrix obtained from matrix $P_{\{1,...,n-1\}}$ by deleting its $m-1$ first rows and columns is a tridiagonal matrix. We thus easily get

$$R_{m+1}(x) = xR_m(x) - \frac{1}{2m}R_{m-1}(x)$$

and, for $k = m+2, ..., n-1$,

$$R_k(x) = xR_{k-1}(x) - \frac{1}{4}R_{k-2}(x).$$
For $k = 1, \dots, n-m+1$, we introduce the notation

$$S_k(x) = \frac{R_{m+k-2}(x)}{\left(x + \frac{1}{m-1}\right)^{m-2}}.$$

We then have

$$ 
\begin{aligned}
S_1(x) &= \frac{(m-1)x - (m-2)}{m-1}, \\
S_2(x) &= \frac{m(m-1)x^2 - m(m-2)x - (m-1)}{m(m-1)}, \\
S_3(x) &= xS_2(x) - \frac{1}{2m}S_1(x) \qquad (14)
\end{aligned}
$$

and, for $k = 4, \dots, n-m+1$,

$$S_k(x) = xS_{k-1}(x) - \frac{1}{4}S_{k-2}(x). \qquad (15)$$

For $k = 1, \dots, n-m+1$, $S_k$ is a k-th order polynomial which satisfies

$$\lim_{x \to -\infty} S_k(x) = \begin{cases} -\infty & \text{if } k \text{ is odd} \\ +\infty & \text{if } k \text{ is even} \end{cases} \quad \text{and} \quad \lim_{x \to \infty} S_k(x) = +\infty. \qquad (16)$$

We denote by $\gamma_1^{(k)}, \dots, \gamma_k^{(k)}$ the k roots of $S_k$. For $k=1$, we easily have

$$\gamma_1^{(1)} = \frac{m-2}{m-1}.$$

For $k=2$, $S_2$ is a second order polynomial with 2 real roots which are

$$\gamma_1^{(2)} = \frac{m(m-2) - \sqrt{m(m^3 - 4m + 4)}}{2m(m-1)} \quad \text{and} \quad \gamma_2^{(2)} = \frac{m(m-2) + \sqrt{m(m^3 - 4m + 4)}}{2m(m-1)}.$$

It is easily checked that we have

$$\gamma_1^{(2)} < 0 \le \gamma_1^{(1)} < \gamma_2^{(2)}.$$

Consider now relations (14) and (15), and fix an integer $k = 3, \dots, n-m+1$. Let $\gamma$ be a root of $S_{k-1}$. We then have $S_{k-1}(\gamma) = 0$ which gives by both (14) and (15), $S_k(\gamma)S_{k-2}(\gamma) \le 0$. Suppose that $S_k(\gamma) = 0$. Since $S_{k-1}(\gamma) = 0$, $S_k(\gamma) = 0$ is equivalent to $S_{k-2}(\gamma) = 0$. Writing (15) for integer $k-1$, this implies that $S_{k-3}(\gamma) = 0$, which in turn implies recursively that $S_{k-4}(\gamma) = 0, \dots, S_2(\gamma) = 0$. Using now (14), this implies that $S_1(\gamma) = 0$, which gives $\gamma = \gamma_1^{(1)}$, which is wrong because the 2 roots $\gamma_1^{(2)}$ and $\gamma_2^{(2)}$ of $S_2$ are different from $\gamma_1^{(1)}$.

It follows that if $\gamma$ is a root of $S_{k-1}$ then $S_k(\gamma)S_{k-2}(\gamma) < 0$, for all $k = 3, \dots, n-m+1$.

We have seen above that the roots of $S_1$ and $S_2$ are real and interlace, i.e. that the root of $S_1$ is in between the two real roots of $S_2$. Suppose that the roots of $S_{k-1}$ and $S_k$ are all real and interlace, i.e. that there is always a root of $S_{k-1}$ in between two successive roots of $S_k$. We thus have

$$\gamma_1^{(k)} < \gamma_1^{(k-1)} < \gamma_2^{(k)} < \dots < \gamma_{k-1}^{(k)} < \gamma_{k-1}^{(k-1)} < \gamma_k^{(k)}.$$

It follows, using (16), that for $\ell = 1, \dots, k$,

$$S_{k-1}(\gamma_{\ell}^{(k)}) > 0 \text{ if } k + \ell \text{ is even and } S_{k-1}(\gamma_{\ell}^{(k)}) < 0 \text{ if } k + \ell \text{ is odd.}$$

Since $S_{k+1}(\gamma_{\ell}^{(k)})S_{k-1}(\gamma_{\ell}^{(k)}) < 0$, we deduce that for $\ell = 1, \dots, k$,

$$S_{k+1}(\gamma_{\ell}^{(k)}) < 0 \text{ if } k + \ell \text{ is even and } S_{k+1}(\gamma_{\ell}^{(k)}) > 0 \text{ if } k + \ell \text{ is odd.}$$
For $k = 1, \dots, n-m+1$, we introduce the notation

$$S_k(x) = \frac{R_{m+k-2}(x)}{\left(x + \frac{1}{m-1}\right)^{m-2}}.$$

We then have

$$ 
\begin{aligned}
S_1(x) &= \frac{(m-1)x - (m-2)}{m-1}, \\
S_2(x) &= \frac{m(m-1)x^2 - m(m-2)x - (m-1)}{m(m-1)}, \\
S_3(x) &= xS_2(x) - \frac{1}{2m}S_1(x) \qquad (14)
\end{aligned}
$$

and, for $k = 4, \dots, n-m+1$,

$$S_k(x) = xS_{k-1}(x) - \frac{1}{4}S_{k-2}(x). \qquad (15)$$

For $k = 1, \dots, n-m+1$, $S_k$ is a $k$-th order polynomial which satisfies

$$\lim_{x \to -\infty} S_k(x) = \begin{cases} -\infty & \text{if } k \text{ is odd} \\ +\infty & \text{if } k \text{ is even} \end{cases} \quad \text{and} \quad \lim_{x \to \infty} S_k(x) = +\infty. \qquad (16)$$

We denote by $\gamma_1^{(k)}, \dots, \gamma_k^{(k)}$ the $k$ roots of $S_k$. For $k=1$, we easily have

$$\gamma_1^{(1)} = \frac{m-2}{m-1}.$$

For $k=2$, $S_2$ is a second order polynomial with 2 real roots which are

$$\gamma_1^{(2)} = \frac{m(m-2) - \sqrt{m(m^3 - 4m + 4)}}{2m(m-1)} \quad \text{and} \quad \gamma_2^{(2)} = \frac{m(m-2) + \sqrt{m(m^3 - 4m + 4)}}{2m(m-1)}.$$

It is easily checked that we have

$$\gamma_1^{(2)} < 0 \le \gamma_1^{(1)} < \gamma_2^{(2)}.$$

Consider now relations (14) and (15), and fix an integer $k=3, \dots, n-m+1$. Let $\gamma$ be a root of $S_{k-1}$. We then have $S_{k-1}(\gamma) = 0$ which gives by both (14) and (15), $S_k(\gamma)S_{k-2}(\gamma) \le 0$. Suppose that $S_k(\gamma) = 0$. Since $S_{k-1}(\gamma) = 0$, $S_k(\gamma) = 0$ is equivalent to $S_{k-2}(\gamma) = 0$. Writing (15) for integer $k-1$, this implies that $S_{k-3}(\gamma) = 0$, which in turn implies recursively that $S_{k-4}(\gamma) = 0, \dots, S_2(\gamma) = 0$. Using now (14), this implies that $S_1(\gamma) = 0$, which gives $\gamma = \gamma_1^{(1)}$, which is wrong because the 2 roots $\gamma_1^{(2)}$ and $\gamma_2^{(2)}$ of $S_2$ are different from $\gamma_1^{(1)}$.

It follows that if $\gamma$ is a root of $S_{k-1}$ then $S_k(\gamma)S_{k-2}(\gamma) < 0$, for all $k=3, \dots, n-m+1$.

We have seen above that the roots of $S_1$ and $S_2$ are real and interlace, i.e. that the root of $S_1$ is in between the two real roots of $S_2$. Suppose that the roots of $S_{k-1}$ and $S_k$ are all real and interlace, i.e. that there is always a root of $S_{k-1}$ in between two successive roots of $S_k$. We thus have

$$\gamma_1^{(k)} < \gamma_1^{(k-1)} < \gamma_2^{(k)} < \dots < \gamma_{k-1}^{(k)} < \gamma_{k-1}^{(k-1)} < \gamma_k^{(k)}.$$

It follows, using (16), that for $\ell = 1, \dots, k$,

$$S_{k-1}(\gamma_{\ell}^{(k)}) > 0 \text{ if } k+\ell \text{ is even and } S_{k-1}(\gamma_{\ell}^{(k)}) < 0 \text{ if } k+\ell \text{ is odd.}$$

Since $S_{k+1}(\gamma_{\ell}^{(k)})S_{k-1}(\gamma_{\ell}^{(k)}) < 0$, we deduce that for $\ell = 1, \dots, k$,

$$S_{k+1}(\gamma_{\ell}^{(k)}) < 0 \text{ if } k+\ell \text{ is even and } S_{k+1}(\gamma_{\ell}^{(k)}) > 0 \text{ if } k+\ell \text{ is odd.}$$
This implies that in each open interval $(\gamma_{\ell-1}^{(k)}, \gamma_{\ell}^{(k)})$ there is a root of $S_{k+1}$. Moreover, since $S_{k+1}(\gamma_k^{(k)}) < 0$ and $\lim_{x \to \infty} S_k(x) = +\infty$, we have $\gamma_{k+1}^{(k+1)} > \gamma_k^{(k)}$. In the same way, if $k$ is even then since $S_{k+1}(\gamma_1^{(k)}) > 0$ and $\lim_{x \to -\infty} S_{k+1}(x) = -\infty$, we have $\gamma_1^{(k+1)} < \gamma_1^{(k)}$. If $k$ is odd then since $S_{k+1}(\gamma_1^{(k)}) < 0$ and $\lim_{x \to -\infty} S_{k+1}(x) = \infty$, we also have $\gamma_1^{(k+1)} < \gamma_1^{(k)}$. The rest of the proof is due to the Perron-Frobenius Theorem. ■

This result allows us to compute recursively by dichotomy the spectral radius $\rho_n$ of matrix $P_{\{1,...,n-1\}}$ for any precision $\varepsilon$ given in advance. From Theorem 5, for $k \ge m$, $\rho_k$ is the greatest root of polynomial $S_{k-m+1}$ defined in the proof of this theorem. The recursion then begins with

$$ \rho_m = \frac{m-2}{m-1} \quad \text{and} \quad \rho_{m+1} = \frac{m(m-2) + \sqrt{m(m^3 - 4m + 4)}}{2m(m-1)}. $$

From Theorem 5, we have $\rho_k \in (\rho_{k-1}, 1)$ and thus the algorithm starts with $a := \rho_{k-1}$ and $b := 1$. We then compute $S_{k-m+1}((a+b)/2)$. If $S_{k-m+1}((a+b)/2) > 0$ then we set $b := (a+b)/2$ and if $S_{k-m+1}((a+b)/2) < 0$ then we set $a := (a+b)/2$. We repeat these instructions until $|S_{k-m+1}((a+b)/2)| \le \varepsilon$, which finally leads to $\rho_k := (a+b)/2$ with a precision equal to $\varepsilon$.

We give below some values of $\rho_k$ for $m = 14$ and $\varepsilon = 10^{-10}$.

$$ \rho_{14} = 0.923076923, \rho_{15} = 0.994873556, \rho_{16} = 0.997361532, \rho_{17} = 0.998227892, \rho_{18} = 0.998668330, $$

$$ \rho_{19} = 0.998934946, \rho_{20} = 0.999113674, \rho_{21} = 0.999241811, \rho_{22} = 0.999338174, \rho_{23} = 0.999413270. $$

# 4 Asymptotic analysis

We analyze in this section the asymptotic behavior of both the moments and the distribution of the hitting time $T_n$ when $n$ tends to infinity.

## 4.1 Maximum expected hitting time and corresponding moments

From Theorem 2 we easily see, as expected, that the maximum expected hitting time on the lollipop graph is obtained when the initial state is any state $i \in \{1, ..., m-1\}$. The value of $m$ which gives the maximum expected hitting time together with the corresponding maximum was obtained in [9]. We recall this result in the following corollary of Theorem 2 and we give, for this optimal value of $m$, the expected hitting time on the lollipop graph for some values of the initial state $i \in \{m, ..., n-1\}$.

**Corollary 6** For every $n \ge 3$ and $i \in \{1, ..., m-1\}$, we have

$$ \max_{m=2,...,n-1} \mathbb{E}_i(T_n) = \begin{cases} \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{2}{3}n - 1 & \text{if } n = 0 \mod 3 \\ \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{4}{9}n - \frac{13}{27} & \text{if } n = 1 \mod 3 \\ \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{2}{3}n - \frac{29}{27} & \text{if } n = 2 \mod 3, \end{cases} $$

the maximum being reached for $m = \lceil 2(n-1)/3 \rceil$. For this value of $m$, we have

$$ \mathbb{E}_m(T_n) \underset{n \to \infty}{\sim} \frac{4n^3}{27} \quad \text{and} \quad \mathbb{E}_{n-1}(T_n) \underset{n \to \infty}{\sim} \frac{4n^2}{9}. $$

**Proof.** From Theorem 2, we have to find, for a fixed $n \ge 3$, the maximum of the sequence $u(m)$ defined by

$$ u(m) = (n-m)(m^2 - 2m + n) + m - 1 = -m^3 + (n+2)m^2 - (3n-1)m + n^2 - 1. $$
This implies that in each open interval $(\gamma_{\ell-1}^{(k)}, \gamma_{\ell}^{(k)})$ there is a root of $S_{k+1}$. Moreover, since $S_{k+1}(\gamma_k^{(k)}) < 0$ and $\lim_{x \to \infty} S_k(x) = +\infty$, we have $\gamma_{k+1}^{(k+1)} > \gamma_k^{(k)}$. In the same way, if $k$ is even then since $S_{k+1}(\gamma_1^{(k)}) > 0$ and $\lim_{x \to -\infty} S_{k+1}(x) = -\infty$, we have $\gamma_1^{(k+1)} < \gamma_1^{(k)}$. If $k$ is odd then since $S_{k+1}(\gamma_1^{(k)}) < 0$ and $\lim_{x \to -\infty} S_{k+1}(x) = \infty$, we also have $\gamma_1^{(k+1)} < \gamma_1^{(k)}$. The rest of the proof is due to the Perron-Frobenius Theorem. ■

This result allows us to compute recursively by dichotomy the spectral radius $\rho_n$ of matrix $P_{\{1,...,n-1\}}$ for any precision $\varepsilon$ given in advance. From Theorem 5, for $k \ge m$, $\rho_k$ is the greatest root of polynomial $S_{k-m+1}$ defined in the proof of this theorem. The recursion then begins with

$$ \rho_m = \frac{m-2}{m-1} \quad \text{and} \quad \rho_{m+1} = \frac{m(m-2) + \sqrt{m(m^3 - 4m + 4)}}{2m(m-1)}. $$

From Theorem 5, we have $\rho_k \in (\rho_{k-1}, 1)$ and thus the algorithm starts with $a := \rho_{k-1}$ and $b := 1$. We then compute $S_{k-m+1}((a+b)/2)$. If $S_{k-m+1}((a+b)/2) > 0$ then we set $b := (a+b)/2$ and if $S_{k-m+1}((a+b)/2) < 0$ then we set $a := (a+b)/2$. We repeat these instructions until $|S_{k-m+1}((a+b)/2)| \le \varepsilon$, which finally leads to $\rho_k := (a+b)/2$ with a precision equal to $\varepsilon$. The algorithm shown in Table 1 computes the spectral radius $\rho_k$ of matrix $P_{\{1,...,k-1\}}$ obtained by removing the $n-k$ last lines and columns of matrix $P_{\{1,...,n-1\}}$, for $k=2,...,n$.

**input**: $m \ge 3, n \ge m, \varepsilon$

**output**: spectral radius $\rho_k$ of submatrix $P_{\{1,...,k-1\}}$ to within $\varepsilon$, for $k=2,...,n$

**for** $k=2$ **to** $m-1$ **do** $\rho_k = \frac{k-2}{m-1}$ **endfor**

$S_1(x) := \frac{(m-1)x - (m-2)}{m-1}$ “formal expression of a 1st degree polynomial”

$$ \rho_m = \frac{m-2}{m-1} $$

$S_2(x) := \frac{m(m-1)x^2 - m(m-2)x - (m-1)}{m(m-1)}$ “formal expression of a 2nd degree polynomial”

$$ \rho_{m+1} = \frac{m(m-2) + \sqrt{m(m^3 - 4m + 4)}}{2m(m-1)} $$

$S_3(x) := xS_2(x) - S_1(x)/(2m)$ “formal expression of a 3rd degree polynomial”

$$ a = \rho_{m+1}, b = 1.0, \text{err} = 1.0 $$

**while** $|err| > \varepsilon$ **do**

$$ err = S_3((a+b)/2) $$

**if** ($err > 0$) **then** $b = (a+b)/2$ **else** $a = (a+b)/2$ **endif**

**endwhile**

$$ \rho_{m+2} := (a+b)/2 $$

**for** $k=4$ **to** $n-m+1$ **do**

$S_k(x) := xS_{k-1}(x) - S_{k-2}(x)/4$ “formal expression of a $k$th degree polynomial”

$$ a = \rho_{m+k-2}, b = 1.0, \text{err} = 1.0 $$

**while** $|err| > \text{eps}$ **do**

$$ err = S_3((a+b)/2) $$

**if** ($err > 0$) **then** $b = (a+b)/2$ **else** $a = (a+b)/2$ **endif**

**endwhile**

$$ \rho_{m+k-1} := (a+b)/2 $$

**endfor**

<caption>Table 1: Algorithm computing the spectral radius $\rho_k$ of matrix $P_{\{1,...,k-1\}}$ obtained by removing the $n-k$ last rows and columns of matrix $P_{\{1,...,n-1\}}$, for $k=2,...,n$ and a fixed precision $\varepsilon$.</caption>
The difference $u(m+1) - u(m)$ gives

$$
\begin{align*}
u(m+1) - u(m) &= -(m+1)^3 + m^3 + (n+2)((m+1)^2 - m^2) - (3n-1)(m+1-m) \\
&= -3m^2 + (2n+1)m - 2(n-1) \\
&= -3(m-1) \left(m - \frac{2(n-1)}{3}\right).
\end{align*}
$$

It is thus easily checked that $u(m)$ is maximal when $m = \lceil 2(n-1)/3 \rceil$. The maximal mean hitting time is then given by $u(\lceil 2(n-1)/3 \rceil)$.

$$
\text{If } n = 0 \quad \text{mod } 3 \text{ then } \left\lfloor \frac{2(n-1)}{3} \right\rfloor = \frac{2n}{3} \quad \text{and} \quad u\left(\frac{2n}{3}\right) = \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{2}{3}n - 1
$$

$$
\text{If } n = 1 \quad \text{mod } 3 \text{ then } \left\lfloor \frac{2(n-1)}{3} \right\rfloor = \frac{2(n-1)}{3} \quad \text{and } u\left(\frac{2(n-1)}{3}\right) = \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{4}{9}n - \frac{13}{27}
$$

$$
\text{If } n = 2 \quad \text{mod } 3 \text{ then } \left\lfloor \frac{2(n-1)}{3} \right\rfloor = \frac{2n-1}{3} \quad \text{and} \quad u\left(\frac{2n-1}{3}\right) = \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{2}{3}n - \frac{29}{27}.
$$

When the initial state $i \in \{m, \dots, n-1\}$ is enough to use Theorem 2.

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

The following corollary of Theorem 3 gives the second order moment of $T_n$ when $m = \lceil 2(n-1)/3 \rceil$ and the initial state is any state $i \in \{1, \dots, m-1\}$, that is when the mean hitting time is maximal.

**Corollary 7** For every $n \ge 3$ with $m = \lceil 2(n-1)/3 \rceil$ and $i = 1, \dots, m-1$, we have

$$
\mathbb{E}_i(T_n^2) = \begin{cases} \frac{32}{729}n^6 - \frac{56}{729}n^5 + \frac{35}{81}n^4 - \frac{112}{81}n^3 + \frac{22}{9}n^2 - 4n + 3 & \text{if } n = 0 \bmod 3 \\ \\ \frac{32}{729}n^6 - \frac{56}{729}n^5 + \frac{187}{729}n^4 - \frac{76}{81}n^3 + \frac{1010}{729}n^2 + \frac{182}{729}n - \frac{671}{729} & \text{if } n = 1 \bmod 3 \\ \\ \frac{32}{729}n^6 - \frac{56}{729}n^5 + \frac{299}{729}n^4 - \frac{1024}{729}n^3 + \frac{1654}{729}n^2 - \frac{2320}{729}n + \frac{635}{243} & \text{if } n = 2 \bmod 3. \end{cases}
$$

**Proof.** It consists simply in setting $m = \lceil 2(n-1)/3 \rceil$ in Theorem 3, that is by taking successively $m = 2n/3$, $m = 2(n-1)/3$ and $m = (2n-1)/3$. $\blacksquare$

The variance of $T_n$, when $m = \lceil 2(n-1)/3 \rceil$ and the initial state is any state $i \in \{1, \dots, m-1\}$, is then easily obtained by $\mathbb{V}_i(T_n) = \mathbb{E}_i(T_n^2) - \mathbb{E}_i(T_n)^2$, which gives

$$
\mathbb{V}_i(T_n) = \begin{cases} \frac{16}{729}n^6 - \frac{32}{729}n^5 + \frac{2}{9}n^4 - \frac{76}{81}n^3 + \frac{16}{9}n^2 - \frac{8}{3}n + 2 & \text{if } n = 0 \bmod 3 \\ \\ \frac{16}{729}n^6 - \frac{32}{729}n^5 + \frac{82}{729}n^4 - \frac{508}{729}n^3 + \frac{788}{729}n^2 + \frac{494}{729}n - \frac{280}{243} & \text{if } n = 1 \bmod 3 \\ \\ \frac{16}{729}n^6 - \frac{32}{729}n^5 + \frac{146}{729}n^4 - \frac{76}{81}n^3 + \frac{1156}{729}n^2 - \frac{1276}{729}n + \frac{1064}{729} & \text{if } n = 2 \bmod 3. \end{cases}
$$

In order to deal with the other moments we first give a recursion to compute them for all the values of $m$ and $n$ with $2 \le m \le n$. This recursion follows the same lines that have been used in the proofs of Theorems 2 and 3. It is also based on Theorem 1.
We give below some numerical values of $\rho_k$ for $m = 14$, $n = 23$ and $\varepsilon = 10^{-10}$. We get $\rho_k = (k - 2)/13$ for $k = 2, \dots, 13$ and

$$ \rho_{14} = 0.923076923, \rho_{15} = 0.994873556, \rho_{16} = 0.997361532, \rho_{17} = 0.998227892, \rho_{18} = 0.998668330, $$

$$ \rho_{19} = 0.998934946, \rho_{20} = 0.999113674, \rho_{21} = 0.999241811, \rho_{22} = 0.999338174, \rho_{23} = 0.999413270. $$

# 4 Asymptotic analysis

We analyze in this section the asymptotic behavior of both the moments and the distribution of the hitting time $T_n$ when $n$ tends to infinity.

## 4.1 Maximum expected hitting time and corresponding moments

From Theorem 2 we easily see, as expected, that the maximum expected hitting time on the lollipop graph is obtained when the initial state is any state $i \in \{1, \dots, m-1\}$. The value of $m$ which gives the maximum expected hitting time together with the corresponding maximum was obtained in [9]. We recall this result in the following corollary of Theorem 2 and we give, for this maximal value of $m$, the expected hitting time on the lollipop graph for the values $i = m$ and $i = n - 1$ of the initial state.

**Corollary 6** For every $n \ge 3$ and $i \in \{1, \dots, m-1\}$, we have

$$ \max_{m=2,\dots,n-1} \mathbb{E}_i(T_n) = \begin{cases} \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{2}{3}n - 1 & \text{if } n = 0 \bmod 3 \\ \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{4}{9}n - \frac{13}{27} & \text{if } n = 1 \bmod 3 \\ \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{2}{3}n - \frac{29}{27} & \text{if } n = 2 \bmod 3, \end{cases} $$

the maximum being reached for $m = \lceil 2(n-1)/3 \rceil$. For this value of $m$, we have

$$ \mathbb{E}_m(T_n) \underset{n \to \infty}{\sim} \frac{4n^3}{27} \quad \text{and} \quad \mathbb{E}_{n-1}(T_n) \underset{n \to \infty}{\sim} \frac{4n^2}{9}. $$

**Proof.** From Theorem 2, we have to find, for a fixed $n \ge 3$, the maximum of the sequence $u(m)$ defined by

$$ u(m) = (n-m)(m^2 - 2m + n) + m - 1 = -m^3 + (n+2)m^2 - (3n-1)m + n^2 - 1. $$

The difference $u(m+1) - u(m)$ gives

$$ \begin{aligned} u(m+1) - u(m) &= -(m+1)^3 + m^3 + (n+2)((m+1)^2 - m^2) - (3n-1)(m+1-m) \\ &= -3m^2 + (2n+1)m - 2(n-1) \\ &= -3(m-1) \left(m - \frac{2(n-1)}{3}\right). \end{aligned} $$

It is thus easily checked that $u(m)$ is maximal when $m = \lceil 2(n-1)/3 \rceil$. The maximal mean hitting time is then given by $u(\lceil 2(n-1)/3 \rceil)$.

$$ \text{If } n = 0 \bmod 3 \text{ then } \left\lfloor \frac{2(n-1)}{3} \right\rfloor = \frac{2n}{3} \quad \text{and} \quad u\left(\frac{2n}{3}\right) = \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{2}{3}n - 1 $$

$$ \text{If } n = 1 \bmod 3 \text{ then } \left\lfloor \frac{2(n-1)}{3} \right\rfloor = \frac{2(n-1)}{3} \quad \text{and} \quad u\left(\frac{2(n-1)}{3}\right) = \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{4}{9}n - \frac{13}{27} $$

$$ \text{If } n = 2 \bmod 3 \text{ then } \left\lfloor \frac{2(n-1)}{3} \right\rfloor = \frac{2n-1}{3} \quad \text{and} \quad u\left(\frac{2n-1}{3}\right) = \frac{4}{27}n^3 - \frac{1}{9}n^2 + \frac{2}{3}n - \frac{29}{27}. $$
**Theorem 8** For every $n, m \in \mathbb{N}$, with $2 \le m \le n$, for every $r \ge 1$ and for every $i \in \{1, \dots, n\}$ we have

$$ \mathbb{E}_i(T^r) = \sum_{\ell=1}^{r} c_{r,\ell} v_i^{(\ell)} $$

where, for every $\ell = 1, \dots, r$,

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

and for $i = 1, \dots, m-1$, the $v_i^{(r)}$ are all equal to $v^{(r)}$ which are recursively given by

$$ v^{(r)} = (n-m) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + (m-1)v^{(r-1)} + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} \quad (17) $$

and for $i = m, \dots, n$, by

$$ v_i^{(r)} = (n-i) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(r-1)} \right) \quad (18) $$

with initial conditions $v^{(-1)} = 0$ and $v_i^{(0)} = 1$, for all $i = 1, \dots, n$.

**Proof.** From Theorem 1, to get the $r$-th moment of $T_n$ we first need to evaluate vector $V^{(r)}$ defined, for $r \ge 0$, by

$$ V^{(r)} = (I - P_{\{1, \dots, n-1\}})^{-r} 1. $$

We then have $V^{(0)} = 1$ and for all $r \ge 1$,

$$ V^{(r)} = (I - P_{\{1, \dots, n-1\}})^{-1} V^{(r-1)} \iff (I - P_{\{1, \dots, n-1\}}) V^{(r)} = V^{(r-1)}. $$

As we did in the proof of Theorems 2 and 3, we decompose vector $V^{(r)}$ following the partition used in (6), by writing

$$ V^{(r)} = \begin{pmatrix} V_1^{(r)} \\ v_m^{(r)} \\ V_2^{(r)} \end{pmatrix}, \quad \text{with } V_1^{(r)} = \begin{pmatrix} v_1^{(r)} \\ \vdots \\ v_{m-1}^{(r)} \end{pmatrix} \quad \text{and} \quad V_2^{(r)} = \begin{pmatrix} v_{m+1}^{(r)} \\ \vdots \\ v_{n-1}^{(r)} \end{pmatrix}. $$

For $r \ge 1$, we have

$$ (I - P_{\{1, \dots, n-1\}}) V^{(r)} = V^{(r-1)} \iff \left\{ \begin{array}{l} V_1^{(r)} - QV_1^{(r)} - \frac{v_m^{(r)}}{m-1} 1 = V_1^{(r-1)} \\[1em] v_m^{(r)} - \frac{1}{m} 1^\top V_1^{(r)} - \frac{1}{m} c^\top V_2^{(r)} = v_m^{(r-1)} \\[1em] V_2^{(r)} - \frac{v_m^{(r)}}{2} c - R V_2^{(r)} = V_2^{(r-1)}. \end{array} \right. $$

Observing, by symmetry, that $\mathbb{E}_i(T_n^r)$ has the same value for every $i \in \{1, \dots, m-1\}$, we have $v_1^{(r)} = \dots = v_{m-1}^{(r)}$. We denote this common value by $v^{(r)}$. We then have

$$ V_1^{(r)} = v^{(r)} 1, \quad QV_1^{(r)} = v^{(r)} Q 1 = \frac{(m-2)v^{(r)}}{m-1} 1, \quad 1^\top V_1^{(r)} = (m-1)v^{(r)}, \quad c^\top V_2^{(r)} = v_{m+1}^{(r)}, $$
When the initial state $i \in \{m, \dots, n-1\}$ its enough to use Theorem 2.

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

The following corollary of Theorem 3 gives the second order moment of $T_n$ when $m = \lceil 2(n-1)/3 \rceil$ and the initial state is any state $i \in \{1, \dots, m-1\}$, that is when the mean hitting time is maximal.

**Corollary 7** For every $n \ge 3$ with $m = \lceil 2(n-1)/3 \rceil$ and $i = 1, \dots, m-1$, we have

$$ \mathbb{E}_i(T_n^2) = \begin{cases} \frac{32}{729}n^6 - \frac{56}{729}n^5 + \frac{35}{81}n^4 - \frac{112}{81}n^3 + \frac{22}{9}n^2 - 4n + 3 & \text{if } n \equiv 0 \pmod 3 \\ \frac{32}{729}n^6 - \frac{56}{729}n^5 + \frac{187}{729}n^4 - \frac{76}{81}n^3 + \frac{1010}{729}n^2 + \frac{182}{729}n - \frac{671}{729} & \text{if } n \equiv 1 \pmod 3 \\ \frac{32}{729}n^6 - \frac{56}{729}n^5 + \frac{299}{729}n^4 - \frac{1024}{729}n^3 + \frac{1654}{729}n^2 - \frac{2320}{729}n + \frac{635}{243} & \text{if } n \equiv 2 \pmod 3. \end{cases} $$

**Proof.** It consists simply in setting $m = \lceil 2(n-1)/3 \rceil$ in Theorem 3, that is by taking successively $m = 2n/3$, $m = 2(n-1)/3$ and $m = (2n-1)/3$. ■

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

In order to deal with the other moments we first give a recursion to compute them for all the values of $m$ and $n$ with $2 \le m \le n$. This recursion follows the same lines that have been used in the proofs of Theorems 2 and 3.

While Theorem 1 gives a vector expression of the moments of $T_n$, Theorem 8 gives, using this vector expression, a recurrence relation to compute the coordinates of this vector which are given in relations (17) and (18). These two relations are quite important because they are used in Theorem 9 and Theorem 11 to get the asymptotic behavior of the moments of $T_n$.

From Theorem 1, to get the $r$-th moment of $T_n$ we need to evaluate the coordinates of the column vector $(I - P_{\{1,...,n-1\}})^{-r} 1$. We introduce the notation

$$ v_i^{(r)} = ((I - P_{\{1,...,n-1\}})^{-r} 1)_i. $$

**Theorem 8** For every $n, m \in \mathbb{N}$, with $2 \le m \le n$ and for every $r \ge 1$, we have

for $i = 1, \dots, m-1$, the $v_i^{(r)}$ are all equal to $v^{(r)}$ which are recursively given by

$$ v^{(r)} = (n-m) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + (m-1)v^{(r-1)} + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} \quad (17) $$

and for $i = m, \dots, n$,

$$ v_i^{(r)} = (n-i) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(r-1)} \right) \quad (18) $$

with initial conditions $v^{(-1)} = 0$ and $v_i^{(0)} = 1$, for all $i = 1, \dots, n$.

**Proof.** Let $V^{(r)}$ the column vector defined, for $r \ge 0$, by

$$ V^{(r)} = (I - P_{\{1,...,n-1\}})^{-r} 1. $$

We then have $V^{(0)} = 1$ and for all $r \ge 1$,

$$ V^{(r)} = (I - P_{\{1,...,n-1\}})^{-1} V^{(r-1)} \iff (I - P_{\{1,...,n-1\}}) V^{(r)} = V^{(r-1)}. $$
which leads to

$$ egin{cases} v^{(r)} - \frac{(m-2)v^{(r)}}{m-1} - \frac{v_m^{(r)}}{m-1} = v^{(r-1)} \\ v_m^{(r)} - \frac{(m-1)v^{(r)}}{m} - \frac{v_{m+1}^{(r)}}{m} = v_m^{(r-1)} \\ v_i^{(r)} - \frac{1}{2}v_{i-1}^{(r)} - \frac{1}{2}v_{i+1}^{(r)} = v_i^{(r-1)}, \text{ for } i = m+1, \dots, n-1, \end{cases} \quad (19) $$

where we have defined $v_n^{(r)} = \mathbb{E}_n(T_n^r) = 0$. The first relation of (19) gives

$$ v_m^{(r)} = v^{(r)} - (m-1)v^{(r-1)}. \quad (20) $$

Using this result in the second relation of (19), we obtain

$$ v_{m+1}^{(r)} = v^{(r)} - m^2 v^{(r-1)} + m(v^{(r-1)} - v_m^{(r-1)}). $$

From (20), we have $v^{(r-1)} - v_m^{(r-1)} = (m-1)v^{(r-2)}$, which is equal to 0 for $r=1$, since have $V^{(r)} = 1$. We thus introduce the notation $V^{(-1)} = 0$ which is the null vector. It follows that for all $r \ge 1$, we have

$$ v_{m+1}^{(r)} = v^{(r)} - m^2 v^{(r-1)} + m(m-1)v^{(r-2)}. $$

Defining $z_i = v_i^{(r)} - v_{i+1}^{(r)}$ for $i = m, \dots, n-1$, the third relation of (19) gives $z_i = z_{i-1} + 2v_i^{(r-1)}$, for $i = m+1, \dots, n-1$ with $z_m = v_m^{(r)} - v_{m+1}^{(r)} = (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)}$. It follows that

$$ z_{m+i} = z_m + 2 \sum_{\ell=1}^{i} v_{m+\ell}^{(r-1)} = (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} + 2 \sum_{\ell=m+1}^{m+i} v_{\ell}^{(r-1)}, $$

and thus

$$ v_m^{(r)} = \sum_{i=m}^{n-1} z_i = \sum_{i=0}^{n-m-1} z_{m+i} = (n-m) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)}. $$

We then get the value of $v^{(r)}$ using $v^{(r)} = v_m^{(r)} + (m-1)v^{(r-1)}$. In the same way, we have

$$ \begin{aligned} v_m^{(r)} - v_{m+i}^{(r)} &= \sum_{\ell=m}^{m+i-1} z_\ell = \sum_{\ell=0}^{i-1} z_{m+\ell} = i \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \sum_{\ell=0}^{i-1} \sum_{j=m+1}^{m+\ell} v_j^{(r-1)} \\ &= i \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \sum_{\ell=m+1}^{m+i-1} (m+i-\ell)v_\ell^{(r-1)} \end{aligned} $$

which gives for $i = 1, \dots, n-m$,

$$ \begin{aligned} v_{m+i}^{(r)} &= v_m^{(r)} - i \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] - 2 \sum_{\ell=m+1}^{m+i-1} (m+i-\ell)v_{\ell}^{(r-1)} \\ &= (n-m-i) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] \\ &\quad + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} - \sum_{\ell=m+1}^{m+i-1} (m+i-\ell)v_{\ell}^{(r-1)} \right), \end{aligned} $$
As we did in the proof of Theorems 2 and 3, we decompose vector $V^{(r)}$ following the partition used in (6), by writing

$$V^{(r)} = \begin{pmatrix} V_1^{(r)} \\ v_m^{(r)} \\ V_2^{(r)} \end{pmatrix}, \quad \text{with } V_1^{(r)} = \begin{pmatrix} v_1^{(r)} \\ \vdots \\ v_{m-1}^{(r)} \end{pmatrix} \quad \text{and} \quad V_2^{(r)} = \begin{pmatrix} v_{m+1}^{(r)} \\ \vdots \\ v_{n-1}^{(r)} \end{pmatrix}.$$

For $r \ge 1$, we have

$$(I - P_{\{1, \dots, n-1\}})V^{(r)} = V^{(r-1)} \iff \left\{ \begin{array}{l} V_1^{(r)} - QV_1^{(r)} - \frac{v_m^{(r)}}{m-1}1 = V_1^{(r-1)} \\ v_m^{(r)} - \frac{1}{m}1^\top V_1^{(r)} - \frac{1}{m}c^\top V_2^{(r)} = v_m^{(r-1)} \\ V_2^{(r)} - \frac{v_m^{(r)}}{2}c - RV_2^{(r)} = V_2^{(r-1)}. \end{array} \right.$$

Observing, by symmetry, that $E_i(T_n^r)$ has the same value for every $i \in \{1, \dots, m-1\}$, we have $v_1^{(r)} = \dots = v_{m-1}^{(r)}$. We denote this common value by $v^{(r)}$. We then have

$$V_1^{(r)} = v^{(r)}1, \quad QV_1^{(r)} = v^{(r)}Q1 = \frac{(m-2)v^{(r)}}{m-1}1, \quad 1^\top V_1^{(r)} = (m-1)v^{(r)}, \quad c^\top V_2^{(r)} = v_{m+1}^{(r)},$$

which leads to

$$\left\{ \begin{array}{l} v^{(r)} - \frac{(m-2)v^{(r)}}{m-1} - \frac{v_m^{(r)}}{m-1} = v^{(r-1)} \\ v_m^{(r)} - \frac{(m-1)v^{(r)}}{m} - \frac{v_{m+1}^{(r)}}{m} = v_m^{(r-1)} \\ v_i^{(r)} - \frac{1}{2}v_{i-1}^{(r)} - \frac{1}{2}v_{i+1}^{(r)} = v_i^{(r-1)}, \quad \text{for } i = m+1, \dots, n-1, \end{array} \right. \qquad (19)$$

where we have defined $v_n^{(r)} = E_n(T_n^r) = 0$. The first relation of (19) gives

$$v_m^{(r)} = v^{(r)} - (m-1)v^{(r-1)}. \qquad (20)$$

Using this result in the second relation of (19), we obtain

$$v_{m+1}^{(r)} = v^{(r)} - m^2 v^{(r-1)} + m(v^{(r-1)} - v_m^{(r-1)}).$$

From (20), we have $v^{(r-1)} - v_m^{(r-1)} = (m-1)v^{(r-2)}$, which is equal to 0 for $r=1$, since have $V^{(r)} = 1$. We thus introduce the notation $V^{(-1)} = 0$ which is the null vector. It follows that for all $r \ge 1$, we have

$$v_{m+1}^{(r)} = v^{(r)} - m^2 v^{(r-1)} + m(m-1)v^{(r-2)}.$$

Defining $z_i = v_i^{(r)} - v_{i+1}^{(r)}$ for $i = m, \dots, n-1$, the third relation of (19) gives $z_i = z_{i-1} + 2v_i^{(r-1)}$, for $i = m+1, \dots, n-1$ with $z_m = v_m^{(r)} - v_{m+1}^{(r)} = (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)}$. It follows that

$$z_{m+i} = z_m + 2 \sum_{\ell=1}^{i} v_{m+\ell}^{(r-1)} = (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} + 2 \sum_{\ell=m+1}^{m+i} v_{\ell}^{(r-1)},$$
which can also be written, for $i = m + 1, \dots, n$, as

$$v_i^{(r)} = (n-i) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(r-1)} \right).$$

Finally Theorem 1 concludes the proof. ■

The following theorem gives the asymptotic behavior of the r-th moment of $T_n$ when the ratio $m/n$ converges to a fixed constant $a \in (0, 1)$ when $n$ tends to infinity. This is the case, for instance, when $m = an + c \ln(n)$ or $m = an + cn^\beta$, with $\beta \in [0, 1)$ and $c$ is a constant.

**Theorem 9** For every $n \ge 3$, $a \in (0, 1)$ and $m = an + n\varepsilon(n)$ where $\varepsilon(n)$ is such that $\lim_{n \to \infty} \varepsilon(n) = 0$, for every $r \ge 1$ we have for $i = 1, \dots, m-1$

$$\mathbb{E}_i(T_n^r) = r! a^{2r} (1-a)^r n^{3r} + n^{3r} \varepsilon(n).$$

Observe that this last value of $\varepsilon(n)$ depends on integer $r$, even if we do not need to specify this dependence.

**Proof.** The proof is based on the asymptotic analysis of the $v^{(r)}$ and $v_i^{(r)}$ obtained in Theorem 8. Set $m = an + n\varepsilon(n)$ where $\varepsilon(n)$ is such that $\lim_{n \to \infty} \varepsilon(n) = 0$.

We prove by recurrence that for every $n \ge 1$, we have

$$v^{(r)} = (a^2(1-a))^r n^{3r} + n^{3r}\varepsilon(n) \text{ and } v_i^{(r)} = a^{2r}(1-a)^{r-1}n^{3r-1}(n-i) + n^{3r}\varepsilon(n), \text{ for } i = m, \dots, n-1, \quad (21)$$

where, in these two expressions, $\varepsilon(n)$ depends on integer $r$.

Observe first that, if (21) is true for a fixed $r$ then we have,

$$\begin{aligned}
\sum_{\ell=m+1}^{n-1} (n-\ell) v_{\ell}^{(r)} &= a^{2r} (1-a)^{r-1} n^{3r-1} \sum_{\ell=1}^{n-m} \ell^2 + n^{3r} \varepsilon(n) \sum_{\ell=1}^{n-m} \ell \\
&= a^{2r} (1-a)^{r-1} n^{3r-1} \left( \frac{(1-a)^3 n^3}{3} + n^3 \varepsilon(n) \right) + n^{3r} \varepsilon(n) \left( \frac{(1-a)^2 n^2}{2} + n^2 \varepsilon(n) \right) \\
&= \frac{1}{3} a^{2r} (1-a)^{r+2} n^{3r+2} + n^{3r+2} \varepsilon(n) \\
&= n^{3(r+1)} \varepsilon(n).
\end{aligned} \quad (22)$$

and, for $i = m, \dots, n-1$,

$$\begin{aligned}
\sum_{\ell=m+1}^{i-1} (i-\ell) v_{\ell}^{(r)} &= a^{2r} (1-a)^{r-1} n^{3r-1} \sum_{\ell=m+1}^{i-1} (i-\ell)(n-\ell) + n^{3r} \varepsilon(n) \sum_{\ell=m+1}^{i-1} (i-\ell) \\
&= a^{2r} (1-a)^{r-1} n^{3r-1} \left( (n-i) \sum_{\ell=1}^{i-m-1} \ell + \sum_{\ell=1}^{i-m-1} \ell^2 \right) + n^{3r} \varepsilon(n) \sum_{\ell=1}^{i-m-1} \ell.
\end{aligned}$$

Replacing $m$ by $an + n\varepsilon(n)$ in this expression we obtain, after some algebra,

$$\sum_{\ell=1}^{i-m-1} \ell = \frac{1}{2} a^2 n^2 - a in + \frac{1}{2} i^2 + n^2 \varepsilon(n)$$

and

$$(n-i) \sum_{\ell=1}^{i-m-1} \ell + \sum_{\ell=1}^{i-m-1} \ell^2 = \frac{1}{6} a^2 (3-2a)n^3 - \frac{1}{2} a(2-a)in^2 + \frac{1}{2} i^2 n - \frac{1}{6} i^3 + n^3 \varepsilon(n)$$
and thus

$$v_m^{(r)} = \sum_{i=m}^{n-1} z_i = \sum_{i=0}^{n-m-1} z_{m+i} = (n-m) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)}.$$

We then get the value of $v^{(r)}$ using $v^{(r)} = v_m^{(r)} + (m-1)v^{(r-1)}$. In the same way, we have

$$\begin{aligned} v_m^{(r)} - v_{m+i}^{(r)} &= \sum_{\ell=m}^{m+i-1} z_\ell = \sum_{\ell=0}^{i-1} z_{m+\ell} = i \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \sum_{\ell=0}^{i-1} \sum_{j=m+1}^{m+\ell} v_j^{(r-1)} \\ &= i \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \sum_{\ell=m+1}^{m+i-1} (m+i-\ell)v_\ell^{(r-1)} \end{aligned}$$

which gives for $i = 1, \dots, n-m$,

$$\begin{aligned} v_{m+i}^{(r)} &= v_m^{(r)} - i \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] - 2 \sum_{\ell=m+1}^{m+i-1} (m+i-\ell)v_{\ell}^{(r-1)} \\ &= (n-m-i) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] \\ &\quad + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} - \sum_{\ell=m+1}^{m+i-1} (m+i-\ell)v_{\ell}^{(r-1)} \right), \end{aligned}$$

which can also be written, for $i = m + 1, \dots, n$, as

$$v_i^{(r)} = (n-i) \left[ (m^2 - m + 1)v^{(r-1)} - m(m-1)v^{(r-2)} \right] + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(r-1)} \right).$$

This concludes the proof. ■

## 4.2 Asymptotic moments and distribution

Armed with Theorem 8, we are now in position to tackle the asymptotic analysis of the various moments $E_i(T_n^r)$ for $r \ge 1$ as $n \to \infty$. Naturally, the result strongly depends on the asymptotic behaviour of the parameter $m$ along with $n$. We consider in this section the two following cases. The first case is the most natural one, namely the case when

$$\frac{m}{n} \xrightarrow{n \to \infty} a \text{ for some } 0 < a < 1.$$

Theorem 9 and Corollary 10 give a complete description of the asymptotic behaviour of both all moments and distribution of $T_n$ in this case. The second case is the complementary situation when $m \ll n$. More technically, we investigate the case when

$$\frac{m}{\sqrt{n}} \xrightarrow{n \to \infty} 0.$$

Theorem 11 and Corollary 12 give a complete description of the asymptotic behaviour of both all moments and distribution of $T_n$ in this case.

Let us begin with the situation when $m/n \to a$. The following theorem gives the asymptotic behavior of the $r$-th moment of $T_n$ in this situation.
which gives

$$ 
\begin{aligned}
\sum_{\ell=m+1}^{i-1} (i-\ell) v_{\ell}^{(r)} &= \frac{1}{6} a^{2r+2} (1-a)^{r-1} (3-2a) n^{3r+2} - \frac{1}{2} a^{2r+1} (1-a)^{r-1} (2-a) in^{3r+1} \\
&\quad + \frac{1}{2} a^{2r} (1-a)^{r-1} i^2 n^{3r} - \frac{1}{6} a^{2r} (1-a)^{r-1} i^3 n^{3r-1} + n^{3r+2} \varepsilon(n) \\
&= n^{3(r+1)} \varepsilon(n).
\end{aligned} 
\quad (23) $$

The expressions of $v^{(r)}$ and $v_i^{(r)}$ given by relations (17) and (18) with $m = an + n\varepsilon(n)$ lead to

$$ 
\begin{aligned}
v^{(r)} &= ((1-a)n + n\varepsilon(n)) (a^2n^2 + n^2\varepsilon(n)) (v^{(r-1)} - v^{(r-2)}) + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} \\
&= (a^2(1-a)n^3 + n^3\varepsilon(n)) (v^{(r-1)} - v^{(r-2)}) + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)}
\end{aligned} 
\quad (24) $$

and, for $i = m, \dots, n-1$,

$$ v_i^{(r)} = (n-i) (a^2n^2 + n^2\varepsilon(n)) (v^{(r-1)} - v^{(r-2)}) + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(r-1)} \right). \quad (25) $$

For $r = 1$, since $v_i^{(0)} = 1$ and $v_i^{(-1)} = 0$, using relations (22) and (23) in relations (24) and (25), we get

$$ v^{(1)} = a^2(1-a)n^3 + n^3\varepsilon(n) + 2 \sum_{\ell=m+1}^{n-1} (n-\ell) = a^2(1-a)n^3 + n^3\varepsilon(n), $$

and, for $i = m, \dots, n-1$,

$$ v_i^{(1)} = (n-i) (a^2n^2 + n^2\varepsilon(n)) + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell) - \sum_{\ell=m+1}^{i-1} (i-\ell) \right) = a^2n^2(n-i) + n^3\varepsilon(n). $$

Thus, relations (21) are true for $r = 1$.

In the same way, for $r = 2$ using relations (22) and (23) in relations (24) and (25), we get

$$ v^{(2)} = (a^2(1-a)n^3 + n^3\varepsilon(n)) (a^2(1-a)n^3 + n^3\varepsilon(n) - 1) + n^6\varepsilon(n) = a^4(1-a)^2n^6 + n^6\varepsilon(n) $$

and, for $i = m, \dots, n-1$,

$$ v_i^{(2)} = (n-i) (a^2n^2 + n^2\varepsilon(n)) (a^2(1-a)n^3 + n^3\varepsilon(n) - 1) + n^6\varepsilon(n) = a^4(1-a)n^5(n-i) + n^6\varepsilon(n). $$

Thus relations (21) are valid for $r = 1$ and $r = 2$.

Suppose now that relations (21) are true for integers $r$ and $r-1$. For integer $r+1$, from (24) and (25), we have, using (22) and (23),

$$ 
\begin{aligned}
v^{(r+1)} &= (a^2(1-a)n^3 + n^3\varepsilon(n)) \left( (a^2(1-a))^r n^{3r} + n^{3r}\varepsilon(n) \right) + n^{3(r+1)}\varepsilon(n) \\
&= (a^2(1-a))^r n^{3(r+1)} + n^{3(r+1)}\varepsilon(n)
\end{aligned} 
$$

and, for $i = m, \dots, n-1$,

$$ 
\begin{aligned}
v_i^{(r+1)} &= (n-i) (a^2n^2 + n^2\varepsilon(n)) \left( (a^2(1-a))^r n^{3r} + n^{3r}\varepsilon(n) \right) + n^{3(r+1)}\varepsilon(n) \\
&= a^2(1-a)^r n^{3r+2} (n-i) + n^{3(r+1)}\varepsilon(n).
\end{aligned} 
$$
**Theorem 9** Assume there is an $a \in (0,1)$ such that for every $n \ge 3$, we have

$$m = an(1 + \varepsilon(n)), \text{ for some sequence } \varepsilon(n) \text{ satisfying } \varepsilon(n) \underset{n \to \infty}{\longrightarrow} 0.$$

Then, for every given value of $r \ge 1$, there exists a $r$-dependent sequence $\varepsilon_r(n)$ such that for any $n \ge 3$ and any $i = 1, \dots, m-1$, we have

$$\mathbb{E}_i(T_n^r) = r! a^{2r} (1-a)^r n^{3r} (1 + \varepsilon_r(n)),$$

where the sequence $\varepsilon_r(n)$ goes to zero as $n \to \infty$. Note that as in Theorem 8 both sides of this relation are independent of $i$.

**Proof.** The proof is based on the asymptotic analysis of the $v^{(r)}$ and $v_i^{(r)}$ obtained in Theorem 8.

From now on, and in order to keep reasonably light notation, any function denoted either by $\varepsilon_r(n)$, or $\varepsilon_r(n, i)$ for $i = 1, \dots, m-1$, or $\varepsilon_r(n, i)$ for $i = m, \dots, n-1$, or simply by $\varepsilon(n)$ if there is no dependence on $r$, denotes a sequence which goes to zero as $n$ goes to infinity uniformly in $i$, in the sense that

$$\varepsilon_r(n) \underset{n \to \infty}{\longrightarrow} 0, \quad \max_{i=1, \dots, m-1} |\varepsilon_r(n, i)| \underset{n \to \infty}{\longrightarrow} 0, \quad \max_{i=m, \dots, n-1} |\varepsilon_r(n, i)| \underset{n \to \infty}{\longrightarrow} 0, \quad \varepsilon(n) \underset{n \to \infty}{\longrightarrow} 0. \quad (21)$$

The precise value of such functions may change from line to line in the computations below.

**First step**

In this step we prove by induction on $r$ that for each $r$, there exists sequences $\varepsilon_r(n)$ and $\varepsilon_r(n, i)$ such that

$$\left\{ \begin{array}{l} v^{(r)} = (a^2(1-a))^r n^{3r} (1 + \varepsilon_r(n)), \\ v_i^{(r)} = a^{2r} (1-a)^{r-1} n^{3r-1} (n-i) + n^{3r} \varepsilon_r(n, i), \quad \text{for } i = m, \dots, n-1, \end{array} \right. \quad (22)$$

where $\varepsilon_r(n)$ and $\varepsilon_r(n, i)$, for $i = m, \dots, n-1$, go to zero as $n \to \infty$ in the sense defined in (21).

If (22) is true for some given $r$, then we have

$$\begin{aligned} \sum_{\ell=m+1}^{n-1} (n-\ell) v_{\ell}^{(r)} &= \sum_{\ell=m+1}^{n-1} (n-\ell) [a^{2r}(1-a)^{r-1} n^{3r-1}(n-\ell) + n^{3r} \varepsilon_r(n, \ell)] \\ &= a^{2r}(1-a)^{r-1} n^{3r-1} \left( \sum_{\ell=1}^{n-m-1} \ell^2 \right) + n^{3r} \varepsilon_r(n) \left( \sum_{\ell=1}^{n-m-1} \ell \right) \\ &= a^{2r}(1-a)^{r-1} n^{3r-1} \frac{(n-m)^3}{3} (1+\varepsilon(n-m)) + n^{3r} \varepsilon_r(n) \frac{(n-m)^2}{2} (1+\varepsilon(n-m)) \\ &= a^{2r}(1-a)^{r-1} n^{3r-1} \frac{(1-a)^3 n^3}{3} (1+\varepsilon(n)) + n^{3r} \varepsilon_r(n) \frac{(1-a)^2 n^2}{2} (1+\varepsilon(n)) \\ &= n^{3(r+1)} \varepsilon_r(n). \end{aligned} \quad (23)$$

Here we used the fact that $n-m = (1-a)n(1+\varepsilon(n))$. We also used the variable change $\ell := n-\ell$ in the original sums over $\ell$ and the well-known asymptotic behaviour

$$\sum_{\ell=1}^{k} \ell^{\alpha} \underset{k \to \infty}{\sim} \frac{k^{\alpha+1}}{\alpha+1}, \quad \text{for any } \alpha \ge 0. \quad (24)$$
This completes the proof of relations (21).

From Theorem 1, we have for every $i = 1, \dots, m-1$,

$$ 
\begin{aligned}
\mathbb{E}_i(T_n^r) &= \sum_{\ell=1}^r c_{r,\ell} v^{(\ell)} = \sum_{\ell=1}^r c_{r,\ell} \left[ (a^2(1-a))^{\ell} n^{3\ell} + n^{3\ell} \varepsilon(n) \right] \\
&= c_{r,r} \left[ (a^2(1-a))^{r} n^{3r} + n^{3r} \varepsilon(n) \right] \\
&= r! (a^2(1-a))^{r} n^{3r} + n^{3r} \varepsilon(n),
\end{aligned}
$$

which completes the proof.

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

This result allows us to determine the asymptotic behavior of the distribution of the hitting time $T_n$, when $m = an + n\varepsilon(n)$.

**Corollary 10** For all $t \ge 0$, $a \in (0,1)$ and $m = an + n\varepsilon(n)$ where $\varepsilon(n)$ is such that $\lim_{n \to \infty} \varepsilon(n) = 0$, we have for every $i = 1, \dots, m-1$

$$ \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{a^2(1-a)n^3} > t \right\} = e^{-t}. $$

**Proof.** Let $Z$ be a random variable exponentially distributed with rate 1. It is well-known that for every $r \ge 0$, we have $\mathbb{E}(Z^r) = r!$. Thus the power series $\sum_{r \ge 0} \mathbb{E}(Z^r)x^r/r!$ has a positive radius (it is equal to 1). This implies, from Theorem 30.1 of [7], that the random variable $Z$ is uniquely determined by its moments. From Theorem 9, we have for every $r \ge 1$,

$$ \lim_{n \to \infty} \mathbb{E}_i \left( \left( \frac{T_n}{a^2(1-a)n^3} \right)^r \right) = r! = \mathbb{E}(Z^r). $$

It follows from Theorem 30.2 of [7] that, for all $i = 1, \dots, m-1$

$$ \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{a^2(1-a)n^3} > t \right\} = \mathbb{P}\{Z > t\} = e^{-t}, $$

which completes the proof.

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

In the particular case where $m = \lceil 2(n-1)/3 \rceil$, which corresponds to the maximum expected hitting time as shown in Corollary 6, we obtain by taking $a = 2/3$ in Theorem 9 and Corollary 10

$$ \mathbb{E}_i(T_n^r) = r! \left(\frac{4n^3}{27}\right)^r + n^{3r} \varepsilon(n) \quad \text{and} \quad \lim_{n \to \infty} \mathbb{P} \left\{ \frac{27T_n}{4n^3} > t \right\} = e^{-t}. $$

Observe, as expected, that the maximum of $a^2(1-a)$ in $(0,1)$ is obtained for $a = 2/3$ and is equal to $4/27$.

Note that when $m = n$, the lollipop graph $L_n^n$ is the complete graph $K_n$. In that case we easily obtain that $T_n$ has a geometric distribution with parameter $1/(n-1)$. We thus get

$$ \mathbb{P}\{T_n > k\} = \left(1 - \frac{1}{n-1}\right)^k. $$

We deduce easily that for the complete graph we have, for all $t \ge 0$,

$$ \lim_{n \to \infty} \mathbb{P} \left\{ \frac{T_n}{n-1} > t \right\} = e^{-t}. $$

In the previous result, we considered the asymptotic behavior of the hitting times when $m$ is asymptotically linear with $n$, that is when $m = an + n\varepsilon(n)$. The case where the parameter $m$ is sublinear with respect to $n$ is not so easy to deal with. The case where $m$ is such that $m/\sqrt{n}$ tends to 0 when $n$ tends to infinity
In the same spirit, if (22) is true for some given $r$, then we also have, for any $i = m, \dots, n-1$,

$$
\begin{align*}
\sum_{\ell=m+1}^{i-1} (i-\ell) v_{\ell}^{(r)} &= \sum_{\ell=m+1}^{i-1} (i-\ell) [a^{2r}(1-a)^{r-1} n^{3r-1}(n-\ell) + n^{3r}\varepsilon_r(n, \ell)] \\
&= a^{2r}(1-a)^{r-1} n^{3r-1} \left( \sum_{\ell=1}^{i-m-1} \ell(n-i+\ell) \right) + n^{3r}\varepsilon_r(n, i) \left( \sum_{\ell=1}^{i-m-1} \ell \right) \\
&= a^{2r}(1-a)^{r-1} n^{3r-1} \left( \frac{(n-i)(i-m)^2}{2}(1+\varepsilon(i-m)) + \frac{(i-m)^3}{3}(1+\varepsilon(i-m)) \right) \\
&\quad + n^{3r}\varepsilon_r(n, i) \frac{(i-m)^2}{2}(1+\varepsilon(i-m)) \\
&= n^{3(r+1)}\varepsilon_r(n, i), \tag{25}
\end{align*}
$$

where we used the variable change $\ell := n - \ell$ in the original sums over $\ell$ and the fact that our assumptions on $m$ and $i$ imply $(n-i)(i-m)^2 = n^4\varepsilon(n, i)$, together with $(i-m)^3 = n^4\varepsilon(n, i)$ and $(i-m)^2 = n^3\varepsilon(n, i)$.

Now, using the expression of $v^{(r)}$ given by relation (17), we may deduce that, if (22) is true for integers $r$ and $r-1$, then we have

$$
\begin{align*}
v^{(r+1)} &= (n-m) \left[ (m^2 - m + 1)v^{(r)} - m(m-1)v^{(r-1)} \right] + (m-1)v^{(r)} + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r)} \\
&= [(1-a)n + n\varepsilon(n)] [a^2n^2 + n^2\varepsilon(n)] [v^{(r)} - v^{(r-1)}] + [an + n\varepsilon(n)] v^{(r)} + n^{3(r+1)}\varepsilon_r(n) \\
&= a^2(1-a)n^3(1+\varepsilon(n)) [v^{(r)} - v^{(r-1)}] + n^{3(r+1)}\varepsilon_r(n) \\
&= a^2(1-a)n^3(1+\varepsilon(n)) \left[ (a^2(1-a))^r n^{3r} + n^{3r}\varepsilon_r(n) \right] + n^{3(r+1)}\varepsilon_r(n) \\
&= (a^2(1-a))^{r+1} n^{3(r+1)} + n^{3(r+1)}\varepsilon_r(n),
\end{align*}
$$

where we have used $m = an(1 + \varepsilon(n))$, together with relation (22) for the values $r$ and $r-1$, as well as the necessary relation (23). Similarly, using the expression of $v_i^{(r)}$ given by relation (18), we obtain that, if (22) is true for integers $r$ and $r-1$, then we have for $i = m, \dots, n-1$,

$$
\begin{align*}
v_i^{(r+1)} &= (n-i) \left[ (m^2 - m + 1)v^{(r)} - m(m-1)v^{(r-1)} \right] + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(r)} \right) \\
&= (n-i)a^2 n^2 (1+\varepsilon(n)) [v^{(r)} - v^{(r-1)}] + n^{3(r+1)} \varepsilon_r(n, i) \\
&= (n-i)a^2 n^2 (1+\varepsilon(n)) \left[ (a^2(1-a))^r n^{3r} + n^{3r} \varepsilon_r(n) \right] + n^{3(r+1)} \varepsilon_r(n, i) \\
&= a^{2(r+1)} (1-a)^r n^{3r+2} (n-i) + n^{3(r+1)} \varepsilon_r(n, i)
\end{align*}
$$

where we have used $m = an(1 + \varepsilon(n))$, together with relation (22) for the values $r$ and $r-1$, as well as the necessary relations (23) and (25).

We have proved that if (22) is true for integers $r$ and $r-1$, then the same relation holds for integer $r+1$.

To conclude this first step, there remains to prove that (22) is true for integers $r=1$ and $r=2$.

For $r=1$, since $v_i^{(0)} = 1$ and $v_i^{(-1)} = 0$, for any $i$, using relation (17) in the case $r=1$ we have

$$
\begin{align*}
v^{(1)} &= (n-m)(m^2 - m + 1) + (m-1) + 2 \sum_{\ell=m+1}^{n-1} (n-\ell) \\
&= a^2(1-a)n^3 + n^3\varepsilon(n).
\end{align*}
$$
is detailed below. The case where $m = an^\beta + n^\beta \varepsilon(n)$, with $\beta \in [1/2, 1)$, is much more complicated and will be the subject of further reasearch.

The following theorem gives the asymptotic behavior of the r-th moment of $T_n$ when the ratio $m/\sqrt{n}$ tends to 0 when $n$ tends to infinity. This is the case, for instance, when $m = c$ constant or $m = c \ln(n)$ or $m = cn^\beta$, with $\beta \in [0, 1/2)$.

**Theorem 11** For every $n \ge 3$ and $m = \sqrt{n}\varepsilon(n)$ where $\varepsilon(n)$ is such that $\lim_{n \to \infty} \varepsilon(n) = 0$, we have for every $r \ge 1$ and for every $i = 1, \dots, m-1$

$$ \mathbb{E}_i(T_n^r) = \frac{|E_{2r}|2^r r!}{(2r)!} n^{2r} + n^{2r} \varepsilon(n), $$

where $E_{2r}$ are the well-known Euler numbers. Observe as previously that this last value of $\varepsilon(n)$ depends on integer $r$, even if we do not need to specify this dependence.

**Proof.** As we did for Theorem 9, the proof is based on the asymptotic analysis of the $v^{(r)}$ and $v_i^{(r)}$ obtained in Theorem 8. Set $m = \sqrt{n}\varepsilon(n)$ where $\varepsilon(n)$ is such that $\lim_{n \to \infty} \varepsilon(n) = 0$. We prove by recurrence that for every $n \ge 1$, we have

$$ v^{(r)} = \frac{2^r |E_{2r}|}{(2r)!} n^{2r} + n^{2r} \varepsilon(n) \quad \text{and} \quad v_i^{(r)} = (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} i^{2(r-k)} n^{2k} + n^{2r} \varepsilon(n), \quad (26) $$

these $\varepsilon(n)$ being dependent on $r$.

Observe first that for every $h \ge 0$, we have

$$ \sum_{\ell=m+1}^{n-1} \ell^h = \sum_{\ell=\sqrt{n\varepsilon(n)+1}}^{n-1} \ell^h = \sum_{\ell=1}^{n-1} \ell^h - \sum_{\ell=1}^{\sqrt{n\varepsilon(n)}} \ell^h = \frac{n^{h+1}}{h+1} + n^{h+1} \varepsilon(n). $$

Using this remark, if (26) is true for a fixed $r$ then we have,

$$ \begin{aligned} \sum_{\ell=m+1}^{n-1} (n-\ell) v_{\ell}^{(r)} &= (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k+1} \sum_{\ell=m+1}^{n-1} \ell^{2(r-k)} \\ &\quad - (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k} \sum_{\ell=m+1}^{n-1} \ell^{2(r-k)+1} + n^{2(r+1)} \varepsilon(n) \\ &= (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} \frac{n^{2(r+1)}}{2(r-k)+1} \\ &\quad - (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} \frac{n^{2(r+1)}}{2(r+1-k)} + n^{2(r+1)} \varepsilon(n) \\ &= (-1)^r 2^r n^{2(r+1)} \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r+1-k))!} + n^{2(r+1)} \varepsilon(n) \\ &= \frac{(-1)^r 2^r}{(2(r+1))!} \sum_{k=0}^{r} \binom{2(r+1)}{2k} E_{2k} + n^{2(r+1)} \varepsilon(n). \end{aligned} $$

Using the well-known identities

$$ E_{2(r+1)} = - \sum_{k=0}^{r} \binom{2(r+1)}{2k} E_{2k} \quad \text{and} \quad (-1)^{r+1} E_{2(r+1)} = |E_{2(r+1)}|, $$
Similarly, using relation (18) in the case $r = 1$ we have for $i = m, \dots, n - 1$,

$$
\begin{align*}
v_i^{(1)} &= (n-i)(m^2 - m + 1) + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell) - \sum_{\ell=m+1}^{i-1} (i-\ell) \right) \\
&= (n-i)(a^2 n^2 + n^2 \varepsilon(n)) + n^3 \varepsilon(n, i) \\
&= a^2 n^2 (n-i) + n^3 \varepsilon(n, i).
\end{align*}
$$

Thus, relations (22) are true for $r = 1$.

In the same way, for $r = 2$ using now relations (23) and (25) in the case $r = 2$, which is legitimate due to the previous verification, and inserting these relations in (17) and (18) in the case $r = 2$, we get successively

$$
\begin{align*}
v^{(2)} &= (n-m) \left[ (m^2 - m + 1)v^{(1)} - m(m-1) \right] + (m-1)v^{(1)} + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(1)} \\
&= (a^2(1-a))^2 n^6 + n^6 \varepsilon(n),
\end{align*}
$$

and, for $i = m, \dots, n - 1$,

$$
\begin{align*}
v_i^{(2)} &= (n-i) \left[ (m^2 - m + 1)v^{(1)} - m(m-1) \right] + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(1)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(1)} \right) \\
&= (n-i) \left[ a^4(1-a)n^5 + n^5\varepsilon(n) \right] + n^6\varepsilon(n,i) = a^4(1-a)n^5(n-i) + n^6\varepsilon(n,i).
\end{align*}
$$

Thus relations (22) are valid for $r = 2$. This concludes our recursion.

**Second Step.**

Inserting the above results in the formulae obtained in Theorem 8, we have for every $i = 1, \dots, m - 1$,

$$
\begin{align*}
\mathbb{E}_i(T_n^r) &= \sum_{\ell=1}^r c_{r,\ell} v^{(\ell)} = \sum_{\ell=1}^r c_{r,\ell} \left[ (a^2(1-a))^{\ell} n^{3\ell} + n^{3\ell} \varepsilon_{\ell}(n) \right] \\
&= c_{r,r} \left[ (a^2(1-a))^{r} n^{3r} + n^{3r} \varepsilon_r(n) \right] \\
&= r! (a^2(1-a))^{r} n^{3r} + n^{3r} \varepsilon_r(n),
\end{align*}
$$

which completes the proof.

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

Theorem 9 now allows us to determine the asymptotic behavior of the distribution of the hitting time $T_n$, when $m/n \to a$ as $n \to \infty$.

**Corollary 10** Assume there is an $a \in (0,1)$ such that for every $n \ge 3$, we have

$$
m = an(1 + \varepsilon(n)), \text{ for some sequence } \varepsilon(n) \text{ satisfying } \varepsilon(n) \xrightarrow{n \to \infty} 0.
$$

Then, for all $t \ge 0$, and every $i = 1, \dots, m - 1$

$$
\lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{a^2(1-a)n^3} > t \right\} = e^{-t}.
$$

**Proof.** Let $Z$ be a random variable exponentially distributed with rate 1. It is well-known that for every $r \ge 0$, we have $\mathbb{E}(Z^r) = r!$. Thus the power series $\sum_{r \ge 0} \mathbb{E}(Z^r)x^r/r!$ has a positive radius (it is equal to 1). This implies, from Theorem 30.1 of [7], that the random variable $Z$ is uniquely determined by its moments. From Theorem 9, we have for every $r \ge 1$,

$$
\lim_{n \to \infty} \mathbb{E}_i \left( \left( \frac{T_n}{a^2(1-a)n^3} \right)^r \right) = r! = \mathbb{E}(Z^r).
$$
we conclude that if (26) is true for a fixed r then we have,

$$ \sum_{\ell=m+1}^{n-1} (n-\ell) v_{\ell}^{(r)} = \frac{2^r |E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} + n^{2(r+1)} \varepsilon(n). \quad (27) $$

Following the same steps, if (26) is true for a fixed r then we have, for $i = m, \dots, n-1$,

$$ \begin{aligned} \sum_{\ell=m+1}^{i-1} (i-\ell) v_{\ell}^{(r)} &= (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k} i \sum_{\ell=m+1}^{i-1} \ell^{2(r-k)} \\ &\quad - (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k} \sum_{\ell=m+1}^{i-1} \ell^{2(r-k)+1} + n^{2(r+1)} \varepsilon(n) \\ &= (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k} \frac{i^{2(r+1-k)}}{2(r-k)+1} \\ &\quad - (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k} \frac{i^{2(r+1-k)}}{2(r+1-k)} + n^{2(r+1)} \varepsilon(n) \\ &= (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r+1-k))!} n^{2k} i^{2(r+1-k)} + n^{2(r+1)} \varepsilon(n). \end{aligned} \quad (28) $$

The expressions of $v^{(r)}$ and $v_i^{(r)}$ given by relations (17) and (18) with $m = \sqrt{n}\varepsilon(n)$ lead to

$$ \begin{aligned} v^{(r)} &= (n - \sqrt{n}\varepsilon(n)) n\varepsilon(n) (v^{(r-1)} - v^{(r-2)}) + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} \\ &= n^2\varepsilon(n) (v^{(r-1)} - v^{(r-2)}) + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} \end{aligned} \quad (29) $$

and, for $i = m, \dots, n-1$,

$$ v_i^{(r)} = (n-i)n\varepsilon(n)(v^{(r-1)} - v^{(r-2)}) + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r-1)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(r-1)} \right). \quad (30) $$

For $r = 1$, since $v_i^{(0)} = 1$ and $v_i^{(-1)} = 0$, using relations (27) and (28) in relations (29) and (30), we get

$$ v^{(1)} = \frac{2|E_2|}{(2)!} n^2 + n^2 \varepsilon(n) = n^2 + n^2 \varepsilon(n). $$

and, for $i = m, \dots, n-1$,

$$ v_i^{(1)} = (n - i) + n^4 \varepsilon(n) + n^2 - i^2 + n^2 \varepsilon(n) = n^2 - i^2 + n^2 \varepsilon(n). $$

Thus, relations (26) are true for $r = 1$.

In the same way, for $r = 2$ using relations (27) and (28) in relations (29) and (30), we get

$$ v^{(2)} = n^2 \varepsilon(n) (n^2 + n^2 \varepsilon(n) - 1) + \frac{4|E_4|}{4!} n^4 + n^4 \varepsilon(n) = \frac{5}{6} n^4 + n^4 \varepsilon(n). $$

and, for $i = m, \dots, n-1$,

$$ v_i^{(2)} = (n - i)n\varepsilon(n)(n^2 + n^2\varepsilon(n) - 1) + \frac{5}{6}n^4 + \frac{1}{6}i^4 - i^2n^2 + n^4\varepsilon(n) = \frac{5}{6}n^4 - i^2n^2 + \frac{1}{6}i^4 + n^4\varepsilon(n). $$
It follows from Theorem 30.2 of [7] that, for all $i = 1, \dots, m-1$

$$ \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{a^2(1-a)n^3} > t \right\} = \mathbb{P}\{Z > t\} = e^{-t}, $$

which completes the proof.

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

In the particular case where

$$ m = \lceil 2(n-1)/3 \rceil, $$

which corresponds to the maximum expected hitting time as shown in Corollary 6, we obtain by taking $a = 2/3$ in Theorem 9 and Corollary 10

$$ \mathbb{E}_i(T_n^r) = r! \left(\frac{4n^3}{27}\right)^r + n^{3r}\varepsilon(n) \quad \text{and} \quad \lim_{n \to \infty} \mathbb{P}\left\{\frac{27T_n}{4n^3} > t\right\} = e^{-t}. $$

Observe, as expected, that the maximum of $a^2(1-a)$ in $(0, 1)$ is obtained for $a = 2/3$ and is equal to $4/27$. Note also that when

$$ m = n, $$

the lollipop graph $L_n^n$ is the complete graph $K_n$. In that case we easily obtain that $T_n$ has a geometric distribution with parameter $1/(n-1)$. We thus get

$$ \mathbb{P}\{T_n > k\} = \left(1 - \frac{1}{n-1}\right)^k. $$

We deduce easily that for the complete graph we have, for all $t \ge 0$,

$$ \lim_{n \to \infty} \mathbb{P} \left\{ \frac{T_n}{n-1} > t \right\} = e^{-t}. $$

This ends our discussion of the case $m/n \to a$ as $n \to \infty$.

Let us now investigate the complementary case when $m \ll n$. More technically, we now discuss the case when

$$ \frac{m}{\sqrt{n}} \xrightarrow{n \to \infty} 0. $$

We stress here that the more general case where the parameter $m$ is sublinear with respect to $n$, i.e. the case when $m \sim an^\beta$ for some $\beta \in (0, 1)$ and some $a > 0$, is much more complicated when $\beta \ge 1/2$, and will be the subject of further research. We thus somehow restrict our attention to the case $\beta < 1/2$ below.

**Theorem 11** Assume that for every $n \ge 3$, we have

$$ m = \sqrt{n\varepsilon(n)}, \quad \text{for some sequence } \varepsilon(n) \text{ satisfying } \varepsilon(n) \xrightarrow{n \to \infty} 0. $$

Then for every $r \ge 1$, there is a sequence $\varepsilon_r(n)$ such that for any $i = 1, \dots, m-1$ we have

$$ \mathbb{E}_i(T_n^r) = \frac{|E_{2r}| 2^r r!}{(2r)!} n^{2r} (1 + \varepsilon_r(n)), $$

where $E_{2r}$ are the well-known Euler numbers.

**Proof.** As we did for Theorem 9, the proof is based on the asymptotic analysis of the $v^{(r)}$ and $v_i^{(r)}$ obtained in Theorem 8. Set $m = \sqrt{n\varepsilon(n)}$, and use the notation defined in (21).
Thus relations (26) are also valid for $r = 2$.

Suppose now that relations (26) are true for integers $r$ and $r-1$. For integer $r+1$, from (29) and (30), we have, using (27) and (28),

$$ 
\begin{aligned}
v^{(r+1)} &= n^2 \varepsilon(n) \left( \frac{2^r |E_{2r}|}{(2r)!} n^{2r} + n^{2r} \varepsilon(n) \right) + 2 \frac{2^r |E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} + n^{2(r+1)} \varepsilon(n) \\
&= \frac{2^{r+1} |E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} + n^{2(r+1)} \varepsilon(n).
\end{aligned}
$$

and, for $i = m, \dots, n-1$,

$$ 
\begin{aligned}
v_i^{(r+1)} = (n-i)n^2\varepsilon(n) \left( \frac{2^r |E_{2r}|}{(2r)!} n^{2r} + n^{2r}\varepsilon(n) \right) &+ \frac{2^{r+1}|E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} + n^{2(r+1)}\varepsilon(n) \\
&- (-1)^r 2^{r+1} \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r+1-k))!} n^{2k} i^{2(r+1-k)} + n^{2(r+1)}\varepsilon(n).
\end{aligned}
$$

Using again the fact that

$$ |E_{2(r+1)}| = (-1)^{r+1} E_{2(r+1)}, $$

we obtain

$$ v_i^{(r+1)} = (-1)^{r+1} 2^{r+1} \sum_{k=0}^{r+1} \frac{E_{2k}}{(2k)!(2(r+1-k))!} n^{2k} i^{2(r+1-k)} + n^{2(r+1)} \varepsilon(n). $$

This completes the proof of relations (26).

From Theorem 1, we have for every $i = 1, \dots, m-1$,

$$ 
\begin{aligned}
\mathbb{E}_i(T_n^r) &= \sum_{\ell=1}^r c_{r,\ell} v^{(\ell)} = \sum_{\ell=1}^r c_{r,\ell} \left[ \frac{2^\ell |E_{2\ell}|}{(2\ell)!} n^{2\ell} + n^{2\ell} \varepsilon(n) \right] \\
&= c_{r,r} \left[ \frac{2^r |E_{2r}|}{(2r)!} n^{2r} + n^{2r} \varepsilon(n) \right] \\
&= \frac{2^r |E_{2r}| r!}{(2r)!} n^{2r} + n^{2r} \varepsilon(n),
\end{aligned}
$$

which completes the proof.

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

This result allows us to determine the asymptotic behavior of the distribution of the hitting time $T_n$, when $m/\sqrt{n}$ tends to 0 when $n$ tends to infinity.

**Corollary 12** For all $t \ge 0$, $a \in (0,1)$ and $m = \sqrt{n}\varepsilon(n)$ where $\varepsilon(n)$ is such that $\lim_{n\to\infty} \varepsilon(n) = 0$, we have for every $i = 1, \dots, m-1$

$$ \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{2n^2} > t \right\} = \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)} e^{-\lambda_k t}, \text{ where } \lambda_k = \frac{\pi^2 (2k+1)^2}{4}. $$

**Proof.** Introducing the notation $Y_n = T_n/(2n^2)$, we deduce from Theorem 11 that, for every $i = 1, \dots, m-1$,

$$ \lim_{n \to \infty} \mathbb{E}_i (Y_n^r) = \frac{|E_{2r}| r!}{(2r)!}. $$

Consider the sequence of positive real numbers $s_r$ defined by

$$ s_r = \frac{|E_{2r}| r!}{(2r)!}. $$
We prove by induction that for every $n \ge 1$, we have

$$ egin{cases} v^{(r)} = \frac{2^r |E_{2r}|}{(2r)!} n^{2r} (1 + \varepsilon_r(n)) \\ v_i^{(r)} = (-1)^r 2^r \left( \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} i^{2(r-k)} n^{2k} \right) + n^{2r} \varepsilon_r(n, i), \quad \text{for } i = m+1, \dots, n-1. \end{cases} \tag{26} $$

If (26) is true for a fixed $r$ then we have,

$$ \begin{aligned} \sum_{\ell=m+1}^{n-1} (n-\ell) v_{\ell}^{(r)} &= \sum_{\ell=m+1}^{n-1} (n-\ell) \left[ (-1)^r 2^r \left( \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} \ell^{2(r-k)} n^{2k} \right) + n^{2r} \varepsilon_r(n, \ell) \right] \\ &= (-1)^r 2^r \left( \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k} \left[ n \sum_{\ell=m+1}^{n-1} \ell^{2(r-k)} - \sum_{\ell=m+1}^{n-1} \ell^{2(r-k)+1} \right] \right) \\ &\quad + n^{2r} \varepsilon_r(n) \left[ \sum_{\ell=m+1}^{n-1} (n-\ell) \right]. \end{aligned} $$

We now observe, using (24), that

$$ \begin{aligned} \sum_{\ell=m+1}^{n-1} \ell^{2(r-k)} &= \sum_{\ell=1}^{n-1} \ell^{2(r-k)} - \sum_{\ell=1}^{m} \ell^{2(r-k)} \\ &= \frac{n^{2(r-k)+1}}{2(r-k)+1} (1 + \varepsilon_{r-k}(n)) - \frac{m^{2(r-k)+1}}{2(r-k)+1} (1 + \varepsilon_{r-k}(m)) \\ &= \frac{n^{2(r-k)+1}}{2(r-k)+1} (1 + \varepsilon_{r-k}(n)), \end{aligned} $$

where we have used that $m = \sqrt{n\varepsilon(n)}$. Similarly we observe

$$ \sum_{\ell=m+1}^{n-1} \ell^{2(r-k)+1} = \frac{n^{2(r-k)+2}}{2(r-k)+2} (1 + \varepsilon_{r-k}(n)) \quad \text{and} \quad \sum_{\ell=m+1}^{n-1} (n-\ell) = \sum_{\ell=1}^{n-m-1} \ell = \frac{n^2}{2} (1 + \varepsilon(n)). $$

This provides

$$ \begin{aligned} \sum_{\ell=m+1}^{n-1} (n-\ell) v_{\ell}^{(r)} &= (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2r+2} (1 + \varepsilon_{r-k}(n)) \left[ \frac{1}{2(r-k)+1} - \frac{1}{2(r-k)+2} \right] \\ &\quad + n^{2r+2} \varepsilon_r(n) \\ &= (-1)^r 2^r n^{2(r+1)} (1 + \varepsilon_r(n)) \left( \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r+1-k))!} \right) + n^{2r+2} \varepsilon_r(n) \\ &= \frac{(-1)^r 2^r n^{2(r+1)}}{(2(r+1))!} \left( \sum_{k=0}^{r} \binom{2(r+1)}{2k} E_{2k} \right) + n^{2r+2} \varepsilon_r(n). \end{aligned} $$

Using now the well-known relations

$$ E_{2(r+1)} = - \sum_{k=0}^{r} \binom{2(r+1)}{2k} E_{2k} \quad \text{and} \quad (-1)^{r+1} E_{2(r+1)} = |E_{2(r+1)}|, $$
The first values of sequence are $s_0 = 1$, $s_1 = 1/2$, $s_2 = 5/12$, $s_3 = 61/120$, $s_4 = 277/336$. The question is : is there a probability measure $\mu$ such that its moments are given by the sequence $s_r$, i.e. such that

$$s_r = \int_0^\infty x^r d\mu(x) ?$$

This problem is well-known and is called the Stieltjes moment problem. If such a measure exists it is called a normalized (because $s_0 = 1$) Stieltjes moment sequence. If the measure is unique then the sequence $s_r$ is said to be determinate, see for instance [6]. A sufficient condition for determinacy is given by the following relation called Carleman's condition :

$$\sum_{r=1}^{\infty} s_r^{-1/2r} = +\infty. \qquad (31)$$

It is well-known (see for instance [8]) that

$$\frac{|E_{2r}|}{(2r)!} \underset{r \to \infty}{\sim} \frac{4^{r+1}}{\pi^{2r+1}}.$$

Using the Stirling formula for $r!$, this leads to

$$s_r \underset{r \to \infty}{\sim} \frac{4^{r+1}}{\pi^{2r+1}} \left(\frac{r}{e}\right)^r \sqrt{2\pi r}.$$

Since $1/2r$ tends to 0 when $r$ tends to infinity, we can write

$$s_r^{1/2r} \underset{r \to \infty}{\sim} \frac{2}{\pi \sqrt{e}} \sqrt{r} \left( \frac{4\sqrt{2r}}{\sqrt{\pi}} \right)^{1/2r} \underset{r \to \infty}{\sim} \frac{2}{\pi \sqrt{e}} \sqrt{r}.$$

Thus

$$s_r^{-1/2r} \underset{r \to \infty}{\sim} \frac{\pi \sqrt{e}}{2} \frac{1}{\sqrt{r}}.$$

This series being divergent the Carleman condition (31) is satisfied.

In order to determine the probability measure $\mu$, we use the following relation, which can be found in [1] or in [4].

$$\sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)^{2r+1}} = \frac{(\pi/2)^{2r+1} |E_{2r}|}{2(2r)!} \text{ for every } r \ge 0.$$

Introducing the notation

$$\lambda_k = \frac{\pi^2 (2k+1)^2}{4} \text{ for every } k \ge 0,$$

the moments $s_r$ can then be written as

$$s_r = \frac{|E_{2r}|r!}{(2r)!} = \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)} \frac{r!}{\lambda_k^r}.$$

Observing that $r!/\lambda_k^r$ is the $r$-th order moment of the exponential distribution with rate $\lambda_k$, we obtain that the probability measure $\mu$ is given by the density

$$f(t) = \begin{cases} 0 & \text{if } t \le 0 \\ \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)} \lambda_k e^{-\lambda_k t} & \text{if } t > 0. \end{cases}$$
we conclude that

$$ \sum_{\ell=m+1}^{n-1} (n-\ell) v_{\ell}^{(r)} = \frac{2^r |E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} + n^{2(r+1)} \varepsilon_r(n). \quad (27) $$

Following the same lines, if (26) is true for a fixed $r$ then we have, for $i = m, \dots, n-1$,

$$
\begin{align}
\sum_{\ell=m+1}^{i-1} (i-\ell) v_{\ell}^{(r)} &= (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k} \left[ i \left( \sum_{\ell=m+1}^{i-1} \ell^{2(r-k)} \right) - \left( \sum_{\ell=m+1}^{i-1} \ell^{2(r-k)+1} \right) \right] \nonumber \\
&\quad + n^{2r} \sum_{\ell=m+1}^{i-1} (i-\ell) \varepsilon_r(n, \ell) \nonumber \\
&= (-1)^r 2^r \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r-k))!} n^{2k} \left[ i \frac{i^{2(r-k)+1}}{2(r-k)+1} - \frac{i^{2(r-k)+2}}{2(r-k)+2} \right] (1 + \varepsilon_{r-k}(i)) \nonumber \\
&\quad + n^{2r} \varepsilon_r(n, i) \sum_{\ell=1}^{i-m-1} \ell \nonumber \\
&= (-1)^r 2^r (1 + \varepsilon_r(n, i)) \left( \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r+1-k))!} n^{2k} i^{2(r-k)+2} \right) + n^{2r+2} \varepsilon_r(n, i) \nonumber \\
&= (-1)^r 2^r \left( \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r+1-k))!} n^{2k} i^{2(r+1-k)} \right) + n^{2(r+1)} \varepsilon_r(n, i). \tag{28}
\end{align}
$$

We are now in position to prove relations (26) by induction.

Suppose relations (26) are true for integers $r$ and $r-1$. We then have, using (27) together with formula (17)

$$
\begin{align*}
v^{(r+1)} &= (n-m) \left[ (m^2 - m + 1)v^{(r)} - m(m-1)v^{(r-1)} \right] + (m-1)v^{(r)} + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r)} \\
&= n[n\varepsilon(n)] \frac{2^r |E_{2r}|}{(2r)!} n^{2r} (1 + \varepsilon_r(n)) + n^{2r+1/2} \varepsilon_r(n) + 2 \frac{2^r |E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} (1 + \varepsilon_r(n)) \\
&= n^{2(r+1)} \varepsilon_r(n) + 2n^{2(r+1)} 2^r \frac{|E_{2(r+1)}|}{(2(r+1))!} + n^{2(r+1)} \varepsilon_r(n) \\
&= \frac{2^{r+1} |E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} + n^{2(r+1)} \varepsilon_r(n).
\end{align*}
$$

Similarly, if relations (26) are true for integers $r$ and $r-1$, we then have, using (27) and (28) together with
We then obtain, using the Fréchet-Shohat Theorem, see [13] or [20],

$$ \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{2n^2} > t \right\} = \int_t^\infty f(x)dx = \frac{4}{\pi} \sum_{k=0}^\infty \frac{(-1)^k}{(2k+1)} e^{-\lambda_k t}, $$

which completes the proof.

Note that this result applies in the particular case $m = 2$, for which the lollipop graph $L_2^n$ is nothing but the classical path graph.

# 5 Conclusion

We considered in this paper both the distribution and the moments of the hitting time on the lollipop graph $L_m^n$ which has the maximum expected hitting time among all the $n$ vertex graph. We obtained recurrence relations for all order moments and we used these relations to analyze the asymptotic behavior of the hitting time distribution when $n$ tends to infinity. Further research will be to analyze other particular graphs such as the barbell graph or the tadpole graph.

# References

[1] M. Abramowitz and I. Stegun. *Handbook of Mathematical Functions*. Dover Publications, New-York, 1972.

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

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

[4] J. M. Amigo. Relations among sums of reciprocal powers. *Israel Journal of Mathematics*, 124, 2001.

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

[6] C. Berg and A. J. Durán. A transformation from Hausdorff to Stieltjes moment sequences. *Arkiv för Mathematik*, 42(2), 2004.

[7] P. Billingsley. *Probability and Measure*. Series in probability and mathematical statistics. WILEY, third edition, 1995.

[8] J. M. Borwein, P. B. Borwein, and K. Dilcher. Pi, euler numbers, and asymptotic expansions. *The American Mathematical Monthly*, 96(8), 1989. http://www.jstor.org/stable/2324715.

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

[10] P. G. Doyle and J. L. Snell. Random walks and electrical networks. *Mathematical Assoc. of America, Washington, DC*, 1984.

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

[12] U. Feige. A tight upper bound on the cover time for random walks on graphs. *Random Structures and Algorithms*, 6, 1995.
formula (18), for $i = m, \dots, n - 1$,

$$
\begin{align*}
v_i^{(r+1)} &= (n-i) \left[ (m^2 - m + 1)v^{(r)} - m(m-1)v^{(r-1)} \right] + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(r)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_{\ell}^{(r)} \right) \\
&= n[n\epsilon(n)] \frac{2^r |E_{2r}|}{(2r)!} n^{2r} (1+\epsilon_r(n)) + 2 \frac{2^r |E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} (1+\epsilon_r(n)) \\
&\quad - 2(-1)^r 2^r \left( \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r+1-k))!} n^{2k} i^{2(r+1-k)} \right) + n^{2(r+1)} \epsilon_r(n,i) \\
&= 2 \frac{2^r |E_{2(r+1)}|}{(2(r+1))!} n^{2(r+1)} - 2(-1)^r 2^r \left( \sum_{k=0}^{r} \frac{E_{2k}}{(2k)!(2(r+1-k))!} n^{2k} i^{2(r+1-k)} \right) + n^{2(r+1)} \epsilon_r(n,i) \\
&= (-1)^{r+1} 2^{r+1} \left( \sum_{k=0}^{r+1} \frac{E_{2k}}{(2k)!(2(r+1-k))!} n^{2k} i^{2(r+1-k)} \right) + n^{2(r+1)} \epsilon_r(n,i),
\end{align*}
$$

where we used the well-known fact that $|E_{2(r+1)}| = (-1)^{r+1} E_{2(r+1)}$.

To complete our recursion, there remains to check that relations (26) are valid for $r=1$ and $r=2$.

For $r=1$, since $v^{(0)} = v_i^{(0)} = 1$ and $v^{(-1)} = v_i^{(-1)} = 0$ for any $i$, we have, using relation (17)

$$
\begin{align*}
v^{(1)} &= (n-m)(m^2-m+1) + (m-1) + 2 \sum_{\ell=m+1}^{n-1} (n-\ell) \\
&= n[n\epsilon(n)] + n^{1/2}\epsilon(n) + 2 \sum_{\ell=1}^{n-m-1} \ell \\
&= n^2\epsilon(n) + n^2(1+\epsilon(n)) = \frac{2|E_2|}{2!}n^2 + n^2\epsilon(n),
\end{align*}
$$

since $|E_2| = 1$, and, whenever $i = m, \dots, n - 1$, using formula (18), we also have

$$
\begin{align*}
v_i^{(1)} &= (n-i)(m^2 - m + 1) + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell) - \sum_{\ell=m+1}^{i-1} (i-\ell) \right) \\
&= n[n\epsilon(n)] + 2 \left( \sum_{\ell=1}^{n-m-1} \ell \right) - 2 \left( \sum_{\ell=1}^{i-m-1} \ell \right) \\
&= n^2\epsilon(n) + n^2(1+\epsilon(n)) - (i-m)^2(1+\epsilon(i-m)) \\
&= n^2 - (i-m)^2 + n^2\epsilon(n,i) = n^2 - i^2 + n^2\epsilon(n,i) \\
&= (-1)^1 2^1 \left( \sum_{k=0}^{1} \frac{E_{2k}}{(2k)!(2(1-k))!} n^{2k} i^{2(1-k)} \right) + n^2\epsilon(n,i),
\end{align*}
$$

since $E_0 = 1$ and $E_2 = 1$. Thus, relations (26) are true for $r=1$.

In the same way, for $r=2$, using relation (27) for $r=1$ in (17), which is legitimate thanks to the previous
verification, provides

$$
\begin{align*}
v^{(2)} &= (n-m) \left[ (m^2 - m + 1)v^{(1)} - m(m-1) \right] + (m-1)v^{(1)} + 2 \sum_{\ell=m+1}^{n-1} (n-\ell)v_{\ell}^{(1)} \\
&= n[n\epsilon(n)] n^2 (1+\epsilon(n)) + [n^{1/2}\epsilon(n)] n^2 (1+\epsilon(n)) + \frac{2|E_4|}{4!} n^4 + n^4\epsilon(n) \\
&= \frac{2n^4|E_4|}{4!} + n^4\epsilon(n) \quad \left( = \frac{5}{6}n^4 + n^4\epsilon(n) \text{ since } E_4 = 5 \right),
\end{align*}
$$
[13] M. Frechet and J. Shohat. A proof of the Generalized Second-Limit Theorem in the Theory of Probability. *Transactions of the American Mathematical Society*, 33(2), 1931. https://www.jstor.org/stable/1989421.

[14] 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, 2009.

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

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

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

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

[19] B. Sericola. On cover times of Markov chains. Technical report, Inria Rennes - Bretagne Atlantique, November 2022. https://hal.inria.fr/hal-03837323/file/cover.pdf.

[20] S. Sodin. The classical moment problem, March 2019. School of Mathematical Sciences, Queen Mary University of London. https://webspace.maths.qmul.ac.uk/a.sodin/teaching/moment/clmp.pdf.
and, using relations (27) and (28) for $r = 1$ in (18), which is legitimate thanks to the previous verification, provides for $i = m, \dots, n - 1$,

$$
\begin{align*}
v_i^{(2)} &= (n-i) \left[ (m^2 - m + 1)v^{(1)} - m(m-1) \right] + (m-1)v^{(1)} + 2 \left( \sum_{\ell=m+1}^{n-1} (n-\ell)v_\ell^{(1)} - \sum_{\ell=m+1}^{i-1} (i-\ell)v_\ell^{(1)} \right) \\
&= (n-i) \left[ n\varepsilon(n) n^2 (1+\varepsilon(n)) - n\varepsilon(n) \right] + \left[ n^{1/2}\varepsilon(n) \right] n^2 (1+\varepsilon(n)) \\
&\quad + 2 \left( \frac{2n^4}{4!} |E_4| + n^4\varepsilon(n) - (-1)^2 \sum_{k=0}^{1} \frac{E_{2k}}{(2k)!(2(2-k))!} n^{2k} i^{2(2-k)} \right) + n^4\varepsilon(n,i) \\
&= 2 \frac{2n^4}{4!} E_4 + 4 \frac{E_0}{4!} i^4 + 4 \frac{E_2}{2!2!} n^2 i^2 + n^4\varepsilon(n,i) \\
&= (-1)^2 2^2 \left( \sum_{k=0}^{2} \frac{E_{2k}}{(2k)!(2(2-k))!} i^{2(2-k)} n^{2k} \right) + n^4\varepsilon_r(n,i) \quad \left( = \frac{5}{6} n^4 - i^2 n^2 + \frac{1}{6} i^4 + n^4\varepsilon(n,i) \right).
\end{align*}
$$

Thus relations (26) are also valid for $r = 2$.

This completes the proof of relations (26) by induction.

Now armed with relation (26), we use Theorem 1, to deduce that, for every $i = 1, \dots, m - 1$, we have

$$
\begin{align*}
\mathbb{E}_i(T_n^r) &= \sum_{\ell=1}^r c_{r,\ell} v^{(\ell)} = \sum_{\ell=1}^r c_{r,\ell} \left[ \frac{2^\ell |E_{2\ell}|}{(2\ell)!} n^{2\ell} + n^{2\ell} \varepsilon_\ell(n) \right] \\
&= c_{r,r} \left[ \frac{2^r |E_{2r}|}{(2r)!} n^{2r} + n^{2r} \varepsilon_r(n) \right] \\
&= \frac{2^r |E_{2r}| r!}{(2r)!} n^{2r} + n^{2r} \varepsilon_r(n),
\end{align*}
$$

which completes the proof.

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

Theorem 11 allows us to determine the asymptotic behavior of the distribution of the hitting time $T_n$, when $m/\sqrt{n}$ tends to 0 when $n$ tends to infinity.

**Corollary 12** Assume that for every $n \ge 3$, we have

$$
m = \sqrt{n\varepsilon(n)}, \text{ for some sequence } \varepsilon(n) \text{ satisfying } \varepsilon(n) \xrightarrow{n\to\infty} 0.
$$

Then for all $t \ge 0$ and for every $i = 1, \dots, m - 1$, we have

$$
\lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{2n^2} > t \right\} = \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)} e^{-\lambda_k t}, \quad \text{where } \lambda_k = \frac{\pi^2 (2k+1)^2}{4}.
$$

**Proof.** Introducing the notation $Y_n = T_n/(2n^2)$, we deduce from Theorem 11 that, for every $i = 1, \dots, m-1$,

$$
\lim_{n \to \infty} \mathbb{E}_i (Y_n^r) = \frac{|E_{2r}| r!}{(2r)!}.
$$

Consider the sequence of positive real numbers $s_r$ defined by

$$
s_r = \frac{|E_{2r}| r!}{(2r)!}.
$$

The first values of this sequence are $s_0 = 1$, $s_1 = 1/2$, $s_2 = 5/12$, $s_3 = 61/120$, $s_4 = 277/336$. Our task is now to identify the probability measure $\mu$ associated with the asymptotic moments given by the sequence $s_r$, i.e. such that for any $r$,

$$
s_r = \int_0^\infty x^r d\mu(t).
$$
This problem is well-known and is called the Stieltjes moment problem. If such a measure exists it is called a normalized (because $s_0 = 1$) Stieltjes moment sequence. If the measure is unique then the sequence $s_r$ is said to be determinate, see for instance [6].

First, a sufficient condition for determinacy is given by the following relation, called Carleman's condition

$$ \sum_{r=1}^{\infty} s_r^{-1/2r} = +\infty. \qquad (29) $$

To prove (29), we use the well-known fact (see for instance [8]) that

$$ \frac{|E_{2r}|}{(2r)!} \underset{r \to \infty}{\sim} \frac{4^{r+1}}{\pi^{2r+1}}. $$

Using the Stirling formula for $r!$, this leads to

$$ s_r \underset{r \to \infty}{\sim} \frac{4^{r+1}}{\pi^{2r+1}} \left(\frac{r}{e}\right)^r \sqrt{2\pi r}. $$

Since $1/2r$ tends to 0 when $r$ tends to infinity, we can write

$$ s_r^{1/2r} \underset{r \to \infty}{\sim} \frac{2}{\pi \sqrt{e}} \sqrt{r} \left( \frac{4\sqrt{2r}}{\sqrt{\pi}} \right)^{1/2r} \underset{r \to \infty}{\sim} \frac{2}{\pi \sqrt{e}} \sqrt{r}. $$

Thus

$$ s_r^{-1/2r} \underset{r \to \infty}{\sim} \frac{\pi \sqrt{e}}{2} \frac{1}{\sqrt{r}}. $$

This series being divergent the Carleman condition (29) is satisfied.

Second, in order to determine the probability measure $\mu$, we use the following relation, which can be found in [1] or in [4].

$$ \sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)^{2r+1}} = \frac{(\pi/2)^{2r+1} |E_{2r}|}{2(2r)!} \quad \text{for every } r \ge 0. $$

Introducing the notation

$$ \lambda_k = \frac{\pi^2 (2k + 1)^2}{4} \quad \text{for every } k \ge 0, $$

the moments $s_r$ can then be written as

$$ s_r = \frac{|E_{2r}| r!}{(2r)!} = \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)} \frac{r!}{\lambda_k^r}. $$

Observing that $r!/\lambda_k^r$ is the $r$-th order moment of the exponential distribution with rate $\lambda_k$, we obtain that the probability measure $\mu$ is given by the density

$$ f(t) = \begin{cases} 0 & \text{if } t \le 0 \\ \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)} \lambda_k e^{-\lambda_k t} & \text{if } t > 0. \end{cases} $$

We then obtain, using the Fréchet-Shohat Theorem, see [13] or [20],

$$ \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{2n^2} > t \right\} = \int_t^\infty f(x) dx = \frac{4}{\pi} \sum_{k=0}^\infty \frac{(-1)^k}{(2k+1)} e^{-\lambda_k t}, $$

which completes the proof.
Note that this result applies in the particular case $m = 2$, for which the lollipop graph $L_2^n$ is nothing but the classical path graph.

Corollaries 10 and 12 show that $T_n$, properly normalized, converges in distribution to an exponential distribution and to a linear combination of exponential distributions respectively. The fact that these limits involve exponential distributions seems to be intuitively clear because $T_n$ is reached after a geometric number of attempts. Nevertheless, observe that the normalisation term which leads to the convergence in distribution is of the order of $\mathbb{E}(T_n)$. Indeed, when $m = an$, Corollary 10 tells us that $T_n/\mathbb{E}(T_n)$ converges in distribution. In the same way, for instance when $m$ is constant, Corollary 12 tells us that $T_n/\mathbb{E}(T_n)$ converges in distribution. This means that the convergence of $T_n/\mathbb{E}(T_n)$ should occur for more general graphs.

# 5 Conclusion

We considered in this paper both the distribution and the moments of the hitting time on the lollipop graph $L_m^n$ which has the maximum expected hitting time among all the $n$ vertex graph. We obtained recurrence relations for all order moments and we used these relations to analyze the asymptotic behavior of the hitting time distribution when $n$ tends to infinity. The main difficulty was to exhibit the asymptotic behavior of all order moments which has led to the asymptotic behavior of the distribution of the hitting times $T_n$. We observed that for several values of $m$ depending on $n$, the random variable $T_n/\mathbb{E}(T_n)$ converges in distribution. Further research will thus be to analyze more general graphs to see if this convergence still occurs. A first step will be to consider 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. Another quite interesting question would be to wonder whether the lollipop graph maximizes some of the higher moments among all $n$ vertex graphs.

Competing interests: The authors declare none.

# References

[1] M. Abramowitz and I. Stegun. *Handbook of Mathematical Functions*. Dover Publications, New-York, 1972.

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

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

[4] J. M. Amigo. Relations among sums of reciprocal powers. *Israel Journal of Mathematics*, 124, 2001.

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

[6] C. Berg and A. J. Durán. A transformation from Hausdorff to Stieltjes moment sequences. *Arkiv för Mathematik*, 42(2), 2004.

[7] P. Billingsley. *Probability and Measure*. Series in probability and mathematical statistics. WILEY, third edition, 1995.

[8] J. M. Borwein, P. B. Borwein, and K. Dilcher. Pi, euler numbers, and asymptotic expansions. *The American Mathematical Monthly*, 96(8), 1989. http://www.jstor.org/stable/2324715.

[9] G. Brightwell and P. Winkler. Maximum hitting time for random walks on graphs. *Random Structures and Algorithms*, 1(3), 1990.
[10] P. G. Doyle and J. L. Snell. Random walks and electrical networks. *Mathematical Assoc. of America, Washington, DC*, 1984.

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

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

[13] M. Frechet and J. Shohat. A proof of the Generalized Second-Limit Theorem in the Theory of Probability. *Transactions of the American Mathematical Society*, 33(2), 1931. https://www.jstor.org/stable/1989421.

[14] 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, 2009.

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

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

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

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

[19] B. Sericola. On cover times of Markov chains. Technical report, Inria Rennes - Bretagne Atlantique, November 2022. https://hal.inria.fr/hal-03837323/file/cover.pdf.

[20] S. Sodin. The classical moment problem, March 2019. School of Mathematical Sciences, Queen Mary University of London. https://webspace.maths.qmul.ac.uk/a.sodin/teaching/moment/clmp.pdf.