, ,

# Analytical results for the distribution of first hitting times of random
walks on random regular graphs

Ido Tishby, Ofer Biham and Eytan Katzav  Racah Institute of Physics, The
Hebrew University, Jerusalem 9190401, Israel<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We present analytical results for the distribution of first hitting times of
random walks (RWs) on random regular graphs (RRGs) of degree $c\geq 3$ and a
finite size $N$. Starting from a random initial node at time $t=1$, at each
time step $t\geq 2$ an RW hops randomly into one of the $c$ neighbors of its
previous node. In some of the time steps the RW may hop into a yet-unvisited
node while in other time steps it may revisit a node that has already been
visited before. The first time at which the RW enters a node that has already
been visited before is called the first hitting time or the first intersection
length. The first hitting event may take place either by backtracking (BT) to
the previous node or by retracing (RET), namely stepping into a node which has
been visited two or more time steps earlier. We calculate the tail
distribution $P(T_{\rm FH}>t)$ of first hitting (FH) times as well as its mean
$\langle T_{\rm FH}\rangle$ and variance ${\rm Var}(T_{\rm FH})$. We also
calculate the probabilities $P_{\rm BT}$ and $P_{\rm RET}$ that the first
hitting event will occur via the backtracking scenario or via the retracing
scenario, respectively. We show that in dilute networks the dominant first
hitting scenario is backtracking while in dense networks the dominant scenario
is retracing and calculate the conditional distributions $P(T_{\rm FH}=t|{\rm
BT})$ and $P(T_{\rm FH}=t|{\rm RET})$, for the two scenarios. The analytical
results are in excellent agreement with the results obtained from computer
simulations. Considering the first hitting event as a termination mechanism of
the RW trajectories, these results provide useful insight into the general
problem of survival analysis and the statistics of mortality rates when two or
more termination scenarios coexist.

Keywords: Random network, random regular graph, random walk, backtracking,
retracing, first hitting time, first intersection length.

##  1 Introduction

Random walk (RW) models [1, 2] are useful for the study of a large variety of
stochastic processes such as diffusion [3, 4], polymer structure [6, 5, 7],
and random search [8, 9]. These models were studied extensively in different
geometries, including continuous space [10], regular lattices [11], fractals
[12] and random networks [13]. In the context of complex networks [14, 15],
random walks provide useful tools for the analysis of dynamical processes such
as the spreading of rumours, opinions and infections [16, 17].

Consider an RW on a random network. Starting at time $t=1$ from a random
initial node $x_{1}$, at each time step $t\geq 2$ it hops randomly to one of
the neighbors of the previous node. The RW thus generates a trajectory of the
form $x_{1}\rightarrow x_{2}\rightarrow\dots\rightarrow
x_{t}\rightarrow\dots$, where $x_{t}$ is the node visited at time $t$. In some
of the time steps the RW hops into nodes that have not been visited before,
while in other time steps it hops into nodes that have already been visited at
an earlier time. Since RWs on random networks may visit some of the nodes more
than once, the number of distinct nodes visited up to time $t$ cannot exceed
$t$ and is typically smaller than $t$. The mean number $\langle S\rangle_{t}$
of distinct nodes visited by an RW on a random network up to time $t$ was
recently studied [18]. It was found that in the infinite network limit it
scales linearly with $t$, namely $\langle S\rangle_{t}\simeq rt$, where the
coefficient $r<1$ depends on the network topology. These scaling properties
resemble those obtained for RWs on high dimensional lattices and Cayley trees
and imply that RWs on random networks revisit previously visited nodes less
frequently than RWs on low dimensional lattices [19]. Therefore, RW models
provide a highly effective framework for search and exploration processes on
random networks.

The early stages of an RW trajectory can be characterized by the distribution
of first hitting (FH) times $P(T_{\rm FH}=t)$, where $T_{\rm FH}$ is the first
time at which the RW steps into a node which has already been visited before.
The first hitting time is also known as the first intersection length [20,
21]. The first hitting event may occur either via the backtracking scenario,
in which the RW hops back into the previous node, or by the retracing
scenario, in which it hops into a node visited two or more time steps earlier.
The first hitting event marks the transition from the first stage to the
second stage in the life cycle of an RW. In the first stage the RW visits a
new node at each time step, while in the second stage it combines moves at
which the RW visits new nodes and moves at which it enters nodes that have
already been visited before. The second stage in the life cycle of an RW on a
finite network can be characterized by the distribution of first passage (FP)
times $P(T_{\rm FP}=t)$, where $T_{\rm FP}$ is the first time at which an RW
starting from a random initial node $i$ visits a random target node $j$ [22,
23]. Finally, the cover time, at which the RW completes visiting all the $N$
nodes in the network at least once marks the transition from the second stage
to the third stage in the life cycle of an RW [24]. Beyond the cover time the
RW continues to revisit nodes that have already been visited before.

Another type of random walk model is the non-backtracking random walk (NBW).
At each time step the NBW steps into a random neighbor of the present node,
except for the node visited in the previous time step. It is thus similar to
the RW, except for the backtracking step which is eliminated. The paths of
NBWs have been studied on regular lattices and random graphs [25]. It was
shown that they explore the network more efficiently than RWs. It was also
shown that they mix faster, namely require a shorter transient time to reach
the stationary distribution of visiting frequencies throughout the network.

In a recent paper we presented analytical results for the distribution of
first hitting times of RWs on Erdős-Rényi (ER) networks [26]. It was found
that the tail distribution of first hitting times, $P(T_{\rm FH}>t)$, consists
of a product of a geometric distribution due to the backtracking process and a
Rayleigh distribution due to the retracing process. The mean and variance of
the distribution of first hitting times were also calculated. In this analysis
we utilized a special property of RWs on ER networks, in which the subnetwork
that consists of the yet-unvisited nodes remains an ER network at all times.
Its degree distribution remains a Poisson distribution, while its mean degree
decreases linearly with the time $t$. This self-similarity enabled us to
calculate the probability that at time $t$ the RW will step into a yet-
unvisited node and the complementary probability that it will step into an
already visited node. In the case of other configuration model networks, there
is no closed form expression for the time evolution of the degree distribution
of the sub-network of the yet-unvisited nodes. Therefore, the approach we used
for the calculation of the distribution of first hitting times in ER networks
cannot be generalized to other configuration model networks. However, it turns
out that in the special case of random regular graphs there are other
simplifying features that can be used to derive a closed form expression for
$P(T_{\rm FH}>t)$.

In another recent paper we studied the distribution of first hitting times of
NBWs on ER networks [27]. Apart from the retracing scenario, NBWs on ER
networks exhibit an additional mechanism of first hitting, referred to as the
trapping scenario. The trapping takes place when the NBW enters a leaf node of
degree $k=1$, which has no other neighbor except from the previous node. It
was found that the tail distribution of first hitting times of NBWs on ER
networks consists of a product of a geometric distribution due to the trapping
process and a Rayleigh distribution due to the retracing process. The mean and
variance of the distribution of first hitting times were also calculated.

In this paper we present analytical results for the distributions of first
hitting times of random walks on random regular graphs (RRGs) of degree $c\geq
3$ and a finite size $N$. The first hitting event may take place either by
backtracking to the previous node or by retracing, namely stepping into a node
which has been visited two or more time steps earlier. Using the
microstructure and statistical properties of RW paths at early times, we
calculate the tail distribution of first hitting (FH) times $P(T_{\rm FH}>t)$,
which is given by a product of a geometric distribution due to the
backtracking process and a Rayleigh distribution due to the retracing process.
We also obtain closed form expressions for the mean first hitting time
$\langle T_{\rm FH}\rangle$ and for the variance ${\rm Var}(T_{\rm FH})$ of
the distribution of first hitting times. The analytical results are found to
be in excellent agreement with the results obtained from computer simulations.
We obtain analytical results for the probabilities $P_{\rm BT}$ and $P_{\rm
RET}$ that the first hitting event will occur via the backtracking or
retracing scenarios, respectively. We show that in dilute networks the
dominant first hitting scenario is backtracking while in dense networks the
dominant scenario is retracing. We also obtain expressions for the conditional
distributions of first hitting time, $P(T_{\rm FH}=t|{\rm BT})$ and $P(T_{\rm
FH}=t|{\rm RET})$, namely conditioned on the first hitting event occurring via
the backtracking or the retracing scenario, respectively.

The paper is organized as follows. In Sec. 2 we briefly describe the random
regular graph. In Sec. 3 we present the random walk model. In Sec. 4 we
calculate the distribution of first hitting times. In Sec. 5 we calculate the
mean first hitting time. In Sec. 6 we calculate the variance of the
distribution of first hitting times. In Sec. 7 we analyze the interplay
between the backtracking and retracing scenarios. In Sec. 8 we compare the
results presented in this paper for RWs on RRGs with previous results for RWs
on ER networks. The results are discussed in Sec. 9 and summarized in Sec. 10.

##  2 The random regular graph

A random network (or graph) consists of a set of $N$ nodes that are connected
by edges in a way that is determined by some random process. For example, in a
configuration model network the degree of each node is drawn independently
from a given degree distribution $P(k)$ and the connections are random and
uncorrelated [30].

An important example of a configuration model network is the Erdős-Rényi (ER)
network [31, 32, 33]. The ER network, denoted by $ER(N,p)$, consists of $N$
nodes such that each pair of nodes is connected with probability $p$. The
degree distribution of an ER network is a binomial distribution, $B(N,p)$. In
the limit $N\rightarrow\infty$ and $p\rightarrow 0$, where the mean degree
$c=(N-1)p$ is held fixed, it converges to a Poisson distribution. In the
asymptotic limit ($N\rightarrow\infty$), the ER network exhibits a phase
transition at $c=1$ (a percolation transition), such that for $c<1$ the
network consists only of small clusters and isolated nodes, while for $c>1$
there is a giant cluster which includes a macroscopic fraction of the network,
in addition to the small clusters and isolated nodes [28, 29]. At a higher
value of the connectivity, namely at $c=\ln N$, there is a second transition,
above which the entire network is included in the giant cluster and there are
no isolated components.

The RRG is a special case of a configuration model network, in which the
degree distribution is a degenerate distribution of the form
$P(k)=\delta_{k,c}$, namely all the nodes are of the same degree $c$. Here we
focus on the case of $3\leq c\leq N-1$, in which for a sufficiently large
value of $N$ the RRG consists of a single connected component. In the infinite
network limit the RRG exhibits a tree structure with no cycles. Thus, in this
limit it coincides with a Bethe lattice whose coordination number is equal to
$c$. In contrast, RRGs of a finite size exhibit a local tree-like structure,
while at larger scales there is a broad spectrum of cycle lengths [34]. In
that sense RRGs differ from Cayley trees, which maintain their tree structure
by reducing the most peripheral nodes to leaf nodes of degree $1$.

A convenient way to construct an RRG of size $N$ and degree $c$ is to prepare
the $N$ nodes such that each node is connected to $c$ half edges or stubs
[15]. At each step of the construction, one connects a random pair of stubs
that belong to two different nodes $i$ and $j$ that are not already connected,
forming an edge between them. This procedure is repeated until all the stubs
are exhausted. The process may get stuck before completion in case that all
the remaining stubs belong to the same node or to pairs of nodes that are
already connected. In such case one needs to perform some random reconnections
in order to complete the construction.

RRGs provide a useful benchmark for the study of dynamical processes on
regular lattices. This is due to the fact that for any regular lattice
structure in any space dimension, one can construct an RRG whose degree $c$ is
equal to the coordination number $z$ of the regular lattice. For example, a
simple cubic lattice in a $d$ dimensional space corresponds to an RRG with
degree $c=2d$. Some special cases in two dimensions include the honeycomb
lattice that corresponds to an RRG with $c=3$ and the triangular lattice that
corresponds to an RRG with $c=6$. However, all the other structural properties
of RRGs are completely different from those of the corresponding regular
lattice. Therefore, comparing the behavior of dynamical processes taking place
on regular lattices and on the corresponding RRGs, one can distinguish between
the properties that depend on the coordination number and those that depend on
other structural properties such as the lengths of short cycles. A famous
example is the Bethe-Peierls approximation of the Ising model [35], which is
actually an exact result on an RRG with the same coordination number as a
$d$-dimensional lattice. In $2$ dimensions the critical exponents are wrongly
identified as the mean-field ones, but the actual predictions for the critical
temperature and the heat capacity are highly insightful. In dimensions higher
than $4$, even the critical exponents are correct.

##  3 The random walk model

Consider an RW on an RRG of degree $c\geq 3$ and size $N$. At each time step
the RW hops from its current node to one of its neighbors, such that the
probability of hopping to each neighbor is $1/c$. For sufficiently large $N$
the RRG consists of a single connected component, thus an RW starting from any
initial node can reach any other node in the network. In the long time limit
$t\gg N$ the RW visits all the nodes with the same frequency, namely on
average each node is visited once every $N$ steps. However, over shorter
periods of time there may be large fluctuations such that some nodes may be
visited several times in a given time interval while other nodes are not
visited at all.

In some of the time steps an RW may visit nodes that have not been visited
before while in other time steps it may revisit nodes that have already been
visited before. For example, at each time step $t\geq 3$ the RW may backtrack
into the previous node with probability of $1/c$. In the infinite network
limit the RRG exhibits a tree structure. Therefore, in this limit the
backtracking mechanism is the only way in which an RW may hop from a newly
visited node to a node that has already been visited before. However, in
finite networks the RW may utilize the cycles to retrace its path and hop into
nodes that have already been visited two or more time steps earlier. Once the
RW stepped into a node that has been visited before, it may continue to hop
back and forth along the path of its previously visited nodes, until it
eventually leaves the path and enters a newly visited node.

In Fig. 1 we present a schematic illustration of the backtracking and the
retracing events which may take place along the path of an RW on an RRG. While
backtracking is independent on the network size, retracing takes place only in
finite networks and is not possible in the infinite network limit, in which
the RRG exhibits a tree structure.

Figure 1:  Schematic illustrations of possible events taking place along the
path of an RW on an RRG: (a) a path segment in which at each time step the RW
enters a node that has not been visited before; (b) a path segment that
includes a backtracking step into the previous node (step no. 4); (c) a path
that includes a retracing step (step no. 5) in which the RW hops into a node
that was visited a few time steps earlier. Retracing steps are not possible in
the infinite network limit and take place only in finite networks, which
include cycles. Note that in this illustration the RRG is of degree $c=4$.

##  4 The distribution of first hitting times

Consider an RW on an RRG of a finite size $N$ and degree $c\geq 3$. Starting
from a random node at time $t=1$, the RW hops randomly between nearest
neighbor nodes. At early times $t\ll N$ all the nodes it enters are likely to
be visited for the first time. The first time at which the RW enters a node
that has already been visited before is called the first hitting time. The
first hitting process may take place either by backtracking (BT) or by
retracing (RET). In the backtracking scenario the RW moves back into the
previous node, while in the retracing scenario it hops into a node that has
already been visited two or more time steps earlier. Below we calculate the
distribution of first hitting times. In case that the RW has not returned to
any previously visited node up to time $t-1$, the first hitting time satisfies
the condition $T_{\rm FH}>t-1$. Given that $T_{\rm FH}>t-1$, the probability
that the first hitting event will not take place in the next time step is
expressed by the conditional probability $P(T_{\rm FH}>t|T_{\rm FH}>t-1)$.
This conditional probability can be expressed as a product of the form

$P(T_{\rm FH}>t|T_{\rm FH}>t-1)=P_{t}(\lnot{\rm RET}|\lnot{\rm
BT})P_{t}(\lnot{\rm BT}),$ (1)

where $P_{t}(\lnot{\rm BT})$ is the probability that the RW will not backtrack
to the previous node at time $t$. Given that the RW has not backtracked at
time $t$, the conditional probability $P_{t}(\lnot{\rm RET}|\lnot{\rm BT})$ is
the probability that it will also not retrace its path at time $t$, namely,
that it will not hop into a node that has already been visited two or more
time steps earlier.

Since all the nodes in the RRG are of degree $c$, at each time step (apart
from $t=1$ and $2$) the probability of backtracking into the previous node is
$1/c$. Therefore, the probability that a backtracking step will not occur at
any given time $t\geq 3$ is

$P_{t}(\lnot{\rm BT})=1-\frac{1}{c}.$ (2)

Provided that the RW has not backtracked at time $t$, we will now evaluate the
probability $P_{t}(\lnot{\rm RET}|\lnot{\rm BT})$ that it will also not
retrace its path. Apart from the current node at time $t-1$ and the previous
node (visited at time $t-2$), there are $N-2$ other nodes in the network, of
which $t-3$ have already been visited by the RW.

Since the network is undirected, an edge connecting a pair of nodes $i$ and
$j$ can be considered as a combination of two links, one from $i$ to $j$ and
the other from $j$ to $i$. Thus, a node of degree $c$ is connected to $c$
incoming links and $c$ outgoing links. The number of yet-unvisited nodes at
time $t-1$ is $N-t+1$. Each one of these nodes is of degree $c$.

Since at each time step the RW enters a node via one edge and leaves it via
another edge, up to time $t-1$ it exhausts $t-2$ edges along the path. Thus,
each one of the nodes visited in the first $t-3$ time steps exhibits only
$c-2$ links that can be used by the RW to enter the node via the retracing
mechanism at time $t$ (apart from the initial node that can be reached via
$c-1$ edges). As a result, the number of incoming links that may lead the RW
to an already visited node via the retracing mechanism at time $t$ is

$L_{\rm v}=(c-2)(t-3)+1.$ (3)

The number of incoming links that may lead the RW to a yet-unvisited node at
time $t$ is

$L_{\rm u}=(N-t+1)c.$ (4)

Summing up $L_{\rm v}$ and $L_{\rm u}$ we obtain the total number of incoming
links that may lead the RW at time $t$ to either a visited node (by retracing)
or to a yet-unvisited node. It is given by

$L_{\rm T}=(N-2)c-2(t-3)+1.$ (5)

Given that the possibility of backtracking into the previous node was
eliminated, the RW selects randomly one of the $c-1$ other neighbors of the
current node. The probability that any one of these neighbors has already been
visited before is thus given by $L_{\rm v}/L_{\rm T}$. Therefore, the
probability of retracing at time $t$ under the condition of no-backtracking is
given by

$P_{t}({\rm RET}|\lnot{\rm BT})=\frac{L_{\rm v}}{L_{\rm
T}}=\frac{(c-2)(t-3)+1}{(N-2)c-2(t-3)+1}.$ (6)

In Fig. 2 we present analytical results, obtained from Eq. (6), for the
probability $P_{t}({\rm RET}|\lnot{\rm BT})$ that an RW on an RRG will retrace
its path for the first time at time $t$ under the condition that it has not
backtracked its path at time $t$ (or earlier). The RRGs used in Fig. 2 are of
size $N=1000$, where the nodes are of degree $c=3$ (solid line), $5$ (dashed
line) and $10$ (dotted line). The analytical results are in excellent
agreement with the results obtained from computer simulations (circles). These
results are qualitatively different from the corresponding results for RWs on
ER networks, which are given by [26]

$P_{t}^{\rm ER}({\rm RET}|\lnot{\rm BT})=\frac{c(t-3)}{(c+1)(N-1)},$ (7)

where $c$ is the mean degree.

Figure 2:  Analytical results for the probability $P_{t}({\rm RET}|\lnot{\rm
BT})$ that an RW will retrace its path at time $t$ under the condition that it
has not backtracked its path at time $t$, on an RRG of size $N=1000$ and $c=3$
(solid line), $5$ (dashed line) and $10$ (dotted line). The analytical
results, obtained from Eq. (6), are in excellent agreement with the results
obtained from computer simulations (circles).

Using Eq. (6), the probability that the RW will not retrace its path at time
$t\geq 3$ is given by

$P_{t}(\lnot{\rm RET}|\lnot{\rm BT})=1-\frac{(c-2)(t-3)+1}{(N-2)c-2(t-3)+1}.$
(8)

Inserting the probabilities $P_{t}(\lnot{\rm BT})$ and $P_{t}(\lnot{\rm
RET}|\lnot{\rm BT})$ from Eqs. (2) and (8), respectively, into Eq. (1), we
obtain

$P(T_{\rm FH}>t|T_{\rm
FH}>t-1)=\left(1-\frac{1}{c}\right)\left[1-\frac{(c-2)(t-3)+1}{(N-2)c-2(t-3)+1}\right].$
(9)

Focusing on large networks, where $N\gg 1$, and assuming that $t\ll Nc$, the
probability $P_{t}(\lnot{\rm RET}|\lnot{\rm BT})$ can be written as a series
expansion in powers of $(t-3)/(Nc)$. It is given by

$P_{t}(\lnot{\rm RET}|\lnot{\rm
BT})=1-\frac{(c-2)(t-3)}{Nc}-\frac{2(c-2)(t-3)^{2}}{(Nc)^{2}}+\mathcal{O}\left[\left(\frac{t-3}{Nc}\right)^{3}\right].$
(10)

Using the expansion $\ln(1-x)=-x-x^{2}/2+\mathcal{O}(x^{3})$ for $x\ll 1$, we
obtain

$\displaystyle\ln\left[P_{t}(\lnot{\rm RET}|\lnot{\rm BT})\right]$
$\displaystyle\simeq$
$\displaystyle-\frac{(c-2)(t-3)}{Nc}-\frac{2(c-2)(t-3)^{2}}{(Nc)^{2}}$ (11)
$\displaystyle-$
$\displaystyle\frac{1}{2}\left[\frac{(c-2)(t-3)}{Nc}+\frac{2(c-2)(t-3)^{2}}{(Nc)^{2}}\right]^{2}.$

Rearranging terms up to second order in $(t-3)/(Nc)$, we obtain

$P_{t}(\lnot{\rm RET}|\lnot{\rm
BT})\simeq\exp\left[-\frac{(c-2)(t-3)}{Nc}-\frac{(c-2)(c+2)(t-3)^{2}}{2(Nc)^{2}}\right].$
(12)

As a result, Eq. (9) is replaced by

$P(T_{\rm FH}>t|T_{\rm
FH}>t-1)\simeq\left(1-\frac{1}{c}\right)\exp\left[-\frac{(c-2)(t-3)}{Nc}-\frac{(c-2)(c+2)(t-3)^{2}}{2(Nc)^{2}}\right],$
(13)

where $t\geq 3$.

The probability $P(T_{\rm FH}>t)$ that the first hitting event will not take
place during the first $t$ time steps is given by the product

$P(T_{\rm FH}>t)=\prod_{t^{\prime}=3}^{t}P(T_{\rm FH}>t^{\prime}|T_{\rm
FH}>t^{\prime}-1).$ (14)

Inserting $P(T_{\rm FH}>t^{\prime}|T_{\rm FH}>t^{\prime}-1)$ from Eq. (13)
into Eq. (14), we obtain the tail distribution of first hitting times

$P(T_{\rm FH}>t)=P_{\rm BT}(T_{\rm FH}>t)P_{\rm RET}(T_{\rm FH}>t),$ (15)

where

$P_{\rm BT}(T_{\rm FH}>t)=\left\\{\begin{array}[]{ll}1&\ \ \ \ \ \ \ t=1,2\\\
\left(1-\frac{1}{c}\right)^{t-2}&\ \ \ \ \ \ \ t\geq 3,\end{array}\right.$
(16)

and

$P_{\rm RET}(T_{\rm FH}>t)\simeq\left\\{\begin{array}[]{ll}1&\ \ \ \ \ \ \
1\leq t\leq 3\\\
\prod_{t^{\prime}=3}^{t}\exp\left[-\frac{(c-2)(t^{\prime}-3)}{Nc}-\frac{(c-2)(c+2)(t^{\prime}-3)^{2}}{2(Nc)^{2}}\right]&\
\ \ \ \ \ \ t\geq 4.\end{array}\right.$ (17)

Note that the contribution of the backtracking process, given by Eq. (16),
depends only on the mean degree $c$, while the contribution of the retracing
process, given by Eq. (17) depends on the mean degree $c$ and on the network
size $N$. In the infinite network limit the retracing scenario becomes
irrelevant and Eq. (15) is simplified to

$P(T_{\rm FH}>t|N\rightarrow\infty)=\left\\{\begin{array}[]{ll}1&\ \ \ \ \ \ \
t=1,2\\\ \left(1-\frac{1}{c}\right)^{t-2}&\ \ \ \ \ \ \ t\geq
3.\end{array}\right.$ (18)

Taking the logarithm of $P_{\rm RET}(T_{\rm FH}>t)$, as expressed in Eq. (17)
for $t\geq 4$, we obtain

$\ln[P_{\rm RET}(T_{\rm
FH}>t)]\simeq-\sum_{t^{\prime}=3}^{t}\frac{(c-2)(t^{\prime}-3)}{Nc}-\sum_{t^{\prime}=3}^{t}\frac{(c-2)(c+2)(t^{\prime}-3)^{2}}{2(Nc)^{2}}.$
(19)

Carrying out the summations in Eq. (19), we obtain

$\ln\left[P_{\rm RET}(T_{\rm
FH}>t)\right]\simeq-\frac{(c-2)(t-2)(t-3)}{2Nc}-\frac{(c-2)(c+2)(t-2)(t-3)(t-5/2)}{6(Nc)^{2}}.$
(20)

Inserting $P_{\rm BT}(T_{\rm FH}>t)$ from Eq. (16) and $P_{\rm RET}(T_{\rm
FH}>t)$ from Eq. (20) into Eq. (15), we obtain

$P(T_{\rm FH}>t)\simeq\left\\{\begin{array}[]{ll}1&\ \ \ \ \ \ \ t=1,2\\\
\exp\left[-\frac{(t-2)(t-3)}{2\alpha^{2}}-\frac{(t-2)(t-3)(t-5/2)}{6\left(\frac{c-2}{c+2}\right)\alpha^{4}}-\beta(t-2)\right]&\
\ \ \ \ \ \ t\geq 3,\end{array}\right.$ (21)

where the parameters $\alpha$ and $\beta$ are given by

$\alpha=\sqrt{\left(\frac{c}{c-2}\right)N},$ (22)

and

$\beta=\ln\left(\frac{c}{c-1}\right).$ (23)

Using a Taylor expansion of the second term in the exponent in Eq. (21), we
obtain

$P(T_{\rm FH}>t)\simeq\left\\{\begin{array}[]{ll}1&\ \ \ \ \ \ \ t=1,2\\\
\left[1-\frac{(t-2)(t-3)(t-5/2)}{6\left(\frac{c-2}{c+2}\right)\alpha^{4}}\right]\exp\left[-\frac{(t-2)(t-3)}{2\alpha^{2}}-\beta(t-2)\right]&\
\ \ \ \ \ \ t\geq 3,\end{array}\right.$ (24)

where the first term in the second line is the leading term and the second
term is a correction term, which is small for sufficiently small values of
$t$.

It turns out that for large networks the second term in the second line of Eq.
(24) is extremely small and its effect on the tail distribution $P(T_{\rm
FH}>t)$ can be neglected in most cases. The only case in which it was found to
make a small but noticeable difference is in the calculation of the second
moment $\langle T_{\rm FH}^{2}\rangle$. For the sake of consistency, we use
Eq. (24) in the calculations of both the mean first hitting time $\langle
T_{\rm FH}\rangle$ and the second moment $\langle T_{\rm FH}^{2}\rangle$. In
all the other calculations presented in this paper we use a simplified form of
the tail distribution, which is given by

$P(T_{\rm FH}>t)\simeq\left\\{\begin{array}[]{ll}1&\ \ \ \ \ \ \ t=1,2\\\
\exp\left[-\frac{(t-2)(t-3)}{2\alpha^{2}}-\beta(t-2)\right]&\ \ \ \ \ \ \
t\geq 3,\end{array}\right.$ (25)

The tail distribution $P(T_{\rm FH}>t)$, given by Eq. (25), is thus a product
of a geometric distribution, associated with the backtracking process and a
Rayleigh distribution, associated with the retracing process [36].

In Fig. 3 we present (on a semi-logarithmic scale) analytical results for the
tail distributions $P(T_{\rm FH}>t)$ of first hitting times (solid lines) of
RWs on RRGs of size $N=1000$ in which the nodes are of degree $c=3$ (left),
$5$ (middle) and $10$ (right). The analytical results, obtained from Eq. (25)
are in excellent agreement with the results obtained from computer simulations
(circles). It is found that as the degree $c$ is increased the first hitting
event tends to occur at a later time. This can be attributed to the fact that
the probability of backtracking decreases as $c$ is increased.

Figure 3:  Analytical results for the tail distributions $P(T_{\rm FH}>t)$ of
first hitting times (solid lines) of RWs on RRGs of size $N=1000$, in which
the nodes are of degree $c=3$ (left), $5$ (middle) and $10$ (right). The
analytical results, obtained from Eq. (25) are in excellent agreement with the
results obtained from computer simulations (circles).

The excellent agreement observed in Fig. 3 between the analytical results and
the results obtained from computer simulations indicates that Eq. (25) is
valid for a broad range of parameters. However, Eq. (25) combines the
backtracking and retracing mechanisms. Thus, for parameters in which the
backtracking mechanism is dominant, Fig. 3 is not sufficient to establish the
validity of the first term in Eq. (25), associated with the retracing
scenario. This is due to the fact that in this regime the retracing process is
effectively screened by the backtracking process.

In order to establish the validity of the retracing term in Eq. (25) we
consider the distribution of first hitting times of NBWs on RRGs. The
suppression of the backtracking process in NBWs leaves the retracing scenario
as the only possible scenario of first hitting in these systems. This is
unlike the case of NBWs on ER networks, in which the trapping scenario emerges
once backtracking is suppressed. This contrast is due to the fact that RRGs do
not include leaf nodes of degree $k=1$, in which an NBW may become trapped.
The suppression of the backtracking mechanism implies that the distribution of
first hitting times of NBWs on RRGs is expressed by the right hand side of Eq.
(25), where $\alpha$ is given by Eq. (22) and $\beta=0$, namely

$P_{\rm NBW}(T_{\rm FH}>t)\simeq\left\\{\begin{array}[]{ll}1&\ \ \ \ \ \ \
t=1,2\\\ \exp\left[-\frac{(t-2)(t-3)}{2\alpha^{2}}\right]&\ \ \ \ \ \ \ t\geq
3.\end{array}\right.$ (26)

In Fig. 4 we present (on a semi-logarithmic scale) analytical results for the
tail distributions $P_{\rm NBW}(T_{\rm FH}>t)$ of first hitting times (solid
lines) of NBWs on RRGs of size $N=1000$ in which the nodes are of degree $c=3$
(left), $5$ (middle) and $10$ (right). The analytical results, obtained from
Eq. (26) are in excellent agreement with the results obtained from computer
simulations (circles).

Figure 4:  Analytical results for the tail distributions $P_{\rm NBW}(T_{\rm
FH}>t)$ of first hitting times (solid lines) of NBWs on RRGs of size $N=1000$,
in which the nodes are of degree $c=3$ (left), $5$ (middle) and $10$ (right).
The analytical results, obtained from Eq. (26) are in excellent agreement with
the results obtained from computer simulations (circles).

##  5 The mean first hitting time

The moments $\langle T_{\rm FH}^{r}\rangle$, $r=1,2,\dots$, of the
distribution of first hitting times of RWs on RRGs can be obtained from the
tail-sum formula [37]

$\langle T_{\rm FH}^{r}\rangle=\sum_{t=0}^{N}[(t+1)^{r}-t^{r}]P(T_{\rm
FH}>t).$ (27)

In particular, the mean first hitting time $\langle T_{\rm FH}\rangle$ can be
obtained by inserting $r=1$ in Eq. (27), which yields

$\langle T_{\rm FH}\rangle=\sum_{t=0}^{N}P(T_{\rm FH}>t).$ (28)

Inserting $P(T_{\rm FH}>t)$ from Eq. (24) into Eq. (28), shifting the
summation index from $t$ to $t-1$, and and replacing the sum in Eq. (28) by a
sum of two integrals, using the formulation of a middle Riemann sum, we obtain

$\langle T_{\rm FH}\rangle\simeq I_{1}+I_{2},$ (29)

where

$I_{1}=3+e^{-\beta}+\int\limits_{3/2}^{N-3/2}\exp\left[-\frac{t(t-1)}{2\alpha^{2}}-\beta
t\right]dt,$ (30)

and

$I_{2}=-\int\limits_{3/2}^{N-3/2}\frac{t(t-1)(t-1/2)}{6\left(\frac{c-2}{c+2}\right)\alpha^{4}}\exp\left[-\frac{t(t-1)}{2\alpha^{2}}-\beta
t\right]dt.$ (31)

Carrying out the integration in Eq. (30), we obtain

$I_{1}\simeq
3+e^{-\beta}+\sqrt{\frac{\pi}{2}}\alpha\exp\left[\frac{\left(2\alpha^{2}\beta-1\right)^{2}}{8\alpha^{2}}\right]\left\\{{\rm
erf}\left[\frac{\alpha(\beta+1-2/c)}{\sqrt{2}}\right]-{\rm
erf}\left(\frac{\alpha^{2}\beta+1}{\sqrt{2}\alpha}\right)\right\\},$ (32)

where ${\rm erf}(x)$ is the error function, also called Gauss error function
[38]. The error function ${\rm erf}(x)$ is a monotonically increasing
function, defined for $-\infty<x<\infty$. It is an odd function, namely ${\rm
erf}(-x)=-{\rm erf}(x)$, and exhibits a sigmoidal shape. For $|x|\ll 1$ it can
be approximated by ${\rm erf}(x)\simeq 2x/\sqrt{\pi}$ while for $|x|>1$ it
quickly converges to ${\rm erf}(x)\rightarrow{\rm sign}(x)$. The parameter
$\beta$ obtains its largest value at $c=3$, where $\beta=\ln(3/2)$, and
decreases monotonically as $c$ is increased. Thus, for any value of $c$ it
satisfies $\beta<1$. In the limit of $c\gg 1$, it can be approximated by

$\beta=\frac{1}{c}+\frac{1}{2c^{2}}+\mathcal{O}\left(\frac{1}{c^{3}}\right).$
(33)

Since the degree $c$ satisfies $c<N-1$, the parameter $\beta$ is bounded from
below by $\beta>1/(N-1)$. In the limit of complete graph it approaches this
lower bound, namely $\beta\rightarrow 1/(N-1)$. The product $\alpha\beta$ thus
takes values in the range $1/\sqrt{N-2}<\alpha\beta\leq\ln(3/2)\sqrt{N-2}$.

Eq. (32) can be written in the form

$\displaystyle I_{1}\simeq 3+e^{-\beta}$ $\displaystyle+$
$\displaystyle\sqrt{\frac{\pi}{2}}\alpha\exp\left({\frac{-\beta}{2}}\right)\exp\left({\frac{1}{8\alpha^{2}}}\right)\exp\left[\left(\frac{\alpha\beta}{\sqrt{2}}\right)^{2}\right]\times$
(34) $\displaystyle\left[{\rm
erf}\left(\frac{\alpha(1-2/c)}{\sqrt{2}}+\frac{\alpha\beta}{\sqrt{2}}\right)-{\rm
erf}\left(\frac{\alpha\beta}{\sqrt{2}}+\frac{1}{\sqrt{2}\alpha}\right)\right].$

In the large network limit, where $N\gg 1$, the term $\exp[1/(8\alpha^{2})]$
satisfies $\exp[1/(8\alpha^{2})]\simeq 1+\mathcal{O}(1/N)$ and thus it can be
neglected. Similarly, in the large network limit the argument of the first
${\rm erf}$ function in Eq. (32) is always very large. Therefore, one can
safely set the first ${\rm erf}$ function to be equal to $1$. The second ${\rm
erf}$ function can be approximated by

${\rm
erf}\left(\frac{\alpha\beta}{\sqrt{2}}+\frac{1}{\sqrt{2}\alpha}\right)\simeq{\rm
erf}\left(\frac{\alpha\beta}{\sqrt{2}}\right)+\frac{\sqrt{2}}{\sqrt{\pi}\alpha}\exp\left[-\left(\frac{\alpha\beta}{\sqrt{2}}\right)^{2}\right]$
(35)

Making these approximations, we obtain

$I_{1}\simeq 3+e^{-\beta}-e^{-\beta/2}+\sqrt{\frac{\pi}{2}}\alpha
e^{\frac{-\beta}{2}}\exp\left[\left(\frac{\alpha\beta}{\sqrt{2}}\right)^{2}\right]\left[1-{\rm
erf}\left(\frac{\alpha\beta}{\sqrt{2}}\right)\right].$ (36)

Carrying out the integration in Eq. (31) and taking the large network limit,
we obtain

$\displaystyle I_{2}$ $\displaystyle\simeq$
$\displaystyle\frac{1}{6}\sqrt{\frac{\pi}{2}}\left(\frac{c+2}{c-2}\right)\alpha\beta\left(\alpha^{2}\beta^{2}+3\right)e^{\frac{\left(1-2\alpha^{2}\beta\right)^{2}}{8\alpha^{2}}}\left[1-\text{erf}\left(\frac{\alpha^{2}\beta+1}{\sqrt{2}\alpha}\right)\right]$
(37) $\displaystyle-$
$\displaystyle\frac{1}{6}\left(\frac{c+2}{c-2}\right)\left(\alpha^{2}\beta^{2}-\beta+2\right)e^{-\frac{3}{8\alpha^{2}}-\frac{3\beta}{2}}.$

In the dilute-network limit, where $3\leq c\ll 1.63\sqrt{N}$, the argument of
the error function in Eq. (36) satisfies the condition
$\alpha\beta/\sqrt{2}\gg 1$. In this limit one can use the approximation [38]

$1-{\rm erf}(x)\simeq\frac{e^{-x^{2}}}{x\sqrt{\pi}},$ (38)

which is the first term in the asymptotic expansion of the complementary error
function, and obtain

$\langle T_{\rm FH}\rangle\simeq c+2+\mathcal{O}\left(\frac{1}{c}\right).$
(39)

This result reflects the fact that in the dilute network limit the first
hitting time is dominated by the backtracking mechanism.

In the dense-network limit, where $1.63\sqrt{N}\ll c\leq N$ the argument of
the error function in Eq. (36) satisfies $\alpha\beta/\sqrt{2}\ll 1$. In this
case, one can use the approximation ${\rm erf}(x)\simeq x$, which is the
leading term in the Taylor expansion of ${\rm erf}(x)$ around $x=0$. Using
this approximation, we obtain

$\langle T_{\rm FH}\rangle\simeq\sqrt{\frac{\pi N}{2}}.$ (40)

In this limit the first hitting time is dominated by the retracing mechanism.

In Fig. 5 we present analytical results for the mean first hitting time
$\langle T_{\rm FH}\rangle$ (solid line) of RWs on RRGs as a function of the
degree $c$. The analytical results, obtained from Eqs. (29), (36) and (37) are
in excellent agreement with the results obtained from computer simulations
(circles). In the dilute-network limit $\langle T_{\rm FH}\rangle$ quickly
increases as $c$ is increased, reaching saturation in the dense-network limit.

Figure 5:  Analytical results for the mean first hitting time $\langle T_{\rm
FH}\rangle$ of RWs on RRGs of size $N=1000$ (solid line), as a function of the
degree $c$. The analytical results, obtained from Eqs. (29), (36) and (37) are
in excellent agreement with the results obtained from computer simulations
(circles).

##  6 The variance of the distribution of first hitting times

Inserting $r=2$ in Eq. (27) we obtain the second moment $\langle T_{\rm
FH}^{2}\rangle$ of the distribution of first hitting times, which is given by

$\langle T_{\rm FH}^{2}\rangle=\sum_{t=0}^{N}(2t+1)P(T_{\rm FH}>t).$ (41)

Inserting the tail distribution $P(T_{\rm FH}>t)$ from Eq. (24) into Eq. (41),
shifting the summation index from $t$ to $t-2$ and replacing the sum by a sum
of two integrals, we obtain

$\langle T_{\rm FH}^{2}\rangle=J_{1}+J_{2},$ (42)

where

$\displaystyle
J_{1}=9+7e^{-\beta}+\int_{3/2}^{N-3/2}(2t+5)\exp\left[-\frac{t(t-1)}{2\alpha^{2}}-\beta
t\right]dt,$ (43)

and

$\displaystyle
J_{2}=-\int_{3/2}^{N-3/2}(2t+5)\frac{t(t-1)(2t-1)}{12\left(\frac{c+2}{c-2}\right)\alpha^{4}}\exp\left[-\frac{t(t-1)}{2\alpha^{2}}-\beta
t\right]dt.$ (44)

Carrying out the integral in Eq. (43) and taking the large network limit, we
obtain

$\displaystyle J_{1}$ $\displaystyle\simeq$ $\displaystyle
9+7e^{-\beta}+2\alpha^{2}\exp\left(-\frac{20\alpha^{2}\beta+15}{8\alpha^{2}}\right)$
(45) $\displaystyle-$
$\displaystyle\alpha\sqrt{2\pi}(\alpha^{2}\beta-3)e^{\frac{(2\alpha^{2}\beta-1)^{2}}{8\alpha^{2}}}\left[1-{\rm
erf}\left(\frac{\alpha^{2}\beta+1}{\sqrt{2}\alpha}\right)\right].$

Carrying out the integration in Eq. (44) and taking the large network limit,
we obtain

$\displaystyle J_{2}$ $\displaystyle\simeq$
$\displaystyle\frac{1}{12}\left(\frac{c+2}{c-2}\right)\left[4\alpha^{4}\beta^{3}-4\alpha^{2}\beta(4\beta-5)+15\beta-36\right]e^{-\frac{3}{8\alpha^{2}}-\frac{3\beta}{2}}$
(46) $\displaystyle-$
$\displaystyle\frac{1}{12}\sqrt{\frac{\pi}{2}}\left(\frac{c+2}{c-2}\right)\alpha\left[4\alpha^{4}\beta^{4}-12\alpha^{2}(\beta-2)\beta^{2}-\beta^{2}-36\beta+12\right]\times$
$\displaystyle\ \ \ \
e^{\frac{\left(1-2\alpha^{2}\beta\right)^{2}}{8\alpha^{2}}}\left[1-\text{erf}\left(\frac{\alpha^{2}\beta+1}{\sqrt{2}\alpha}\right)\right].$

In the limit of dilute networks, where $3\leq c\ll 1.63\sqrt{N}$, the product
$\alpha\beta$ satisfies $\alpha\beta\gg 1$. In this limit the second moment
can be approximated by

$\displaystyle\langle T_{\rm FH}^{2}\rangle$ $\displaystyle\simeq$
$\displaystyle 9+7e^{-\beta}-\sqrt{2\pi}\alpha^{3}\beta
e^{\left(\frac{\alpha\beta}{\sqrt{2}}\right)^{2}}\left[1-{\rm
erf}\left(\frac{\alpha^{2}\beta+1}{\sqrt{2}\alpha}\right)\right]$ (47)
$\displaystyle+$ $\displaystyle 2\alpha^{2}e^{-5\beta/2}.$

In the dense network limit, where $1.63\sqrt{N}\ll c<N$, the parameter $\beta$
satisfies $\beta\simeq 1/c$ and $\alpha\beta\ll 1$. As a result, the error
function on the right hand side of Eq. (45) becomes negligible and the second
moment converges towards

$\langle T_{\rm FH}^{2}\rangle\simeq 2N.$ (48)

The variance of the distribution of first hitting times is given by

${\rm Var}(T_{\rm FH})=\langle T_{\rm FH}^{2}\rangle-\langle T_{\rm
FH}\rangle^{2}.$ (49)

In the dense network limit, the variance converges towards

${\rm Var}(T_{\rm FH})\simeq\left(2-\frac{\pi}{2}\right)N.$ (50)

In Fig. 6 we present analytical results for the variance of the distribution
of first hitting times of RWs on RRGs of size $N=1000$ (solid line), as a
function of the degree $c$. The analytical results, obtained from Eq. (49),
where $\langle T_{\rm FH}^{2}\rangle$ is given by Eqs. (42), (45) and (46) and
$\langle T_{\rm FH}\rangle$ is given by Eqs. (29), (36) and (37), are in
excellent agreement with the results obtained from computer simulations
(circles).

Figure 6:  Analytical results for the variance ${\rm Var}(T_{\rm FH})$ of the
distribution of first hitting times of RWs on RRGs of size $N=1000$ (solid
line), as a function of the degree $c$. The analytical results, obtained from
Eq. (49), are in excellent agreement with the results obtained from computer
simulations (circles).

##  7 Analysis of the backtracking and retracing mechanisms

The first hitting process consists of two competing scenarios, backtracking
and retracing. In each instance of an RW trajectory the first hitting time is
determined by the scenario that occurs first. We denote by $P_{\rm BT}$ the
probability that the first hitting event of an RW starting from a random
initial node will take place by backtracking. Similarly, we denote by $P_{\rm
RET}$ the probability that the first hitting event will take place by
retracing. Since these are the only possible mechanisms of first hitting of
RWs, these two probabilities must satisfy $P_{\rm BT}+P_{\rm RET}=1$. The
conditional probability that the first hitting event will take place at time
$t$, given that it occurs via the backtracking scenario, is denoted by
$P(T_{\rm FH}=t|{\rm BT})$. Similarly, the conditional probability that the
first hitting event will take place at time $t$ given that it occurs via the
retracing scenario is denoted by $P(T_{\rm FH}=t|{\rm RET})$. The overall
distribution of first hitting times can be expressed as a weighted sum of the
two conditional distributions, in the form

$P(T_{\rm FH}=t)=P_{\rm BT}P(T_{\rm FH}=t|{\rm BT})+P_{\rm RET}P(T_{\rm
FH}=t|{\rm RET}).$ (51)

The first term on the right hand side of Eq. (51) can be written in the form

$P_{\rm BT}P(T_{\rm FH}=t|{\rm BT})=P(T_{\rm FH}>t-1)[1-P_{t}(\lnot{\rm
BT})],$ (52)

namely as the probability that the first hitting event will not take place up
to time $t-1$ and will occur at time $t$ due to backtracking. Inserting
$P_{t}(\lnot{\rm BT})$ from Eq. (2) into Eq. (52) and summing up over $t$, it
is found that the overall probability that the first hitting event will take
place via the backtracking scenario is given by

$P_{\rm BT}=\frac{1}{c}\sum_{t=3}^{N+1}P(T_{\rm FH}>t-1).$ (53)

Comparing with the tail-sum formula (28), the probability $P_{\rm BT}$ can be
expressed in terms of the mean first hitting time, namely

$P_{\rm BT}=\frac{\langle T_{\rm FH}\rangle-2}{c}.$ (54)

Thus, the complementary probability that the first hitting will occur via the
retracing mechansim is given by

$P_{\rm RET}=1-\frac{\langle T_{\rm FH}\rangle-2}{c}.$ (55)

Note that Eqs. (54) and (55) are exact. However, inserting $\langle T_{\rm
FH}\rangle$ from Eq. (29) with $I_{1}$ and $I_{2}$ given by Eqs. (36) and
(37), respectively, the results become approximate due to the replacement of
the sum in Eq. (28) by integrals.

In Fig. 7 we present the probability $P_{\rm BT}$ that the first hitting event
will occur via the backtracking scenario and the complementary probability
$P_{\rm RET}$ that it will occur via the retracing scenario, as a function of
the degree $c$. As expected, the probability $P_{\rm BT}$ decreases as $c$ is
increased while the probability $P_{\rm RET}$ increases. The crossover from
the backtracking-dominated regime of dilute networks to the retracing-
dominated regime of dense networks occurs where $P_{\rm BT}=P_{\rm RET}=1/2$.
Using Eqs. (54) and (55) we find that at the crossover point $\langle T_{\rm
FH}\rangle=(c+4)/2$. Comparing the right hand side of Eq. (36) to $(c+4)/2$,
it is found that the crossover point occurs at $c\simeq 1.63\sqrt{N}$.

Figure 7:  Analytical results for the probabilities $P_{\rm BT}$ and $P_{\rm
RET}$ that the first hitting event will occur via the backtracking or the
retracing scenarios, respectively. The analytical results, obtained from Eqs.
(54) and (55), are in excellent agreement with the results obtained from
computer simulations (circles).

In Fig. 8 we present a diagram describing the first hitting process of RWs on
RRGs. In the regime of dilute networks, where $c\lesssim 1.63\sqrt{N}$ the
first hitting process is dominated by backtracking, while in the regime of
dense networks, where $c\gtrsim 1.63\sqrt{N}$ the first hitting process is
dominated by retracing.

Figure 8:  A diagram describing the first hitting process of RWs on RRGs. In
the regime of dilute networks, where $c\lesssim 1.63\sqrt{N}$ the first
hitting process is dominated by backtracking, while in the regime of dense
networks, where $c\gtrsim 1.63\sqrt{N}$ the first hitting process is dominated
by retracing.

The conditional probability $P(T_{\rm FH}=t|{\rm BT})$, for $t\geq 3$, can be
written in the form

$P(T_{\rm FH}=t|{\rm BT})=\frac{P(T_{\rm FH}>t-1)[1-P_{t}(\lnot{\rm
BT})]}{P_{\rm BT}}.$ (56)

Inserting $P_{t}(\lnot{\rm BT})$ from Eq. (2) and $P_{\rm BT}$ from Eq. (54),
we obtain

$P(T_{\rm FH}=t|{\rm BT})=\frac{P(T_{\rm FH}>t-1)}{\langle T_{\rm
FH}\rangle-2}.$ (57)

Focusing on the retracing mechanism, the second term on the right hand side of
Eq. (51) can be expressed in the form

$P_{\rm RET}P(T_{\rm FH}=t|{\rm RET})=P(T_{\rm FH}>t-1)P_{t}(\lnot{\rm
BT})[1-P_{t}(\lnot{\rm RET}|\lnot{\rm BT})].$ (58)

Inserting $P_{t}(\lnot{\rm BT})$ from Eq. (2), $P_{t}(\lnot{\rm RET}|\lnot{\rm
BT})$ from Eq. (8), and $P_{\rm RET}$ from Eq. (55) into Eq. (58), we obtain

$P(T_{\rm FH}=t|{\rm RET})=\left(\frac{c-1}{c-\langle T_{\rm
FH}\rangle+2}\right)\frac{(c-2)(t-3)+1}{(N-2)c-2(t-3)+1}P(T_{\rm FH}>t-1).$
(59)

In Fig. 9 we present the probabilities $P(T_{\rm FH}=t|{\rm BT})$ and
$P(T_{\rm FH}=t|{\rm RET})$ that the first hitting process will take place at
time $t$, under the condition that it occurs via the backtracking and the
retracing scenarios, respectively.

Figure 9:  Analytical results for the distribution $P(T_{\rm FH}=t|{\rm BT})$
and $P(T_{\rm FH}=t|{\rm RET})$ of first hitting times, conditioned on the
first hitting to occur via the backtracking or the retracing scenarios,
respectively. The analytical results, obtained from Eqs. (57) and (59), are in
excellent agreement with the results obtained from computer simulations
(circles).

The mean first hitting time under the condition that the first hitting occurs
via the backtracking scenario is given by

$\mathbb{E}[T_{\rm FH}|{\rm BT}]=\sum_{t=3}^{N+1}tP(T_{\rm FH}=t|{\rm BT}).$
(60)

Inserting $P(T_{\rm FH}=t|{\rm BT})$ from Eq. (57) into Eq. (60), we obtain

$\mathbb{E}[T_{\rm FH}|{\rm BT}]=\frac{1}{\langle T_{\rm
FH}\rangle-2}\sum_{t=3}^{N+1}tP(T_{\rm FH}>t-1)$ (61)

Using the tail-sum formula [37], it is found that

$\mathbb{E}[T_{\rm FH}|{\rm BT}]=\frac{\langle T_{\rm FH}^{2}\rangle+\langle
T_{\rm FH}\rangle-6}{2(\langle T_{\rm FH}\rangle-2)}.$ (62)

The mean first hitting time $\langle T_{\rm FH}\rangle$ can be expressed as a
weighted sum of the form

$\langle T_{\rm FH}\rangle=\mathbb{E}[T_{\rm FH}|{\rm BT}]P_{\rm
BT}+\mathbb{E}[T_{\rm FH}|{\rm RET}]P_{\rm RET}.$ (63)

Inserting $\mathbb{E}[T_{\rm FH}|{\rm BT}]$ from Eq. (62) into Eq. (63) and
solving for $\mathbb{E}[T_{\rm FH}|{\rm RET}]$, we obtain

$\mathbb{E}[T_{\rm FH}|{\rm RET}]=\frac{\langle T_{\rm
FH}^{2}\rangle-(2c-1)\langle T_{\rm FH}\rangle-6}{2(\langle T_{\rm
FH}\rangle-c-2)}.$ (64)

In Fig. 10 we present analytical results for the conditional expectation
values $\mathbb{E}[T_{\rm FH}|{\rm BT}]$ and $\mathbb{E}[T_{\rm FH}|{\rm
RET}]$ of the first hitting time, vs. the degree $c$ given that the first
hitting event occurs via the backtracking or the retracing scenario,
respectively. The analytical results, obtained from Eqs. (62) and (64), are in
excellent agreement with the results obtained from computer simulations
(circles).

Figure 10:  Analytical results for the conditional expectation values
$\mathbb{E}[T_{\rm FH}|{\rm BT}]$ and $\mathbb{E}[T_{\rm FH}|{\rm RET}]$ of
the first hitting time, vs. the degree $c$ given that the first hitting event
occurs via the backtracking or the retracing scenario, respectively. The
analytical results, obtained from Eqs. (62) and (64), are in excellent
agreement with the results obtained from computer simulations (circles).

##  8 Comparing $P(T_{\rm FH}>t)$ between RWs on RRGs and RWs on ER networks

The distribution $P(T_{\rm FH}>t)$ of first hitting times of RWs on RRGs is
given by Eq. (25). It can be expressed as a product of a geometric
distribution, associated with the backtracking process, and a Rayleigh
distribution, associated with the retracing process. The Rayleigh distribution
is parameterized by the parameter $\alpha$, while the geometric distribution
is parameterized by $\beta$. It is interesting to compare the results obtained
above for the distribution $P(T_{\rm FH}>t)$ of RWs on RRGs of size $N$ and
degree $c$ with the corresponding results for RWs on ER networks of the same
size and mean degree $\langle K\rangle=c$ [26]. Another interesting comparison
is between the distributions of first hitting times of NBWs on RRGs and ER
networks. In all these cases, the tail distribution of first hitting times is
described by the same functional form as in Eq. (25), but the expressions for
$\alpha$ and $\beta$ are different. In Table 1 we present a $2\times 2$
diagram that provides the parameters $\alpha$ and $\beta$ for RWs on RRGs
(upper-left cell), NBWs on RRGs (upper-right cell), RWs on ER networks (lower-
left cell) and NBWs on ER networks (lower-right cell).

Table 1: The parameters $\alpha$ and $\beta$ of the distribution $P(T_{\rm FH}>t)$ [Eq. (25)] for RWs and NBWs on RRGs and on ER networks |  RW |  NBW
---|---|---
| $\alpha=\sqrt{\left(\frac{c}{c-2}\right)N}$ | $\alpha=\sqrt{\left(\frac{c}{c-2}\right)N}$
RRG |  |
| $\beta=\ln\left(\frac{c}{c-1}\right)$ | $\beta=0$
| $\alpha=\sqrt{\left(\frac{c+1}{c}\right)N}$ | $\alpha=\sqrt{\left(\frac{c+1}{c}\right)N}$
ER |  |
| $\beta=\ln\left(\frac{c}{c-1+e^{-c}}\right)$ | $\beta=-\ln(1-e^{-c})$

One difference between RRGs and ER networks is that ER networks include
isolated nodes of degree $k=0$. Since an RW starting from an isolated node
cannot make even a single move, the initial node of an RW on an ER network is
chosen randomly from all the nodes of degree $k\geq 1$. Moreover, isolated
nodes are not accessible to the RW at times $t>1$. As a result, for RWs on ER
networks the probability of backtracking at any time $t$ is given by
$P_{t}({\rm BT})=(1-e^{-c})/c$, compared to $1/c$ in the case of RWs on RRGs
[26]. This is reflected in the parameter $\beta$ for RWs on ER networks, which
includes the $e^{-c}$ term.

The effect of the retracing process on the distribution of first hitting times
is described by a Rayleigh distribution parametrized by $\alpha$. In fact, the
probability that at any time $t$ the RW will hop into any one of the nodes
that were previously visited up to time $t-3$ is given by $1/\alpha^{2}$.
Naively, one expects that the probability to enter a specific node at time $t$
is $1/N$. However, each visit of a node exhausts two of its edges, which
cannot be used to revisit the node in the retracing scenario. Therefore, the
probability that at a given time an RW will revisit a specific node that has
already been visited two or more time steps earlier is smaller than $1/N$. In
the case of RWs on RRGs it is given by $(1-2/c)/N$, while in the case of RWs
on ER networks it is given by $[1-1/(c+1)]/N$. These corrections are reflected
in the values of $\alpha$ in Table 1.

In Fig. 11 we compare the analytical results for the distributions $P(T_{\rm
FH}>t)$ of RWs on RRGs (circles) and ER networks ($+$) of size $N=1000$ and
(a) $c=3$ and (b) $c=5$. For $c=3$, where the first hitting process is
dominated by the backtracking scenario, there is a slight difference at short
times due to $e^{-c}$ term in the expression for $\beta$ in the ER network.
For $c=5$ the results obtained for the two networks are found to be similar.
This is due to the fact that as $c$ is increased the $e^{-c}$ term in the
expression for $\beta$ of the ER network becomes negligible and it converges
towards the expression for $\beta$ of the RRG. This convergence occurs within
the dilute network regime, in which the first hitting process is dominated by
backtracking.

Figure 11:  Comparison between the analytical results for the tail
distributions $P(T_{\rm FH}>t)$ of first hitting times of RWs on RRGs
($\circ$) and RWs on ER networks ($+$). The network size is $N=1000$. The
degree is (a) $c=3$ and (b) $c=5$. In both cases, the tail distribution takes
the form of Eq. (25), with the parameters $\alpha$ and $\beta$ given in Table
1. Note that the agreement between the analytical results and computer
simulations was established in Fig. 3 (for RWs on RRGs) and in Ref. [26] (for
RWs on ER networks).

In order to take a closer look at the retracing process, we consider the
distribution of first hitting times in NBWs, in which the backtracking process
is suppressed. In the case of NBWs on RRGs, upon suppression of the
backtracking process, the retracing scenario remains unchanged and the
distribution of first hitting times becomes a Rayleigh distribution. In
contrast, in the case of NBWs on ER networks the suppression of the
backtracking process gives rise to a new mechanism of first hitting, referred
to as the trapping scenario. This scenario occurs when the NBW enters a leaf
node of degree $k=1$. In the following time step it becomes trapped in the
leaf node because the backtracking move into the previous node is not allowed.
The distribution of first hitting times of NBWs on ER networks was studied in
Ref. [27] and the corresponding expressions for $\alpha$ and $\beta$ are shown
in the lower-right cell in Table 1.

In Fig. 12 we present a comparison between analytical results for the
distributions $P_{\rm NBW}(T_{\rm FH}>t)$ of NBWs on RRGs (circles) and ER
networks ($+$) of size $N=1000$ and (a) $c=3$ and (b) $c=5$. The first hitting
times of NBWs on ER networks are found to be much shorter than those obtained
for NBWs on RRGs. This contrast is most pronounced for small values of $c$.
This is due to the emergence of the trapping scenario which is most effective
in the limit of dilute networks.

Figure 12:  Comparison between the analytical results for the tail
distributions $P_{\rm NBW}(T_{\rm FH}>t)$ of first hitting times of NBWs on
RRGs ($\circ$) and NBWs on ER networks ($+$). The network size is of size
$N=1000$. The degree is (a) $c=3$ and (b) $c=5$. In both cases, the tail
distribution takes the form of Eq. (25), with the parameters $\alpha$ and
$\beta$ given in Table 1. Note that the agreement between the analytical
results and computer simulations was established in Fig. 4 (for NBWs on RRGs)
and in Ref. [27] (for NBWs on ER networks).

##  9 Discussion

Beyond the specific problem of first hitting times of RW on networks, the
analysis presented here provides useful insight into the general context of
the distribution of life expectancies of humans, animals and machines [39,
40]. It illustrates the combination of two lethal hazards, where one hits at a
fixed, age-independent rate, while the other increases linearly with age. The
first hazard may be considered as an external cause such as an accident while
the second hazard involves some aging related degradation which results in an
increasing failure rate.

In a more specific context of survival problems, the RW model that terminates
upon its first hitting event can be cast in the language of foraging theory as
a model describing a wild animal, which is randomly foraging in a random
network environment [41]. Each time the animal visits a node it consumes all
the food available in this node and needs to move on to one of the adjacent
nodes. The model describes rather harsh conditions, in which the regeneration
of resources is very slow and the visited nodes do not replenish within the
lifetime of the forager. Moreover, the forager does not carry any reserves and
in order to survive it must hit a vital node at every time step. More
realistic variants of this model have been studied on lattices of different
dimensions. It was shown that under slow regeneration rates, the forager is
still susceptible to starvation, while above some threshold of the
regeneration rate, the probability of starvation diminishes significantly
[41]. The case in which the forager carries sufficient resources that enable
it to avoid starvation even when it visits up to $S$ non-replenished nodes in
a row, was also studied [42, 43].

In the dense network limit the first hitting process is dominated by the
retracing scenario. As a result, the distribution of first hitting times
becomes insensitive to the degree $c$. In this limit the mean first hitting
time scales like $\sqrt{N}$. This can be understood as follows. In this limit,
the backtracking probability is very low and thus the backtracking-induced
first hitting events become negligible. Instead, retracing becomes the
dominant scenario. Due to the very high connectivity, the hopping between
adjacent nodes can be considered as the simple combinatorial problem of
randomly choosing one node at a time from a set of $N$ nodes, allowing each
node to be chosen more than once. In this limit the statistical properties of
first hitting times become analogous to those of the birthday problem [44,
45]. More specifically, in this limit the probability that $P(T_{\rm FH}>t)$
in a network that consists of $N=365$ nodes is equal to the probability that
in a party of $t$ participants there will not be even one pair who share the
same birthday [44].

##  10 Summary

We presented a statistical analysis of the first hitting times of RWs on RRGs,
which may take place either via backtracking or via retracing. The tail
distribution $P(T_{\rm FH}>t)$ of first hitting times was calculated. It can
be expressed as a product of a geometric distribution associated with the
backtracking process and a Rayleigh distribution which is due to the retracing
process. We also obtained closed form expressions for the mean first hitting
time $\langle T_{\rm FH}\rangle$ and for the variance ${\rm Var}(T_{\rm FH})$
of the distribution of first hitting times. The analytical results are found
to be in excellent agreement with the results obtained from computer
simulations. We obtained analytical results for the probabilities $P_{\rm BT}$
and $P_{\rm RET}$ that the first hitting event will occur via the backtracking
or retracing scenarios, respectively. We showed that in dilute networks the
dominant first hitting scenario is backtracking while in dense networks the
dominant scenario is retracing. We also obtained expressions for the
conditional distributions of first hitting time, $P(T_{\rm FH}=t|{\rm BT})$
and $P(T_{\rm FH}=t|{\rm RET})$, in which the first hitting event occurs via
the backtracking or the retracing scenario, respectively. These results
provide useful insight into the general problem of survival analysis and the
statistics of mortality rates when two or more termination scenarios coexist.
We also analyzed the distribution of first hitting times in non-backtracking
random walks (NBWs), in which the backtracking process is suppressed and
compared the results obtained here for RWs and NBWs on RRGs to earlier results
for RWs and NBWs on Erdős-Rényi networks.

This work was supported by the Israel Science Foundation grant no. 1682/18.

## References

## References

  * [1] Spitzer F 1964 Principles of Random Walk (New York: Springer-Verlag)
  * [2] Weiss G H 1994 Aspects and Applications of the Random Walk (New York: North Holland)
  * [3] Berg H C 1993 Random Walks in Biology (Princeton: Princeton University Press)
  * [4] Ibe O C 2013 Elements of Random Walk and Diffusion Processes (New Jersey: Wiley & Sons)
  * [5] Fisher M E 1966 Shape of a self‐avoiding walk or polymer chain J. Chem. Phys. 44 616
  * [6] Edwards S F 1965 The statistical mechanics of polymers with excluded volume, Proceedings of the Physical Society 85 613
  * [7] De Gennes P G 1979 Scaling Concepts in Polymer Physics (Ithaca: Cornell University Press)
  * [8] Evans M R and Majumdar S N 2011 Diffusion with stochastic resetting Phys. Rev. Lett. 106 160601
  * [9] Lopez Millán V M, Cholvi V, Lopez L and Anta A F 2012 A model of self‐avoiding random walks for searching complex networks Networks 60 71
  * [10] Lawler G F 2010 Random Walk and the Heat Equation (Providence: American Mathematical Society)
  * [11] Lawler G F and Limic V 2010 Random Walk: A Modern Introduction (Cambridge: Cambridge University Press)
  * [12] ben-Avraham D and Havlin S 2000 Diffusion and Reactions in Fractals and Disordered Systems (Cambridge: Cambridge University Press)
  * [13] Noh D J and Rieger H 2004 Random walks on complex networks Phys. Rev. Lett. 92 118701
  * [14] Havlin S and Cohen R 2010 Complex Networks: Structure, Robustness and Function (Cambridge University Press, New York)
  * [15] Newman M E J 2018 Networks: an Introduction, 2nd Ed. (Oxford: Oxford University Press)
  * [16] Pastor-Satorras R and Vespignani A 2001 Epidemic spreading in scale-free networks Phys. Rev. Lett. 86 3200
  * [17] Barrat A, Barthélemy M and Vespignani A 2012 Dynamical Processes on Complex Networks (Boston: Cambridge University Press)
  * [18] De Bacco C, Majumdar S N and Sollich P 2015 The average number of distinct sites visited by a random walker on random graphs J. Phys. A 48 205004
  * [19] Montroll E W and Weiss G H 1965 Random Walks on Lattices II J. Math. Phys. 6 167
  * [20] Herrero C P and Saboyá M 2003 Self-avoiding walks and connective constants in small-world networks Phys. Rev. E 68 026106
  * [21] Herrero C P 2005 Kinetic growth walks on complex networks J. Phys. A 38 4349
  * [22] Redner S 2001 A Guide to First Passage Processes (Cambridge: Cambridge University Press)
  * [23] Note that occasionally in the literature the term ”first hitting time” is used as an alternative to the term ”first passage time”.
  * [24] Kahn J D, Linial N, Nisan N and Saks M E 1989 On the cover time of random walks on graphs J. Theor. Probab. 2 121
  * [25] Alon N, Benjamini I, Lubetzky E and Sodin S 2007 Non-backtracking random walks mix faster Commun. Contemp. Math. 9 585
  * [26] Tishby I, Biham O and Katzav E 2017 The distribution of first hitting times of random walks on Erdős-Rényi networks J. Phys. A 50 115001
  * [27] Tishby I, Biham O and Katzav E 2017 The distribution of first hitting times of nonbacktracking random walks on Erdős-Rényi networks J. Phys. A 50 205003
  * [28] Molloy M and Reed A 1995 A critical point for random graphs with a given degree sequence Rand. Struct. Alg. 6 161
  * [29] Molloy M and Reed A 1998 The Size of the Giant Component of a Random Graph with a Given Degree Sequence Combinatorics, Probability and Computing 7 295
  * [30] Newman M E J, Strogatz S H and Watts D J 2001 Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64 026118
  * [31] Erdős P and Rényi A 1959 On random graphs. I Publicationes Mathematicae (Debrecen) 6 290
  * [32] Erdős P and Rényi A 1960 On the evolution of random graphs Publ. Math. Inst. Hung. Acad. Sci. 5 17
  * [33] Erdős P and Rényi A 1961 On the evolution of random graphs. II Bull. Inst. Int. Stat. 38 343
  * [34] Bonneau H, Hassid A, Biham O, Kühn R and Katzav E 2017 Distribution of shortest cycle lengths in random networks Phys. Rev. E 96 062307
  * [35] Pathria R K and Beale P D 2011 Statistical Mechanics 3rd Edition (Amsterdam: Academic Press)
  * [36] Papoulis A, Pillai S and Unnikrishna S 2002 Probability, Random Variables and Stochastic Processes (Boston: McGraw-Hill)
  * [37] Pitman J 1993 Probability (New York: Springer-Verlag)
  * [38] Olver F W J, Lozier D M, Boisvert R R and Clark C W 2010 NIST Handbook of Mathematical Functions (Cambridge: Cambridge University Press)
  * [39] Finkelstein M 2008 Failure Rate Modeling for Reliability and Risk (London: Springer-Verlag)
  * [40] Gavrilov L A and Gavrilova N S 2001 The reliability theory of aging and longevity J. theor. Biol 213 527
  * [41] Chupeau M, Bénichou O and Redner S 2016 Universality classes of foraging with resource renewal Phys. Rev. E 93 032403
  * [42] Bénichou O and Redner S 2014 Depletion-Controlled Starvation of a Diffusing Forager Phys. Rev. Lett 113 238101
  * [43] Bénichou O, Chupeau M and Redner S 2016 Role of depletion on the dynamics of a diffusing forager J. Phys. A 49 394003
  * [44] Knight W and Bloom D M 1973 A birthday problem Amer. Math. Monthly 80 1141
  * [45] Flajolet P, Gardy D and Thimonier L 1992 Birthday paradox, coupon collectors, caching algorithms and self-organizing search Discrete Applied Mathematics 39 207