# The Pólya and Sisyphus lattice random walks with resetting – a first passage
under restart approach

Ofek Lauber Bonomo and Arnab Pal<EMAIL_ADDRESS>School of Chemistry,
Raymond and Beverly Sackler Faculty of Exact Sciences & The Center for Physics
and Chemistry of Living Systems & The Ratner Center for Single Molecule
Science, Tel Aviv University, Tel Aviv 6997801, Israel

###### Abstract

We revisit the simple lattice random walk (Pólya walk) and the Sisyphus random
walk in $\mathbb{Z}$, in the presence of random restarts. We use a relatively
direct approach namely First passage under restart for discrete space and time
which was recently developed by us in PRE 103, 052129 (2021) and rederive the
first passage properties of these walks under the memoryless geometric restart
mechanism. Subsequently, we show how our method could be generalized to
arbitrary first passage process subject to more complex restart mechanisms
such as sharp, Poisson and Zeta distribution where the latter is heavy tailed.
We emphasize that the method is very useful to treat such problems both
analytically and numerically.

##  I Motivation

First passage under restart recently emerged as a useful framework to study
arbitrary stochastic processes under arbitrary restart mechanisms FPUR .
Although the problems with continuous space and time set-ups have been studied
in full glory, their discrete counterparts have been largely overlooked. To
bridge this void, in a recent work RW1 , we developed a First Passage Under
Restart formalism for discrete space and time processes. This comprehensive
framework can be used to derive exact and useful formulae such as the
generating functions for the survival and first passage, the mean first
passage time (and higher order moments) etc. in the presence of arbitrary
restart distributions. The derivation does not assume any specific form for
the underlying first passage process or the restart process, hence can be
ubiquitously used in a generic set-up.

In this note, power of this approach is illustrated using the following
examples: Pólya’s lattice random walk on the integer points of the real line,
and the one sided and double sided Sisyphus random walk in the presence of
geometric restart – a memoryless distribution. These models were studied
earlier and we will refer to these works in proper context. Moving forward, we
show our method could be used to accommodate any first passage process that
maybe subject to more complex restart distributions (and not necessarily
memoryless) namely sharp, Poisson and Zeta. In the conclusions, we sketch out
a three-step blue-print on how to use our recipe in a plug-n-play manner
either analytically or numerically.

##  II Notations

Before we proceed, it will be useful to introduce the notations used
throughout the paper. We will use $P_{X}(x)$, $\langle X\rangle$,
$\sigma_{X}^{2}$, and $G_{X}(z)\equiv\langle z^{X}\rangle$ to denote,
respectively, the probability mass/density function (PMF/PDF),
mean/expectation, variance, and the probability generating function (PGF) of a
discrete random variable $X$ taking values in the non-negative integers. In
addition, the survival function and its corresponding generating function for
the underlying process are denoted by $Q_{N}(n)$ and $G_{Q_{N}}(z)$
respectively. In the presence of restart, generating function for the survival
function will be denoted by $G_{Q_{N_{R}}}(z)$.

##  III Discrete First passage under discrete restart

Consider a generic discrete step first passage process that starts at the
origin and, if allowed to take place without interruptions, ends after a
random number of steps $N$. The process is, however, restarted after some
random number of steps $R$. Thus, $P_{N}(n)$ and $P_{R}(n)$ are the
probability density functions for the first passage and restart process
respectively. If the process is completed only prior to the restart, we mark a
completion of the event. Otherwise, the process will start from scratch and
begin completely anew. This procedure repeats itself until the process reaches
completion. Denoting the random completion number of steps of the restarted
process by $N_{R}$, it can be seen that

$\displaystyle N_{R}=\begin{cases}N&N<R\\\ R+N^{\prime}_{R}&N\geq
R,\end{cases}$ (1)

where $N^{\prime}_{R}$ is an independent and identically distributed copy of
$N_{R}$. Eq. (1) is the central renewal equation for first passage step under
restart and assumes that after each restart, the memory is erased from the
previous trial. To obtain the mean number of steps for the restarted process,
we note that Eq. (1) can be written as
$N_{R}=min\left(N,R\right)+I\left\\{N\geq R\right\\}N^{\prime}_{R}$, where
$I\left\\{N\geq R\right\\}$ is an indicator random variable that takes the
value 1 when $N\geq R$ and zero otherwise. This approach is slightly different
than the one used in RW1  where we assumed that process can complete even when
the steps for first passage and restart coincide i.e., $N_{R}=N$ when $N\leq
R$ unlike here [see Eq. (1) in above].

###  III.1 Mean

We take expectations on both sides of Eq. (1) and use the fact that $N$ and
$R$ are independent of each other. This results in the following expression
for the mean completion time under restart

$\displaystyle\left\langle N_{R}\right\rangle=\frac{\left\langle
min\left(N,R\right)\right\rangle}{\text{Pr}\left(N<R\right)}.$ (2)

The numerator can be computed by noting that the probability
$\text{Pr}\left(min\left(N,R\right)>n\right)=\text{Pr}\left(N>n\right)\text{Pr}\left(R>n\right)$
and thus

$\displaystyle\left\langle min\left(N,R\right)\right\rangle$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\text{Pr}\left(min\left(N,R\right)>n\right)$
(3) $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\left(\sum_{k=n+1}^{\infty}P_{N}\left(k\right)\right)\left(\sum_{m=n+1}^{\infty}P_{R}\left(m\right)\right)$
$\displaystyle=$ $\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)Q_{R}(n),$

where note that $Q_{N}(n)$ and $Q_{R}(n)$ are the survival functions for the
first passage and restart processes respectively i.e.,

$\displaystyle Q_{N}(n)$ $\displaystyle=\text{Pr}(N>n),$ (4) $\displaystyle
Q_{R}(n)$ $\displaystyle=\text{Pr}(R>n).$ (5)

The denominator in Eq. (2) can also be computed easily

$\displaystyle\text{Pr}\left(N<R\right)=\sum_{n=0}^{\infty}P_{N}(n)\sum_{m=n+1}^{\infty}P_{R}(m).$
(6)

###  III.2 Generating function for the restarted process

We now turn our attention to derive the generating function for the restarted
process. The probability generating function of the discrete random variable
$N_{R}$ taking values in the non-negative integers ${0,1,...}$ is defined as

$\displaystyle G_{N_{R}}(z)\equiv\left\langle
z^{N_{R}}\right\rangle=\sum_{n=0}^{\infty}P_{N_{R}}(n)z^{n},$ (7)

where $P_{N_{R}}(n)$ is the probability mass function of $N_{R}$. It will now
prove useful to introduce the following conditional random variables

$\displaystyle N_{min}$ $\displaystyle\equiv$
$\displaystyle\left\\{N|N<R\right\\},$ (8) $\displaystyle R_{min}$
$\displaystyle\equiv$ $\displaystyle\left\\{R|N\geq R\right\\},$ (9)

with their respective densities

$\displaystyle P_{N_{min}}(n)$ $\displaystyle=$ $\displaystyle
P_{N}(n)\frac{\sum_{m=n+1}^{\infty}P_{R}(m)}{\text{Pr}\left(N<R\right)},$ (10)
$\displaystyle P_{R_{min}}(n)$ $\displaystyle=$ $\displaystyle
P_{R}(n)\frac{\sum_{m=n}^{\infty}P_{N}(m)}{\text{Pr}\left(N\geq R\right)},$
(11)

where $\text{Pr}\left(N\geq R\right)=1-\text{Pr}\left(N<R\right)$. Using the
renewal Eq. (1) and the new random variables in Eqs.(8)-(9), we can write

$\displaystyle G_{N_{R}}(z)$ $\displaystyle=$
$\displaystyle\text{Pr}\left(N<R\right)\left\langle
z^{N_{min}}\right\rangle+\text{Pr}\left(N\geq R\right)\left\langle
z^{R_{min}+N^{\prime}_{R}}\right\rangle.$ (12)

Now using the fact that $N^{\prime}_{R}$ is an independent and identically
distributed copy of $N_{R}$ in above, we arrive at the following expression
for the generating function of the restarted process

$\displaystyle G_{N_{R}}(z)$ $\displaystyle=$
$\displaystyle\frac{\left(1-\text{Pr}\left(N\geq
R\right)\right)G_{N_{min}}(z)}{1-\text{Pr}\left(N\geq
R\right)G_{R_{min}}(z)},$ (13)

where $G_{X_{min}}(z)$ is the generating function for the random variable
$X_{min}$. The above formula (13), being a simple analogue to Eq. (11) in RW1
, is extremely useful since it allows one to compute all the moments

$\displaystyle\left\langle N_{R}^{k}\right\rangle$ $\displaystyle=$
$\displaystyle\left(z\frac{\partial}{\partial
z}\right)^{k}G_{N_{R}}(z)\Big{|}_{z=1^{-}},$ (14)

and, importantly, also the probability density function of $N_{R}$

$\displaystyle P_{N_{R}}(n)$ $\displaystyle=$
$\displaystyle\text{Pr}(N_{R}=n)=\frac{G_{N_{R}}^{(n)}(0)}{n!},$ (15)

where $\left\langle N_{R}^{k}\right\rangle$ is the $k$-th moment and
$G_{X}^{(n)}(z)$ is the $n$-th derivative of $G_{X}(z)$ with respect to $z$,
and $n=0,1,2...$. Note that in discrete set-up, computation of the first
passage time probability mass requires only derivatives of the generating
function as seen in Eq. (15), and thus is more accessible compared to the
continuous time set-up FPUR .

###  III.3 First passage and survival probability

Depending on the quantities of interest, survival functions are often computed
to infer first passage statistics. In $z$-space, the first passage and
survival functions are almost trivially connected. For the random variable
$N$, we can write

$\displaystyle G_{Q_{N}}(z)$
$\displaystyle\equiv\sum_{n=0}^{\infty}z^{n}Q_{N}(n)=\frac{1-G_{N}(z)}{1-z},$
(16)

where recall $G_{N}(z)=\sum_{n=0}^{\infty}z^{n}P_{N}(n)$ is the PGF for first
passage time density (see RW1  for derivation). This relation is very general
and useful, and holds for any non-negative random variable $X$ e.g., with
restarts, we have

$\displaystyle
G_{Q_{N_{R}}}(z)\equiv\sum_{n=0}^{\infty}z^{n}Q_{N_{R}}(n)=\frac{1-G_{N_{R}}(z)}{1-z},$
(17)

where $G_{N_{R}}(z)$ is given by Eq. (7).

##  IV Geometrically distributed restart

In this section, we consider a specific form of restart time distribution,
namely the Geometric distribution. Here, a resetting step number is taken from
the following distribution with parameter $p~{}(0<p<1)$,

$\displaystyle P_{R}(n)=(1-p)^{n-1}p,~{}~{}n\geq 1.$ (18)

In other words, restart will occur exactly at the $n$-th step with probability
$p$, after $n-1$ unsuccessful attempts. Notably, this distribution is the
discrete analog of the exponential distribution, being a discrete distribution
possessing the memory-less property.

###  IV.1 Mean

To derive the mean completion time, we first note that the survival function
for the restart can be written as

$\displaystyle Q_{R}(n)$ $\displaystyle=$ $\displaystyle\text{Pr}(R>n)$ (19)
$\displaystyle=$ $\displaystyle\sum_{k=n+1}^{\infty}(1-p)^{k-1}p$
$\displaystyle=$ $\displaystyle\sum_{k=1}^{\infty}(1-p)^{k+n-1}p$
$\displaystyle=$ $\displaystyle(1-p)^{n}\sum_{k=1}^{\infty}(1-p)^{k-1}p$
$\displaystyle=$ $\displaystyle(1-p)^{n}.$

We now use Eq. (19) and Eq. (16) to calculate $\left\langle
min\left(N,R\right)\right\rangle$, given in Eq. (3)

$\displaystyle\left\langle min\left(N,R\right)\right\rangle$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)Q_{R}(n)$ (20) $\displaystyle=$
$\displaystyle Q_{N}(0)+\sum_{n=1}^{\infty}Q_{N}(n)(1-p)^{n}$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)(1-p)^{n}$ $\displaystyle=$
$\displaystyle G_{Q_{N}}(1-p)$ $\displaystyle=$
$\displaystyle\frac{1-G_{N}(1-p)}{p}.$

Next, following Eq. (6), we have

$\displaystyle\text{Pr}\left(N<R\right)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}P_{N}(n)\sum_{m=n+1}^{\infty}P_{R}(m)$ (21)
$\displaystyle=$ $\displaystyle P_{N}(0)+\sum_{n=1}^{\infty}P_{N}(n)(1-p)^{n}$
$\displaystyle=$ $\displaystyle G_{N}(1-p),$

Substituting Eqs. (20) and (21) into the formula for the mean of the restarted
process given in Eq. (2) yields

$\displaystyle\langle N_{R}\rangle$ $\displaystyle=$
$\displaystyle\frac{1-G_{N}(1-p)}{pG_{N}(1-p)},$ (22)

which gives us a simple plug-n-play solution for the mean completion time with
the knowledge of the underlying first passage time distribution. We can also
rewrite the mean first passage time in term of the PGF of the survival
function. This is done by substituting Eq. (16) into Eq. (22)

$\displaystyle\langle N_{R}\rangle$ $\displaystyle=$
$\displaystyle\frac{G_{Q_{N}}(1-p)}{1-pG_{Q_{N}}(1-p)},$ (23)

which is identical to Eq. (7), derived by Kusmierz et al in Lukasz .

###  IV.2 Generating function for the restarted process

We now turn to the derivation of the PGF of the restarted process under
geometric restart. We first compute the PGFs for the conditional random
variables $N_{min}$ and $R_{min}$. Following a similar computation as in RW1 ,
we find

$\displaystyle G_{N_{min}}(z)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}P_{N}(n)\frac{\sum_{m=n+1}^{\infty}P_{R}(m)}{\text{Pr}\left(N<R\right)}z^{n}$
(24) $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}P_{N}(n)\frac{(1-p)^{n}}{G_{N}(1-p)}z^{n}$
$\displaystyle=$
$\displaystyle\frac{1}{G_{N}(1-p)}\sum_{n=0}^{\infty}P_{N}(n)(1-p)^{n}z^{n}$
$\displaystyle=$ $\displaystyle\frac{G_{N}(z(1-p))}{G_{N}(1-p)},$

and

$\displaystyle G_{R_{min}}(z)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}P_{R}(n)\frac{\sum_{m=n}^{\infty}P_{N}(m)}{\text{Pr}\left(N\geq
R\right)}z^{n}$ (25) $\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}(1-p)^{n-1}p\frac{Q_{N}(n-1)}{1-G_{N}(1-p)}z^{n}$
$\displaystyle=$
$\displaystyle\frac{pz}{1-G_{N}(1-p)}\sum_{n=0}^{\infty}Q_{N}(n)(1-p)^{n}z^{n}$
$\displaystyle=$ $\displaystyle\frac{pzG_{Q_{N}}((1-p)z)}{1-G_{N}(1-p)}$
$\displaystyle=$
$\displaystyle\frac{pz(1-G_{N}((1-p)z))}{(1-(1-p)z)(1-G_{N}(1-p))},$

where in the last step we once again used Eq. (16). Substituting Eqs.
(24)-(25) into Eq. (13) we find

$\displaystyle G_{N_{R}}(z)$ $\displaystyle=$
$\displaystyle\frac{(1-(1-p)z)G_{N}((1-p)z)}{1-z+pzG_{N}((1-p)z)},$ (26)

from which one can derive the probability mass function of the restarted
process by taking the derivatives of the generating function using Eq. (15).
Now substituting (using Eq. (16))

$\displaystyle G_{N}(z)$ $\displaystyle=(z-1)G_{Q_{N}}(z)+1$ (27)

and

$\displaystyle G_{{N_{R}}}(z)=(z-1)G_{Q_{N_{R}}}(z)+1$ (28)

into Eq. (26) we obtain a relation between the survival functions with and
without restart

$\displaystyle
G_{Q_{N_{R}}}(z)=\frac{G_{Q_{N}}((1-p)z)}{1-pzG_{Q_{N}}((1-p)z)},$ (29)

which is identical to Eq. (5), derived by Kusmierz et al in Lukasz . While Eq.
(26) connects the first passage time distributions, Eq. (29) relates the
survival functions.

##  V Applications

In this section, we revisit a few lattice restarted random walk problems which
were studied recently by different groups (and that will be mentioned in
context).

###  V.1 Simple random walk

Consider a simple random walker (starting at the origin) in the presence of
only one absorbing boundary located at $x$. In this case, the generating
function for the underlying process can be easily obtained following steps
from LRW-5  and this reads

$\displaystyle G_{N}(z)=\left(\frac{1-\sqrt{1-z^{2}}}{z}\right)^{|x|},\quad
x\neq 0.$ (30)

In fact, it is known that for large $n$, the first passage time density has a
power law tail $n^{-3/2}$ LRW-4 ; LRW-5 ; LRW-6 , which is similar to the
Lévy-Smirnov distribution for the first passage time of a Brownian walker in
one dimension. This power law trivially leads to a diverging mean first
passage time for a RW. However, motion of the walker is restarted to the
origin with a probability $p$. This simple restart mechanism can lead to
finiteness of the mean first passage time (like the simple diffusion problem
in Restart1  and see the recent review Restart-review ). The mean completion
time of a random walker on this geometry reads

$\displaystyle\langle
N_{R}\rangle=\frac{1}{p}\left[\left(\frac{1+\sqrt{2p-p^{2}}}{1-p}\right)^{|x|}-1\right],$
(31)

which can be obtained by substituting Eq. (30) into Eq. (22). This result was
previously obtained by Riascos et al [see Eq. (26) in network-2 ].

###  V.2 One sided Sisyphus random walk

In RW2 , Montero and Villarroel studied one sided Sisyphus random walk in the
presence of geometric restarts. In this dynamics, the walker starts from the
origin and makes a deterministic step to the right at each time step. However,
the motion is stopped with probability $p$ and the walker is returned to the
origin. The process ends as soon as the walker reaches the threshold $a>0$.
The first passage time is recorded accordingly. Since the process is
deterministic, for the underlying first passage process, we should have

$\displaystyle N=a,$ (32)

so that $P_{N}(n)=\delta_{n,a}$, where $\delta_{a,b}$ is the Kronecker delta.
The PGF of this first passage process is given by

$\displaystyle G_{N}(z)=\sum_{n=0}^{\infty}P_{N}(n)z^{n}=z^{a}.$ (33)

Substituting the PGF of the underlying process given in Eq. (33) into Eq. (26)
yields

$\displaystyle
G_{N_{R}}(z)=\frac{(1-(1-p)z)(z(1-p))^{a}}{1-z(1-p(z(1-p)^{a})}.$ (34)

Substituting $p\rightarrow 1-q$ (keeping the notation as in RW2 ) yields

$\displaystyle G_{N_{R}}(z)=(qz)^{a}\frac{1-qz}{1-z+(1-q)z(qz)^{a}},$ (35)

which is identical to Eq. (16) in RW2 . Furthermore, substituting the PGF into
Eq. (22) gives us

$\displaystyle\langle
N_{R}\rangle=\frac{1}{1-q}\left(\frac{1}{q^{a}}-1\right),$ (36)

(again by replacing $p\to 1-q$) which is identical to Eq. (18) in RW2 .

###  V.3 Two sided Sisyphus random walk

In a recent preprint RW3 , Villarroel et al extended their study of one sided
Sisyphus random walk to a two sided Sisyphus walk resulting in the walker in a
1D confinement (see interval1 ; interval2  for such other examples in
continuous set-ups). The underlying first passage process in the interval
$[-b,a]$ can be understood in the following way

$\displaystyle N=\begin{cases}b&\text{prob.}\quad 1-\rho\\\
a&\text{prob.}\quad\rho\end{cases}.$ (37)

This means that the walker deterministically moves to the right with
probability $\rho$ and to the left with the complementary probability. The
process ends as soon as the walker reaches one of the boundaries. The PGF of
$N$ is then given by

$\displaystyle
G_{N}(z)=\sum_{n=0}^{\infty}P_{N}(n)z^{n}=z^{b}(1-\rho)+z^{a}\rho.$ (38)

Substituting the PGF of the underlying process given in Eq. (38) into Eq.
(26), and substituting $p\rightarrow 1-q$ yields the generating function for
the entire process

$\displaystyle
G_{N_{R}}(z)=\frac{(1-qz)((qz)^{a}\rho+(qz)^{b}(1-\rho))}{1-z+(1-q)z((qz)^{a}\rho+(qz)^{b}(1-\rho))}.$
(39)

This is a useful result since it helps one to derive not only the mean but
also the higher order moments. For a symmetric box, Eq. (39) reduces to

$\displaystyle G_{N_{R}}(z)=(qz)^{a}\frac{1-qz}{1-z+(1-q)z(qz)^{a}},$ (40)

which is identical to Eq. (35), as it should [also see Eq. (51) in RW3 ]. The
results are identical since a walk directed to the left boundary and a walk
directed to the right boundary are identically distributed for the case of a
symmetric box. Thus, walks in opposite directions can be considered as
different realizations of the same process.

Substituting the PGF given in Eq. (38) into Eq. (22), and $p\rightarrow 1-q$,
yields the mean escape time for the walker from the interval in the presence
of restart

$\displaystyle\langle N_{R}\rangle=\frac{1-(\rho
q^{a}+(1-\rho)q^{b})}{(1-q)(\rho q^{a}+(1-\rho)q^{b})}.$ (41)

In the case of symmetric box, the mean first passage reduces to

$\displaystyle\langle
N_{R}\rangle=\frac{1}{1-q}\left(\frac{1}{q^{a}}-1\right).$ (42)

which is identical to Eq. (36). In RW3 , the authors introduced $l$ as the
average number of steps the walker takes until resetting. Translating to our
language $\langle R\rangle=l$, and also $l=\frac{1}{1-p}=\frac{1}{q}$.
Substituting this into Eq. (42), we get

$\displaystyle\langle N_{R}\rangle=l\frac{l^{a}-1}{l-1},$ (43)

which was also derived in RW3  [see Eq. (55)]. It is important to note that
our results hold for asymmetric interval, and thus are more general.

##  VI Examples of Other restart protocols

In this section, we present exact results for the mean completion time of a
generic first passage process (discrete space and time) under discrete restart
protocols which are not necessarily memoryless. In other words, unlike
geometric distribution, they may not be often thought as a probabilistic way.
In fact, the protocols we choose can also come from a heavy-tailed
distribution. We show how our formalism is robust to all these changes and
finally the results are given in terms of the statistical metrics of the
underlying first passage process.

###  VI.1 Sharp restart

Consider now a strategy when restart events always take place after a fixed
number of steps. This is often known as sharp, periodic or deterministic
restart protocol (see PalJphysA ; FPUR  for more details of this strategy).
Since the resetting takes place always after a fixed period, the density can
be written as

$\displaystyle P_{R}(n)=\delta_{n,r}=\begin{cases}0,&n\neq r\\\
1,&n=r\end{cases},$ (44)

where $\delta_{n,r}$ is the Kronecker delta. So, we will refer to this as a
distribution with restart step or period $r$. We have studied this set-up in
the preceding work RW1 . Here, we recall the results for brevity. For sharp
restart, we have

$\displaystyle\text{Pr}\left(N<R\right)=\text{Pr}\left(N<r\right)=\sum_{n=0}^{r-1}P_{N}(n).$
(45)

Furthermore, we find

$\displaystyle\langle\text{min}(N,R)\rangle$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)Q_{R}(n)$ (46) $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)\sum_{m=n+1}^{\infty}P_{R}(m)$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)\sum_{m=n+1}^{\infty}\delta_{m,r}$
$\displaystyle=$ $\displaystyle\sum_{n=0}^{r-1}Q_{N}(n).$

Substituting Eq. (45) and Eq. (46) into Eq. (2) we get the following
expression for the mean completion time

$\displaystyle\langle
N_{R}\rangle=\frac{\sum_{n=0}^{r-1}Q_{N}(n)}{\sum_{n=0}^{r-1}P_{N}(n)},$ (47)

which is given in terms of the survival and first passage of the underlying
process.

###  VI.2 Poisson restart

Here we consider the restart steps to be drawn from the Poisson distribution
namely

$\displaystyle P_{R}(n)=\frac{\lambda^{n-1}e^{-\lambda}}{(n-1)!},n=1,2,3,...$
(48)

where $\lambda$ is a positive rate parameter. Here, we use a Poisson
distribution with rate parameter $\lambda$, shifted by 1, so the support of
the restart distribution is strictly positive, i.e., avoiding restart at 0.
Under this resetting protocol, we get

$\displaystyle\text{Pr}(N<R)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}P_{N}(n)\sum_{m=n+1}^{\infty}P_{R}(m)$ (49)
$\displaystyle=$ $\displaystyle
P_{N}(0)+\sum_{n=1}^{\infty}P_{N}(n)\sum_{m=n+1}^{\infty}P_{R}(m)$
$\displaystyle=$ $\displaystyle
P_{N}(0)+\sum_{n=1}^{\infty}P_{N}(n)\left(1-\sum_{m=1}^{n}P_{R}(m)\right)$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}P_{N}(n)-\sum_{n=1}^{\infty}P_{N}(n)\sum_{m=1}^{n}P_{R}(m)$
$\displaystyle=$ $\displaystyle
1-\sum_{n=1}^{\infty}P_{N}(n)\sum_{m=1}^{n}P_{R}(m)$ $\displaystyle=$
$\displaystyle 1-\sum_{n=1}^{\infty}\sum_{m=1}^{n}P_{N}(n)P_{R}(m)$
$\displaystyle=$ $\displaystyle
1-\sum_{m=1}^{\infty}\sum_{n=m}^{\infty}P_{N}(n)P_{R}(m)$ $\displaystyle=$
$\displaystyle 1-\sum_{m=1}^{\infty}P_{R}(m)\sum_{n=m}^{\infty}P_{N}(n)$
$\displaystyle=$ $\displaystyle 1-\sum_{m=1}^{\infty}P_{R}(m)Q_{N}(m-1)$
$\displaystyle=$ $\displaystyle 1-\sum_{m=0}^{\infty}P_{R}(m+1)Q_{N}(m)$
$\displaystyle=$ $\displaystyle
1-e^{-\lambda}\sum_{m=0}^{\infty}\frac{\lambda^{m}}{m!}Q_{N}(m),$

and

$\displaystyle\langle\text{min}(N,R)\rangle$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)Q_{R}(n)$ (50) $\displaystyle=$
$\displaystyle Q_{N}(0)+\sum_{n=1}^{\infty}Q_{N}(n)Q_{R}(n)$ $\displaystyle=$
$\displaystyle
Q_{N}(0)+\sum_{n=1}^{\infty}Q_{N}(n)\left(1-\sum_{m=1}^{n}P_{R}(m)\right)$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)-\sum_{n=1}^{\infty}Q_{N}(n)\sum_{m=1}^{n}P_{R}(m)$
$\displaystyle=$ $\displaystyle\langle
N\rangle-\sum_{n=1}^{\infty}Q_{N}(n)\sum_{m=1}^{n}\frac{\lambda^{m-1}e^{-\lambda}}{(m-1)!}$
$\displaystyle=$ $\displaystyle\langle
N\rangle-\sum_{n=1}^{\infty}Q_{N}(n)\sum_{m=0}^{n-1}\frac{\lambda^{m}e^{-\lambda}}{m!}$
$\displaystyle=$ $\displaystyle\langle
N\rangle-e^{-\lambda}\sum_{n=1}^{\infty}Q_{N}(n)\sum_{m=0}^{n-1}\frac{\lambda^{m}}{m!}.$

Substituting Eq. (49) and Eq. (50) into Eq. (2) we get the following formula
for the mean first passage time under Poissonian resetting

$\displaystyle\langle N_{R}\rangle=\frac{\langle
N\rangle-e^{-\lambda}\sum_{n=1}^{\infty}Q_{N}(n)\sum_{m=0}^{n-1}\frac{\lambda^{m}}{m!}}{1-e^{-\lambda}\sum_{m=0}^{\infty}\frac{\lambda^{m}}{m!}Q_{N}(m)},$
(51)

which is given in terms of the survival function of the underlying first
passage time process.

###  VI.3 Zeta restart

We now consider restart steps which are taken from Zeta distribution

$\displaystyle P_{R}(n)=\frac{n^{-s}}{\zeta(s)},n=1,2,3,...$ (52)

where $s$ is a positive integer, and $\zeta(s)$ is the Zeta function, defined
as

$\displaystyle\zeta(s)=\sum_{m=1}^{\infty}\frac{1}{m^{s}},Re(s)>1.$ (53)

The Zeta distribution is a heavy-tailed distribution. Under this resetting
protocol, following similar steps to the Poisson case, we get

$\displaystyle\text{Pr}(N<R)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}P_{N}(n)\sum_{m=n+1}^{\infty}P_{R}(m)$ (54)
$\displaystyle=$ $\displaystyle
P_{N}(0)+\sum_{n=1}^{\infty}P_{N}(n)\sum_{m=n+1}^{\infty}P_{R}(m)$
$\displaystyle=$ $\displaystyle
P_{N}(0)+\sum_{n=1}^{\infty}P_{N}(n)\left(1-\sum_{m=1}^{n}P_{R}(m)\right)$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}P_{N}(n)-\sum_{n=1}^{\infty}P_{N}(n)\sum_{m=1}^{n}P_{R}(m)$
$\displaystyle=$ $\displaystyle
1-\sum_{n=1}^{\infty}P_{N}(n)\sum_{m=1}^{n}P_{R}(m)$ $\displaystyle=$
$\displaystyle 1-\sum_{n=1}^{\infty}\sum_{m=1}^{n}P_{N}(n)P_{R}(m)$
$\displaystyle=$ $\displaystyle
1-\sum_{m=1}^{\infty}\sum_{n=m}^{\infty}P_{N}(n)P_{R}(m)$ $\displaystyle=$
$\displaystyle 1-\sum_{m=1}^{\infty}P_{R}(m)\sum_{n=m}^{\infty}P_{N}(n)$
$\displaystyle=$ $\displaystyle 1-\sum_{m=1}^{\infty}P_{R}(m)Q_{N}(m-1)$
$\displaystyle=$ $\displaystyle
1-\frac{1}{\zeta(s)}\sum_{m=1}^{\infty}Q_{N}(m-1)m^{-s},$

and

$\displaystyle\langle\text{min}(N,R)\rangle$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)Q_{R}(n)$ (55) $\displaystyle=$
$\displaystyle Q_{N}(0)+\sum_{n=1}^{\infty}Q_{N}(n)Q_{R}(n)$ $\displaystyle=$
$\displaystyle
Q_{N}(0)+\sum_{n=1}^{\infty}Q_{N}(n)\left(1-\sum_{m=1}^{n}P_{R}(m)\right)$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}Q_{N}(n)-\sum_{n=1}^{\infty}Q_{N}(n)\sum_{m=1}^{n}P_{R}(m)$
$\displaystyle=$ $\displaystyle\langle
N\rangle-\sum_{n=1}^{\infty}Q_{N}(n)\sum_{m=1}^{n}\frac{m^{-s}}{\zeta(s)}$
$\displaystyle=$ $\displaystyle\langle
N\rangle-\frac{1}{\zeta(s)}\sum_{n=1}^{\infty}Q_{N}(n)\sum_{m=1}^{n}m^{-s}$
$\displaystyle=$ $\displaystyle\langle
N\rangle-\frac{1}{\zeta(s)}\sum_{n=1}^{\infty}Q_{N}(n)H_{n,s},$

where $H_{n,s}$ is the generalized harmonic number of order $s$ of $n$.
Substituting Eq. (54) and Eq. (55) into Eq. (2) we get the following formula
for the mean first passage time under Zeta distributed resetting

$\displaystyle\langle N_{R}\rangle=\frac{\langle
N\rangle-\frac{1}{\zeta(s)}\sum_{n=1}^{\infty}Q_{N}(n)H_{n,s}}{1-\frac{1}{\zeta(s)}\sum_{m=1}^{\infty}Q_{N}(m-1)m^{-s}},$
(56)

which is given in terms of the survival function of the underlying process.

##  VII Concluding perspective

In this note, we presented a simple, and completely general recipe to study
statistical properties of discrete first passage processes under arbitrary
discrete restart steps. The stages of the computation are as follows:

  * •

Survival functions: compute the survival functions $Q_{N}(n)$ and $Q_{R}(n)$
from the given first passage and restart time distributions namely $P_{N}(n)$
and $P_{R}(n)$ respectively [use Eqs. (4) and (5)].

  * •

Mean completion time under restart: next, compute $\text{Pr}(N<R)$ and its
complementary probability $\text{Pr}(N\geq R)$ using Eq. (6). The mean
completion time can then be obtained from Eq. (2).

  * •

Generating function of the restarted first passage process: compute the
generating functions for the random variable $N_{min}$ and $R_{min}$ and plug
in Eq. (13) to derive the generating function for the restarted process from
which all the moments can be derived. In some cases, the first passage time
density of the compound process can be obtained making use of Eq. (15). This
was demonstrated in RW1 .

The three-step algorithm prescribed above gives a systematic way to compute
first passage quantities and investigate the effects of different restart
mechanisms. Since the formalism holds for any first passage process (Markov or
non-Markov) under any restart mechanism (Markov or non-Markov), we anticipate
that the method would be useful to develop synergy between discrete stochastic
process and resetting which are much less studied compared to the continuous
space-time processes.

Numerical treatment.— Finally, it is worth emphasizing that the machinery
presented above also works to treat the problems numerically without having to
solve the exact dynamics of the stochastic process of interest. What one needs
is two datasets: one is for the underlying first passage time (which is known
for many problems numerically) and the other for resetting (which is an
external input). The above-mentioned three-step recipe can then be implemented
numerically, and relevant quantities may be computed. To this end, a
supplemented MATHEMATICA file will be available on the Notebook Archive.

###### Acknowledgements.

AP gratefully acknowledges support from the Raymond and Beverly Sackler Post-
Doctoral Scholarship and the Ratner Center for Single Molecule Science at Tel-
Aviv University.

## References

  * (1) Pal, A. and Reuveni, S., 2017. First passage under restart. Physical review letters, 118(3), p.030603.
  * (2) Bonomo, O.L. and Pal, A., 2021. First passage under restart for discrete space and time: Application to one-dimensional confined lattice random walks. Physical Review E, 103(5), p.052129.
  * (3) Kusmierz, L., Majumdar, S.N., Sabhapandit, S. and Schehr, G., 2014. First order transition for the optimal search time of Lévy flights with resetting. Physical review letters, 113(22), p.220602.
  * (4) Klafter, J. and Sokolov, I.M., 2011. First steps in random walks: from tools to applications. Oxford University Press.
  * (5) Rudnick, J. and Gaspari, G., 2004. Elements of the random walk: an introduction for advanced students and researchers. Cambridge University Press.
  * (6) Majumdar, S.N., 2010. Universal first-passage properties of discrete-time random walks and Lévy flights on a line: Statistics of the global maximum and records. Physica A: Statistical Mechanics and its Applications, 389(20), pp.4299-4316.
  * (7) Evans, M.R. and Majumdar, S.N., 2011. Diffusion with stochastic resetting. Physical review letters, 106(16), p.160601.
  * (8) Evans, M.R., Majumdar, S.N. and Schehr, G., 2020. Stochastic resetting and applications. Journal of Physics A: Mathematical and Theoretical, 53(19), p.193001.
  * (9) Riascos, A.P., Boyer, D., Herringer, P. and Mateos, J.L., 2020. Random walks on networks with stochastic resetting. Physical Review E, 101(6), p.062147.
  * (10) Montero, M. and Villarroel, J., 2016. Directed random walk with random restarts: The Sisyphus random walk. Physical Review E, 94(3), p.032132.
  * (11) Villarroel, J.; Montero, M.; Vega, J.A. A Semi-Deterministic Random Walk with Resetting. Preprints 2021, 2021060151
  * (12) Pal, A. and Prasad, V.V., 2019. First passage under stochastic resetting in an interval. Physical Review E, 99(3), p.032123.
  * (13) Pal, A. and Prasad, V.V., 2019. Landau-like expansion for phase transitions in stochastic resetting. Physical Review Research, 1(3), p.032001.
  * (14) Pal, A., Kundu, A. and Evans, M.R., 2016. Diffusion under time-dependent resetting. Journal of Physics A: Mathematical and Theoretical, 49(22), p.225001.