# Hitting and cover times of the path graph

Bruno Sericola

► To cite this version:

Bruno Sericola. Hitting and cover times of the path graph. Inria Centre at the University of Rennes, France. 2025, pp.1-35. hal-04975338

HAL Id: hal-04975338

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

Submitted on 4 Mar 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Hitting and cover times of the path graph

Bruno Sericola *

March 3, 2025

## Abstract

We consider the moments and the distribution of the hitting times and cover time of the path graph. We obtain recurrence relations for the moments of all order of both the hitting and cover times and we propose two conjectures giving explicit expressions of these moments. We use the recurrence relations on the moments to analyze their asymptotic behavior together with the asymptotic behavior of the distribution of these random variables, for different values of the initial state, when the number of nodes tends to infinity.

**Keywords**: Path graph; Markov chain; Random walk; Hitting time; Cover time; Euler, Bernoulli, Genocchi, Stirling, central factorial, Catalan, ballot numbers.

## 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 [20] while [21] 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 [17].

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 [4] 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 [16], 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 [24] where general formulae for its distribution and its moments are considered with applications to particular finite graphs. The expected hitting times on the lollipop graph, which consists of a complete graph connected with a path graph, has been obtained in [6] where the authors prove that this graph achieves the maximum expected hitting time among all the $n$-vertex graphs when its clique represents 2/3 of the total graph. A detailed analysis of the hitting times on this particular graph has been proposed in [8].

<footnote>*Bruno Sericola is with Inria, Univ. Rennes, CNRS, IRISA</footnote>
In this paper we consider hitting times and cover time of both the finite and the infinite path graphs whose transition probabilities are represented on Figures 1 and 2 respectively. In section 2, we review the main results obtained in [24] which give general expressions for the moments and the distribution of the hitting and cover time of a Markov chain. We analyze in section 3 the hitting time $T_n$ of state $n$ in the path graph when the initial state $i$ belongs to the set $\{0, 1, ..., n-1\}$. A simple recursion is proposed to compute the distribution of $T_n$. The moments of all order of $T_n$ are given through another simple recursion which allows us to obtain an asymptotic expression for the $r$ order moment when $n$ goes to infinity. Having obtained explicit expressions of the four first moments as functions of $i$ and $n$, we formulate a conjecture giving an explicit expression of the $r$ order moment. The asymptotic expression of the $r$ order moment leads to an explicit expression of the limit of the moments of $T_n/n^2$ when $n$ tends to infinity in the cases when the initial state $i$ is fixed and when the initial state $i$ depends linearly on $n$. These results allow us to get the asymptotic distribution of $T_n/n^2$, in both cases, when $n$ tends to infinity using standard arguments of complex analysis. We analyze in section 4 the hitting time $T_{\{0,n\}}$ of subset of state $\{0, n\}$ in the path graph when the initial state $i$ belongs to the set $\{1, ..., n-1\}$. The distribution of $T_{\{0,n\}}$ and its limiting value when $n$ tends to infinity have explicit expressions. The moments of all order of $T_{\{0,n\}}$ are given, as in section 3, through a simple recursion allowing the obtention of an asymptotic expression when $n$ goes to infinity. Another conjecture is formulated for the $r$ order moment when $n$ goes to infinity. As in section 3, we also obtain an explicit expression of the limit of the moments of $T_{\{0,n\}}/n^2$ when $n$ tends to infinity in the both cases when $i$ is fixed and when $i$ depends linearly on $n$. These results allow us to get the asymptotic distribution of $T_{\{0,n\}}/n^2$, in both cases, when $n$ tends to infinity using standard arguments of complex analysis. Section 5 is devoted to the analysis of the cover time of the path graph, which is the time needed to visit at least once all the nodes of the graph. The moments of the cover time are expressed as a function of the moments of $T_n$ and of $T_{\{0,n\}}$. A similar analysis, in terms of moments and distribution, to those of sections 3 and 4 is conducted for the cover time. Section 6 concludes the paper.

# 2 Notation, basic results and path graph

## 2.1 Basic results

We review here the results obtained in [24], which are needed to analyze the moments and distribution of both the hitting times and the cover time of the path graph. Consider a homogeneous discrete-time Markov chain $X = \{X_\ell, \ell \in \mathbb{N}\}$ over a finite state space $S$. We denote by $P$ its transition probability matrix. We suppose that $X$ is irreducible and, for every non empty subset $A$ of $S$, we define the hitting time $T_A$ of $A$ as the first instant at which a state of $A$ is reached by the Markov chain $X$, that is

$$ T_A = \inf\{\ell \ge 0 \mid X_\ell \in A\}. \qquad (1) $$

We denote by $C_A$ the cover time of subset $A$, defined by the time needed to reach all the states of $A$, that is

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

The cover time of the Markov chain $X$, which is the time needed to reach all the states of $S$, is simply denoted by $C$ and is thus given by $C = C_S$. The complementary subset of $A$ in $S$, $S \setminus A$, is denoted by $A^c$ for simplicity. The partition $\{A, A^c\}$ of $S$ induces a decomposition of $P$ into four submatrices as

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

where matrix $P_A$ (resp. $P_{A^c}$) contains the transition probabilities between states of $A$ (resp. $A^c$) and matrix $P_{A,A^c}$ (resp. $P_{A^c,A}$) contains the transition probabilities from states of $A$ (resp. $A^c$) to states of $A^c$ (resp. $A$). We also denote by $\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$, $j \in A$ and $\ell \ge 1$, see for instance [23],

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

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

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

It has been shown in [8] that for every $r \ge 1$ and $i \in A^c$, we have

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

where, for every $\ell = 1, \dots, r$, the $c_{r,\ell}$ are given by

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

In the same way, using (2) and the result of [8], we obtain, for every $i \in A^c$, $j \in A$ and $r \ge 1$,

$$ \mathbb{E}(T_A^r 1_{\{X_{T_A}=j\}} | X_0 = i) = \sum_{\ell=1}^{\infty} \ell^r (P_{A^c}^{\ell-1} P_{A^c,A})_{i,j} = \sum_{\ell=1}^{r} c_{r,\ell} ((I - P_{A^c})^{-(\ell+1)} P_{A^c,A})_{i,j}. \qquad (5) $$

In order to simplify the presentation, we introduce, for any event $u$ and for any random variable $U$, the notation $\mathbb{P}_i\{u\} = \mathbb{P}\{u | X_0 = i\}$ and $\mathbb{E}_i(U) = \mathbb{E}(U | X_0 = i)$.

Concerning the cover time, note that, for every $j \in S$, we have $C_{\{j\}} = T_{\{j\}}$. Moreover, for every $k \ge 0$ and for every $i \in A$, with $|A| \ge 2$, we have, by definition of $C_A$,

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

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

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

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

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

The previous results are used to get the following recursive expression of the distribution of $C_A$ which has been obtained in [24]. For every $A \subset S$ such that $|A| \ge 2$, $i \in A^c$ and $k \ge 0$, we have

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

In the same way, for every $r \ge 1$, the $r$ order moment of the cover time of subset $A$, with $|A| \ge 2$, when starting from state $i \in A^c$ has been obtained in [24] as

$$ \mathbb{E}_i(C_A^r) = \mathbb{E}_i(T_A^r) + \sum_{j \in A} \sum_{m=1}^{r} \binom{r}{m} \mathbb{E}_j(C_{A\setminus\{j\}}^m) \mathbb{E}_i(T_A^{r-m} 1_{\{X_{T_A}=j\}}). \qquad (7) $$
For instance, taking $\ell = 1$ in (7), we get, using (4) and (5), the mean cover time of subset A, that is

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

Taking $\ell = 2$ in (7), we get, using (4) and (5), the second moment of the cover time of subset A, that is

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

In the following, we apply these results to the random walk on the path graph.

## 2.2 Random walk on the path graph

The random walk on the path graph is a Markov chain with state space $S = \{0, 1, \dots, n\}$, $n \ge 1$, with transition probability matrix $P$. Its non zero transition probabilities are given by

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

This Markov chain, denoted by $X = \{X_\ell, \ell \in \mathbb{N}\}$ is also called the classical n-path graph. The analysis of the expected hitting times and expected cover time of this random walk have been analyzed in various papers. We consider here higher order moments and the distributions of these random variables together with their asymptotic behavior when $n$ goes to infinity. The transition graph of $X$ is given by Figure 1.

<figure><img src="image_2.png" /><figcaption>Figure 1: Transition probabilities of the path graph.</figcaption></figure>

## 3 Hitting time of state n

We consider the hitting time of state $n$ in the path graph, when the initial state is state $i \in \{0, 1, \dots, n-1\}$. According to (1), this hitting time is $T_{\{n\}}$ but we simply denote it by $T_n$ because the set of states that has to be reached contains only one state. We introduce the matrix $R$ obtained from matrix $P$ by deleting its last row and its last column corresponding to state $n$. Its non zero entries are thus given by

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

We analyze in the following sections both the distribution and all the moments of $T_n$, together with their asymptotic behavior when $n$ goes to infinity.
## 3.1 Distribution of $T_n$

The distribution of $T_n$ can be obtained using relation (3) with $A = \{n\}$ and $A^c = \{0, 1, \dots, n-1\}$. It can then be written using matrix $R$, for every $i \in \{0, \dots, n-1\}$ and $k \ge 1$, as

$$ \mathbb{P}_i\{T_n = k\} = (R^{k-1}(I - R)\mathbb{1})_i. \qquad (8) $$

We introduce the notation $\Theta_i^{(k)} = \mathbb{P}_i\{T_n = k\}$ and we consider the column vector of dimension $n$

$$ \Theta_i^{(k)} = (\Theta_0^{(k)}, \Theta_1^{(k)}, \dots, \Theta_{n-1}^{(k)}). $$

Relation (8) then reads, for every $n \ge 1$, $k \ge 1$ and $i \in \{0, \dots, n-1\}$, as

$$ \Theta_i^{(k)} = (R^{k-1}\Theta^{(1)})_i, $$

since $\Theta^{(1)} = (I - R)\mathbb{1} = (0, \dots, 0, 1/2)$. The distribution of $T_n$ can then be easily computed using the simple recursion $\Theta^{(k)} = R\Theta^{(k-1)}$, which leads for $n \ge 1$, $k \ge 2$ and $i \in \{0, \dots, n-1\}$, to

$$ \left\{ \begin{array}{l} \mathbb{P}_0\{T_n = k\} = \mathbb{P}_1\{T_n = k-1\} \\ \\ \mathbb{P}_i\{T_n = k\} = \frac{1}{2}\mathbb{P}_{i-1}\{T_n = k-1\} + \frac{1}{2}\mathbb{P}_{i+1}\{T_n = k-1\} \quad \text{for } i = 1, \dots, n-2 \\ \\ \mathbb{P}_{n-1}\{T_n = k\} = \frac{1}{2}\mathbb{P}_{n-2}\{T_n = k-1\}. \end{array} \right. $$

## 3.2 Moments analysis of $T_n$

The general result obtained in Theorem 1 of [8] implies that for every $r \ge 1$ and $i \in \{0, 1, \dots, n-1\}$, we have

$$ \mathbb{E}_i(T_n^r) = \sum_{\ell=1}^{r} c_{r,\ell} ((I-R)^{-\ell}\mathbb{1})_i, \qquad (9) $$

where, for every $\ell = 1, \dots, r$, the coefficients $c_{r,\ell}$ are given by

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

In order to evaluate the moments $\mathbb{E}_i(T_n^r)$, we introduce the column vectors $U^{(\ell)}(n) = (u_0^{(\ell)}(n), \dots, u_{n-1}^{(\ell)}(n))$ defined, for every $\ell \ge 1$, by $U^{(\ell)}(n) = (I - R)^{-\ell}\mathbb{1}$. The following theorem gives a recursive expression of the coordinates

$$ u_i^{(\ell)}(n) = ((I - R)^{-\ell}\mathbb{1})_i. $$

**Theorem 1** For every $n \ge 1$ and $i = 0, \dots, n-1$, we have $u_i^{(0)}(n) = 1$ and for every $\ell \ge 1$

$$ u_i^{(\ell)}(n) = (n - i)u_0^{(\ell-1)}(n) + 2(n - i) \sum_{j=1}^{i} u_j^{(\ell-1)}(n) + 2 \sum_{j=i+1}^{n-1} (n - j)u_j^{(\ell-1)}(n). \qquad (10) $$

**Proof.** By definition of $U^{(\ell)}(n)$, we have $U^{(0)}(n) = \mathbb{1}$ and, for $\ell \ge 1$, $U^{(\ell)}(n) = (I - R)^{-\ell}U^{(\ell-1)}(n)$. This can be written as

$$ U^{(\ell)}(n) - RU^{(\ell)}(n) = U^{(\ell-1)}(n) $$
or equivalently

$$
\left\{
\begin{array}{l}
u_0^{(\ell)}(n) - u_1^{(\ell)}(n) = u_0^{(\ell-1)}(n) \\
\\
u_i^{(\ell)}(n) - \frac{1}{2}u_{i-1}^{(\ell)}(n) - \frac{1}{2}u_{i+1}^{(\ell)}(n) = u_i^{(\ell-1)}(n), \text{ for } i=1, \dots, n-2 \\
\\
u_{n-1}^{(\ell)}(n) - \frac{1}{2}u_{n-2}^{(\ell)}(n) = u_{n-1}^{(\ell-1)}(n).
\end{array}
\right.
$$

Introducing the differences $z_h = u_h^{(\ell)}(n) - u_{h-1}^{(\ell)}(n)$, for $h = 1, \dots, n-1$, with $u_n^{(\ell)}(n) = 0$, we get

$$
z_h - z_{h+1} = 2u_h^{(\ell-1)}(n), \quad h = 1, \dots, n-1.
$$

We then have

$$
z_1 - z_h = \sum_{j=1}^{h-1} (z_j - z_{j+1}) = 2 \sum_{j=1}^{h-1} u_j^{(\ell-1)}(n)
$$

which gives, since $z_1 = -u_0^{(\ell-1)}(n)$,

$$
z_h = -u_0^{(\ell-1)}(n) - 2 \sum_{j=1}^{h-1} u_j^{(\ell-1)}(n).
$$

Summing the $z_h$ for $h = 1$ to $i$ leads to

$$
\sum_{h=1}^{i} z_h = u_{i}^{(\ell)}(n) - u_{0}^{(\ell)}(n) = -i u_{0}^{(\ell-1)}(n) - 2 \sum_{h=1}^{i} \sum_{j=1}^{h-1} u_{j}^{(\ell-1)}(n) = -i u_{0}^{(\ell-1)}(n) - 2 \sum_{h=1}^{i-1} \sum_{j=1}^{h} u_{j}^{(\ell-1)}(n),
$$

that is

$$
u_i^{(\ell)}(n) = u_0^{(\ell)}(n) - i u_0^{(\ell-1)}(n) - 2 \sum_{h=1}^{i-1} \sum_{j=1}^{h} u_j^{(\ell-1)}(n).
$$

Since $u_n^{(\ell)} = 0$ we obtain by setting $i = n$,

$$
u_0^{(\ell)}(n) = n u_0^{(\ell-1)}(n) + 2 \sum_{h=1}^{n-1} \sum_{j=1}^{h} u_j^{(\ell-1)}(n).
$$

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

$$
u_i^{(\ell)}(n) = (n-i)u_0^{(\ell-1)}(n) + 2 \sum_{h=1}^{n-1} \sum_{j=1}^{h} u_j^{(\ell-1)}(n) - 2 \sum_{h=1}^{i-1} \sum_{j=1}^{h} u_j^{(\ell-1)}(n) = (n-i)u_0^{(\ell-1)}(n) + 2 \sum_{h=i}^{n-1} \sum_{j=1}^{h} u_j^{(\ell-1)}(n),
$$

which can also be written as

$$
u_i^{(\ell)}(n) = (n - i)u_0^{(\ell-1)}(n) + 2(n - i) \sum_{j=1}^{i} u_j^{(\ell-1)}(n) + 2 \sum_{j=i+1}^{n-1} (n - j)u_j^{(\ell-1)}(n).
$$

This completes the proof.
Using Theorem 1, we obtain the values of $u_i^{(\ell)}(n) = ((I-R)^{-\ell}1)_i$ recursively, for $i \in \{0, \dots, n-1\}$. The first values are

$$
\begin{align*}
u_i^{(1)}(n) &= (n-i)(n+i), \\
u_i^{(2)}(n) &= \frac{(n-i)(n+i)(5n^2 - (i^2 - 1))}{6}, \\
u_i^{(3)}(n) &= \frac{(n-i)(n+i)\left(61n^4 - (14i^2 - 25)n^2 + (i^2 - 1)(i^2 - 4)\right)}{90}, \\
u_i^{(4)}(n) &= \frac{(n-i)(n+i)\left(1385n^6 - (323i^2 - 854)n^4 + (27i^4 - 196i^2 + 245)n^2 - (i^2 - 1)(i^2 - 4)(i^2 - 9)\right)}{2520}.
\end{align*}
$$

The moments of $T_n$ are then easily obtained from relation (9). The first four moments are given, $n \ge 1$ and $i \in \{0, \dots, n-1\}$, by

$$
\begin{align*}
\mathbb{E}_i(T_n) &= (n-i)(n+i), \\
\mathbb{E}_i(T_n^2) &= \frac{(n-i)(n+i)(5n^2 - i^2 - 2)}{3}, \\
\mathbb{E}_i(T_n^3) &= \frac{(n-i)(n+i)(61n^4 - (14i^2 + 50)n^2 + i^4 + 10i^2 + 4)}{15}, \tag{11} \\
\mathbb{E}_i(T_n^4) &= \frac{(n-i)(n+i)(1385n^6 - (323i^2 + 1708)n^4 + (27i^4 + 392i^2 + 420)n^2 - i^6 - 28i^4 - 84i^2 + 8)}{105}.
\end{align*}
$$

The following theorem will be used to analyze the asymptotic behavior of the $u_i^{(\ell)}(n)$ and then of the moments $\mathbb{E}_i(T_n^\ell)$. We first need to prove a technical lemma based on the Faulhaber formula which uses the well-known Bernoulli numbers $B_j$ defined recursively by $B_0 = 1$ and, for $j \ge 1$,

$$
B_j = - \frac{1}{n+1} \sum_{k=0}^{j-1} \binom{j+1}{k} B_k.
$$

Note that we have $B_1 = -1/2$ and $B_{2j+1} = 0$ for $j \ge 1$. The first non zero Bernoulli numbers are

$$
\begin{align*}
B_0 &= 1, \quad B_1 = -\frac{1}{2}, \quad B_2 = \frac{1}{6}, \quad B_4 = -\frac{1}{30}, \quad B_6 = \frac{1}{42}, \quad B_8 = -\frac{1}{30}, \quad B_{10} = \frac{5}{66}, \quad B_{12} = -\frac{691}{2730}, \\
B_{14} &= \frac{7}{6}, \quad B_{16} = -\frac{3617}{510}, \quad B_{18} = \frac{43867}{798}, \quad B_{20} = -\frac{174611}{330}, \quad B_{22} = \frac{854513}{138}, \quad B_{24} = -\frac{236364091}{2730}.
\end{align*}
$$

**Lemma 2** For every $k \ge 0$, $n \ge 0$ and $i = 0, \dots, n-1$, we have

$$
(n-i) \sum_{j=1}^{i} j^{2k} + \sum_{j=i+1}^{n-1} (n-j)j^{2k} = \begin{cases} \frac{1}{2} (n^2 - i^2 - (n-i)) & \text{if } k=0 \\ \sum_{j=0}^{k} \left[ \frac{\binom{2k+1}{2j}}{2k+1} - \frac{\binom{2k+2}{2j}}{2k+2} \right] B_{2j} (n^{2k+2-2j} - i^{2k+2-2j}) & \text{if } k \ge 1. \end{cases}
$$

Moreover, for $k \ge 1$ we have

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

where $Q_{2k}(i, n)$ is a degree $2k$ polynomial in the two variables $i$ and $n$.
**Proof.** The proof is immediate when $k = 0$. For $k \ge 1$ it based on the Faulhaber formula, see for instance [19], which establishes that, for every $k \ge 1$, we have

$$ \sum_{j=1}^{n} j^k = \frac{1}{k+1} \left( n^{k+1} + \frac{k+1}{2} n^k + \sum_{j=2}^{k} \binom{k+1}{j} B_j n^{k+1-j} \right). \quad (12) $$

Using this formula, we obtain, for every $k \ge 1$,

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

Observing that terms in $i^{2k+1}$ and $n^{2k+1}$ vanish and using the fact that $B_{2j+1} = 0$ for $j \ge 1$, we get

$$ (n-i) \sum_{j=1}^{i} j^{2k} + \sum_{j=i+1}^{n-1} (n-j) j^{2k} = \sum_{j=0}^{k} \left[ \frac{\binom{2k+1}{2j}}{2k+1} - \frac{\binom{2k+2}{2j}}{2k+2} \right] B_{2j} (n^{2k+2-2j} - i^{2k+2-2j}). $$

The second part of the proof is then immediate.

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

We will need in the following both the Euler polynomials and the Euler numbers. The Euler polynomials are defined by

$$ \frac{2e^{xt}}{e^t + 1} = \sum_{n=0}^{\infty} E_n(x) \frac{t^n}{n!}, \quad \text{for } |t| < \pi. $$

They are then recursively given for $n \ge 1$ by

$$ E_0(x) = 1 \text{ and } E_n(x) = x^n - \frac{1}{2} \sum_{\ell=0}^{n-1} \binom{n}{\ell} E_{\ell}(x). $$

The first Euler polynomials are

$$ \begin{aligned} E_0(x) &= 1, \quad E_1(x) = x - \frac{1}{2}, \quad E_2(x) = x^2 - x, \quad E_3(x) = x^3 - \frac{3x^2}{2} + \frac{1}{4}, \quad E_4(x) = x^4 - 2x^3 + x, \\ E_5(x) &= x^5 - \frac{5x^4}{2} + \frac{5x^2}{2} - \frac{1}{2}, \quad E_6(x) = x^6 - 3x^5 + 5x^3 - 3x, \quad E_7(x) = x^7 - \frac{7x^6}{2} + \frac{35x^4}{4} - \frac{21x^2}{2} + \frac{17}{8}. \end{aligned} $$
The Euler numbers $E_n$ are defined by $E_n = 2^n E_n(1/2)$. We then have for $n \ge 0$, $E_{2n+1} = 0$ and the first non-zero Euler numbers are

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

It follows that they are recursively given by $E_0 = 1$ and for $n \ge 1$

$$E_n = -2^{n-1} \sum_{\ell=0}^{n-1} \frac{1}{2^\ell} \binom{n}{\ell} E_\ell + 1.$$

They can also be recursively defined by, see for instance [18], $E_{2\ell+1} = 0$ for $\ell \ge 0$, $E_0 = 1$ and for $\ell \ge 1$,

$$E_{2\ell} = - \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} E_{2h}. \qquad (13)$$

The coefficients of the Euler polynomials can be expressed using the Euler numbers using the following relation

$$E_r(x) = \sum_{k=0}^{r} \binom{r}{h} \frac{E_{2k}}{2^k} \left(x - \frac{1}{2}\right)^{r-h}. \qquad (14)$$

The next theorem will be used to exhibit the asymptotic behaviour of the moments of $T_n$.

**Theorem 3** For every $n \ge 1$, $r, \ell \ge 1$ and $i = 0, \dots, n-1$, we have

$$u_i^{(\ell)}(n) = \frac{(-1)^\ell 2^\ell}{(2\ell)!} \sum_{h=0}^{\ell} \binom{2\ell}{2h} E_{2h} i^{2(\ell-h)} n^{2h} + Q_{2\ell-2}(i, n) \qquad (15)$$

and

$$\mathbb{E}_i(T_n^r) = \sum_{\ell=1}^{r} c_{r,\ell} \left[ \frac{(-1)^\ell 2^\ell}{(2\ell)!} \sum_{h=0}^{\ell} \binom{2\ell}{2h} E_{2h} i^{2(\ell-h)} n^{2h} + Q_{2\ell-2}(i,n) \right]. \qquad (16)$$

where $Q_m(i, n)$ is a degree $m$ polynomial in the two variables $i$ and $n$, with $Q_0(i, n) = 0$.

**Proof.** We proceed by recurrence on integer $\ell$. The result is true for integer $\ell = 1$. Indeed, from relation (10) and since $u_i^{(0)}(n) = 1$ we have

$$u_i^{(1)}(n) = n - i + 2i(n - i) + 2 \sum_{j=i+1}^{n-1} (n - j) = n^2 - i^2.$$

The same result is obtained when putting $\ell = 1$ in (15).

Suppose now that the relation is true for integer $\ell - 1$, that is suppose that

$$u_i^{(\ell-1)}(n) = \frac{(-1)^{\ell-1} 2^{\ell-1}}{(2\ell-2)!} \sum_{h=0}^{\ell-1} \binom{2\ell-2}{2h} E_{2h} i^{2(\ell-1-h)} n^{2h} + Q_{2\ell-4}(i, n).$$

Replacing this expression in relation (10), we obtain

$$\begin{aligned} u_i^{(\ell)}(n) = & \frac{(-1)^{\ell-1} 2^{\ell-1}}{(2\ell-2)!} E_{2\ell-2}(n-i)n^{2\ell-2} + (n-i)Q_{2\ell-4}(0,n) \\ & + \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} \sum_{h=0}^{\ell-1} \binom{2\ell-2}{2h} E_{2h}(n-i) \sum_{j=1}^{i} j^{2(\ell-1-h)} n^{2h} + (n-i) \sum_{j=1}^{i} Q_{2\ell-4}(j,n) \\ & + \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} \sum_{h=0}^{\ell-1} \binom{2\ell-2}{2h} E_{2h} \sum_{j=i+1}^{n-1} (n-j)j^{2(\ell-1-h)} n^{2h} + \sum_{j=i+1}^{n-1} (n-j)Q_{2\ell-4}(j,n) \end{aligned}$$
Observing that we have

$$ (n-i)Q_{2\ell-4}(0,n) = Q_{2\ell-3}(i,n), \quad (n-i)\sum_{j=1}^{i} Q_{2\ell-4}(j,n) = Q_{2\ell-2}(i,n) $$

and

$$ \sum_{j=i+1}^{n-1} (n-j)Q_{2\ell-4}(j,n) = \sum_{j=1}^{n-1} (n-j)Q_{2\ell-4}(j,n) - \sum_{j=1}^{i} (n-j)Q_{2\ell-4}(j,n) = Q_{2\ell-2}(i,n), $$

we obtain

$$ u_i^{(\ell)}(n) = \frac{(-1)^{\ell-1} 2^{\ell-1}}{(2\ell-2)!} E_{2\ell-2}(n-i) n^{2\ell-2} + Q_{2\ell-2}(i,n) \\ + \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} \sum_{h=0}^{\ell-1} \binom{2\ell-2}{2h} E_{2h} \left[ (n-i) \sum_{j=1}^{i} j^{2(\ell-1-h)} + \sum_{j=i+1}^{n-1} (n-j) j^{2(\ell-1-h)} \right] n^{2h}. $$

Extracting the term corresponding to $h = \ell - 1$ in the previous sum leads to

$$ u_i^{(\ell)}(n) = \frac{(-1)^{\ell-1} 2^{\ell-1}}{(2\ell-2)!} E_{2\ell-2}(n-i) n^{2\ell-2} + Q_{2\ell-2}(i,n) \\ + \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} E_{2h} \left[ (n-i) \sum_{j=1}^{i} j^{2(\ell-1-h)} + \sum_{j=i+1}^{n-1} (n-j) j^{2(\ell-1-h)} \right] n^{2h} \\ + \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} E_{2\ell-2} \frac{n^2 - i^2 - (n-i)}{2} n^{2\ell-2} \\ = \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} E_{2h} \left[ (n-i) \sum_{j=1}^{i} j^{2(\ell-1-h)} + \sum_{j=i+1}^{n-1} (n-j) j^{2(\ell-1-h)} \right] n^{2h} \\ + \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} E_{2\ell-2} \frac{n^2 - i^2}{2} n^{2\ell-2} + Q_{2\ell-2}(i,n). $$

Applying Lemma 2 with $k = \ell - 1 - h$, we obtain

$$ \begin{aligned} u_i^{(\ell)}(n) &= \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} E_{2h} \sum_{j=0}^{\ell-1-h} \left[ \frac{\binom{2\ell-2h-1}{2j}}{2\ell-2h-1} - \frac{\binom{2\ell-2h}{2j}}{2\ell-2h} \right] B_{2j} (n^{2\ell-2h-2j} - i^{2\ell-2h-2j}) n^{2h} \\ &\quad + \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} E_{2\ell-2} \frac{n^2 - i^2}{2} n^{2\ell-2} + Q_{2\ell-2}(i,n) \\ &= \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell-2)!} \sum_{h=0}^{\ell-1} \binom{2\ell-2}{2h} E_{2h} \sum_{j=0}^{\ell-1-h} \left[ \frac{\binom{2\ell-2h-1}{2j}}{2\ell-2h-1} - \frac{\binom{2\ell-2h}{2j}}{2\ell-2h} \right] B_{2j} (n^{2\ell-2j} - i^{2\ell-2h-2j} n^{2h}) \\ &\quad + Q_{2\ell-2}(i,n). \end{aligned} $$
The greatest powers of these polynomials are obtained for $j = 0$. We thus get since $B_0 = 1$

$$
\begin{align*}
u_i^{(\ell)}(n) &= \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell)!} \sum_{h=0}^{\ell-1} \binom{2\ell-2}{2h} E_{2h} \left[ \frac{1}{2\ell-2h-1} - \frac{1}{2\ell-2h} \right] (n^{2\ell} - i^{2\ell-2h} n^{2h}) + Q_{2\ell-2}(i, n) \\
&= \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell)!} \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} E_{2h} n^{2\ell} - \frac{(-1)^{\ell-1} 2^{\ell}}{(2\ell)!} \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} E_{2h} i^{2\ell-2h} n^{2h} + Q_{2\ell-2}(i, n) \\
&= \frac{(-1)^{\ell} 2^{\ell}}{(2\ell)!} \left[ \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} E_{2h} i^{2\ell-2h} n^{2h} - \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} E_{2h} n^{2\ell} \right] + Q_{2\ell-2}(i, n).
\end{align*}
$$

Using relation (13), we obtain

$$
\begin{align*}
u_i^{(\ell)}(n) &= \frac{(-1)^{\ell} 2^{\ell}}{(2\ell)!} \left[ \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} E_{2h} i^{2\ell-2h} n^{2h} + E_{2\ell} n^{2\ell} \right] + Q_{2\ell-2}(i, n) \\
&= \frac{(-1)^{\ell} 2^{\ell}}{(2\ell)!} \sum_{h=0}^{\ell} \binom{2\ell}{2h} E_{2h} i^{2\ell-2h} n^{2h} + Q_{2\ell-2}(i, n).
\end{align*}
$$

Relation (16) then follows easily from relation (9).

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

3.3 A first conjecture

The following result is a conjecture giving an explicit expression of the quantities

$$
u_i^{(\ell)}(n) = ((I - Q)^{-\ell} 1)_i
$$

which leads, if true, to an explicit expression for all the moments $E_i(T_n^r)$. We first introduce other well-known
numbers called the Stirling numbers of the first kind and the central factorial numbers of the first kind, see
for instance [22].

The Stirling numbers of the first kind, denoted by $s(\ell, j)$, are defined, for $\ell \ge 0$ and $j = 0, \dots, \ell$, by

$$
s(\ell, 0) = 1_{\{\ell=0\}}, s(\ell, \ell) = 1 \text{ and } s(\ell, j) = s(\ell-1, j-1) - (\ell-1)s(\ell-1, j), \text{ for } \ell \ge 2, j = 1, \dots, \ell-1.
$$

These numbers were introduced by James Stirling (1692-1770) and arise in combinatorial analysis, especially
in the study of permutations. Some values of the Stirling numbers of the first kind $s(\ell, j)$ are given in the
following triangular array.

<table>
  <thead>
    <tr>
      <th></th>
      <th>0</th>
      <th>1</th>
      <th>2</th>
      <th>3</th>
      <th>4</th>
      <th>5</th>
      <th>6</th>
      <th>7</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>1</th>
      <td>0</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>2</th>
      <td>0</td>
      <td>-1</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>3</th>
      <td>0</td>
      <td>2</td>
      <td>-3</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>4</th>
      <td>0</td>
      <td>-6</td>
      <td>11</td>
      <td>-6</td>
      <td>1</td>
      <td></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>5</th>
      <td>0</td>
      <td>24</td>
      <td>-50</td>
      <td>35</td>
      <td>-10</td>
      <td>1</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <th>6</th>
      <td>0</td>
      <td>-120</td>
      <td>274</td>
      <td>-225</td>
      <td>85</td>
      <td>-15</td>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <th>7</th>
      <td>0</td>
      <td>720</td>
      <td>-1764</td>
      <td>1624</td>
      <td>-735</td>
      <td>175</td>
      <td>-21</td>
      <td>1</td>
    </tr>
  </tbody>
</table>

The central factorial numbers of the first kind are denoted by $t(\ell, j)$ and they are defined, for $\ell \ge 0$ and $j = 0, \dots, \ell$, by

$$
t(\ell, 0) = 1, t(\ell, \ell) = (\ell!)^2 \text{ and } t(\ell, j) = t(\ell-1, j) + \ell^2 t(\ell-1, j-1), \text{ for } \ell \ge 2, j = 1, \dots, \ell-1.
$$
They are also characterized by the following closed formula which uses the Stirling numbers of the first kind

$$t(\ell, j) = \sum_{m=\lceil\ell+1-2j\rceil+1}^{\ell+1} (-1)^{\ell+1-j+m} s(\ell+1, m) s(\ell+1, 2(\ell+1-j)-m),$$

where $x^+ = \max(x, 0)$. Some values of the central factorial numbers $t(\ell, j)$ are given in the following triangular array.

<table><thead><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1</td><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td>1</td><td>5</td><td>4</td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>1</td><td>14</td><td>49</td><td>36</td><td></td><td></td><td></td></tr><tr><td>4</td><td>1</td><td>30</td><td>273</td><td>820</td><td>576</td><td></td><td></td></tr><tr><td>5</td><td>1</td><td>55</td><td>1023</td><td>7645</td><td>21076</td><td>14400</td><td></td></tr><tr><td>6</td><td>1</td><td>91</td><td>3003</td><td>44473</td><td>296296</td><td>773136</td><td>518400</td></tr><tr><td>7</td><td>1</td><td>140</td><td>7462</td><td>191620</td><td>2475473</td><td>15291640</td><td>38402064</td><td>25401600</td></tr></tbody></table>

**Conjecture 1.** For every $n \ge 1$, $\ell \ge 1$ and $i = 0, \dots, n-1$, we have

$$u_i^{(\ell)}(n) = \frac{2^{\ell}}{(2\ell)!} \sum_{j=1}^{\ell} (-1)^j t(\ell-1, \ell-j) \sum_{h=0}^{j} \binom{2j}{2h} E_{2h} i^{2(j-h)} n^{2h}. \quad (17)$$

**Motivation.** This conjecture is motivated by the fact that it is true for every $n \ge 1$, $i \in \{0, \dots, n-1\}$ and $\ell = 1, 2, 3, 4$. Indeed, for these first four values of $\ell$, both relations (10) and (17) give the same result. ■

If this conjecture is correct we easily get the following explicit expression for all the $r$ order moments of $T_n$, using relation (9), that is

$$\begin{aligned} \mathbb{E}_i(T_n^r) &= \sum_{\ell=1}^r c_{r,\ell} \frac{2^\ell}{(2\ell)!} \sum_{j=1}^\ell (-1)^j t(\ell-1, \ell-j) \sum_{h=0}^j \binom{2j}{2h} E_{2h} i^{2(j-h)} n^{2h} \\ &= \sum_{j=1}^r (-1)^j \sum_{h=0}^j \binom{2j}{2h} E_{2h} i^{2(j-h)} n^{2h} \sum_{\ell=j}^r \frac{c_{r,\ell} 2^\ell}{(2\ell)!} t(\ell-1, \ell-j). \end{aligned}$$

This relation yields the same results as those obtained in (11).

## 3.4 Asymptotic moments and distribution of $T_n$

We give in the next corollary the limiting value of all the moments of $T_n/n^2$.

**Corollary 4** For each fixed $i \ge 0$ and for every $r \ge 1$, we have,

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

**Proof.** Let us recall relation (16).

$$\mathbb{E}_i(T_n^r) = \sum_{\ell=1}^r c_{r,\ell} \left[ \frac{(-1)^\ell 2^\ell}{(2\ell)!} \sum_{h=0}^\ell \binom{2\ell}{2h} E_{2h} i^{2(\ell-h)} n^{2h} + Q_{2\ell-2}(i,n) \right],$$
where $Q_{2\ell-2}(i, n)$ is a degree $2\ell - 2$ polynomial in the variables $i$ and $n$. If the initial state $i$ is fixed, the greatest power of $n$ is obtained when $h = \ell = r$. It follows that

$$ \mathbb{E}_i(T_n^r) = c_{r,r} \frac{(-1)^r 2^r}{(2r)!} E_{2r} n^{2r} + Q_{2r-2}(n). $$

Since $c(r, r) = r!$ and $(-1)^r E_{2r} = |E_{2r}|$, we obtain

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

which completes the proof.

Observe that we already got a similar result in [8] but in a different context. Indeed, in [8] we considered different sizes of the clique of the lollipop graph while we consider here different values of the initial state.

The limiting distribution of $T_n/n^2$, when the initial state $i$ is fixed, is obtained in the following corollary.

**Corollary 5** For all $t \ge 0$, for each fixed $i \ge 0$, we have

$$ \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{T_n}{n^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}{8}. $$

**Proof.** See [8], Corollary 12.

We now deal with the case where the initial state $i$ is linear with $n$, that is $i = an$ with $a \in (0, 1)$.

**Corollary 6** When $i = an$ with $a \in (0, 1)$, we have for every $r \ge 1$,

$$ \lim_{n \to \infty} \mathbb{E}_{an} \left( \left[ \frac{T_n}{n^2} \right]^r \right) = \frac{(-1)^r 8^r r! E_{2r} ((a+1)/2)}{(2r)!}. $$

**Proof.** If $i = an$, with $a \in (0, 1)$, then relation (16) writes

$$ \mathbb{E}_{an}(T_n^r) = \sum_{\ell=1}^{r} c_{r,\ell} \left[ \frac{(-1)^\ell 2^\ell n^{2\ell}}{(2\ell)!} \sum_{h=0}^{\ell} \binom{2\ell}{2h} E_{2h} a^{2(\ell-h)} + Q_{2\ell-2}(n) \right]. $$

Again, the greatest power of $n$ is obtained when $\ell = r$, which leads to

$$ \mathbb{E}_{an}(T_n^r) = \frac{(-1)^r 2^r r! n^{2r}}{(2r)!} \sum_{h=0}^{r} \binom{2r}{2h} E_{2h} a^{2(r-h)} + Q_{2r-2}(n). $$

Observing that relation (14) leads to the following relation

$$ \sum_{h=0}^{r} \binom{2r}{2h} E_{2h} a^{2(r-h)} = 2^{2r} E_{2r} ((a+1)/2), $$

we obtain

$$ \mathbb{E}_{an}(T_n^r) = \frac{(-1)^r 8^r r! E_{2r}((a+1)/2) n^{2r}}{(2r)!} + Q_{2r-2}(n), $$

that is

$$ \lim_{n \to \infty} \mathbb{E}_{an} \left( \left[ \frac{T_n}{n^2} \right]^r \right) = \frac{(-1)^r 8^r r! E_{2r}((a+1)/2)}{(2r)!}, $$

which completes the proof.
We are now able to determine the asymptotic distribution of $T_n/n^2$ when the initial state is $i = an$, with $a \in (0, 1)$, when $n$ tends to infinity.

**Corollary 7** For all $t \ge 0$ and $a \in (0, 1)$, we have

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

**Proof.** Let $w_r$ be the limiting $r$ order moment of $T_n/n^2$ when the initial state is $i = an$, with $a \in (0, 1)$. From Corollary 6, we have

$$ w_r = \frac{(-1)^r 8^r r! E_{2r}((a+1)/2)}{(2r)!}. $$

Using the results of [1] page 804, we have $E_r(1-x) = (-1)^r E_r(x)$, which means that $E_{2r}(1-x) = E_{2r}(x)$. It follows that $w_r$ can be written as

$$ w_r = \frac{(-1)^r 8^r r! E_{2r}((1-a)/2)}{(2r)!}. $$

Our task is now to identify the probability measure $\mu$ associated with the asymptotic moments given by the sequence $w_r$, that is such that for any $r$,

$$ w_r = \int_0^\infty t^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 $w_0 = 1$) Stieltjes moment sequence. If the measure is unique then the sequence $w_r$ is said to be determinate, see for instance [5].

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

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

For every $r \ge 0$ and $x \in (0, 1/2)$, we have, see [1] page 805,

$$ 0 < (-1)^r E_{2r}(x) \le \frac{|E_{2r}|}{4^r}. $$

Since $a \in (0, 1)$, we have $(1-a)/2 \in (0, 1/2)$ and thus

$$ 0 < w_r \le s_r, \quad \text{where} \quad s_r = \frac{2^r r! |E_{2r}|}{(2r)!}. $$

It follows that $w_r^{-1/2r} \ge s_r^{-1/2r}$ and we already proved in [8], Corollary 12 that $\sum_{r=1}^{\infty} s_r^{-1/2r} = +\infty$. We thus have $\sum_{r=1}^{\infty} w_r^{-1/2r} = +\infty$ which means that the Carleman's condition (19) is satisfied.

Second, in order to determine the probability measure $\mu$, we use the Fourier series of the periodic function associated to $E_{2r}(x)$ which is given, see again [1] page 805, for $r \ge 0$ and $x \in (0, 1)$, by

$$ E_{2r}(x) = \frac{4(-1)^r (2r)!}{\pi^{2r+1}} \sum_{k=0}^{\infty} \frac{\sin\left(\frac{(2k+1)\pi x}{2}\right)}{(2k+1)^{2r+1}}. \qquad (20) $$

Our coefficient $a$ satisfies $a \in (0, 1)$ which means that $(1-a)/2 \in (0, 1/2)$ and thus

$$ E_{2r}((1-a)/2) = \frac{4(-1)^r (2r)!}{\pi^{2r+1}} \sum_{k=0}^{\infty} \frac{\sin\left(\frac{(2k+1)\pi(1-a)}{2}\right)}{(2k+1)^{2r+1}}. $$
It follows that

$$
\begin{align*}
w_r &= \frac{8^r r! 4}{\pi^{2r+1}} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi(1-a)/2)}{(2k+1)^{2r+1}} \\
&= \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi(1-a)/2)}{2k+1} \frac{r!}{\lambda_k^r}, \quad \text{where } \lambda_k = \frac{(2k+1)^2\pi^2}{8}.
\end{align*}
$$

Note that, since $E_0(x) = 1$, when $r = 0$ relation (20) gives, for $x \in (0, 1)$,

$$
\frac{4}{\pi} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi x)}{2k+1} = 1.
$$

Observing that $r! / \lambda_k^r$ is the $r$ 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{\sin\left(\frac{(2k+1)\pi(1-a)}{2}\right)}{(2k+1)} \lambda_k e^{-\lambda_k t} & \text{if } t > 0. \end{cases}
$$

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

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

which completes the proof.

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

4 Hitting time of subset {0, n}

We consider in this section the hitting time $T_{\{0,n\}}$ of subset of states $\{0,n\}$ in the path graph. Following
(1), it is defined by

$$
T_{\{0,n\}} = \inf \{ \ell \ge 0 \mid X_{\ell} \in \{0,n\} \}.
$$

To simplify the notation, we introduce the matrix $Q = P_{\{1,...,n-1\}}$ which is the transition probability matrix between the states of $\{1,...,n-1\}$ of the path graph. The non zero entries of matrix $Q$ are given by

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

4.1 Distribution of $T_{\{0,n\}}$ and its limiting value

The distribution of $T_{\{0,n\}}$ can be obtained using relation (3) with $A = \{0,n\}$ and $A^c = \{1,...,n-1\}$. It
can then be written using matrix $Q$, for every $i \in \{1,...,n-1\}$ and $k \ge 1$, as

$$
\mathbb{P}_i\{T_{\{0,n\}} = k\} = (Q^{k-1}(I - Q)1)_i. \quad (21)
$$

We introduce the notation $\Gamma_i^{(k)} = \mathbb{P}_i\{T_{\{0,n\}} = k\}$ and we consider the column vector of dimension $n-1$

$$
\Gamma^{(k)} = (\Gamma_{1}^{(k)}, \dots, \Gamma_{n-1}^{(k)}).
$$

Relation (21) then reads, for every $n \ge 1$, $k \ge 1$ and $i \in \{0, \dots, n-1\}$, as

$$
\Gamma_i^{(k)} = (Q^{k-1} \Gamma^{(1)})_i,
$$
since $\Gamma^{(1)} = (I - Q)1 = (1/2, 0, \dots, 0, 1/2)$. The distribution of $T_n$ can then be easily computed using the simple recursion $\Gamma^{(k)} = Q\Gamma^{(k-1)}$, which leads for $n \ge 1$, $k \ge 2$ and $i \in \{1, \dots, n-1\}$, to

$$ 
\left\{ 
\begin{array}{l}
\mathbb{P}_1\{T_{\{0,n\}} = k\} = \frac{1}{2}\mathbb{P}_2\{T_{\{0,n\}} = k-1\} \\[1.5ex]
\mathbb{P}_i\{T_{\{0,n\}} = k\} = \frac{1}{2}\mathbb{P}_{i-1}\{T_{\{0,n\}} = k-1\} + \frac{1}{2}\mathbb{P}_{i+1}\{T_{\{0,n\}} = k-1\} \quad \text{for } i=2, \dots, n-3 \\[1.5ex]
\mathbb{P}_{n-1}\{T_{\{0,n\}} = k\} = \frac{1}{2}\mathbb{P}_{n-2}\{T_{\{0,n\}} = k-1\}.
\end{array}
\right. 
$$

Observe that the initial condition is given by $\mathbb{P}_0\{T_{\{0,n\}} = 0\} = \mathbb{P}_n\{T_{\{0,n\}} = 0\} = 1$ and $\mathbb{P}_i\{T_{\{0,n\}} = 0\} = 0$, for $i = 1, \dots, n-1$.

Its easy to obtain an explicit expression of the distribution of $T_{\{0,n\}}$ because matrix $Q$ is a tridiagonal Toeplitz matrix. Its eigenvalues are then all real with multiplicity 1. We denote them by $\lambda_1, \dots, \lambda_{n-1}$ and it is well-known that for $\ell \in \{1, \dots, n-1\}$, we have

$$ \lambda_{\ell} = \cos \left( \frac{\ell \pi}{n} \right). $$

The matrix $Z$ of the right eigenvectors of $Q$ is given, for $\ell, k = 1, \dots, n-1$, by

$$ Z_{\ell,k} = \sin \left( \frac{\ell k \pi}{n} \right). $$

The matrix $Y$ of the left eigenvectors of $Q$ given by $Y = Z$ and we have

$$ Z^2 = \frac{n}{2} I. $$

Let $D$ be the diagonal matrix defined by $D = \text{diag}(\lambda_1, \dots, \lambda_n)$. Matrix $Q$ can then be written as

$$ Q = ZDZ^{-1}, $$

which leads, for every $k \ge 0$, to

$$ Q^k = ZD^k Z^{-1} = \frac{2}{n} ZD^k Z $$

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

$$ (Q^k)_{i,j} = \frac{2}{n} \sum_{\ell=1}^{n-1} Z_{i,\ell} \lambda_{\ell}^k Z_{\ell,j} = \frac{2}{n} \sum_{\ell=1}^{n-1} \sin\left(\frac{\ell i \pi}{n}\right) \sin\left(\frac{\ell j \pi}{n}\right) \cos^k\left(\frac{\ell \pi}{n}\right). $$

Observing that $(I - Q)1 = (1/2, 0, \dots, 0, 1/2)$, except when $n = 2$ in which case we have $(I - Q)1 = 1$, the probability mass function of $T_{\{0,n\}}$ given that the initial state is state $i \in \{1, \dots, n-1\}$ can be written, using (21) for $k \ge 1$, as

$$ 
\begin{align} 
\mathbb{P}_i\{T_{\{0,n\}} = k\} &= \frac{1}{2} (Q^{k-1})_{i,1} + \frac{1}{2} (Q^{k-1})_{i,n-1} \tag{22} \\
&= \frac{1}{n} \sum_{\ell=1}^{n-1} \sin\left(\frac{\ell i \pi}{n}\right) \sin\left(\frac{\ell \pi}{n}\right) \cos^{k-1}\left(\frac{\ell \pi}{n}\right) + \frac{1}{n} \sum_{\ell=1}^{n-1} \sin\left(\frac{\ell i \pi}{n}\right) \sin\left(\frac{\ell (n-1) \pi}{n}\right) \cos^{k-1}\left(\frac{\ell \pi}{n}\right). \nonumber
\end{align} 
$$

The first (resp. the second) term of this expression is equal to the probability that the Markov chain $X$ reaches state 0 (resp. state $n$) at the $k$th step, that is

$$ \mathbb{P}_i\{T_{\{0,n\}} = k, X_k = 0\} = \frac{1}{n} \sum_{\ell=1}^{n-1} \sin\left(\frac{\ell i \pi}{n}\right) \sin\left(\frac{\ell \pi}{n}\right) \cos^{k-1}\left(\frac{\ell \pi}{n}\right) \quad (23) $$
and

$$ \mathbb{P}_i\{T_{\{0,n\}} = k, X_k = n\} = \frac{1}{n} \sum_{\ell=1}^{n-1} \sin\left(\frac{\ell i \pi}{n}\right) \sin\left(\frac{\ell(n-1)\pi}{n}\right) \cos^{k-1}\left(\frac{\ell \pi}{n}\right). $$

Observe that Relation (23) has been obtained in [13] using generating functions and partial fractions. We now consider the limiting distribution of the hitting time $T_{\{0,n\}}$ when $n$ tends to infinity. The transition graph of $X$ is now infinite. It is given by Figure 2.

<figure><img src="image_6.png" /><figcaption>Figure 2: Transition graph of the infinite path graph.</figcaption></figure>

We denote by $T_0$ the hitting time of state 0 in this infinite path graph, that is the first instant at which the infinite Markov chain $X$ enters state 0, when the initial state is state $i \ge 1$. More formally,

$$ T_0 = \inf\{\ell \ge 0 \mid X_\ell = 0\}. $$

The distribution of $T_0$ when the initial state is state $i \ge 1$ is given, for every $k \ge 1$, by

$$ \mathbb{P}_i\{T_0 = k\} = (Q^{k-1}(I-Q)1)_i \quad (24) $$

where the matrix $Q$ is now infinite. Its non zero entries are given by

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

**Remark 8** The probability mass function of $T_0$ has been obtained in [13] by taking the limit of relation (23) when $n$ tends to infinity. Indeed relation (23) can be interpreted as a Riemann sum converging to an integral which can be calculated, for $i \ge 1$ and $k \ge 1$, as

$$ \lim_{n \to \infty} \mathbb{P}_i\{T_{\{0,n\}} = k, X_k = 0\} = \int_0^1 \sin(i\pi x) \sin(\pi x) \cos^{k-1}(\pi x) dx = \binom{k}{(k-i)/2} \frac{i}{k2^k}, $$

where the binomial coefficient is equal to 0 if $(k-i)/2$ is not an integer of the interval $[0, k]$.

We propose another interesting approach to calculate the distribution of $T_0$. It will be used, in particular, to show that the random variable $T_0$ is almost surely finite. We first need to introduce other well-known numbers called the Catalan and the generalized Catalan's numbers. Eugene Charles Catalan (1814-1894) used these numbers while studying well-formed sequences of parentheses. They are used today in several areas such as in computational geometry, geographic information systems, geodesy, cryptography, and medicine. The Catalan's numbers are denoted by $C_k$, for $k \ge 0$ and are defined by

$$ C_k = \binom{2k}{k} \frac{1}{k+1} = \binom{2k+1}{k} \frac{1}{2k+1}. $$

The first values of this sequence are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012.

The generating function $C(x)$ of this sequence is given by

$$ C(x) = \sum_{k=0}^{\infty} C_k x^k = \frac{1 - \sqrt{1 - 4x}}{2x}, \quad \text{for } |x| \le 1/4. $$
For $k \ge 0$ and $i \ge 0$, we denote by $C_{k,i}$ the generalized Catalan numbers, which are also called the ballot numbers, see for instance [7], and are defined by

$$C_{0,0} = 1 \text{ and } C_{k,i} = \binom{2k+i}{k} \frac{i}{2k+i}.$$

Observe that we have $C_k = C_{k,1}$. The generating function of this sequence is equal to $C^i(x)$, that is,

$$C^i(x) = \sum_{k=0}^{\infty} C_{k,i} x^k = \left( \frac{1 - \sqrt{1 - 4x}}{2x} \right)^i, \quad \text{for } |x| \le 1/4. \qquad (25)$$

The probability mass function of $T_0$ is given by the following theorem which uses these numbers.

**Theorem 9** The probability mass function of random variable $T_0$ is given by

$$\mathbb{P}_{2i+1}\{T_0 = 2k\} = 0 \quad \text{for } i \ge 0 \text{ and } k \ge 0 \qquad (26)$$

$$\mathbb{P}_{2i}\{T_0 = 2k\} = \begin{cases} \frac{C_{k-i, 2i}}{2^{2k}} & \text{for } 1 \le i \le k \\ 0 & \text{for } i \ge k+1 \end{cases} \qquad (27)$$

$$\mathbb{P}_{2i+1}\{T_0 = 2k+1\} = \begin{cases} \frac{C_{k-i, 2i+1}}{2^{2k+1}} & \text{for } 0 \le i \le k \\ 0 & \text{for } i \ge k+1 \end{cases} \qquad (28)$$

$$\mathbb{P}_{2i}\{T_0 = 2k+1\} = 0 \quad \text{for } i \ge 1 \text{ and } k \ge 0. \qquad (29)$$

**Proof.** We clearly have $\mathbb{P}_i\{T_0 = 0\} = 0$ for every $i \ge 1$. For $k \ge 1$ and $i \ge 1$, the distribution of $T_0$ is given by relation of (24). For $k \ge 1$, we introduce the infinite column vector $U(k)$ defined by $U(k) = (\mathbb{P}_i\{T_0 = k\}, i \ge 1)$. Relation of (24) can then be written as $U(k) = Q^{k-1}(I - Q)1$. It follows that $U(k)$ is recursively given by

$$U(1) = (I - Q)1 = (1/2, 0, 0, 0, \dots) \text{ and } U(k) = QU(k-1), \text{ for every } k \ge 2.$$

Observing that $\mathbb{P}_i\{T_0 = k\} = 0$ for every $i \ge k+1$, this relation can be written, for $k \ge 2$, as

$$\left\{ \begin{array}{l} \mathbb{P}_1\{T_0 = k\} = \frac{1}{2}\mathbb{P}_2\{T_0 = k-1\} \\ \\ \mathbb{P}_i\{T_0 = k\} = \frac{1}{2}\mathbb{P}_{i-1}\{T_0 = k-1\} + \frac{1}{2}\mathbb{P}_{i+1}\{T_0 = k-1\}, \text{ for every } i = 2, \dots, k-2 \\ \\ \mathbb{P}_{k-1}\{T_0 = k\} = \frac{1}{2}\mathbb{P}_{k-2}\{T_0 = k-2\} \\ \\ \mathbb{P}_k\{T_0 = k\} = \frac{1}{2}\mathbb{P}_{k-1}\{T_0 = k-1\}. \end{array} \right. \qquad (30)$$

We proceed by recurrence. The relations (26) to (29) are clearly true for $k = 0$. Suppose that relations (28) and (29) are true for integer $2k-1$. We then have from relation (30)

$$\mathbb{P}_{2i+1}\{T_0 = 2k\} = \frac{1}{2}\mathbb{P}_{2i}\{T_0 = 2k-1\} + \frac{1}{2}\mathbb{P}_{2i+2}\{T_0 = 2k-1\} = 0$$
and

$$
\begin{align*}
\mathbb{P}_{2i}\{T_0 = 2k\} &= \frac{1}{2}\mathbb{P}_{2i-1}\{T_0 = 2k-1\} + \frac{1}{2}\mathbb{P}_{2i+1}\{T_0 = 2k-1\} \\
&= \frac{1}{2}\frac{C_{k-i, 2i-1}}{2^{2k-1}} + \frac{1}{2}\frac{C_{k-i-1, 2i+1}}{2^{2k-1}} \\
&= \frac{C_{k-i, 2i-1} + C_{k-i-1, 2i+1}}{2^{2k}} \\
&= \frac{1}{2^{2k}}\binom{2k-1}{k-i}\frac{2i}{k+i} = \frac{C_{k-i, 2i}}{2^{2k}},
\end{align*}
$$

which are relations (26) and (27). Suppose now that relations (26) and (27) are true for integer $2k$. We then
have from relation (30)

$$
\mathbb{P}_{2i}\{T_0 = 2k+1\} = \frac{1}{2}\mathbb{P}_{2i-1}\{T_0 = 2k\} + \frac{1}{2}\mathbb{P}_{2i+1}\{T_0 = 2k\} = 0
$$

and

$$
\begin{align*}
\mathbb{P}_{2i+1}\{T_0 = 2k+1\} &= \frac{1}{2}\mathbb{P}_{2i}\{T_0 = 2k\} + \frac{1}{2}\mathbb{P}_{2i+2}\{T_0 = 2k\} \\
&= \frac{1}{2}\frac{C_{k-i, 2i}}{2^{2k}} + \frac{1}{2}\frac{C_{k-i-1, 2i+2}}{2^{2k}} \\
&= \frac{C_{k-i, 2i} + C_{k-i-1, 2i+2}}{2^{2k+1}} \\
&= \frac{1}{2^{2k+1}}\binom{2k}{k-i}\frac{2i+1}{k+i+1} = \frac{C_{k-i, 2i+1}}{2^{2k+1}},
\end{align*}
$$

which are relations (28) and (29). This completes the proof.

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

In order to determine if the random variable is almost surely finite we have to prove that $\mathbb{P}_i\{T_0 < \infty\} = 1$.
This is given by the following result.

**Lemma 10** For every $i \ge 1$, we have $\mathbb{P}_i\{T_0 < \infty\} = 1$.

**Proof.** From Theorem 9 and using relation (25), we have by taking $x = 1/4$,

$$
\mathbb{P}_{2i}\{T_0 < \infty\} = \sum_{k=i}^{\infty} \mathbb{P}_{2i}\{T_0 = 2k\} = \sum_{k=i}^{\infty} C_{k-i, 2i} \left(\frac{1}{4}\right)^k = \frac{1}{4^i} \sum_{k=0}^{\infty} C_{k, 2i} \left(\frac{1}{4}\right)^k = 1.
$$

In the same way, we have from Theorem 9 and from relation (25),

$$
\mathbb{P}_{2i+1}\{T_0 < \infty\} = \sum_{k=i}^{\infty} \mathbb{P}_{2i+1}\{T_0 = 2k+1\} = \frac{1}{2} \sum_{k=i}^{\infty} C_{k-i, 2i+1} \left(\frac{1}{4}\right)^k = \frac{1}{2^{2i+1}} \sum_{k=0}^{\infty} C_{k, 2i+1} \left(\frac{1}{4}\right)^k = 1,
$$

which completes the proof.

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

The following section deals with the analysis of the moments of both $T_{\{0,n\}}$ on the finite path graph and $T_0$ on the infinite path graph.

**4.2 Moments analysis of T<sub>{0,n}</sub>**

The general result obtained in Theorem 1 of [8] implies that for every $r \ge 1$ and $i \in \{1, \dots, n-1\}$, we have

$$
\mathbb{E}_i \left( T_{\{0,n\}}^r \right) = \sum_{\ell=1}^{r} c_{r,\ell} \left( (I-Q)^{-\ell} 1 \right)_i . \qquad (31)
$$
In order to use this relation, as we did for random variable $T_n$, we need to compute the column vectors $(I-Q)^{-\ell}1$, for every $\ell \ge 1$. They are given recursively by the following theorem. We first introduce the notation

$$v_i^{(\ell)}(n) = ((I-Q)^{-\ell}1)_i.$$

**Theorem 11** For every $n \ge 2$, $\ell \ge 1$ and $i \in \{1, \dots, n-1\}$, we have $v_i^{(0)}(n) = 1$ and

$$v_i^{(\ell)}(n) = \frac{2i}{n} \sum_{j=1}^{n-1} (n-j)v_j^{(\ell-1)}(n) - 2 \sum_{j=1}^{i-1} (i-j)v_j^{(\ell-1)}(n). \quad (32)$$

**Proof.** By definition, when $\ell = 0$ we have $v_i^{(0)}(n) = 1$. Consider the column vector $V^{(\ell)}(n)$ defined by $V^{(\ell)}(n) = (I-Q)^{-\ell}1 = (v_1^{(\ell)}(n), \dots, v_{n-1}^{(\ell)}(n))$. It is solution to the system $(I-Q)V^{(\ell)}(n) = V^{(\ell-1)}(n)$, which can be written as

$$\left\{
\begin{aligned}
v_1^{(\ell)}(n) - \frac{1}{2}v_2^{(\ell)}(n) &= v_1^{(\ell-1)}(n) \\
-\frac{1}{2}v_{k-1}^{(\ell)}(n) + v_k^{(\ell)}(n) - \frac{1}{2}v_{k+1}^{(\ell)}(n) &= v_k^{(\ell-1)}(n), \quad \text{for } k=2, \dots, n-2 \\
-\frac{1}{2}v_{n-2}^{(\ell)}(n) + v_{n-1}^{(\ell)}(n) &= v_{n-1}^{(\ell-1)}(n).
\end{aligned}
\right.$$

Introducing the notation $v_0^{(\ell)}(n) = 0$ and $v_n^{(\ell)}(n) = 0$, these equations lead to

$$-\frac{1}{2}v_{k-1}^{(\ell)}(n) + v_k^{(\ell)}(n) - \frac{1}{2}v_{k+1}^{(\ell)}(n) = v_k^{(\ell-1)}(n), \quad \text{for } k=1, \dots, n-1.$$

Writing $v_k^{(\ell)}(n) = v_k^{(\ell)}(n)/2 + v_k^{(\ell)}(n)/2$, we get

$$\frac{1}{2}(v_k^{(\ell)}(n) - v_{k-1}^{(\ell)}(n)) - \frac{1}{2}(v_{k+1}^{(\ell)}(n) - v_k^{(\ell)}(n)) = v_k^{(\ell-1)}(n), \quad \text{for } k=1, \dots, n-1,$$

that is

$$v_{k+1}^{(\ell)}(n) - v_k^{(\ell)}(n) = v_k^{(\ell)}(n) - v_{k-1}^{(\ell)}(n) - 2v_k^{(\ell-1)}(n), \quad \text{for } k=1, \dots, n-1,$$

which gives, since $v_0^{(\ell)}(n) = 0$,

$$v_{k+1}^{(\ell)}(n) - v_k^{(\ell)}(n) = v_1^{(\ell)}(n) - 2 \sum_{j=0}^{k-1} v_{k-j}^{(\ell-1)}(n) = v_1^{(\ell)}(n) - 2 \sum_{j=1}^{k} v_j^{(\ell-1)}(n). \quad (33)$$

Summing relation (33) from $k=1$ to $n-1$ gives, since $v_n^{(\ell)}(n) = 0$,

$$-v_1^{(\ell)}(n) = (n-1)v_1^{(\ell)}(n) - 2 \sum_{k=1}^{n-1} \sum_{j=1}^{k} v_j^{(\ell-1)}(n) = (n-1)v_1^{(\ell)}(n) - 2 \sum_{j=1}^{n-1} (n-j)v_j^{(\ell-1)}(n).$$

This leads to

$$v_1^{(\ell)}(n) = \frac{2}{n} \sum_{j=1}^{n-1} (n-j) v_j^{(\ell-1)}(n).$$

Summing relation (33) from $k=1$ to $i-1$ gives

$$v_i^{(\ell)}(n) - v_1^{(\ell)}(n) = (i-1)v_1^{(\ell)}(n) - 2 \sum_{k=1}^{i-1} \sum_{j=1}^{k} v_j^{(\ell-1)}(n) = (i-1)v_1^{(\ell)}(n) - 2 \sum_{j=1}^{i-1} (i-j)v_j^{(\ell-1)}(n),$$
that is

$$v_i^{(\ell)}(n) = iv_1^{(\ell)}(n) - 2 \sum_{j=1}^{i-1} (i-j)v_j^{(\ell-1)}(n).$$

It follows that

$$v_i^{(\ell)}(n) = \frac{2i}{n} \sum_{j=1}^{n-1} (n-j)v_j^{(\ell-1)}(n) - 2 \sum_{j=1}^{i-1} (i-j)v_j^{(\ell-1)}(n),$$

which completes the proof.

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

Using Theorem 11, we obtain the values of $v_i^{(\ell)}(n) = ((I-Q)^{-\ell}1)_i$ recursively, for $i \in \{1, \dots, n-1\}$. The first values are the following ones.

$$ 
\begin{align} 
v_i^{(0)}(n) &= 1, \quad v_i^{(1)}(n) = i[n-i], \quad v_i^{(2)}(n) = \frac{i}{6}[n^3 - 2i^2n + i^3 + n - i], \nonumber \\ 
v_i^{(3)}(n) &= \frac{i}{90}[3n^5 - 5i^2n^3 + 3i^4n - i^5 + 5(n^3 - 2i^2n + i^3) + 4(n-i)], \tag{34} \\ 
v_i^{(4)}(n) &= \frac{i}{2520}[17n^7 - 28i^2n^5 + 14i^4n^3 - 4i^6n + i^7 + 14(3n^5 - 5i^2n^3 + 3i^4n - i^5) \nonumber \\ 
&\quad + 49(n^3 - 2i^2n + i^3) + 36(n-i)]. \nonumber 
\end{align} 
$$

Putting these values in relation (31) leads to

$$ 
\begin{align} 
\mathbb{E}_i(T_{\{0,n\}}) &= v_i^{(1)}(n) = i[n-i] \nonumber \\ 
\mathbb{E}_i(T_{\{0,n\}}^2) &= -v_i^{(1)}(n) + 2v_i^{(2)}(n) = \frac{i}{3}[(n^3 - 2i^2n + i^3) - 2(n-i)] \nonumber \\ 
\mathbb{E}_i(T_{\{0,n\}}^3) &= v_i^{(1)}(n) - 6v_i^{(2)}(n) + 6v_i^{(3)}(n) \nonumber \\ 
&= \frac{i}{15}[(3n^5 - 5i^2n^3 + 3i^4n - i^5) - 10(n^3 - 2i^2n + i^3) + 4(n-i)] \tag{35} \\ 
\mathbb{E}_i(T_{\{0,n\}}^4) &= -v_i^{(1)}(n) + 14v_i^{(2)}(n) - 36v_i^{(3)}(n) + 24v_i^{(4)}(n) \nonumber \\ 
&= \frac{i}{105}[(17n^7 - 28i^2n^5 + 14i^4n^3 - 4i^6n + i^7) - 28(3n^5 - 5i^2n^3 + 3i^4n - i^5) \nonumber \\ 
&\quad + 84(n^3 - 2i^2n + i^3) + 8(n-i)]. \nonumber 
\end{align} 
$$

The following theorem will be useful for the asymptotic analysis of the moments $\mathbb{E}(T_{\{0,n\}})$. We first need to introduce some well-known polynomials and numbers.

The Genocchi polynomials $G_n(x)$ are defined by

$$\frac{2te^{xt}}{e^t + 1} = \sum_{n=0}^{\infty} G_n(x) \frac{t^n}{n!}, \quad |t| < \pi.$$

The Genocchi numbers are defined by $g_n = G_n(0)$, that is

$$\frac{2t}{e^t + 1} = \sum_{n=0}^{\infty} g_n \frac{t^n}{n!}, \quad |t| < \pi.$$

We then have $g_{2k+1} = 0$ for $k \ge 1$ and

$$g_0 = 0, \quad g_1 = 1, \quad g_2 = -1, \quad g_4 = 1, \quad g_6 = -3, \quad g_8 = 17, \quad g_{10} = -155, \quad g_{12} = 2073.$$
We thus have

$$G_n(x) = \sum_{k=0}^{n} \binom{n}{k} g_k x^{n-k}. \qquad (36)$$

Observing that the odd Genocchi numbers, except $g_1$, are equal to 0, sometimes the Genocchi numbers are defined by $G_n = (-1)^n g_{2n}$ which gives

$$G_0 = 0, G_1 = 1, G_2 = 1, G_3 = 3, G_4 = 17, G_5 = 155, G_6 = 2073. \qquad (37)$$

We will use this definition. These integers numbers were discovered by Angelo Genocchi (1817–1889) and have been extensively studied in many different branches of mathematics and in quantum physics.

Bernoulli and Genocchi numbers are related by the following formula

$$G_n = (-1)^n 2(1 - 2^{2n}) B_{2n} = 2(2^{2n} - 1)|B_{2n}|.$$

We will use the following relation which is proved for instance in [9]. For every $\ell \ge 1$, we have

$$\sum_{h=0}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^h G_{\ell-h}}{2h+1} = (-1)^{\ell-1}. \qquad (38)$$

**Theorem 12** For every $n \ge 2$, for every $r$, $\ell \ge 1$ and $i \in \{1, \dots, n-1\}$, we have

$$v_i^{(\ell)}(n) = \frac{i2^\ell}{(2\ell)!} \left( \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^h G_{\ell-h}}{2h+1} i^{2h} n^{2\ell-2h-1} + (-1)^\ell i^{2\ell-1} \right) + Q_{2\ell-2}(i,n),$$

where $Q_m(i, n)$ is a degree $m$ polynomial in the two variables $i$ and $n$, with $Q_0(i, n) = 0$. Moreover,

$$\mathbb{E}_i \left( T_{\{0,n\}}^r \right) = i \sum_{\ell=1}^{r} \frac{c_{r,\ell} 2^\ell}{(2\ell)!} \left( \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^h G_{\ell-h}}{2h+1} i^{2h} n^{2\ell-2h-1} + (-1)^\ell i^{2\ell-1} \right) + Q_{2r-2}(i,n),$$

**Proof.** The proof is made by recurrence. For $\ell = 1$ we already saw that $v_i^{(1)}(n) = i(n - i)$. On the other hand, for $\ell = 1$ we have $G_1 = 1$ and thus the right hand side of the formula of the theorem is equal to $i(n - i)$.

Suppose that the theorem is true for integer $\ell - 1$. We then have

$$v_i^{(\ell-1)}(n) = \frac{i 2^{\ell-1}}{(2\ell-2)!} \left( \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} i^{2h} n^{2\ell-2h-3} + (-1)^{\ell-1} i^{2\ell-3} \right) + Q_{2\ell-4}(i,n).$$
We consider separately the two sums of relation (32). Concerning the first one, we get

$$
\begin{align*}
& \frac{2i}{n} \sum_{k=1}^{n-1} (n-k) v_k^{(\ell-1)}(n) \\
&= \frac{2i}{n} \sum_{k=1}^{n-1} \frac{k(n-k) 2^{\ell-1}}{(2\ell-2)!} \left( \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} k^{2h} n^{2\ell-2h-3} + (-1)^{\ell-1} k^{2\ell-3} \right) \\
&\quad + \frac{2i}{n} \sum_{k=1}^{n-1} (n-k) Q_{2\ell-4}(k,n) \\
&= \frac{i 2^\ell}{(2\ell-2)!} \left( \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} n^{2\ell-2h-3} \sum_{k=1}^{n-1} k^{2h+1} + (-1)^{\ell-1} \sum_{k=1}^{n-1} k^{2\ell-2} \right) \\
&\quad - \frac{i 2^\ell}{(2\ell-2)!} \left( \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} n^{2\ell-2h-3} \frac{1}{n} \sum_{k=1}^{n-1} k^{2h+2} + (-1)^{\ell-1} \frac{1}{n} \sum_{k=1}^{n-1} k^{2\ell-1} \right) \\
&\quad + \frac{2i}{n} \sum_{k=1}^{n-1} (n-k) Q_{2\ell-4}(k,n).
\end{align*}
$$

Observe that for every non negative integer $m$ we have

$$
\sum_{k=1}^{n-1} k^m = \frac{n^{m+1}}{m+1} + \Theta_m(n), \quad (39)
$$

where $\Theta_m(n)$ is a degree $m$ polynomial in the variable $n$. We then have

$$
\frac{2i}{n} \sum_{k=1}^{n-1} (n-k) Q_{2\ell-4}(k,n) = 2i \sum_{k=1}^{n-1} Q_{2\ell-4}(k,n) - 2i \sum_{k=1}^{n-1} \frac{k}{n} Q_{2\ell-4}(k,n) = i \Theta_{2\ell-3}(n) = Q_{2\ell-2}(i,n).
$$

It follows that

$$
\frac{2i}{n} \sum_{k=1}^{n-1} (n-k) v_k^{(\ell-1)}(n) = \frac{i 2^\ell}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} n^{2\ell-2h-3} \left( \sum_{k=1}^{n-1} k^{2h+1} - \frac{1}{n} \sum_{k=1}^{n-1} k^{2h+2} \right) \\
+ \frac{i 2^\ell}{(2\ell-2)!} (-1)^{\ell-1} \left( \sum_{k=1}^{n-1} k^{2\ell-2} - \frac{1}{n} \sum_{k=1}^{n-1} k^{2\ell-1} \right) + Q_{2\ell-2}(i,n).
$$

It is easily checked, using the Faulhaber formula (12) and the fact the Bernoulli numbers satisfy $B_{2j+1} = 0$ for $j \ge 1$, that the odd coefficients of polynomial in $n \left( \sum_{k=1}^{n-1} k^{2h+1} - \frac{1}{n} \sum_{k=1}^{n-1} k^{2h+2} \right)$ are equal to 0 and that the even coefficients of polynomial in $n \left( \sum_{k=1}^{n-1} k^{2\ell-2} - \frac{1}{n} \sum_{k=1}^{n-1} k^{2\ell-1} \right)$ are also equal to 0. It follows, from relation (39), that

$$
\begin{align*}
\frac{2i}{n} \sum_{k=1}^{n-1} (n-k) u_k^{(\ell-1)}(n) &= \frac{i 2^\ell}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} n^{2\ell-2h-3} \left( \frac{n^{2h+2}}{(2h+2)(2h+3)} + \Theta_{2h}(n) \right) \\
&\quad + \frac{i 2^\ell}{(2\ell-2)!} (-1)^{\ell-1} \left( \frac{n^{2\ell-1}}{(2\ell-1)2\ell} + \Theta_{2\ell-3}(n) \right) + Q_{2\ell-2}(i,n) \\
&= \frac{i 2^\ell}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{(2h+1)(2h+2)(2h+3)} n^{2\ell-1} \\
&\quad + \frac{i 2^\ell}{(2\ell-2)!} (-1)^{\ell-1} \frac{n^{2\ell-1}}{(2\ell-1)2\ell} + Q_{2\ell-2}(i,n).
\end{align*}
$$
Writing

$$ \binom{2\ell-2}{2h} \frac{(2\ell-1)2\ell}{(2h+1)(2h+2)} = \frac{(2\ell)!}{(2h+2)!(2\ell-2-2h)!} = \binom{2\ell}{2h+2} $$

yields

$$ \begin{aligned} \frac{2i}{n} \sum_{k=1}^{n-1} (n-k) v_k^{(\ell-1)}(n) &= \frac{i2^\ell}{(2\ell)!} \sum_{h=0}^{\ell-2} \binom{2\ell}{2h+2} \frac{(-1)^h G_{\ell-1-h}}{2h+3} n^{2\ell-1} + \frac{i2^\ell}{(2\ell)!} (-1)^{\ell-1} n^{2\ell-1} + Q_{2\ell-2}(i,n) \\ &= \frac{i2^\ell}{(2\ell)!} \sum_{h=1}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^{h-1} G_{\ell-h}}{2h+1} n^{2\ell-1} + \frac{i2^\ell}{(2\ell)!} (-1)^{\ell-1} n^{2\ell-1} + Q_{2\ell-2}(i,n) \\ &= \frac{i n^{2\ell-1} 2^\ell}{(2\ell)!} \left( \sum_{h=1}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^{h-1} G_{\ell-h}}{2h+1} + (-1)^{\ell-1} \right) + Q_{2\ell-2}(i,n). \end{aligned} $$

This leads, using relation (38), to

$$ \frac{2i}{n} \sum_{k=1}^{n-1} (n-k) v_k^{(\ell-1)}(n) = \frac{2^\ell G_\ell}{(2\ell)!} i n^{2\ell-1} + Q_{2\ell-2}(i,n). \quad (40) $$

In the same way, the second sum of relation (32) leads to

$$ \begin{aligned} 2 \sum_{k=1}^{i-1} (i-k) v_k^{(\ell-1)}(n) &= \sum_{k=1}^{i-1} \frac{(i-k) k 2^\ell}{(2\ell-2)!} \left( \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} k^{2h} n^{2\ell-2h-3} + (-1)^{\ell-1} k^{2\ell-3} \right) \\ &\quad + 2 \sum_{k=1}^{i-1} (i-k) Q_{2\ell-5}(k,n) \\ &= \frac{i 2^\ell}{(2\ell-2)!} \left( \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} n^{2\ell-2h-3} \sum_{k=1}^{i-1} k^{2h+1} + (-1)^{\ell-1} \sum_{k=1}^{i-1} k^{2\ell-2} \right) \\ &\quad - \frac{2^\ell}{(2\ell-2)!} \left( \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} n^{2\ell-2h-3} \sum_{k=1}^{i-1} k^{2h+2} + (-1)^{\ell-1} \sum_{k=1}^{i-1} k^{2\ell-1} \right) \\ &\quad + 2 \sum_{k=1}^{i-1} (i-k) Q_{2\ell-4}(k,n). \end{aligned} $$

Using relation (39), we obtain

$$ \sum_{k=1}^{i-1} (i-k) Q_{2\ell-4}(k,n) = i \sum_{k=1}^{i-1} Q_{2\ell-4}(k,n) - \sum_{k=1}^{i-1} k Q_{2\ell-4}(k,n) = Q_{2\ell-2}(i,n). $$

This leads to

$$ \begin{aligned} 2 \sum_{k=1}^{i-1} (i-k) u_k^{(\ell-1)}(n) = \frac{2^\ell}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} n^{2\ell-2h-3} \left( i \sum_{k=1}^{i-1} k^{2h+1} - \sum_{k=1}^{i-1} k^{2h+2} \right) \\ + \frac{2^\ell}{(2\ell-2)!} (-1)^{\ell-1} \left( i \sum_{k=1}^{i-1} k^{2\ell-2} - \sum_{k=1}^{i-1} k^{2\ell-1} \right) + Q_{2\ell-2}(i,n). \end{aligned} $$
Using again relation (39), we have

$$
\begin{align*}
2 \sum_{k=1}^{i-1} (i-k) v_k^{(\ell-1)}(n) &= \frac{2^\ell}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{2h+1} n^{2\ell-2h-3} \left( \frac{i^{2h+3}}{(2h+2)(2h+3)} + \Theta_{2h+1}(i) \right) \\
&\quad + \frac{2^\ell}{(2\ell-2)!} (-1)^{\ell-1} \left( \frac{i^{2\ell}}{(2\ell-1)2\ell} + \Theta_{2\ell-2}(i) \right) + Q_{2\ell-2}(i,n) \\
&= \frac{2^\ell}{(2\ell-2)!} \sum_{h=0}^{\ell-2} \binom{2\ell-2}{2h} \frac{(-1)^h G_{\ell-1-h}}{(2h+1)(2h+2)(2h+3)} i^{2h+3} n^{2\ell-2h-3} \\
&\quad + \frac{2^\ell}{(2\ell)!} (-1)^{\ell-1} i^{2\ell} + Q_{2\ell-2}(i,n).
\end{align*}
$$

Writing, as previously,

$$
\binom{2\ell-2}{2h} \frac{(2\ell-1)2\ell}{(2h+1)(2h+2)} = \frac{(2\ell)!}{(2h+2)!(2\ell-2-2h)!} = \binom{2\ell}{2h+2}
$$

we obtain

$$
\begin{align}
2 \sum_{k=1}^{i-1} (i-k) v_k^{(\ell-1)}(n) &= \frac{2^\ell}{(2\ell)!} \left( \sum_{h=0}^{\ell-2} \binom{2\ell}{2h+2} \frac{(-1)^h G_{\ell-1-h}}{2h+3} i^{2h+3} n^{2\ell-2h-3} + (-1)^{\ell-1} i^{2\ell} \right) + Q_{2\ell-2}(i,n) \nonumber \\
&= \frac{2^\ell}{(2\ell)!} \left( \sum_{h=1}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^{h-1} G_{\ell-h}}{2h+1} i^{2h+1} n^{2\ell-2h-1} + (-1)^{\ell-1} i^{2\ell} \right) + Q_{2\ell-2}(i,n). \tag{41}
\end{align}
$$

Putting together terms (40) and (41), we get

$$
\begin{align*}
v_i^{(\ell)}(n) &= \frac{2i}{n} \sum_{k=1}^{n-1} (n-k) v_k^{(\ell-1)} - 2 \sum_{k=1}^{i-1} (i-k) v_k^{(\ell-1)} \\
&= \frac{2^\ell G_\ell}{(2\ell)!} i n^{2\ell-1} - \frac{2^\ell}{(2\ell)!} \left( \sum_{h=1}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^{h-1} G_{\ell-h}}{2h+1} i^{2h+1} n^{2\ell-2h-1} + (-1)^{\ell-1} i^{2\ell} \right) + Q_{2\ell-2}(i,n) \\
&= \frac{i 2^\ell}{(2\ell)!} G_\ell n^{2\ell-1} + \frac{i 2^\ell}{(2\ell)!} \left( \sum_{h=1}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^h G_{\ell-h}}{2h+1} i^{2h} n^{2\ell-2h-1} + (-1)^{\ell-1} i^{2\ell-1} \right) + Q_{2\ell-2}(i,n) \\
&= \frac{i 2^\ell}{(2\ell)!} \left( \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^h G_{\ell-h}}{2h+1} i^{2h} n^{2\ell-2h-1} + (-1)^{\ell-1} i^{2\ell-1} \right) + Q_{2\ell-2}(i,n).
\end{align*}
$$

The rest of the proof is based on relation (31).

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

This new result together with the following one will be used in the next section for the asymptotic
analysis. The following result gives an expression of both quantities $v_i^{(\ell)}(n)$ and $\mathbb{E}_i(T_{\{0,n\}}^r)$ in terms of the
Euler polynomials. These expressions will be useful for the asymptotic analysis.

**Corollary 13** For every $n \ge 2$, for every $r, \ell \ge 1$ and $i \in \{1, \dots, n-1\}$, we have

$$
v_i^{(\ell)}(n) = \frac{(-1)^{\ell} 2^{\ell} n^{2\ell} E_{2\ell}(i/n)}{(2\ell)!} + Q_{2\ell-2}(i,n)
$$

and

$$
\mathbb{E}_i \left( T_{\{0,n\}}^r \right) = \sum_{\ell=1}^{r} c_{r,\ell} \frac{(-1)^{\ell} 2^{\ell} n^{2\ell} E_{2\ell}(i/n)}{(2\ell)!} + Q_{2r-2}(i,n),
$$

where $Q_m(i, n)$ is a degree $m$ polynomial in the two variables $i$ and $n$, with $Q_0(i, n) = 0$.
**Proof.** It is easy to check, using their definitions, that the Euler and Genocchi polynomials are related by

$$E_n(x) = \frac{G_{n+1}(x)}{n+1}.$$

Using this relation and relation (36), we obtain

$$E_n(x) = \frac{1}{n+1} \sum_{k=0}^{n+1} \binom{n+1}{k} g_k x^{n+1-k}.$$

Since $g_0 = 0$, $g_1 = 1$ and $g_{2k+1} = 0$, for $k \ge 1$, we get

$$E_{2n}(x) = \frac{1}{2n+1} \sum_{k=0}^{2n+1} \binom{2n+1}{k} g_k x^{2n+1-k} = x^{2n} + \frac{1}{2n+1} \sum_{k=1}^{n} \binom{2n+1}{2k} g_{2k} x^{2n-2k+1}.$$

Moreover, since the Genocchi numbers we use, are given by $G_k = (-1)^k g_{2k}$, this yields

$$E_{2n}(x) = x^{2n} + \frac{1}{2n+1} \sum_{k=1}^{n} \binom{2n+1}{2k} (-1)^k G_k x^{2n-2k+1}.$$

The variable change $k := n - k$ leads to

$$E_{2n}(x) = x^{2n} + \frac{1}{2n+1} \sum_{k=0}^{n-1} \binom{2n+1}{2n-2k} (-1)^{n-k} G_{n-k} x^{2k+1}.$$

Observing that

$$\frac{1}{2n+1} \binom{2n+1}{2n-2k} = \binom{2n}{2k} \frac{1}{2k+1}$$

we obtain

$$E_{2n}(x) = x^{2n} + \sum_{k=0}^{n-1} \binom{2n}{2k} \frac{(-1)^{n-k} G_{n-k}}{2k+1} x^{2k+1}. \qquad (42)$$

From Theorem 12, we have

$$v_i^{(\ell)}(n) = \frac{(-1)^{\ell} 2^{\ell} n^{2\ell}}{(2\ell)!} \left( \sum_{h=0}^{\ell-1} \binom{2\ell}{2h} \frac{(-1)^{\ell-h}}{2h+1} G_{\ell-h} \left( \frac{i}{n} \right)^{2h+1} + \left( \frac{i}{n} \right)^{2\ell} \right) + Q_{2\ell-2}(i, n) \\ = \frac{(-1)^{\ell} 2^{\ell} n^{2\ell} E_{2\ell}(i/n)}{(2\ell)!} + Q_{2\ell-2}(i, n),$$

It follows easily, from relation (31), that

$$\mathbb{E}_i \left( T_{\{0,n\}}^r \right) = \sum_{\ell=1}^{r} \frac{c_{r,\ell} (-1)^{\ell} 2^{\ell} n^{2\ell} E_{2\ell}(i/n)}{(2\ell)!} + Q_{2r-2}(i, n),$$

which completes the proof.

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

## 4.3 A second conjecture

We now propose another conjecture giving an explicit expression of the quantities

$$v_i^{(\ell)}(n) = ((I - Q)^{-\ell} 1)_i$$
which leads, if true, to an explicit expression for all the moments $\mathbb{E}_i(T_{\{0,n\}}^r)$.

**Conjecture 2.** For every $n \ge 2$, $\ell \ge 1$ and $i \in \{1, \dots, n-1\}$, we have

$$v_i^{(\ell)}(n) = \frac{i2^\ell}{(2\ell)!} \sum_{j=1}^{\ell} t(\ell-1, \ell-j) \left( \sum_{h=0}^{j-1} \binom{2j}{2h} \frac{(-1)^h G_{j-h}}{2h+1} i^{2h} n^{2j-2h-1} + (-1)^j i^{2j-1} \right). \quad (43)$$

Using relation (42), with $x = i/n$, this conjecture can also be written as

$$v_i^{(\ell)}(n) = \frac{2^\ell}{(2\ell)!} \sum_{j=1}^{\ell} t(\ell-1, \ell-j) (-1)^j n^{2j} E_{2j}(i/n).$$

**Motivation.** This conjecture is motivated by the fact that it is true for every $n \ge 2$, $i \in \{1, \dots, n-1\}$ and $\ell = 1, 2, 3, 4$. Indeed, for these first four values of $\ell$, both relations (34) and (43) give the same result. ■

If this conjecture is correct, we have the following explicit expression for all the $r$ order moments of $T_{\{0,n\}}$, using relation (31),

$$\begin{align*}
\mathbb{E}_i (T_{\{0,n\}}^r) &= \sum_{\ell=1}^r c_{r,\ell} \frac{i2^\ell}{(2\ell)!} \sum_{j=1}^\ell t(\ell-1, \ell-j) \left( \sum_{h=0}^{j-1} \binom{2j}{2h} \frac{(-1)^h G_{j-h}}{2h+1} i^{2h} n^{2j-2h-1} + (-1)^j i^{2j-1} \right) \\
&= \sum_{\ell=1}^r \frac{c_{r,\ell} 2^\ell}{(2\ell)!} \sum_{j=1}^\ell t(\ell-1, \ell-j) (-1)^j n^{2j} E_{2j}(i/n) \\
&= \sum_{j=1}^r (-1)^j n^{2j} E_{2j}(i/n) \sum_{\ell=j}^r \frac{c_{r,\ell} 2^\ell}{(2\ell)!} t(\ell-1, \ell-j).
\end{align*}$$

This relation yields the same results as those obtained in (35).

We are now in position to analyze the asymptotic behavior of the moments of the hitting times $T_{\{0,n\}}$.

## 4.4 Asymptotic moments of $T_{\{0,n\}}$

The following corollary gives the asymptotic behavior of the $r$ order moments when the initial state $i$ is fixed.

**Corollary 14** For every $r$, $\ell \ge 1$ and $i \ge 1$, we have

$$v_i^{(\ell)}(n) \underset{n \to \infty}{\sim} \frac{i G_{\ell} 2^{\ell}}{(2\ell)!} n^{2\ell-1} \quad \text{and} \quad \mathbb{E}_i (T_{\{0,n\}}^r) \underset{n \to \infty}{\sim} \frac{i r! G_r 2^r}{(2r)!} n^{2r-1},$$

where $G_h$ is the $(h+1)$th Genocchi number defined in (37).

**Proof.** The greatest power of $n$ in the expression of $v_i^{(\ell)}(n)$ in Theorem 12 is $n^{2\ell-1}$. We thus only consider the index $h = 0$ in this expression in order to get an equivalent of $v_i^{(\ell)}(n)$.

In the same way, the greatest power of $n$ in the expression of $\mathbb{E}_i(T_{\{0,n\}}^r)$ in Theorem 12 is $n^{2r-1}$. We thus only consider the indices $\ell = r$ and $h = 0$ in this expression in order to get an equivalent of $\mathbb{E}_i(T_{\{0,n\}}^r)$. Since $c_{r,r} = r!$, we obtained the desired result. ■

**Remark 15** This result is consistent with the conjecture proposed in (43). Observe that, from Theorem 10, the random variable $T_0$ is a.s. finite and that all its moments are infinite, from Corollary 14.
We consider now the case where the initial state $i = an$, with $a \in (0, 1)$, that is when the initial state is linear with $n$. We have the following asymptotic result.

**Theorem 16** For every $r \ge 1$ and $a \in (0, 1)$, we have

$$ \lim_{n \to \infty} \mathbb{E}_{an} \left( \left[ \frac{T_{\{0,n\}}}{n^2} \right]^r \right) = \frac{r! (-1)^r 2^r E_{2r}(a)}{(2r)!} $$

and for all $t \ge 0$,

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

**Proof.** Denoting by $Q_{2r-2}(n)$ a degree $2r-2$ polynomial in the variable $n$, with $Q_0(n) = 0$ and taking $i = an$ in Corollary 13, yields

$$ \mathbb{E}_{an} \left( T_{\{0,n\}}^r \right) = \sum_{\ell=1}^{r} \frac{c_{r,\ell} (-1)^{\ell} 2^{\ell} n^{2\ell} E_{2\ell}(a)}{(2\ell)!} + Q_{2r-2}(n), $$

Recalling that $c_{r,r} = r!$, we obtain

$$ \mathbb{E}_{an} \left( T_{\{0,n\}}^r \right) \underset{n \to \infty}{\sim} \frac{r! (-1)^r 2^r n^{2r} E_{2r}(a)}{(2r)!} $$

or equivalently

$$ \lim_{n \to \infty} \mathbb{E}_{an} \left( \left[ \frac{T_{\{0,n\}}}{n^2} \right]^r \right) = \frac{r! (-1)^r 2^r E_{2r}(a)}{(2r)!}. $$

Now consider the sequence of reals numbers $w_r$ defined by this limit, that is

$$ w_r = \frac{r! (-1)^r 2^r E_{2r}(a)}{(2r)!}. $$

It is shown in [1] pages 804 and 805 that for all $x$, $E_{2r}(x) = E_{2r}(1-x)$ and that

$$ 0 < (-1)^r E_{2r}(x) < \frac{|E_{2r}|}{4^r}, \text{ for } r \ge 1 \text{ and } x \in (0, 1/2). $$

The relation $E_{2r}(x) = E_{2r}(1-x)$ imply that the previous inequalities are also true for $x \in (1/2, 1)$. Moreover [15] tells us that $E_{2r}(1/2) = (-1)^r |E_{2r}|/4^r$. It follows that we have

$$ 0 < (-1)^r E_{2r}(x) \le \frac{|E_{2r}|}{4^r}, \text{ for } r \ge 1 \text{ and } x \in (0, 1). \quad (44) $$

We thus have, using relation (44)

$$ 0 < w_r \le s_r, \quad \text{where} \quad s_r = \frac{r!|E_{2r}|}{(2r)!2^r}. $$

It is easily checked, as we did in the proof of Corollary 7, that Carleman's condition (19) is satisfied, which means there is a unique measure with its moments given by $w_r$. Using again relation (20), we obtain

$$ w_r = \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi a)}{2k+1} \frac{r!}{\lambda_k^r}, \quad \text{where} \quad \lambda_k = \frac{(2k+1)^2 \pi^2}{2}. $$
Observing that $r!/\lambda_k^r$ is the r-th order moment of the exponential distribution with rate $\lambda_k$, we obtain that the unique probability measure is given by the density

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

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

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

which completes the proof.

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

In particular, when $i = n/2$ which means that $a = 1/2$ we obtain

$$\lim_{n \to \infty} \mathbb{E}_{n/2} \left( \left[ \frac{T_{\{0,n\}}}{n^2} \right]^r \right) = \frac{r! |E_{2r}|}{(2r)! 2^r}$$

and for all $t \ge 0$,

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

We focus now on the moments and distribution of the cover time of the path graph. We show in the following section that they can be expressed as functions of the moments and distributions of the hitting times $T_n$ and $T_{\{0,n\}}$.

# 5 Cover times

Recall that the state space of the path graph is $S = \{0, 1, \dots, n\}$ and that $C$ denotes the cover time of the path graph. If $A$ is a non empty subset of $S$, we denoted by $C_A$ the cover time of subset $A$. We thus have $C = C_S$. As we did for the hitting time, when the set $A$ is reduced to a single state, say $j$, we write $C_j$ instead of $C_{\{j\}}$. The symmetry of the transition probabilities of the path graph together with the fact that $C_j = T_j$ allows us to write, for every $r \ge 0$,

$$\mathbb{E}_0(C^r) = \mathbb{E}_0(C_n^r) = \mathbb{E}_0(T_n^r) = \mathbb{E}_n(T_0^r) = \mathbb{E}_n(C_0^r) = \mathbb{E}_n(C^r). \quad (45)$$

Note also that the linearity of the path graph implies that its cover time is equal to the time to reach both states 0 and $n$. More precisely, we have

$$C = C_{\{0,n\}}.$$

## 5.1 Moments analysis of $C$

The expected cover time of the path graph is well-known. The following theorem deals with all the moments of any order.

**Theorem 17** For every $i = 0, \dots, n$ and $r \ge 1$, we have

$$\mathbb{E}_i(C^r) = \sum_{m=0}^{r} \binom{r}{m} \mathbb{E}_0(T_n^m) \mathbb{E}_i(T_{\{0,n\}}^{r-m}). \quad (46)$$
**Proof.** For $i=0$ and $i=n$ relation (45) gives

$$ \mathbb{E}_0(C^r) = \mathbb{E}_n(C^r) = \mathbb{E}_0(T_n^r). $$

We suppose now that $i \in \{1, \dots, n-1\}$. For every $r \ge 1$, we have using relation (7),

$$ \begin{aligned} \mathbb{E}_i(C^r) = \mathbb{E}_i(C_{\{0,n\}}^r) = \mathbb{E}_i(T_{\{0,n\}}^r) &+ \sum_{m=1}^r \binom{r}{m} \mathbb{E}_0(C_n^m) \mathbb{E}_i(T_{\{0,n\}}^{r-m} 1_{\{X_{T_{\{0,n\}}} = 0\}}) \\ &+ \sum_{m=1}^r \binom{r}{m} \mathbb{E}_n(C_0^m) \mathbb{E}_i(T_{\{0,n\}}^{r-m} 1_{\{X_{T_{\{0,n\}}} = n\}}). \end{aligned} $$

Using again relation (45), we obtain

$$ \mathbb{E}_i(C^r) = \mathbb{E}_i(T_{\{0,n\}}^r) + \sum_{m=1}^r \binom{r}{m} \mathbb{E}_0(T_n^m) \mathbb{E}_i(T_{\{0,n\}}^{r-m}), $$

which completes the proof.

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

From Theorem 17, using relations (9) and (10) for the computation of $\mathbb{E}_0(T_n^m)$ and relations (31) and (32) for the computation of $\mathbb{E}_i(T_{\{0,n\}}^{r-m})$, we easily obtain all the $r$ order moments of $C$. Moreover, if Conjectures (17) and (43) are true, we obtain a closed form expression of all the $r$ order moments of $C$.

The first moments of $C$ given that the initial state is $i \in \{0, \dots, n\}$ are

$$ \mathbb{E}_i(C) = n^2 + in - i^2 $$

$$ \mathbb{E}_i(C^2) = \frac{1}{3} [5n^4 + 7in^3 - 6i^2n^2 - 2i^3n + i^4] - \frac{2}{3} [n^2 + in - i^2] $$

$$ \begin{aligned} \mathbb{E}_i(C^3) = & \frac{1}{15} [61n^6 + 93in^5 - 75i^2n^4 - 35i^3n^3 + 15i^4n^2 + 3i^5n - i^6] \\ & - \frac{2}{3} [5n^4 + 7in^3 - 6i^2n^2 - 2i^3n + i^4] + \frac{4}{15} [n^2 + in - i^2] \end{aligned} $$

$$ \begin{aligned} \mathbb{E}_i(C^4) = & \frac{1}{105} [1385n^8 + 2159in^7 - 1708i^2n^6 - 868i^3n^5 + 350i^4n^4 + 98i^5n^3 - 28i^6n^2 - 4i^7n + i^8] \\ & - \frac{4}{15} [61n^6 + 93in^5 - 75i^2n^4 - 35i^3n^3 + 15i^4n^2 + 3i^5n - i^6] \\ & + \frac{4}{5} [5n^4 + 7in^3 - 6i^2n^2 - 2i^3n + i^4] + \frac{8}{105} [n^2 + in - i^2]. \end{aligned} $$

## 5.2 Distribution of $C$

The distribution of the cover time $C$ is obtained using relation (6). In the following theorem we obtain an expression of the distribution of $C$ as a function of the distributions of $T_n$ and $T_{\{0,n\}}$.

**Theorem 18** For every $k \ge 0$, $i \in \{0, \dots, n\}$ we have

$$ \mathbb{P}_i\{C = k\} = \sum_{h=1}^{k} \mathbb{P}_i\{T_{\{0,n\}} = h\} \mathbb{P}_0\{T_n = k - h\}. $$

**Proof.** Using relation (6) with $A = \{0, n\}$ and using the fact that $C = C_{\{0,n\}}$, we have for $k \ge 0$,

$$ \mathbb{P}_i\{C = k\} = \mathbb{P}_i\{C_{\{0,n\}} = k\} = \sum_{h=1}^{k} (P_{A^c}^{h-1} P_{A^c, A})_{i,0} \mathbb{P}_0\{C_n = k-h\} + \sum_{h=1}^{k} (P_{A^c}^{h-1} P_{A^c, A})_{i,n} \mathbb{P}_n\{C_0 = k-h\}. $$
The symmetry of the path graph imply that

$$ \mathbb{P}_n\{C_0 = k - h\} = \mathbb{P}_0\{C_n = k - h\} = \mathbb{P}_0\{T_n = k - h\}. $$

This leads to

$$ \mathbb{P}_i\{C = k\} = \sum_{h=1}^{k} [(P_{A^c}^{h-1} P_{A^c,A})_{i,0} + (P_{A^c}^{h-1} P_{A^c,A})_{i,n}] \mathbb{P}_0\{T_n = k - h\}. $$

Moreover, since $A^c = \{1, \dots, n-1\}$, we have $P_{A^c} = Q$ and relation (22) gives

$$ (P_{A^c}^{h-1} P_{A^c,A})_{i,0} + (P_{A^c}^{h-1} P_{A^c,A})_{i,n} = \frac{1}{2} (Q^{h-1})_{i,1} + \frac{1}{2} (Q^{h-1})_{i,n-1} = \mathbb{P}_i\{T_{\{0,n\}} = h\}. $$

Finally, we have

$$ \mathbb{P}_i\{C = k\} = \sum_{h=1}^{k} \mathbb{P}_i\{T_{\{0,n\}} = h\} \mathbb{P}_0\{T_n = k - h\}, $$

which completes the proof.

Observe that $\mathbb{P}_i\{C = 0\} = 0$ for every $i \in \{0, \dots, n\}$ and that $\mathbb{P}_n\{C = k\} = \mathbb{P}_0\{C = k\} = \mathbb{P}_0\{T_n = k\}$, which is due to the fact that $\mathbb{P}_0\{T_{\{0,n\}} = 0\} = \mathbb{P}_n\{T_{\{0,n\}} = 0\} = 1$.

Observe also that the distribution of C can also be obtained, for every $i = 1, \dots, n-1$, by the following recursion.

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

the initial and final values being $\mathbb{P}_0\{C = k\} = \mathbb{P}_n\{C = k\} = \mathbb{P}_0\{T_n = k\}$.

## 5.3 Asymptotic moments and distribution of C

We consider in this section the asymptotic behavior of the moments and distribution of C in two different cases. The first one consists in assuming that the initial state i has a fixed value and the second one deals with an initial state i which is linear with n.

**Theorem 19** For every $r \ge 1$, for a fixed initial state $i \ge 0$ and for all $t \ge 0$, we have

$$ \lim_{n \to \infty} \mathbb{E}_i \left( \left[ \frac{C}{n^2} \right]^r \right) = \frac{2^r r! |E_{2r}|}{(2r)!} \quad \text{and} \quad \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{C}{n^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}{8}. $$

**Proof.** By taking the limit when $n$ goes to infinity in relation (46), we obtain

$$ \lim_{n \to \infty} \mathbb{E}_i \left( \left[ \frac{C}{n^2} \right]^r \right) = \sum_{m=0}^{r} \binom{r}{m} \left[ \lim_{n \to \infty} \mathbb{E}_0 \left( \left[ \frac{T_n}{n^2} \right]^m \right) \right] \left[ \lim_{n \to \infty} \mathbb{E}_i \left( \left[ \frac{T_{\{0,n\}}}{n^2} \right]^{r-m} \right) \right]. $$

From Corollary 14 we have, for every $h \ge 1$,

$$ \lim_{n \to \infty} \mathbb{E}_i \left( \left[ \frac{T_{\{0,n\}}}{n^2} \right]^h \right) = 0. $$

It follows, from relation (18) that

$$ \lim_{n \to \infty} \mathbb{E}_i \left( \left[ \frac{C}{n^2} \right]^r \right) = \lim_{n \to \infty} \mathbb{E}_0 \left( \left[ \frac{T_n}{n^2} \right]^r \right) = \frac{2^r r! |E_{2r}|}{(2r)!}. $$
We thus get the same result we got in Corollary 5 that is, for all $t \ge 0$, for a fixed value of the initial state $i \ge 0$,

$$ \lim_{n \to \infty} \mathbb{P}_i \left\{ \frac{C}{n^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}{8}, $$

which completes the proof.

We consider now the case where the initial state $i$ is linear with $n$.

**Theorem 20** For every $r \ge 1$ when the initial state is $i = an$ with $a \in (0, 1)$, we have

$$ \lim_{n \to \infty} \mathbb{E}_{an} \left( \left[ \frac{C}{n^2} \right]^r \right) = \frac{(-1)^r r! 2^r}{(2r)!} \sum_{m=0}^{r} \binom{2r}{2m} E_{2m} E_{2(r-m)}(a). $$

and

$$ \lim_{n \to \infty} \mathbb{P}_{an} \left\{ \frac{C}{n^2} > t \right\} = \int_t^\infty f(x) dx = \frac{4}{\pi} \sum_{\ell=0}^\infty \frac{(-1)^\ell}{2\ell+1} \frac{4}{\pi} \sum_{k=0}^\infty \frac{\sin((2k+1)\pi a)}{2k+1} \left( \frac{4\lambda_k e^{-\lambda_\ell t} - \lambda_\ell e^{-4\lambda_k t}}{4\lambda_k - \lambda_\ell} \right), $$

where, for every $j \ge 0$,

$$ \lambda_j = \frac{(2j+1)^2 \pi^2}{8}. $$

**Proof.** By taking the limit when $n$ goes to infinity in relation (46) with $i = an$, we obtain

$$ \lim_{n \to \infty} \mathbb{E}_{an} \left( \left[ \frac{C}{n^2} \right]^r \right) = \sum_{m=0}^{r} \binom{r}{m} \left[ \lim_{n \to \infty} \mathbb{E}_0 \left( \left[ \frac{T_n}{n^2} \right]^m \right) \right] \left[ \lim_{n \to \infty} \mathbb{E}_{an} \left( \left[ \frac{T_{\{0,n\}}}{n^2} \right]^{r-m} \right) \right]. $$

It follows, from relation (18) and Theorem 16 that

$$ \begin{aligned} \lim_{n \to \infty} \mathbb{E}_{an} \left( \left[ \frac{C}{n^2} \right]^r \right) &= \sum_{m=0}^{r} \binom{r}{m} \frac{2^m m! (-1)^m E_{2m}}{(2m)!} \frac{2^{r-m} (r-m)! (-1)^{r-m} E_{2(r-m)}(a)}{(2(r-m))!} \\ &= \frac{(-1)^r r! 2^r}{(2r)!} \sum_{m=0}^{r} \binom{2r}{2m} E_{2m} E_{2(r-m)}(a), \end{aligned} $$

which completes the first part of the proof. In order to deal with the second part, we denote by $w_r$ the sequence of limiting moments of $C/n^2$ with initial state $i = an$, when $n$ tends to infinity, that is

$$ w_r = \frac{(-1)^r r! 2^r}{(2r)!} \sum_{m=0}^{r} \binom{2r}{2m} E_{2m} E_{2(r-m)}(a) = \frac{r! 2^r}{(2r)!} \sum_{m=0}^{r} \binom{2r}{2m} (-1)^m E_{2m} (-1)^{r-m} E_{2(r-m)}(a). $$

Using the inequalities (44) and the fact that $(-1)^m E_{2m} > 0$, we obtain

$$ 0 < w_r \le \frac{r! 2^r}{(2r)!} \sum_{m=0}^{r} \binom{2r}{2m} (-1)^m E_{2m} \frac{(-1)^{r-m} E_{2(r-m)}}{4^{r-m}}. $$

Using twice the following inequality of [1] page 805,

$$ (-1)^m E_{2m} \le \frac{4^{m+1} (2m)!}{\pi^{2m+1}}, $$

we get

$$ 0 < w_r \le \frac{r! 2^r}{(2r)!} \sum_{m=0}^{r} \binom{2r}{2m} \frac{4^{m+1} (2m)!}{\pi^{2m+1}} \frac{4^{r-m+1} (2(r-m))!}{\pi^{2(r-m)+1} 4^{r-m}} = \frac{16r! 2^r}{\pi^{2r+2}} \sum_{m=0}^{r} 4^m \le \frac{64r! 8^r}{3\pi^{2r+2}} \le \frac{64r!}{\pi^2}. $$
If $s_r$ denotes the sequence defined by $s_r = 64r! / \pi^2$, we have $0 < w_r \le s_r$. Using the well-known Stirling formula

$$r! \underset{r \to \infty}{\sim} \frac{r^r \sqrt{2\pi r}}{e^r}$$

we get

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

which means that $\sum_{r=1}^{\infty} s_r^{-1/2r} = +\infty$. Since $w_r^{-1/2r} \ge s_r^{-1/2r}$ we also have $\sum_{r=1}^{\infty} w_r^{-1/2r} = +\infty$ and thus the Carleman's condition (19) is satisfied. It follows that there is a unique probability measure $\mu$ associated with the asymptotic moments given by the sequence $w_r$, that is such that for any $r$,

$$w_r = \int_0^\infty t^r d\mu(t).$$

In order to determine $\mu$ we use the expansion of the Euler polynomials in Fourier series as shown in (20) to get another expression of the moments $w_r$. Using the equality $E_{2m} = 4^m E_{2m}(1/2)$, which can be found in [15], we have

$$w_r = \frac{r! 2^r}{(2r)!} \sum_{m=0}^{r} \binom{2r}{2m} 4^m (-1)^m E_{2m}(1/2) (-1)^{r-m} E_{2(r-m)}(a).$$

Using now twice relation (20) with $x = 1/2$ and $x = a$, we obtain

$$\begin{aligned}
w_r &= \frac{r! 2^r}{(2r)!} \sum_{m=0}^{r} \binom{2r}{2m} 4^m \frac{4(2m)!}{\pi^{2m+1}} \left( \sum_{\ell=0}^{\infty} \frac{(-1)^\ell}{(2\ell+1)^{2m+1}} \right) \frac{4(2(r-m))!}{\pi^{2(r-m)+1}} \left( \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi a)}{(2k+1)^{2(r-m)+1}} \right) \\
&= r! 2^r \sum_{m=0}^{r} \binom{4^m}{2m} \frac{4}{\pi^{2m+1}} \left( \sum_{\ell=0}^{\infty} \frac{(-1)^\ell}{(2\ell+1)^{2m+1}} \right) \frac{4}{\pi^{2(r-m)+1}} \left( \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi a)}{(2k+1)^{2(r-m)+1}} \right) \\
&= \sum_{m=0}^{r} \binom{r}{m} \frac{8^m m!}{\pi^{2m}} \left( \frac{4}{\pi} \sum_{\ell=0}^{\infty} \frac{(-1)^\ell}{(2\ell+1)^{2m+1}} \right) \frac{2^{r-m}(r-m)!}{\pi^{2(r-m)}} \left( \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi a)}{(2k+1)^{2(r-m)+1}} \right) \\
&= \sum_{m=0}^{r} \binom{r}{m} \left( \frac{4}{\pi} \sum_{\ell=0}^{\infty} \frac{(-1)^\ell}{2\ell+1} \frac{m!}{\lambda_\ell^m} \right) \left( \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi a)}{2k+1} \frac{(r-m)!}{(4\lambda_k)^{r-m}} \right),
\end{aligned}$$

where, for every $j \ge 0$,

$$\lambda_j = \frac{(2j+1)^2 \pi^2}{8}.$$

The moments $w_r$ can then be written as

$$w_r = \frac{4}{\pi} \sum_{\ell=0}^{\infty} \frac{(-1)^\ell}{2\ell+1} \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi a)}{2k+1} \sum_{m=0}^{r} \binom{r}{m} \frac{m!}{\lambda_\ell^m} \frac{(r-m)!}{(4\lambda_k)^{r-m}}.$$

If $Y_\ell$ and $Z_k$ are two independent random variables exponentially distributed with respective rates $\lambda_\ell$ and $4\lambda_k$, we have

$$\mathbb{E}((Y_{\ell} + Z_{k})^{r}) = \sum_{m=0}^{r} \binom{r}{m} \frac{m!}{\lambda_{\ell}^{m}} \frac{(r-m)!}{(4\lambda_{k})^{r-m}},$$

that is

$$w_r = \frac{4}{\pi} \sum_{\ell=0}^{\infty} \frac{(-1)^\ell}{2\ell+1} \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi a)}{2k+1} \mathbb{E}((Y_\ell + Z_k)^r).$$
Observing that there is no pair $(\ell, k)$ such that $\lambda_\ell = 4\lambda_k$, the density $h_{\ell,k}$ of $Y_\ell + Z_k$ is given by

$$h_{\ell,k}(t) = \frac{4\lambda_{\ell}\lambda_{k}(e^{-\lambda_{\ell}t} - e^{-4\lambda_{k}t})}{4\lambda_{k} - \lambda_{\ell}}.$$

The unique probability measure $\mu$ is then given by the density

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

Using the Fréchet-Shohat Theorem, see [14] or [25], we obtain

$$\lim_{n \to \infty} \mathbb{P}_{an} \left\{ \frac{C}{n^2} > t \right\} = \int_t^\infty f(x) dx = \frac{4}{\pi} \sum_{\ell=0}^{\infty} \frac{(-1)^{\ell}}{2\ell+1} \frac{4}{\pi} \sum_{k=0}^{\infty} \frac{\sin((2k+1)\pi a)}{2k+1} \left( \frac{4\lambda_k e^{-\lambda_\ell t} - \lambda_\ell e^{-4\lambda_k t}}{4\lambda_k - \lambda_\ell} \right),$$

which completes the proof. ■

# 6 Conclusion

We considered in this paper both the distribution and the moments of the hitting times and cover times on the path graph. We obtained recurrence relations for all order moments and we used these relations to analyze the asymptotic behavior of the hitting times and cover times distributions when $n$ tends to infinity. We observed that these random variables divided by their expectations converge in distribution. An extension of this work will be to consider more general path graphs which will not exhibit the same symmetry properties. Further research will consist in analyzing more general graphs to see if this convergence still occurs. A first step will be to analyze other particular graphs such as the barbell graph obtained by connecting two copies of a complete graph by a bridge or the tadpole graph obtained by joining a cycle graph to a path graph.

# 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] C. Banderier and R. P. Dobrow. A generalized cover time for random walk on graphs. In *12th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC)*, Moscow, Russia, Berlin, June 2000. Springer Verlag.

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

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

[7] D. Callan. A recursive bijective approach to counting permutations containing 3-letter patterns, 2002.
[8] F. Castella and B. Sericola. Hitting times on the lollipop graph. Technical report, Centre Inria de l'université de Rennes, December 2024. To appear in Probability in the Engineering and Informational Sciences.

[9] J. Cigler. Fibonacci polynomials, generalized Stirling numbers, and Bernoulli, Genocchi and tangent numbers, 2011.

[10] P. G. Doyle and J. L. Snell. *Random Walks and Electrical Networks*. The carus mathematical monographs. 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(4):433–438, 1995.

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

[13] W. Feller. *An introduction to probability theory and its applications*, volume I. John Wiley and Sons Inc., New York, 1951.

[14] 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):533–543, 1931. https://www.jstor.org/stable/1989421.

[15] M. Hoffman. Derivative polynomials, euler polynomials, and associated integer sequences. *Electronic Journal of Combinatorics*, 6(1), May 1999.

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

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

[18] T. Kim. Euler Numbers and Polynomials Associated with Zeta Functions. *Abstract and Applied Analysis*, 2008(none):581–582, 2008.

[19] D. E. Knuth. Johann Faulhaber and sums of powers. *Mathematics of Computation*, 61(203):277–294, 1993.

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

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

[22] J. Riordan. *Combinatorial Identities*. Wiley, New York, 1968.

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

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

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