# First-passage process in degree space for the time-dependent Erdős-Rényi and
Watts-Strogatz models

F. Ampuero and M. O. Hase  Escola de Artes, Ciências e Humanidades,
Universidade de São Paulo, Av. Arlindo Béttio 1000, 03828-000 São Paulo,
Brazil

###### Abstract

In this work, we investigate the temporal evolution of the degree of a given
vertex in a network by mapping the dynamics into a random walk problem in
degree space. We analyze when the degree approximates a pre-established value
through a parallel with the first-passage problem of random walks. The method
is illustrated on the time-dependent versions of the Erdős-Rényi and Watts-
Strogatz models, which originally were formulated as static networks. We have
succeeded in obtaining an analytic form for the first and the second moments
of the first-passage time and showing how they depend on the size of the
network. The dominant contribution for large networks with $N$ vertices
indicates that these quantities scale on the ratio $N/p$, where $p$ is the
linking probability.

networks, random walk

##  I Introduction

The study of the properties of networks led to the development of many
mathematical, statistical and computational tools that can be used to analyze,
model, and understand how systems behave in many areas of knowledge such as
physics, biology, ecology, and social sciences, to name some of them. Modeling
complex systems by networks AB02 ; DM03 ; N10  is a natural strategy to
investigate a system from a very basic structure composed of agents and
interactions among them, represented, respectively, by vertices (or nodes) and
links.

In this work, we are mainly interested in the time evolution of the degree of
a given node. Concretely, a vertex can gain and/or lose connections during its
dynamics, and we investigate when it achieves a pre-established degree for the
first time. This is a particularly relevant issue when agents can not afford
an indefinite number of connections and some indication of approaching the
maximum capacity of the node ASBS00 ; HCG16  is desired. As an instance, it is
known that airports (where the links can be assigned to the routes) have
constraints that prevent growth without careful planning UTGR03 .

We map the dynamics of increasing/decreasing degrees into a random walk
process, as was introduced in CGCH17 , and see if and how long it takes for a
vertex with degree $k_{0}$ to achieve degree $k$ for the first time. This is a
one-dimensional random walk in degree space, where the rules of
gaining/losings degree are governed by the dynamics of the network. The random
walk is a classical problem R80 ; P05  where a particle moves in random
directions and one typically inquires about its statistical properties after a
long time. Starting from an origin, one possible question that can be
formulated concerns the probability of returning to the starting point, and
the first-passage process refers to its return for the first time R07 . First-
passage processes are seen in many applications, and examples are present in
fluorescence quenching, integrate-and-fire neurons, and triggering of stock
options, to cite some of them KRBN10 ; R07 . When the random walk is defined
on a (hyper)cubic lattice P21 , and the particle can move in any direction
with the same probability, it is known that the mean first-passage time scales
as $L^{d}$ MW65 , where $L$ is the linear size of the $d$-dimensional lattice
with periodic boundary conditions; furthermore, in the limit of infinite
lattice, this random walk is known to be recurrent (i.e., it returns to the
origin with probability $1$) for one-dimensional chains and two-dimensional
square lattices, while the process is transient (i.e, there is a positive
probability of not returning to the origin) for hypercubic lattices with
larger dimensions MW65 ; KRBN10 .

We investigate how the mean first-passage time of a vertex to reach a pre-
established degree scales with the size of the network and other relevant
parameters. Our study is based on an extended version of the Watts-Strogatz
model WS98 , which was also introduced in CGCH17 , but we consider first a
dynamical version of the Erdős-Rényi model ER59  to illustrate and outline the
main steps of analysis. The choice of these two models is justified by a
simplification that arises from a property shared between them, which is the
time-translational invariance. Systems that do not have this property, like
the random recursive tree NR70  or Barabási-Albert network BA99 , indicate the
need for a different approach, and will be examined elsewhere.

This paper is organized as follows. We define the dynamical version of the
Erdős-Rényi and Watts-Strogatz models in Section II and the general formalism
to investigate the moments of the first-passage time is presented in Section
III. The results for both models are shown in Section IV and some final
comments are given in the last section.

##  II Models

Two models are introduced to test our ideas in this work. Both of them are
already well-known in the literature ER59 ; WS98 , but were initially defined
as static networks.

The first one, which is a minimal model, is the dynamical Erdős-Rényi network:
the dynamics is just a simple addition of edges per time unit, and we monitor
the increase of degrees only. The second one, the dynamical Watts-Strogatz
model, is the simplest network that contains the process where a vertex can
gain and/or lose connections randomly. The usual first-passage process (which
is concerned with the return to the starting point) in the latter model
corresponds to the so-called Motzkin paths OvdJ15 .

###  II.1 Time-dependent Erdős-Rényi model

In the dynamical version of the Erdős-Rényi model, consider a network with $N$
vertices. At each unitary time step, two vertices are randomly chosen and
connected with probability $p$; this includes the possibility of (a) having a
self-loop (i.e, an edge that connects a vertex to itself) and (b) having more
than one connection between the same pair of vertices. Since there is no
preferential attachment, the probability of any vertex being chosen is $1/N$.

Defining $p_{s}(k,t)$ as the probability that a vertex $s$ has degree $k$ at
time $t$, the dynamics can be represented by the recurrence relation

$\displaystyle p_{s}(k,t+1)$ $\displaystyle=\omega_{\text{\tiny
ER}}(k|k-2)p_{s}(k-2,t)+$ $\displaystyle+\omega_{\text{\tiny
ER}}(k|k-1)p_{s}(k-1,t)+$ $\displaystyle+\omega_{\text{\tiny
ER}}(k|k)p_{s}(k,t).$ (1)

The term $\omega_{\text{\tiny ER}}(k|m)$ is the time-independent transition
rate of changing the degree of a vertex from $m$ to $k$; in this time-discrete
case with unitary time step, the transition rate coincides numerically to the
conditional probability. The right-hand-side of the dynamics (1) contemplates
three cases:

  1. (i)

The degree of vertex $s$ changes from $k-2$ (at time $t$) to $k$ (at time
$t+1$). An edge is introduced, with probability $p$ (there should be no
confusion with $p_{s}$), the vertex $s$ is chosen twice and is connected to
itself; this leads to

$\displaystyle\omega_{\text{\tiny ER}}(k|k-2)=\frac{p}{N^{2}};$ (2)

  2. (ii)

The degree of vertex $s$ changes from $k-1$ (at time $t$) to $k$ (at time
$t+1$). An edge is introduced, with probability $p$, and links to two
different vertices: the vertex $s$ is just one of them. This situation is
described by

$\displaystyle\omega_{\text{\tiny
ER}}(k|k-1)=\frac{2p}{N}\left(1-\frac{1}{N}\right);$ (3)

  3. (iii)

The vertex $s$ already has degree $k$, and one should consider the probability
of not changing its degree, i.e., the link is not introduced (with probability
$1-p$) or, when the edge joins the network (with probability $p$), it connects
two vertices other than $s$ with probability $\left(1-1/N\right)^{2}$. In this
case, one has

$\displaystyle\omega_{\text{\tiny ER}}(k|k)$
$\displaystyle=\left(1-p\right)+p\left(1-\frac{1}{N}\right)^{2}$
$\displaystyle=1-\frac{2p}{N}+\frac{p}{N^{2}}.$ (4)

###  II.2 Time-dependent Watts-Strogatz model

In this version of the Watts-Strogatz model, the network has a fixed number
$N$ of vertices and

$\displaystyle M:=cN$ (5)

degrees, where $c$ is the mean degree of the network (therefore, the entire
graph has $cN/2$ edges). At each time step, an edge end is chosen at random
with uniform probability $1/M$ and reconnected with probability $p$ (and no
action takes place with probability $1-p$). This scheme does not forbid self-
loops.

Defining $p_{s}(k,t)$ as the probability that a vertex $s$ has degree $k$ at
time $t$ as before, the dynamics can be represented by

$\displaystyle p_{s}(k,t+1)$ $\displaystyle=\omega_{\text{\tiny
WS}}(k|k-1)p_{s}(k-1,t)+$ $\displaystyle+\omega_{\text{\tiny
WS}}(k|k+1)p_{s}(k+1,t)+$ $\displaystyle+\omega_{\text{\tiny
WS}}(k|k)p_{s}(k,t),$ (6)

where $\omega_{\text{\tiny WS}}(k|m)$ represents the time-independent
transition rate of a vertex changing its degree from $m$ to $k$.

There are some different possible scenarios for a given vertex to change its
degree from $m$ to $k$ in a single time step:

  1. (i)

The degree of vertex $s$ changes from $k-1$ (at time $t$) to $k$ (at time
$t+1$). An edge end not connected to $s$ is chosen with probability
$1-\frac{k-1}{M}$, rewired with probability $p$ and connects to $s$ with
probability $\frac{1}{N}$. This gives

$\displaystyle\omega(k|k-1)=\frac{p}{N}\left(1-\frac{k-1}{M}\right);$ (7)

  2. (ii)

The degree of vertex $s$ changes from $k+1$ (at time $t$) to $k$ (at time
$t+1$). An edge end connected to $s$ is chosen with probability
$\frac{k+1}{M}$, rewired with probability $p$ and connects to a vertex other
than $s$ with probability $1-\frac{1}{N}$, resulting in

$\displaystyle\omega(k|k+1)=\frac{k+1}{M}p\left(1-\frac{1}{N}\right);$ (8)

  3. (iii)

The vertex $s$ has degree $k$ at time $t$ and neither gains or loses
connections. This is represented by the sum of some disjoint cases: (a) there
is no rewiring at all in the process with probability $1-p$, or (b) an edge
end connected to $s$ is chosen with probability $\frac{k}{M}$, rewired with
probability $p$ and connected again to $s$ with probability $\frac{1}{N}$; (c)
an edge end not connected to $s$ is chosen with probability $1-\frac{k}{M}$
and rewired (with probability $p$) to connect to a vertex othen than $s$ with
probability $1-1/N$. The sum of these probabilities results in

$\displaystyle\omega(k|k)$
$\displaystyle=\left(1-p\right)+p\frac{k}{M}\frac{1}{N}+p\left(1-\frac{k}{M}\right)\left(1-\frac{1}{N}\right)$
$\displaystyle=1-\frac{p}{N}\left(1+\frac{kN}{M}-\frac{2k}{M}\right).$ (9)

##  III Random walk in degree space

Considering that vertices, in general, gain or lose connections, one can look
at these changes in degree (of a specified vertex) as a one-dimensional random
walk in degree space CGCH17 . Furthermore, the mean time required by a vertex
to achieve a certain degree for the first time can be evaluated through a
parallel with the first-passage problem of random walks R07 ; KRBN10 .

In both models presented in the previous section, there are two important
symmetries. Firstly, the particular choice of a vertex $s$ is irrelevant, and
this parameter has no role in our work - except for remembering that we are
dealing with the time evolution of the degree of a given vertex.

The mean time $\langle t\rangle$ to achieve a certain degree $k$ for the first
time (starting from $k_{0}$ at time $t_{0}=0$) is given by

$\displaystyle\langle t\rangle=\sum_{t=0}^{\infty}tf_{s}(k,t|k_{0},0),$ (10)

where $f_{s}(k,t|k_{0},0)$ is the probability of vertex $s$ having degree $k$
for the first time at $t$, given that it had degree $k_{0}$ at time $t_{0}=0$.
This probability can be obtained from the discrete time version of the first-
passage process equation R07 ; KRBN10 , and can be cast as

$\displaystyle
p_{s}(k,t|k_{0},0)=\sum_{t^{\prime}=0}^{t}f_{s}(k,t^{\prime}|k_{0},0)p_{s}(k,t|k,t^{\prime}),$
(11)

which describes the probability $p_{s}(k,t|k_{0},0)$ of the vertex $s$ having
degree $k$ at time $t$ (not necessarily for the first time), given that it had
degree $k_{0}$ at time $t_{0}=0$. This is a sum of all disjoint probabilities
where the degree of the vertex achieves degree $k$ at time $t^{\prime}$ ($\leq
t$) for the first time, and then reaches degree $k$ again at instant $t$. The
initial condition $p_{s}(k,0|k_{0},0)=\delta_{k,k_{0}}$ is satisfied by
assuming $f_{s}(k,0|k_{0},0)=\delta_{k,k_{0}}$ (an extra term in (11)
associated to the initial condition is not required here as it is in the
continuous-time version R07 ; KRBN10  of the equation).

The second important symmetry of our models can be seen from the transitions
rates $\omega_{\text{\tiny ER}}$ and $\omega_{\text{\tiny WS}}$: they are
invariant under time translation. As a consequence,
$p_{s}(k,t|k^{\prime},t^{\prime})=p_{s}(k|k^{\prime};t-t^{\prime})$ and
$f_{s}(k,t|k^{\prime},t^{\prime})=f_{s}(k|k^{\prime};t-t^{\prime})$ depend on
the difference $t-t^{\prime}$ only. Therefore, equation (11) can be cast as

$\displaystyle
p_{s}(k|k_{0};t)=\sum_{t^{\prime}=0}^{t}f_{s}(k|k_{0};t^{\prime})p_{s}(k|k;t-t^{\prime}).$
(12)

As usual, the convolution product in (12) suggests the introduction of the
characteristic function

$\displaystyle p_{s}^{z}(k|k_{0};z)=\sum_{t=0}^{\infty}z^{t}p_{s}(k|k_{0};t)$
(13)

and a similar definition for the characteristic function of the function
$f_{s}$. Then, it is immediate that

$\displaystyle
f_{s}^{z}(k|k_{0};z)=\frac{p_{s}^{z}(k|k_{0};z)}{p_{s}^{z}(k|k;z)},$ (14)

and we can obtain $f_{s}^{z}$ from $p_{s}^{z}$. As stated before, this is a
consequence of the time-translation invariance; models that do not have this
symmetry (like the random recursive tree R80 ; P05  or Barabási-Albert network
BA99 ) do not display the form (12).

We are mainly interested in (14) because it provides some quantities of
interest. The first one is

$\displaystyle\mathcal{A}:=\lim_{z\rightarrow
1}f_{s}^{z}(k|k_{0};z)=\sum_{t=0}^{\infty}f_{s}(k|k_{0};t),$ (15)

which stands for the arriving probability of a vertex achieving degree $k$,
starting from degree $k_{0}$, at some time, while

$\displaystyle\langle t^{n}\rangle=\lim_{z\rightarrow
1}\,\left(z\partial_{z}\right)^{n}\,f_{s}^{z}(k|k_{0};z)=\sum_{t=0}^{\infty}t^{n}f_{s}(k|k_{0};t),$
(16)

where $\partial_{z}$ stands for the partial derivation in $z$ variable, shows
that the quantity $f_{s}^{z}$ is also useful to evaluate any moment of the
first-passage time. In this work, we are particularly interested in the first
and second moments, $\langle t\rangle$ and $\langle t^{2}\rangle$,
respectively; the latter is directly associated to the variance
$\sigma^{2}=\langle t^{2}\rangle-\langle t\rangle^{2}$.

Hence, one can also expand (14) as

$\displaystyle f_{s}^{z}(k|k_{0};z)=\mathcal{A}+\langle
t\rangle\left(z-1\right)+\left[\frac{\langle t^{2}\rangle-\langle
t\rangle}{2}\right]\left(z-1\right)^{2}+\cdots$ (17)

and obtain the desired quantites ($\mathcal{A}$, $\langle t\rangle$ and
$\langle t^{2}\rangle$) through this representation.

##  IV Results

In this section, we present the results for the first and second moments of
the first-passage time for both models.

###  IV.1 Time-dependent Erdős-Rényi model

The discrete time evolution for the dynamical version of Erdős-Rényi model,
introduced in section II, is given by (1). Introducing the characteristic
function

$\displaystyle p_{s}^{K}(K;t)=\sum_{k=0}^{\infty}K^{k}p_{s}(k|k_{0};t)$ (18)

into (1) leads to

$\displaystyle
p_{s}^{K}(K,t)=\left[1-p+p\,\left(\frac{K}{N}+1-\frac{1}{N}\right)^{2}\right]^{t}\,K^{k_{0}},$
(19)

where the initial condition $p_{s}(k|k_{0};0)=\delta_{k,k_{0}}$ or,
equivalently, $p_{s}^{K}(K;0)=K^{k_{0}}$ was adopted. From (18), the
probability $p_{s}(k|k_{0};t)$ is the coefficient of the term $K^{k}$ in the
series; therefore, expanding (19) and organizing the terms implies

$\displaystyle p_{s}(k|k_{0};t)$
$\displaystyle=\sum_{m=\left\lceil\frac{\Delta}{2}\right\rceil}^{t}{t\choose
m}{2m\choose\Delta}\left(1-p\right)^{t-m}p^{m}\times$
$\displaystyle\times\left(1-\frac{1}{N}\right)^{2m-\Delta}\frac{1}{N^{\Delta}}.$
(20)

From (20), the function $p_{s}$ depends on the difference $\Delta:=k-k_{0}$
only, and not on the initial and final degrees independently. This property is
propagated to the quantities of interest in this work.

Using (20), the characteristic function (in time variable) of $p_{s}$ is

$\displaystyle p_{s}^{z}(k|k_{0};z)=\sum_{t=0}^{\infty}z^{t}p_{s}(k|k_{0};t)$
$\displaystyle=\sum_{m=\left\lceil\frac{\Delta}{2}\right\rceil}^{\infty}{2m\choose\Delta}\left(1-\frac{1}{N}\right)^{2m-\Delta}\frac{1}{N^{\Delta}}\frac{\left(zp\right)^{m}}{\left[1-z\left(1-p\right)\right]^{m+1}},$

from which one can also evaluate $p_{s}^{z}(k|k;z)$ by taking $k_{0}=k$ (or
$\Delta=0$). Then, using the relation

$\displaystyle\sum_{m=\left\lceil\frac{\Delta}{2}\right\rceil}^{\infty}{2m\choose\Delta}x^{2m}=\frac{x^{\Delta}}{2}\Big{[}\left(1-x\right)^{-\Delta-1}+$
$\displaystyle+\left(-1\right)^{\Delta}\left(1+x\right)^{-\Delta-1}\Big{]}\quad(\Delta\in\mathbb{N},x\in(-1,1)\subset\mathbb{R}),$

which can be seen by combining the expansion of $(1\pm x)^{-\Delta-1}$ for
$|x|<1$, it is now possible to obtain the function $f_{s}^{z}(k|k_{0};z)$

$\displaystyle f_{s}^{z}(k|k_{0};z)$
$\displaystyle=\displaystyle\frac{1-\zeta^{2}}{2\left(N-1\right)^{\Delta}}\left[\frac{\zeta^{\Delta}}{\left(1-\zeta\right)^{\Delta+1}}+\frac{\left(-1\right)^{\Delta}\zeta^{\Delta}}{\left(1+\zeta\right)^{\Delta+1}}\right],$

where

$\displaystyle\zeta:=\zeta(z)=\left(1-\frac{1}{N}\right)\sqrt{\frac{zp}{1-z\left(1-p\right)}}.$
(24)

Expanding (LABEL:fz_ER) as in (17) is a tedious, but direct procedure. From
this operation, the arrival probability can be obtained as being

$\displaystyle\mathcal{A}_{\text{\tiny
ER}}=1-\frac{1}{2N}\left[1-\frac{\left(-1\right)^{\Delta}}{\left(2N-1\right)^{\Delta}}\right].$
(25)

Although the dynamics suggests that the vertex $s$ can achieve any larger
degree if one waits a sufficiently long time, the probability (25) is less
than one. However, this odd result is a consequence of the growing rule, which
allows a vertex to increase its degree by two units by forming a loop. In this
case, the targeted degree, $k$, may be surpassed from $k-1$ to $k+1$ without
being. For this reason, the arrival probability is not $1$. Nonetheless, if
one evaluates

$\displaystyle\sum_{t=0}^{\infty}f_{s}(\text{degree $\geq k$}|k_{0};t)=$
$\displaystyle=\displaystyle\sum_{t=0}^{\infty}\Big{[}f_{s}(k|k_{0};t)+\omega_{\text{\tiny
ER}}(k+1|k-1)p_{s}(k-1,t)\Big{]},$

which is a correction to (25), the arrival probability is $1$, as expected.
Note that the arrival probability (25) tends to $1$ with the size of the
network, which is expected since the loop becomes rare with the number of
vertices. One should also note that this result is valid for any positive
probability $p$ (the case $p=0$ is trivial), but does not depend explicitly on
this parameter. As shown below, this parameter scales the time elapsed until a
vertex reaches some degree for the first time, but it does not have any impact
on the probability of reaching the pre-established degree (except the trivial
case $p=0$, when $\mathcal{A}=0$ for $\Delta>0$).

The first and second time moments can also be derived from (LABEL:fz_ER). The
leading term of the mean first-passage time is

$\displaystyle\langle t\rangle_{\text{\tiny ER}}\simeq\frac{N\Delta}{2p}$ (27)

for $N\gg 1$, while the second moment is

$\displaystyle\langle t^{2}\rangle_{\text{\tiny
ER}}\simeq\left(\frac{N}{2p}\right)^{2}\Delta\left(\Delta+1\right).$ (28)

The variance can also be determined from (27) and (28), and depends
quadratically on $N/2p$, but linearly on the difference $\Delta:=k-k_{0}$ as
$\sigma^{2}_{\text{\tiny ER}}:=\langle t^{2}\rangle_{\text{\tiny ER}}-\langle
t\rangle_{\text{\tiny ER}}^{2}\simeq\left(\frac{N}{2p}\right)^{2}\Delta$. The
results (27) and (28) are supported by numerical simulations, as one can see
in figure (1).

Figure 1: The mean first (left) and second (right) moments of the first-
passage time as a function of the ratio $N/p$ for the dynamical version of the
Erdős-Rényi model with $k_{0}=2$ and $k=5$. The simulations used $100$ samples
and compared with the asymptotic results (27) and (28); the error bars are
smaller than the size of the points.

###  IV.2 Time-dependent Watts-Strogatz model

The analysis of the dynamical version of the Watts-Strogatz model is much more
intricate than the previous model. To convey better the ideas, all the
technical details are presented in the supplemental material, and we will
restrict ourselves to highlighting only the important points in this
subsection.

The dynamics of this model was already presented in (6), where the transition
rates are given in (7), (8) and (9). Introducing a characteritic function that
transforms both the degree and time variables (see (18) and (13)) into new
ones, the recurrence relation (6) can be converted into the differential
equation

$\displaystyle\frac{\partial}{\partial K}p_{s}^{Kz}(K,z)=$
$\displaystyle=-\frac{M}{p}\left(\frac{1-z^{-1}}{1-K}+\frac{1-p-z^{-1}}{N+K-1}\right)p_{s}^{Kz}(K,z)-$
$\displaystyle-\frac{Mz^{-1}}{p}\left(\frac{1}{1-K}+\frac{1}{N+K-1}\right)p_{s}^{K}(K,t=0).$
(29)

Using the normalization condition $p_{s}^{Kz}(K=1,z)=\frac{1}{1-z}$ and
assuming $N\gg 1$, the solution of (29) can be cast as

$\displaystyle p_{s}^{Kz}(K,z)$
$\displaystyle=\frac{Mz^{-1}}{p}\left(1-K\right)^{-M\alpha}e^{-c\left(1+\alpha\right)\left(1-K\right)}\times$
$\displaystyle\times\int_{K}^{1}\text{d}\xi
e^{c\left(1+\alpha\right)\left(1-\xi\right)}\left(1-\xi\right)^{M\alpha-1}p_{s}^{z}(\xi,t=0),$
(30)

where

$\displaystyle\alpha:=\frac{1}{p}\left(z^{-1}-1\right).$ (31)

Then, returning back to the degree variable by inverting the transform (18)
leads to

$\displaystyle p_{s}^{z}(k|m;z)$
$\displaystyle=\frac{1}{k!}\frac{\partial^{k}}{\partial
K^{k}}\Bigg{[}\frac{Mz^{-1}}{p}A_{\alpha}^{-1}(K)\times$
$\displaystyle\times\int_{K}^{1}\textup{d}\xi\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{m}\Bigg{]}_{K\rightarrow
0},$ (32)

for $m\in\\{k,k_{0}\\}$ and

$\displaystyle
A_{\alpha}(K):=e^{c\left(1+\alpha\right)\left(1-K\right)}\left(1-K\right)^{M\alpha}.$
(33)

The probability (32) is the key function to compute (14), which can be used to
evaluate some quantities of interest through (17). This procedure is not
direct as it was in the case of the dynamical Erdős-Rényi model and the
technicalities are exposed in the supplemental material. Here, we will show
the results only.

The arrival probability in this model is

$\displaystyle\mathcal{A}_{\text{\tiny WS}}=1,$ (34)

as expected. No anomalous behavior as seen in the previous model is present
here, where the degree changes by a single unit only.

The leading term of the first-passage time is

$\displaystyle\langle t\rangle_{\text{\tiny
WS}}\sim\left\\{\begin{array}[]{ccl}\displaystyle\frac{N}{p}e^{c}\sum_{n=k_{0}}^{k-1}\frac{\Gamma(n+1,c)}{c^{n}}&,&k>k_{0}\\\
&&\\\
\displaystyle\frac{N}{p}e^{c}\sum_{n=k}^{k_{0}-1}\frac{\gamma(n+1,c)}{c^{n}}&,&k<k_{0}\end{array}\right.,$
(38)

where $\Gamma(\cdot,\cdot)$ and $\gamma(\cdot,\cdot)$ are, respectively, the
upper and lower incomplete Gamma functions. It is worth mentioning that this
time is also proportional to $N/p$, as in the dynamical Erdős-Rényi model. The
simulation of this model supports the analytical expression (38), as shown in
figure 2.

Figure 2: The mean first-passage time as a function of the ratio $N/p$. Left:
$k_{0}=2$ and $k=5$; right: $k_{0}=5$ and $k=2$. In both graphs, the mean
degree of the network is $c=4$ and the results were obtained from $100$
samples; the error bar is smaller than the size of the points. These
simulations were compared with the analytical result (38).

On the other hand, the leading contribution to the second moment is given by

$\displaystyle\langle t^{2}\rangle_{\text{\tiny
WS}}\sim\left\\{\begin{array}[]{ccl}\displaystyle
2\left(\frac{N}{p}\right)^{2}e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\sum_{m=\ell}^{k-1}\frac{\Gamma(m+1,c)}{c^{m}}&,&k>k_{0}\\\
&&\\\ \displaystyle
2\left(\frac{N}{p}\right)^{2}e^{c}\sum_{n=k}^{k_{0}-1}\frac{n!}{c^{n}}\sum_{\ell=n+1}^{\infty}\frac{c^{\ell}}{\ell!}\sum_{m=k}^{\ell-1}\frac{\gamma(m+1,c)}{c^{m}}&,&k<k_{0}\\\
\end{array}\right.,$ (42)

and is proportional to $\left(N/p\right)^{2}$. The validity of (42) was tested
by comparing to simulation in figure 3. There is an alternative representation
of (42) in the supplemental material, but the form given here seems to be the
most compact one. Naturally, (42) and (38) can be used to compute the
variance, which is also proportional to $\left(N/p\right)^{2}$. Since this
expression shows no special aesthetic appeal, it will not be presented here.

Figure 3: The (mean) second moment of the first-passage time as a function of
the ratio $N/p$. Left: $k_{0}=2$ and $k=5$; right: $k_{0}=5$ and $k=2$. In
both graphs, the mean degree of the network is $c=4$ and the results were
obtained from $100$ samples; the error bar is smaller than the size of the
points. These simulations were compared with the analytical result (42).

##  V Conclusion

In this work, we investigated the time needed for a vertex to achieve a pre-
established degree for the first time. The main strategy was mapping the
problem into a first-passage problem in degree space. The gain/loss of degrees
was illustrated by the time-dependent version of the Erdős-Rényi and Watts-
Strogatz models, which display time-translational symmetry. This property was
explored and analytical results concerning the first and second moments of the
first-passage time were obtained. In both cases, the arrival probability
ensured that the pre-established degree is achieved with probability $1$ (with
a careful interpretation in the case of the Erdős-Rényi dynamics).
Furthermore, the mean first-passage time is scaled linearly with the ratio
$N/p$ for both models in the asymptotic regime of large networks, while this
scale is quadratic for the second moment also in both models. On the other
hand, these moments depend on the difference $\Delta$ in the Erdős-Rényi
network only. In the dynamical Watts-Strogatz model, both moments depend on
the initial and final degrees independently, as can be seen from (38) and
(42), although the structure of both $\langle t\rangle_{\text{\tiny WS}}$ and
$\langle t^{2}\rangle_{\text{\tiny WS}}$ can be compactly represented as a sum
of terms involving upper (lower) incomplete Gamma functions when the final
degree is larger (smaller) than the initial one.

## Acknowledgments

F.A. was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de
Nível Superior - Brasil (CAPES) - Finance Code 001.

## References

  * (1) R. Albert and A. -L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  * (2) S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks (Oxford University Press, Oxford, 2013).
  * (3) M. E. J. Newman, Networks (Oxford University Press, Oxford, 2010).
  * (4) L. A. N. Amaral, A. Scala, M. Barthélémy and H. E. Stanley, Proc. Natl. Acad. Sci. 97, 11149 (2000).
  * (5) M. O. Hase and H. L. Casa Grande, J. Stat. Mech. (2016) P043304.
  * (6) P. Upham, C. Thomas, D. Gillingwater, D. Raper, J. Air Transp. Manag. 9, 145 (2003).
  * (7) H. L. Casa Grande, M. Cotacallapa and M. O. Hase, Phys. Rev. E 95, 012321 (2017).
  * (8) L. Rayleigh, Phil. Mag. 10, 73 (1880).
  * (9) K. Pearson, Nature 72, 294 (1905).
  * (10) S. Redner, A Guide to First-Passage Processes (Cambridge University Press, New York, 2007).
  * (11) P. L. Krapivsky, S. Redner and E. Ben-Naim, A Kinetic View of Statistical Physics (Cambridge University Press, New York, 2010).
  * (12) G. Pólya, Math. Ann. 84, 149 (1921).
  * (13) E. W. Montroll and G. H. Weiss, J. Math. Phys. 2, 167 (1965).
  * (14) D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998).
  * (15) P. Erdős and A. Rényi, Publ. Math. (Debrecen) 6, 290 (1959).
  * (16) H. S. Na and A. Rapoport, Math. Biosci. 6, 313 (1970).
  * (17) A. -L. Barabási and R. Albert, Science 286, 509 (1999).
  * (18) R. Oste and J Van der Jeugt, Electron. J. Combin. 22, P2.8 (2015)

##  VI Supplemental material

The next sections provide the details to obtain the first and second moments
of the first-passage distribution of the dynamical Watts-Strogatz model. For
convenience, some definitions and results from the main text are repeated
here.

##  VII First-passage function

The starting point is the recurrence relation

$\displaystyle p_{s}(k,t+1)=\omega_{\text{\tiny
WS}}(k|k-1)p_{s}(k-1,t)+\omega_{\text{\tiny
WS}}(k|k+1)p_{s}(k+1,t)+\omega_{\text{\tiny WS}}(k|k)p_{s}(k,t),$ (S1)

where $p_{s}(k,t)$ is the probability of the vertex $s$ having degree $k$ at
time $t$ and $\omega_{\text{\tiny WS}}(k|m)$ is the conditional probability of
a vertex of degree $m$ change to a state of degree $k$. For the dynamical
version of the Watts-Strogatz model, these probabilities are

$\displaystyle\omega_{\text{\tiny
WS}}(k|k-1)=\left(1-\frac{k-1}{M}\right)\frac{p}{N},\quad\omega_{\text{\tiny
WS}}(k|k+1)=\frac{k+1}{M}\left(1-\frac{1}{N}\right)p,\quad\textnormal{ and
}\quad\omega_{\text{\tiny
WS}}(k|k)=1+p\left(\frac{2k}{MN}-\frac{1}{N}-\frac{k}{M}\right),$ (S2)

as shown in the main text. Here, $p$ is the linking probability, and $N$ and
$M$ are the total number of vertices and degrees, respectively, related by

$\displaystyle M=cN,$ (S3)

where $c$ is the mean degree of the Watts-Strogatz network. From the discrete
Laplace transforms

$\displaystyle
p_{s}^{K}(K,t)=\sum_{k=0}^{\infty}K^{k}p_{s}(k,t)\quad\textnormal{ and }\quad
p_{s}^{Kz}(K,z)=\sum_{t=0}^{\infty}z^{t}p_{s}^{K}(K,t),$ (S4)

the recurrence relation (S1) can be cast as

$\displaystyle\partial_{K}p_{s}^{Kz}(K,t)=-\frac{M}{p}\left(\frac{1-z^{-1}}{1-K}+\frac{1-p-z^{-1}}{N+K-1}\right)p_{s}^{Kz}(K,z)-\frac{Mz^{-1}}{p}\left(\frac{1}{1-K}+\frac{1}{N+K-1}\right)p_{s}^{K}(K,t=0).$
(S5)

Using the boundary condition $p_{s}^{Kz}(1,z)=(1-z)^{-1}$, which is the
normalization condition, the solution of the differential equation (S5) is

$\displaystyle
p_{s}^{Kz}(K,t)=\frac{MNz^{-1}}{p}\frac{\left(N+K-1\right)^{M\left(\alpha+1\right)}}{\left(1-K\right)^{M\alpha}}\int_{K}^{1}\textup{d}\xi\,\frac{\left(1-\xi\right)^{M\alpha-1}}{\left(N+\xi-1\right)^{M\alpha+M+1}}p_{s}^{K}(\xi,t=0),$
(S6)

where

$\displaystyle\alpha:=\frac{1}{p}\left(z^{-1}-1\right).$ (S7)

Since

$\displaystyle\left(N+K-1\right)^{M\alpha+M}=N^{M\left(\alpha+1\right)}e^{-c\left(\alpha+1\right)\left(1-K\right)}\left[1+\mathcal{O}(N^{-1})\right],$
(S8)

the Laplace-transformed degree distribution (S6) equals

$\displaystyle
p_{s}^{Kz}(K,t)=\frac{Mz^{-1}}{p}\left(1-K\right)^{-M\alpha}e^{-c\left(\alpha+1\right)\left(1-K\right)}\int_{K}^{1}\textup{d}\xi\,\left(1-\xi\right)^{M\alpha-1}e^{c\left(\alpha+1\right)\left(1-\xi\right)}p_{s}^{K}(\xi,t=0),$
(S9)

except for terms which are $\mathcal{O}(N^{-1})$ times smaller.

Defining

$\displaystyle
A_{\alpha}(K):=e^{c\left(1+\alpha\right)\left(1-K\right)}\left(1-K\right)^{M\alpha},$
(S10)

and taking the inverse Laplace transformation in the first argument of
$P^{Kz}(K,z)$ through

$\displaystyle p_{s}^{z}(k,z)=\frac{1}{k!}\lim_{K\rightarrow
0}\frac{\textup{d}^{k}}{\textup{d}K^{k}}p_{s}^{Kz}(K,z)$ (S11)

leads to

$\displaystyle p_{s}^{z}(k,z)=\frac{1}{k!}\lim_{K\rightarrow
0}\frac{\textup{d}^{k}}{\textup{d}K^{k}}\left[\frac{Mz^{-1}}{p}A_{\alpha}^{-1}(K)\int_{K}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)P^{K}(\xi,t=0)\right].$
(S12)

One should keep in mind that the expression above for $p_{s}^{z}$ denpends on
the initial condition of $p_{s}^{K}$ at time $t=0$. If the network starts with
degree $m$, one has $p_{s}^{K}(\xi,t=0)=\xi^{m}$, which implies

$\displaystyle p_{s}^{z}(k|m;z)=\frac{1}{k!}\lim_{K\rightarrow
0}\frac{\textup{d}^{k}}{\textup{d}K^{k}}\left[\frac{Mz^{-1}}{p}A_{\alpha}^{-1}(K)\int_{K}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{m}\right],$
(S13)

and a new notation, $p_{s}^{z}(k|m;z)$, was introduced to make clear the
initial degree. Then, the key function $f_{s}^{z}$ defined in the main text
can be cast as

$\displaystyle
f_{s}^{z}(k|k_{0};z)=\frac{p_{s}^{z}(k|k_{0};z)}{p_{s}^{z}(k|k;z)}=\frac{\frac{\textup{d}^{k}}{\textup{d}K^{k}}\left[A_{\alpha}^{-1}(K)\int_{K}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k_{0}}\right]_{K\rightarrow
0}}{\frac{\textup{d}^{k}}{\textup{d}K^{k}}\left[A_{\alpha}^{-1}(K)\int_{K}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k}\right]_{K\rightarrow
0}}.$ (S14)

The main point investigated is the following: given a vertex of the network
(with $N$ vertices and total degree $M=cN$, where $c$ is the mean degree) with
degree $k_{0}$, one is interested in the time needed to it reach degree $k$
for the first time.

For $\lambda\in\\{k_{0},k\\}$, and expanding the multiple derivatives in (S14)
leads to

$\displaystyle\frac{\textup{d}^{k}}{\textup{d}K^{k}}\left[A_{\alpha}^{-1}(K)\int_{K}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}\right]_{K\rightarrow
0}$ $\displaystyle=\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(k)}\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}+$
$\displaystyle+\theta(k-1)\sum_{\ell=1}^{k}{k\choose\ell}\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(k-\ell)}\left[\int_{K}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}\right]_{K\rightarrow
0}^{(\ell)},$ (S15)

where $f^{(n)}$ stands for the $n$th derivative of $f$ and

$\displaystyle\theta(x)=\left\\{\begin{array}[]{ccl}1&,&x\geq 0\\\
0&,&x<0\end{array}\right.$ (S18)

is the unit step funtion. Although the introduction of this function is
redundant (for instance, one might define $\sum_{\ell=1}^{0}(\cdots)$ to be
zero in (S15)), it helps to keep in mind the range of the variables that
produces nonzero contributions. This is particularly useful in later
calculations where many of such constraints appear.

One should note that

$\displaystyle\left[\int_{K}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}\right]_{K\rightarrow
0}^{(\ell)}$
$\displaystyle=\left[-\left(1-K\right)^{-1}A_{\alpha}(K)K^{\lambda}\right]_{K\rightarrow
0}^{(\ell-1)}$
$\displaystyle=\left\\{\begin{array}[]{ccl}0&,&\lambda>\ell-1\\\ &&\\\
-\lambda!\theta(\ell-1-\lambda){\ell-1\choose\lambda}\left[\left(1-K\right)^{-1}A_{\alpha}(K)\right]_{K\rightarrow
0}^{(\ell-1-\lambda)}&,&\lambda\leq\ell-1\end{array}\right.,$ (S22)

where the factor $\theta(\ell-1-\lambda)$ is a reminder that the condition
$\lambda\leq\ell-1$ should be satisfied to generate a nonzero result.

From (S22), the expression (S14) can be written as

$\displaystyle f_{s}^{z}(k|k_{0};z)$
$\displaystyle=\frac{\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k_{0}}}{\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k}}-$
$\displaystyle-\theta(k-1)\frac{\sum_{\ell=1}^{k}{k\choose\ell}\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(k-\ell)}k_{0}!\theta(\ell-1-k_{0}){\ell-1\choose
k_{0}}\left[\left(1-K\right)^{-1}A_{\alpha}(K)\right]_{K\rightarrow
0}^{(\ell-1-k_{0})}}{\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(k)}\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k}}$
$\displaystyle=\frac{\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k_{0}}}{\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k}}-$
$\displaystyle-\theta(k-1)\theta(k-k_{0}-1)\frac{\sum_{\ell=k_{0}+1}^{k}{k\choose\ell}\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(k-\ell)}k_{0}!{\ell-1\choose
k_{0}}\left[\left(1-K\right)^{-1}A_{\alpha}(K)\right]_{K\rightarrow
0}^{(\ell-1-k_{0})}}{\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(k)}\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k}}.$
(S23)

From now on, the notation

$\displaystyle\Delta:=k-k_{0}$ (S24)

will be adopted. Therefore, from
$\theta(k-1)\theta(k-k_{0}-1)=\theta(k-k_{0}-1)=\theta(\Delta-1)$, one has

$\displaystyle f_{s}^{z}(k|k_{0};z)$
$\displaystyle=\frac{\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k_{0}}}{\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k}}-$
$\displaystyle-\theta(\Delta-1)\frac{\sum_{\ell=k_{0}+1}^{k}{k\choose\ell}{\ell-1\choose
k_{0}}k_{0}!\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(k-\ell)}\left[\left(1-K\right)^{-1}A_{\alpha}(K)\right]_{K\rightarrow
0}^{(\ell-1-k_{0})}}{\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(k)}\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{k}}.$
(S25)

##  VIII Some key functions

In this section, the behavior of the following functions will be examined.

  1. (i)

$\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}$,
$\lambda\in\\{k_{0},k\\}$

  2. (ii)

$\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow 0}^{(n)}$

  3. (iii)

$\left[\left(1-K\right)^{-1}A_{\alpha}(K)\right]_{K\rightarrow 0}^{(n)}$

The asymptotic behavior of these three functions for small $\alpha$ will be
considered. The first and second-order terms in $\alpha$ are directly related
to the first and second first-passage time moments.

###  VIII.1 The function
$\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}$,
$\lambda\in\\{k_{0},k\\}$

Integrating
$\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}$
($\lambda\in\\{k_{0},k\\}$ and $A_{\alpha}$ given by (S10)) by parts yields

$\displaystyle\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}=\frac{1}{M\alpha}\left\\{\delta_{\lambda,0}e^{c\left(1+\alpha\right)}+\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{M\alpha}e^{c\left(1+\alpha\right)\left(1-\xi\right)}\xi^{\lambda-1}\left[\lambda-c\xi\left(1+\alpha\right)\right]\right\\},$
(S26)

where $\delta_{m,n}$ stands for the Kronecker delta, defined by

$\displaystyle\delta_{m,n}=\left\\{\begin{array}[]{ccl}1&,&m=n\\\ 0&,&m\neq
n\end{array}\right..$ (S29)

By expanding the expression inside the brace in (S26) for $\alpha\sim 0$ leads
to

$\displaystyle\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}=$
$\displaystyle=\frac{1}{M\alpha}\Bigg{\\{}e^{c}\delta_{\lambda,0}+\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda-1}\left(\lambda-c\xi\right)+$
$\displaystyle+\alpha
ce^{c}\delta_{\lambda,0}+\alpha\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda-1}\left[M\left(\lambda-c\xi\right)\ln\left(1-\xi\right)+c\left(\lambda-c\xi\right)\left(1-\xi\right)-c\xi\right]+$
$\displaystyle+\alpha^{2}\frac{c^{2}e^{c}}{2}\delta_{\lambda,0}+\alpha^{2}\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda-1}\Bigg{[}\frac{M^{2}}{2}\left(\lambda-c\xi\right)\ln^{2}\left(1-\xi\right)+Mc\left(\lambda-c\xi\right)\left(1-\xi\right)\ln\left(1-\xi\right)-$
$\displaystyle-
Mc\xi\ln\left(1-\xi\right)+\frac{c^{2}}{2}\left(\lambda-c\xi\right)\left(1-\xi\right)^{2}-c^{2}\xi\left(1-\xi\right)\Bigg{]}+\mathcal{O}(\alpha^{3})\Bigg{\\}}.$
(S30)

Defining

$\displaystyle\left\\{\begin{array}[]{ccl}\Omega_{1}(\lambda)&:=&\displaystyle\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda-1}\left(\lambda-c\xi\right)\ln\left(1-\xi\right)\\\
&&\\\
\Omega_{2}(\lambda)&:=&\displaystyle\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda-1}\left(\lambda-c\xi\right)\ln^{2}\left(1-\xi\right)\end{array}\right.\quad(n\in\\{1,2\\})$
(S34)

and from the relation

$\displaystyle\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{m}=m!c^{-m-1}\left(e^{c}-\sum_{\ell=0}^{m}\frac{c^{\ell}}{\ell!}\right)=m!c^{-m-1}\sum_{\ell=m+1}^{\infty}\frac{c^{\ell}}{\ell!},\quad(m\in\\{0,1,2,\ldots\\}),$
(S35)

one can cast (S30) as

$\displaystyle\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}$
$\displaystyle=\frac{1}{M\alpha}\Bigg{[}1+\alpha
M\Omega_{1}(\lambda)+\frac{\alpha^{2}M^{2}}{2}\Omega_{2}(\lambda)+\alpha^{2}Mc\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda-1}\left(\lambda-c\xi\right)\left(1-\xi\right)\ln\left(1-\xi\right)-$
$\displaystyle-\alpha^{2}Mc\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda}\ln\left(1-\xi\right)+\mathcal{O}(\alpha^{3})\Bigg{]}.$
(S36)

after some lengthy (but direct) calculations. Integrating the last integral in
(S36),
$\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda}\ln\left(1-\xi\right)$,
by parts (choosing the resulting integral to be composed by the antiderivative
of $\ln\left(1-\xi\right)$ and derivative of
$e^{c\left(1-\xi\right)}\xi^{\lambda}$), the term associated to $\alpha^{2}$
is simplified. Using (S35) again, one can finally state that

$\displaystyle\int_{0}^{1}\textup{d}\xi\,\left(1-\xi\right)^{-1}A_{\alpha}(\xi)\xi^{\lambda}=\frac{1}{M\alpha}\Bigg{\\{}1+\alpha
M\Omega_{1}(\lambda)+\frac{\alpha^{2}M^{2}}{2}\Omega_{2}(\lambda)+\alpha^{2}Mc\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda-1}+\mathcal{O}(\alpha^{3})\Bigg{\\}}.$
(S37)

###  VIII.2 The function $\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(n)}$

From the definition (S10) of $A_{\alpha}$,

$\displaystyle\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow 0}^{(n)}$
$\displaystyle=\sum_{\ell=0}^{n}{n\choose\ell}\Big{[}e^{-c\left(1+\alpha\right)\left(1-K\right)}\Big{]}_{K\rightarrow
0}^{(n-\ell)}\Big{[}\left(1-K\right)^{-M\alpha}\Big{]}_{K\rightarrow
0}^{(\ell)}$
$\displaystyle=\sum_{\ell=0}^{n}{n\choose\ell}e^{-c\left(1+\alpha\right)}\left[c\left(1+\alpha\right)\right]^{n-\ell}\frac{\Gamma(M\alpha+\ell)}{\Gamma(M\alpha)}$
$\displaystyle=\left[c\left(1+\alpha\right)\right]^{n}e^{-c\left(1+\alpha\right)}+\theta(n-1)\sum_{\ell=1}^{n}{n\choose\ell}e^{-c\left(1+\alpha\right)}\left[c\left(1+\alpha\right)\right]^{n-\ell}\left(M\alpha\right)\cdots\left(M\alpha+\ell-1\right),$
(S38)

where the sum was splitted in the $\ell=0$ term and the $\ell>0$ ones. Again,
the factor $\theta(n-1)$ was introduced as a reminder that the last sum is
nonzero for $n\geq 1$ only. Expanding (S38) for small $\alpha$ leads to

$\displaystyle\left[A_{\alpha}^{-1}(K)\right]_{K\rightarrow
0}^{(n)}=c^{n}e^{-c}+\alpha\left(n-c\right)c^{n}e^{-c}+\alpha
Me^{-c}\theta(n-1)n!\sum_{\ell=0}^{n-1}\frac{c^{\ell}}{\ell!}\frac{1}{n-\ell}+\mathcal{O}(\alpha^{2}).$
(S39)

There is no need to determine exactly the second-order term in this case, as
it will be seen later.

###  VIII.3 The function
$\left[\left(1-K\right)^{-1}A_{\alpha}(K)\right]_{K\rightarrow 0}^{(n)}$

One may first expand $\left(1-K\right)^{-1}A_{\alpha}(K)$ in power of $\alpha$
first, which leads to

$\displaystyle\left[\left(1-K\right)^{-1}A_{\alpha}(K)\right]_{K\rightarrow
0}^{(n)}=\left[e^{c\left(1-K\right)}\left(1-K\right)^{-1}+\alpha
ce^{c\left(1-K\right)}+\alpha
Me^{c\left(1-K\right)}\left(1-K\right)^{-1}\ln\left(1-K\right)\right]_{K\rightarrow
0}^{(n)}+\mathcal{O}(\alpha^{2}).$ (S40)

Then, from

$\displaystyle\left[e^{c\left(1-K\right)}\left(1-K\right)^{-1}\right]_{K\rightarrow
0}^{(n)}=\sum_{\ell=0}^{n}{n\choose\ell}\left[e^{c\left(1-K\right)}\right]_{K\rightarrow
0}^{(n-\ell)}\left[\left(1-K\right)^{-1}\right]_{K\rightarrow
0}^{(\ell)}=n!e^{c}\sum_{u=0}^{n}\frac{\left(-c\right)^{u}}{u!}$ (S41)

and $\left[\ln\left(1-K\right)\right]_{K\rightarrow
0}^{(r)}=-\theta(r-1)(r-1)!$, one has

$\displaystyle\left[\left(1-K\right)^{-1}A_{\alpha}(K)\right]_{K\rightarrow
0}^{(n)}=n!e^{c}\sum_{\ell=0}^{n}\frac{\left(-c\right)^{\ell}}{\ell!}+\alpha\left[ce^{c}\left(-c\right)^{n}-Mn!e^{c}\theta(n-1)\sum_{\ell=0}^{n-1}\frac{1}{n-\ell}\sum_{m=0}^{\ell}\frac{\left(-c\right)^{m}}{m!}\right]+\mathcal{O}(\alpha^{2}).$
(S42)

##  IX Expansion of the first-passage function

One should now insert (S37), (S39) and (S42) into (S25), and expanding the
resulting expression in $\alpha$. After a lengthy (but direct) calculation, it
leads to

$\displaystyle f_{s}^{z}(k|k_{0};z)=1+\alpha
L(k,k_{0})+\alpha^{2}Q(k,k_{0})+\mathcal{O}(\alpha^{3}),$ (S43)

where the coeficients of the linear and quadratic terms are given,
respectively, by

$\displaystyle L(k,k_{0})$
$\displaystyle:=M\left[\Omega_{1}(k_{0})-\Omega_{1}(k)\right]-M\theta(\Delta-1)e^{c}\sum_{\ell=k_{0}+1}^{k}\frac{k!}{\left(k-\ell\right)!}\frac{c^{-\ell}}{\ell}\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}$
$\displaystyle=M\left[\Omega_{1}(k_{0})-\Omega_{1}(k)\right]-M\theta(\Delta-1)k!e^{c}\sum_{\ell=0}^{\Delta-1}\frac{c^{\ell-k}}{\ell!}\frac{1}{k-\ell}\sum_{m=0}^{\Delta-1-\ell}\frac{\left(-c\right)^{m}}{m!},$
(S44)

where the change of variable $\ell\rightarrow k-\ell$ was performed in the
last passage, and

$\displaystyle Q(k,k_{0})$
$\displaystyle:=M^{2}\left[\frac{1}{2}\Omega_{2}(k_{0})-\frac{1}{2}\Omega_{2}(k)+\Omega_{1}^{2}(k)-\Omega_{1}(k_{0})\Omega_{1}(k)\right]+Mc\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\left(\xi^{k_{0}}-\xi^{k}\right)+$
$\displaystyle+Me^{c}c^{-k}\theta(\Delta-1)\sum_{\ell=k_{0}+1}^{k}\frac{k!}{\left(k-\ell\right)!\ell}\Bigg{\\{}\frac{c^{k-\ell}\left(-c\right)^{\ell-
k_{0}}}{\left(\ell-1-k_{0}\right)!}+\ell
c^{k-\ell}\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}+$
$\displaystyle+M\Omega_{1}(k)c^{k-\ell}\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}-M\left(k-\ell\right)!\theta(k-\ell-1)\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{k-\ell-1}\frac{c^{q}}{q!}\frac{1}{k-\ell-q}+$
$\displaystyle+Mc^{k-\ell}\theta(\ell-2-k_{0})\sum_{m=0}^{\ell-2-k_{0}}\frac{1}{\ell-1-k_{0}-m}\sum_{q=0}^{m}\frac{\left(-c\right)^{q}}{q!}+Mc^{-\ell}k!\theta(k-1)\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}\Bigg{\\}}.$
(S45)

From now on, the behavior of the coefficients $L(k,k_{0})$ and $Q(k,k_{0})$ is
analyzed. In the next section, some useful relations are presented to deal
with this task.

##  X Some useful relations

For any positive $u>0$, the relations

$\displaystyle\frac{1}{u}=\int_{1}^{\infty}\textup{d}x\,x^{-u-1}$ (S46)

and

$\displaystyle\frac{1}{u^{\alpha}}=\frac{1}{\Gamma(\alpha)}\int_{0}^{\infty}\textup{d}x\,e^{-ux}x^{\alpha-1}\qquad(\alpha>0)$
(S47)

will be used extensively, as well as the relations

$\displaystyle\sum_{n=0}^{a}\frac{x^{n}}{n!}=\frac{e^{x}\Gamma(a+1,x)}{a!}\quad\textnormal{
and
}\quad\sum_{n=a+1}^{\infty}\frac{x^{n}}{n!}=\frac{e^{x}\gamma(a+1,x)}{a!},$
(S48)

where $a$ is a non-negative integer number and $x\in\mathbb{R}$. Furthermore,
$\Gamma$ and $\gamma$ are the (upper and lower, respectively) incomplete Gamma
functions, defined as

$\displaystyle\Gamma(n,x):=\int_{x}^{\infty}\textup{d}t\,e^{-t}t^{n-1}\quad\textnormal{
and }\quad\gamma(n,x):=\int_{0}^{x}\textup{d}t\,e^{-t}t^{n-1},$ (S49)

and satisfy

$\displaystyle\Gamma(n,x)+\gamma(n,x)=\Gamma(n).$ (S50)

Both expressions in (S48) can be obtained by integrating the incomplete Gamma
functions by part repeatedly. The incomplete Gamma functions also satisfy

$\displaystyle\Gamma(n+1,x)=n\Gamma(n,x)+x^{n}e^{-x}\quad\textnormal{ and
}\quad\gamma(n+1,x)=n\gamma(n,x)-x^{n}e^{-x}.$ (S51)

Defining

$\displaystyle\psi(\lambda):=\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\xi^{\lambda}\ln\left(1-\xi\right)$
(S52)

for non-negative integer $\lambda$, one can see, from the definition (S34),
that

$\displaystyle\Omega_{1}(\lambda)=\lambda\psi(\lambda-1)-c\psi(\lambda),$
(S53)

where the arguments are taken to be non-negative. Inverting this recurrence
relation yields

$\displaystyle-\frac{c^{\lambda+1}}{\lambda!}\psi(\lambda)=\sum_{n=0}^{\lambda}\frac{c^{n}}{n!}\Omega_{1}(n).$
(S54)

By letting $\lambda\rightarrow\infty$, (S54) implies

$\displaystyle\sum_{n=0}^{\infty}\frac{c^{n}}{n!}\Omega_{1}(n)=0.$ (S55)

Another important relation is obtained by Taylor-expanding the logarithmic
term in (S34) and invoking (S35), which allows one to derive

$\displaystyle\Omega_{1}(a)-\Omega_{1}(b)=e^{c}\sum_{n=a}^{b-1}\frac{\gamma(n+1,c)}{c^{n+1}}\qquad(\textnormal{$a,b\in\\{0,1,2,\ldots\\}\subset\mathbb{Z}$
and $a<b$}).$ (S56)

There is also a relation involving differences of $\Omega_{2}$ functions.
Firstly, expanding both logarithms in $\Omega_{2}$ defined in (S34) and using
(S35), (S48) and (S49) yields

$\displaystyle\Omega_{2}(\lambda)=\sum_{n,m=1}^{\infty}\left[\frac{1}{nm}-\left(\frac{n+m}{nm}\right)\int_{0}^{1}\textup{d}u\,e^{c\left(1-u\right)}u^{\lambda+n+m-1}\right].$
(S57)

Note that the expression inside the square brackets is symmetric with respect
to $n$ and $m$, but it is not possible to split into two terms because the sum
over each term diverges. Let $a,b\in\\{0,1,2,\ldots\\}\subset\mathbb{Z}$ with
$a<b$. Taking into account the symmetry between $n$ and $m$ in the sum (S57),
one has

$\displaystyle\frac{1}{2}\left[\Omega_{2}(a)-\Omega_{2}(b)\right]=\sum_{n,m=1}^{\infty}\frac{1}{n}\int_{0}^{1}\textup{d}u\,e^{c\left(1-u\right)}u^{n+m-1}\left(u^{b}-u^{a}\right)=\int_{0}^{1}\textup{d}u\,e^{c\left(1-u\right)}\left(\frac{u^{b}-u^{a}}{1-u}\right)\ln\left(1-u\right)\qquad(a<b).$
(S58)

This formula can also be cast as

$\displaystyle\frac{1}{2}\left[\Omega_{2}(a)-\Omega_{2}(b)\right]=\sum_{n=a}^{b-1}\int_{0}^{1}\textup{d}u\,e^{c\left(1-u\right)}u^{n}\ln\left(1-u\right)=\sum_{n=a}^{b-1}\psi(n),$
(S59)

where $a<b$ and $\psi$ is defined in (S52).

In the next sections, the following integral is recurrent:

$\displaystyle\int_{0}^{\infty}\textup{d}x\,e^{-\alpha
x}x^{\beta}\int_{0}^{\infty}\textup{d}y\,e^{y\left(1-x\right)}\int_{y}^{\infty}\textup{d}z\,e^{-z}z^{\gamma}\qquad(\alpha,\beta,\gamma>0\textnormal{
and }\beta>\gamma).$ (S60)

This integral shows an “apparent singularity”, which can be circumvented by a
suitable procedure. Splitting the integral into two parts,

$\displaystyle\int_{0}^{\infty}\textup{d}x\,e^{-\alpha
x}x^{\beta}\int_{0}^{\infty}\textup{d}y\,e^{y\left(1-x\right)}\int_{y}^{\infty}\textup{d}z\,e^{-z}z^{\gamma}$
$\displaystyle=\int_{0}^{1}\textup{d}x\,e^{-\alpha
x}x^{\beta}\int_{0}^{\infty}\textup{d}y\,e^{y\left(1-x\right)}\int_{y}^{\infty}\textup{d}z\,e^{-z}z^{\gamma}+$
$\displaystyle+\int_{1}^{\infty}\textup{d}x\,e^{-\alpha
x}x^{\beta}\int_{0}^{\infty}\textup{d}y\,e^{y\left(1-x\right)}\int_{y}^{\infty}\textup{d}z\,e^{-z}z^{\gamma},$
(S61)

and changing the order of integration through
$\int_{0}^{\infty}\textup{d}y\int_{y}^{\infty}\textup{d}z\,\left(\cdots\right)=\int_{0}^{\infty}\textup{d}z\int_{0}^{z}\textup{d}y\,\left(\cdots\right)$
leads to

$\displaystyle\int_{0}^{\infty}\textup{d}x\,e^{-\alpha
x}x^{\beta}\int_{0}^{\infty}\textup{d}y\,e^{y\left(1-x\right)}\int_{y}^{\infty}\textup{d}z\,e^{-z}z^{\gamma}=$
$\displaystyle=\int_{0}^{1}\textup{d}x\,e^{-\alpha
x}x^{\beta}\int_{0}^{\infty}\textup{d}z\,e^{-z}z^{\gamma}\int_{0}^{z}\textup{d}y\,e^{y\left(1-x\right)}+\int_{1}^{\infty}\textup{d}x\,e^{-\alpha
x}x^{\beta}\int_{0}^{\infty}\textup{d}z\,e^{-z}z^{\gamma}\int_{0}^{z}\textup{d}y\,e^{y\left(1-x\right)}$
$\displaystyle=\int_{0}^{1}\textup{d}x\,e^{-\alpha
x}\frac{x^{\beta}}{1-x}\int_{0}^{\infty}\textup{d}z\,z^{\gamma}\left(e^{-zx}-e^{-z}\right)+\int_{1}^{\infty}\textup{d}x\,e^{-\alpha
x}\frac{x^{\beta}}{1-x}\int_{0}^{\infty}\textup{d}z\,z^{\gamma}\left(e^{-zx}-e^{-z}\right)$
$\displaystyle=\int_{0}^{1}\textup{d}x\,e^{-\alpha
x}\frac{x^{\beta}}{1-x}\left[\Gamma(\gamma+1)\left(\frac{1}{x^{\gamma+1}}-1\right)\right]+\int_{1}^{\infty}\textup{d}x\,e^{-\alpha
x}\frac{x^{\beta}}{1-x}\left[\Gamma(\gamma+1)\left(\frac{1}{x^{\gamma+1}}-1\right)\right]$
$\displaystyle=\Gamma(\gamma+1)\sum_{n=\beta-\gamma-1}^{\beta-1}\left[\int_{0}^{1}\textup{d}x\,e^{-\alpha
x}x^{n}+\int_{1}^{\infty}\textup{d}x\,e^{-\alpha x}n^{n}\right].$ (S62)

Then,

$\displaystyle\int_{0}^{\infty}\textup{d}x\,e^{-\alpha
x}x^{\beta}\int_{0}^{\infty}\textup{d}y\,e^{y\left(1-x\right)}\int_{y}^{\infty}\textup{d}z\,e^{-z}z^{\gamma}=\Gamma(\gamma+1)\sum_{n=\beta-\gamma-1}^{\beta-1}\frac{\Gamma(n+1)}{\alpha^{n+1}}\qquad(\alpha,\beta,\gamma>0\textnormal{
and }\beta>\gamma).$ (S63)

##  XI The coefficient of the linear term - $L(k,k_{0})$

In this section, the last term of (S44) is analyzed. Since this term is
associated with the factor $\theta(\Delta-1)$, it is assumed that $\Delta$ is
a positive integer. Then,

$\displaystyle
k!e^{c}\sum_{\ell=0}^{\Delta-1}\frac{c^{\ell-k}}{\ell!}\frac{1}{k-\ell}\sum_{m=0}^{\Delta-1-\ell}\frac{\left(-c\right)^{m}}{m!}$
$\displaystyle=\frac{k!c^{-k}}{\left(\Delta-1\right)!}\int_{1}^{\infty}\textup{d}w\,w^{-k-1}\int_{-c}^{\infty}\textup{d}t\,e^{-t}\sum_{\ell=0}^{\Delta-1}{\Delta-1\choose\ell}t^{\Delta-1-\ell}\left(cw\right)^{\ell}$
$\displaystyle=\frac{k!c^{-k}}{\left(\Delta-1\right)!}\int_{1}^{\infty}\textup{d}w\,w^{-k-1}\int_{-c}^{\infty}\textup{d}t\,e^{-t}\left(t+cw\right)^{\Delta-1}$
$\displaystyle=\frac{1}{\left(\Delta-1\right)!}\int_{0}^{\infty}\textup{d}u\,e^{c\left(1-u\right)}u^{k}\int_{0}^{\infty}\textup{d}x\,e^{x\left(1-u\right)}\int_{x}^{\infty}\textup{d}y\,e^{-y}y^{\Delta-1},$
(S64)

where (S46) and (S48) (together with (S49)) was invoked in the first passage,
while (S47) and some change of variables were used in the last passage. The
resulting triple integral is evaluated using (S63), and the result is

$\displaystyle
k!e^{c}\sum_{\ell=0}^{\Delta-1}\frac{c^{\ell-k}}{\ell!}\frac{1}{k-\ell}\sum_{m=0}^{\Delta-1-\ell}\frac{\left(-c\right)^{m}}{m!}$
$\displaystyle=\sum_{n=k_{0}}^{k-1}\left[\int_{0}^{1}\textup{d}u\,e^{c\left(1-u\right)}u^{n}+\int_{1}^{\infty}\textup{d}u\,e^{c\left(1-u\right)}u^{n}\right]$
$\displaystyle=e^{c}\sum_{n=k_{0}}^{k-1}\left[\frac{\gamma(n+1,c)}{c^{n+1}}+\frac{\Gamma(n+1,c)}{c^{n+1}}\right]\qquad(k>k_{0}).$
(S65)

Therefore, from (S56) and (S65), the coefficient $L(k,k_{0})$ in (S44) can be
cast as

$\displaystyle L(k,k_{0})=\left\\{\begin{array}[]{ccl}\displaystyle-
Me^{c}\sum_{n=k_{0}}^{k-1}\frac{\Gamma(n+1,c)}{c^{n+1}}&,&k>k_{0}\\\ &&\\\
\displaystyle-
Me^{c}\sum_{n=k}^{k_{0}-1}\frac{\gamma(n+1,c)}{c^{n+1}}&,&k<k_{0}\end{array}\right..$
(S69)

##  XII The coefficient of the quadratic term - $Q(k,k_{0})$

By defining

$\displaystyle Q(k,k_{0})=MQ_{1}(k,k_{0})+M^{2}Q_{2}(k,k_{0}),$ (S70)

the coeffcient of the quadratic term (S45) was splitted into two parts, where

$\displaystyle Q_{1}(k,k_{0})$
$\displaystyle:=c\int_{0}^{1}\textup{d}\xi\,e^{c\left(1-\xi\right)}\left(\xi^{k_{0}}-\xi^{k}\right)+\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\sum_{\ell=k_{0}+1}^{k}\frac{c^{k-\ell}}{\left(k-\ell\right)!}\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}+$
$\displaystyle+\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\sum_{\ell=k_{0}+1}^{k}\frac{c^{k-\ell}}{\left(k-\ell\right)!\ell}\frac{\left(-c\right)^{\ell-
k_{0}}}{\left(\ell-1-k_{0}\right)!}$ (S71)

and

$\displaystyle Q_{2}(k,k_{0})$
$\displaystyle:=\frac{1}{2}\Omega_{2}(k_{0})-\frac{1}{2}\Omega_{2}(k)+\Omega_{1}^{2}(k)-\Omega_{1}(k_{0})\Omega_{1}(k)+$
$\displaystyle+\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\Omega_{1}(k)\sum_{\ell=k_{0}+1}^{k}\frac{c^{k-\ell}}{\left(k-\ell\right)!\ell}\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}-$
$\displaystyle-\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\sum_{\ell=k_{0}+1}^{k}\frac{\theta(k-\ell-1)}{\ell}\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{k-\ell-1}\frac{c^{q}}{q!}\frac{1}{k-\ell-q}+$
$\displaystyle+\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\sum_{\ell=k_{0}+1}^{k}\frac{c^{k-\ell}}{\left(k-\ell\right)!}\frac{\theta(\ell-2-k_{0})}{\ell}\sum_{m=0}^{\ell-2-k_{0}}\frac{1}{\ell-1-k_{0}-m}\sum_{q=0}^{m}\frac{\left(-c\right)^{q}}{q!}+$
$\displaystyle+\frac{e^{c}k!}{c^{2k}}\theta(\Delta-1)\sum_{\ell=k_{0}+1}^{k}\frac{k!}{\left(k-\ell\right)!}\frac{c^{k-\ell}}{\ell}\theta(k-1)\sum_{m=0}^{\ell-1-k_{0}}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}.$
(S72)

The functions $Q_{1}$ and $Q_{2}$ are, respectively, the coefficients of the
second-order terms (in $\alpha$) associated to $M$ and $M^{2}$. Naturally, the
dominant term of $Q$ is given by $M^{2}Q_{2}$, but the exact expression for
$Q_{1}$ will also be determined, which is useful for numerical purposes.

###  XII.1 The coefficient of the quadratic term - the $Q_{1}(k,k_{0})$ term

Starting from (S71), invoking (S35) and (S48) to deal with the integral, and
introducing the variable $u=\ell-1-k_{0}$ leads to

$\displaystyle Q_{1}(k,k_{0})$
$\displaystyle:=e^{c}\left[\frac{\gamma(k_{0}+1,c)}{c^{k_{0}}}-\frac{\gamma(k+1,c)}{c^{k}}\right]+\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\Bigg{[}\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}+$
$\displaystyle+\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!u!}\frac{\left(-c\right)^{u+1}}{u+k_{0}+1}\Bigg{]}.$
(S73)

From (S48), (S49) and the integral representation of the Gamma function, one
has

$\displaystyle\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}$
$\displaystyle=\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{e^{-c}}{u!}\int_{-c}^{\infty}\textup{d}t\,e^{-t}t^{u}$
$\displaystyle=\frac{e^{-c}}{\left(\Delta-1\right)!}\int_{-c}^{\infty}\textup{d}t\,e^{-t}\sum_{u=0}^{\Delta-1}{\Delta-1\choose
u}c^{\Delta-1-u}t^{u}$
$\displaystyle=\frac{e^{-c}}{\left(\Delta-1\right)!}\int_{-c}^{\infty}\textup{d}t\,e^{-t}\left(t+c\right)^{\Delta-1}$
$\displaystyle=1.$ (S74)

Furthermore, from (S46), it is also possible to show that

$\displaystyle\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!u!}\frac{\left(-c\right)^{u+1}}{u+k_{0}+1}$
$\displaystyle=\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!u!}\left(-c\right)^{u+1}\int_{1}^{\infty}\textup{d}w\,w^{-\left(u+k_{0}+1\right)-1}$
$\displaystyle=\frac{\left(-c\right)}{\left(\Delta-1\right)!}\int_{1}^{\infty}\textup{d}w\,w^{-k-1}\sum_{u=0}^{\Delta-1}{\Delta-1\choose
u}\left(cw\right)^{\Delta-1-u}\left(-c\right)^{u}$
$\displaystyle=\frac{\left(-c\right)}{\left(\Delta-1\right)!}\int_{1}^{\infty}\textup{d}w\,w^{-k-1}\left(cw-c\right)^{\Delta-1}$
$\displaystyle=-\frac{c^{\Delta}}{\left(\Delta-1\right)!}\int_{0}^{\infty}\textup{d}y\,y^{\Delta-1}\frac{1}{\left(y+1\right)^{k+1}},$
(S75)

where the change of variable $y=w-1$ was performed in the last passage.
Invoking (S47), one can cast (S75) as

$\displaystyle\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!u!}\frac{\left(-c\right)^{u+1}}{u+k_{0}+1}$
$\displaystyle=-\frac{c^{\Delta}}{\left(\Delta-1\right)!}\int_{0}^{\infty}\textup{d}y\,y^{\Delta-1}\frac{1}{\left(y+1\right)^{k+1}}$
$\displaystyle=-\frac{c^{\Delta}}{\left(\Delta-1\right)!}\int_{0}^{\infty}\textup{d}y\,y^{\Delta-1}\frac{1}{k!}\int_{0}^{\infty}\textup{d}t\,e^{-t\left(y+1\right)}t^{k}$
$\displaystyle=-c^{\Delta}\frac{k_{0}!}{k!},$ (S76)

where the integration in $y$ variable was performed before $t$ in the last
passage.

Inserting (S74) and (S76) into (S73) leads to

$\displaystyle Q_{1}(k,k_{0})$
$\displaystyle:=e^{c}\left[\frac{\gamma(k_{0}+1,c)}{c^{k_{0}}}-\frac{\gamma(k+1,c)}{c^{k}}\right]+e^{c}\theta(\Delta-1)\Bigg{[}\frac{k!}{c^{k}}-\frac{k_{0}!}{c^{k_{0}}}\Bigg{]}$
$\displaystyle=\left\\{\begin{array}[]{ccl}\displaystyle
e^{c}\left[\frac{\Gamma(k+1,c)}{c^{k}}-\frac{\Gamma(k_{0}+1,c)}{c^{k_{0}}}\right]&,&\Delta\geq
0\\\ &&\\\ \displaystyle
e^{c}\left[\frac{\gamma(k_{0}+1,c)}{c^{k_{0}}}-\frac{\gamma(k+1,c)}{c^{k}}\right]&,&\Delta<0\end{array}\right.,$
(S80)

obtained by (S50) (the $\Delta\geq 0$ case).

###  XII.2 The coefficient of the quadratic term - the $Q_{2}(k,k_{0})$ term
(Part I)

Starting from (S72), the introduction of the change of variable
$u=\ell-1-k_{0}$ leads to

$\displaystyle Q_{2}(k,k_{0})$
$\displaystyle:=\frac{1}{2}\Omega_{2}(k_{0})-\frac{1}{2}\Omega_{2}(k)+\Omega_{1}^{2}(k)-\Omega_{1}(k_{0})\Omega_{1}(k)+$
$\displaystyle+\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\Omega_{1}(k)\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{1}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}-$
$\displaystyle-\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\sum_{u=0}^{\Delta-1}\frac{\theta(\Delta-2-u)}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{\Delta-2-u}\frac{c^{q}}{q!}\frac{1}{\Delta-1-u-q}+$
$\displaystyle+\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{\theta(u-1)}{u+k_{0}+1}\sum_{m=0}^{u-1}\frac{1}{u-m}\sum_{q=0}^{m}\frac{\left(-c\right)^{q}}{q!}+$
$\displaystyle+\frac{e^{c}k!}{c^{2k}}\theta(\Delta-1)\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{k!\theta(k-1)}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}.$
(S81)

Since
$\theta(\Delta-1)\sum_{u=0}^{\Delta-1}\theta(\Delta-2-u)\left(\cdots\right)=\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\left(\cdots\right)$,
$\theta(\Delta-1)\sum_{u=0}^{\Delta-1}\theta(u-1)\left(\cdots\right)=\theta(\Delta-2)\sum_{u=1}^{\Delta-1}\left(\cdots\right)$
and $\theta(\Delta-1)\theta(k-1)=\theta(\Delta-1)$, the above expression can
be cast as

$\displaystyle Q_{2}(k,k_{0})$
$\displaystyle:=\frac{1}{2}\Omega_{2}(k_{0})-\frac{1}{2}\Omega_{2}(k)+\Omega_{1}^{2}(k)-\Omega_{1}(k_{0})\Omega_{1}(k)+$
$\displaystyle+\frac{e^{c}k!}{c^{k}}\theta(\Delta-1)\Omega_{1}(k)\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{1}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}-$
$\displaystyle-\frac{e^{c}k!}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{1}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{\Delta-2-u}\frac{c^{q}}{q!}\frac{1}{\Delta-1-u-q}+$
$\displaystyle+\frac{e^{c}k!}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{c^{\Delta-2-u}}{\left(\Delta-2-u\right)!}\frac{1}{u+k_{0}+2}\sum_{m=0}^{u}\frac{1}{u+1-m}\sum_{q=0}^{m}\frac{\left(-c\right)^{q}}{q!}+$
$\displaystyle+\frac{e^{c}k!}{c^{2k}}\theta(\Delta-1)\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{k!}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}$
(S82)

after a simple change of variable in the penultimate term. From
$\frac{1}{\left(u+k_{0}+2\right)\left(u+1-m\right)}=\frac{1}{m+k_{0}+1}\left(\frac{1}{u+1-m}-\frac{1}{u+k_{0}+2}\right)$,
the penultimate term in (S82) can be written as

$\displaystyle\frac{e^{c}k!}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{c^{\Delta-2-u}}{\left(\Delta-2-u\right)!}\frac{1}{u+k_{0}+2}\sum_{m=0}^{u}\frac{1}{u+1-m}\sum_{q=0}^{m}\frac{\left(-c\right)^{q}}{q!}=$
$\displaystyle=\frac{e^{c}k!}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{c^{\Delta-2-u}}{\left(\Delta-2-u\right)!}\sum_{m=0}^{u}\frac{1}{m+k_{0}+1}\left(\frac{1}{u+1-m}-\frac{1}{u+k_{0}+2}\right)\sum_{q=0}^{m}\frac{\left(-c\right)^{q}}{q!}$
$\displaystyle=\frac{e^{c}k!}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{c^{u}}{u!}\sum_{m=0}^{\Delta-2-u}\frac{1}{m+k_{0}+1}\left(\frac{1}{\Delta-1-u-m}-\frac{1}{k-u}\right)\sum_{q=0}^{m}\frac{\left(-c\right)^{q}}{q!},$
(S83)

where the change of variable $u\rightarrow\Delta-2-u$ was invoked in the last
passage. Inverting the order of the summation through
$\sum_{u=0}^{\Delta-2}\sum_{m=0}^{\Delta-2-u}(\cdots)=\sum_{m=0}^{\Delta-2}\sum_{u=0}^{\Delta-2-m}(\cdots)$
and relabelling then some summation indices leads to

$\displaystyle\frac{e^{c}k!}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{c^{\Delta-2-u}}{\left(\Delta-2-u\right)!}\frac{1}{u+k_{0}+2}\sum_{m=0}^{u}\frac{1}{u+1-m}\sum_{q=0}^{m}\frac{\left(-c\right)^{q}}{q!}=$
$\displaystyle=-\frac{e^{c}k!}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{1}{u+k_{0}+1}\sum_{q=0}^{\Delta-2-u}\frac{c^{q}}{q!}\frac{1}{k-q}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}+$
$\displaystyle+\frac{e^{c}k!}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{1}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{\Delta-2-u}\frac{c^{q}}{q!}\frac{1}{\Delta-1-u-q},$
(S84)

and the last term matches the third line in (S82). Therefore, from (S82) and
(S84), one has

$\displaystyle Q_{2}(k,k_{0})$
$\displaystyle:=\frac{1}{2}\Omega_{2}(k_{0})-\frac{1}{2}\Omega_{2}(k)+\Omega_{1}^{2}(k)-\Omega_{1}(k_{0})\Omega_{1}(k)-$
$\displaystyle-\frac{k!e^{c}}{c^{k}}\theta(\Delta-2)\sum_{u=0}^{\Delta-2}\frac{1}{u+k_{0}+1}\sum_{q=0}^{\Delta-2-u}\frac{c^{q}}{q!}\frac{1}{k-q}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}+$
$\displaystyle+\frac{k!e^{c}}{c^{k}}\theta(\Delta-1)\Omega_{1}(k)\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{1}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}+$
$\displaystyle+\frac{k!e^{c}}{c^{2k}}\theta(\Delta-1)\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{k!}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}.$
(S85)

Let $Q_{2A}$, $Q_{2B}$ and $Q_{2C}$ be defined by

$\displaystyle\left\\{\begin{array}[]{ccl}Q_{2A}(k,k_{0})&:=&\displaystyle\frac{k!e^{c}}{c^{k}}\sum_{u=0}^{\Delta-2}\frac{1}{u+k_{0}+1}\sum_{q=0}^{\Delta-2-u}\frac{c^{q}}{q!}\frac{1}{k-q}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\\\
Q_{2B}(k,k_{0})&:=&\displaystyle\frac{k!e^{c}}{c^{k}}\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{1}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\\\
Q_{2C}(k,k_{0})&:=&\displaystyle\frac{k!e^{c}}{c^{2k}}\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{k!}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}\end{array}\right..$
(S89)

These functions are part of (S85), and they are analyzed separately. All of
them are associated with a factor $\theta(\Delta-1)$ or $\theta(\Delta-2)$,
which allows one to concentrate on the case $\Delta>0$ only in the next three
subsections.

####  XII.2.1 The $Q_{2A}(k,k_{0})$ function

From (S46) and (S48) (with (S49)), one can cast $Q_{2A}$ as

$\displaystyle Q_{2A}(k,k_{0})$
$\displaystyle=\frac{k!}{c^{k}}\sum_{u=0}^{\Delta-2}\int_{1}^{\infty}\textup{d}w\,w^{-k+\left(\Delta-2-u\right)}\int_{1}^{\infty}\textup{d}z\,z^{-k-1}\sum_{q=0}^{\Delta-2-u}\frac{\left(cz\right)^{q}}{q!}\frac{1}{u!}\int_{-c}^{\infty}\textup{d}t\,e^{-t}t^{u}$
$\displaystyle=\frac{k!c^{-k}}{\left(\Delta-2\right)!}\int_{1}^{\infty}\textup{d}w\,w^{-k}\int_{1}^{\infty}\textup{d}z\,e^{cz}z^{-k-1}\int_{cz}^{\infty}\textup{d}y\,e^{-y}\int_{-c}^{\infty}\textup{d}t\,e^{-t}\sum_{u=0}^{\Delta-2}{\Delta-2\choose
u}\left(wy\right)^{\Delta-2-u}t^{u}$
$\displaystyle=\frac{k!c^{-k}}{\left(\Delta-2\right)!}\int_{1}^{\infty}\textup{d}w\,w^{-k}\int_{1}^{\infty}\textup{d}z\,e^{cz}z^{-k-1}\int_{cz}^{\infty}\textup{d}y\,e^{-y}\int_{-c}^{\infty}\textup{d}t\,e^{-t}\left(wy+t\right)^{\Delta-2}.$
(S90)

Introducing the change of variables $x=z-1$, $v=y/c-1$ and $s=t/c+w$
(replacing $t$ for $s$) leads to

$\displaystyle Q_{2A}(k,k_{0})$
$\displaystyle=\frac{k!c^{-k_{0}}}{\left(\Delta-2\right)!}\int_{1}^{\infty}\textup{d}w\,e^{cw}w^{-k}\int_{0}^{\infty}\textup{d}x\,e^{cx}\left(1+x\right)^{-k-1}\int_{x}^{\infty}\textup{d}v\,e^{-cv}\int_{w-1}^{\infty}\textup{d}s\,e^{-cs}\left(wv+s\right)^{\Delta-2}$
$\displaystyle=\frac{k!c^{-k_{0}}}{\left(\Delta-2\right)!}\sum_{n=0}^{\Delta-2}{\Delta-2\choose
n}\int_{1}^{\infty}\textup{d}w\,e^{cw}w^{-\left(k-n\right)}\int_{w-1}^{\infty}\textup{d}s\,e^{-cs}s^{\Delta-2-n}\times$
$\displaystyle\times\int_{0}^{\infty}\textup{d}x\,e^{cx}\left(1+x\right)^{-k-1}\int_{x}^{\infty}\textup{d}v\,e^{-cv}v^{n}.$
(S91)

Changing the order of integration through
$\int_{1}^{\infty}\textup{d}w\int_{w-1}^{\infty}\textup{d}s\,\left(\cdots\right)=\int_{0}^{\infty}\textup{d}s\int_{1}^{s+1}\textup{d}w\,\left(\cdots\right)$,
and then invoking (S47) leads to

$\displaystyle Q_{2A}(k,k_{0})$
$\displaystyle=\frac{k!c^{-k_{0}}}{\left(\Delta-2\right)!}\sum_{n=0}^{\Delta-2}{\Delta-2\choose
n}\int_{0}^{\infty}\textup{d}s\,e^{-cs}s^{\Delta-2-n}\int_{1}^{s+1}\textup{d}w\,e^{cw}\left[\frac{1}{\left(k-n-1\right)!}\int_{0}^{\infty}\textup{d}z\,e^{-zw}z^{k-n-1}\right]\times$
$\displaystyle\times\int_{0}^{\infty}\textup{d}x\,e^{cx}\left[\frac{1}{k!}\int_{0}^{\infty}\textup{d}y\,e^{-y\left(1+x\right)}y^{k}\right]\int_{x}^{\infty}\textup{d}v\,e^{-cv}v^{n}$
$\displaystyle=\frac{c^{-k_{0}}}{\left(\Delta-2\right)!}\sum_{n=0}^{\Delta-2}{\Delta-2\choose
n}\frac{1}{\left(k-n-1\right)!}\int_{0}^{\infty}\textup{d}z\,z^{k-n-1}\int_{0}^{\infty}\textup{d}s\,e^{-cs}s^{\Delta-2-n}\int_{1}^{s+1}\textup{d}w\,e^{\left(c-z\right)w}\times$
$\displaystyle\times\int_{0}^{\infty}\textup{d}y\,e^{-y}y^{k}\int_{0}^{\infty}\textup{d}x\,e^{x\left(c-y\right)}\int_{x}^{\infty}\textup{d}v\,e^{-cv}v^{n}.$
(S92)

In (S92), there are two independent triple integrals. The first one, which
involves integration in $z$, $s$, and $w$ variables, can be performed by a
similar argument used to derive (S63) to circumvent an “apparent singularity”.
The evaluation of the triple integral, which involves the variables $y$, $x$,
and $v$ can be done using (S63) after some simple change of variables. After
these operations and some simplifications, one has

$\displaystyle
Q_{2A}(k,k_{0})=e^{c}\sum_{n=0}^{\Delta-2}\frac{c^{k-1-n}}{\left(k-1-n\right)!}\sum_{\ell=k_{0}}^{k-n-2}\frac{\ell!}{c^{\ell+1}}\sum_{m=k-1-n}^{k-1}\frac{m!}{c^{m+1}}.$
(S93)

The introduction of the change of variable $k-1-n\rightarrow n$ leads to

$\displaystyle
Q_{2A}(k,k_{0})=e^{c}\sum_{n=k_{0}+1}^{k-1}\frac{c^{n}}{n!}\sum_{\ell=k_{0}}^{n-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}.$
(S94)

####  XII.2.2 The $Q_{2B}(k,k_{0})$ function

From (S46) and (S48) (with (S49)), one can cast $Q_{2B}$ as

$\displaystyle Q_{2B}(k,k_{0})$
$\displaystyle=\frac{k!c^{-k}}{\left(\Delta-1\right)!}\int_{1}^{\infty}\textup{d}w\,w^{-k-1}\int_{-c}^{\infty}\textup{d}t\,e^{-t}\sum_{u=0}^{\Delta-1}{\Delta-1\choose
u}\left(cw\right)^{\Delta-1-u}t^{u}$
$\displaystyle=\frac{c^{-k}}{\left(\Delta-1\right)!}\int_{1}^{\infty}\textup{d}w\,\int_{0}^{\infty}\textup{d}z\,e^{-zw}z^{k}\int_{-c}^{\infty}\textup{d}t\,e^{-t}\left(cw+t\right)^{\Delta-1},$
(S95)

where (S47) was invoked in the last passage. By the change of variables
$x=c\left(w-1\right)$, $y=t+c$ and $r=z/c$, one has

$\displaystyle Q_{2B}(k,k_{0})$
$\displaystyle=\frac{e^{c}}{\left(\Delta-1\right)!}\int_{0}^{\infty}\textup{d}r\,e^{-cr}r^{k}\int_{0}^{\infty}\textup{d}x\,e^{-rx}\int_{0}^{\infty}\textup{d}y\,e^{-y}\left(x+y\right)^{\Delta-1}$
$\displaystyle=\frac{e^{c}}{\left(\Delta-1\right)!}\int_{0}^{\infty}\textup{d}r\,e^{-cr}r^{k}\int_{0}^{\infty}\textup{d}x\,e^{x\left(1-r\right)}\int_{x}^{\infty}\textup{d}v\,e^{-v}v^{\Delta-1},$
(S96)

where the change of variable $v=x+y$ (changing from $y$ to $v$) was
introduced. The resulting triple integral can be evaluated using (S63), which
leads to

$\displaystyle Q_{2B}(k,k_{0})=e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}.$
(S97)

####  XII.2.3 The $Q_{2C}(k,k_{0})$ function

This function can be seen as a product of two independent parts, which are

$\displaystyle\frac{e^{c}k!}{c^{k}}\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{1}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}\quad\textnormal{
and }\quad\frac{k!}{c^{k}}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}.$
(S98)

The first one is equal to $Q_{2B}$ and, according to (S97), can be cast as

$\displaystyle\frac{e^{c}k!}{c^{k}}\sum_{u=0}^{\Delta-1}\frac{c^{\Delta-1-u}}{\left(\Delta-1-u\right)!}\frac{1}{u+k_{0}+1}\sum_{m=0}^{u}\frac{\left(-c\right)^{m}}{m!}=e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}.$
(S99)

The second part of $Q_{2C}$, on the other hand, can be written as

$\displaystyle\frac{k!}{c^{k}}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}$
$\displaystyle=\frac{k!}{c^{k}}\int_{1}^{\infty}\textup{d}w\,w^{-k-1}\sum_{q=0}^{k-1}\frac{\left(cw\right)^{q}}{q!}$
$\displaystyle=\frac{k!}{c^{k}}\int_{1}^{\infty}\textup{d}w\,\left[\frac{1}{k!}\int_{0}^{\infty}\textup{d}z\,e^{-zw}z^{k}\right]\frac{e^{cw}}{\left(k-1\right)!}\int_{cw}^{\infty}\textup{d}t\,e^{-t}t^{k-1}$
$\displaystyle=\frac{c^{-k}}{\left(k-1\right)!}\int_{1}^{\infty}\textup{d}w\,e^{cw}\int_{0}^{\infty}\textup{d}z\,e^{-zw}z^{k}\int_{cw}^{\infty}\textup{d}t\,e^{-t}t^{k-1},$
(S100)

where (S46), (S48) (and (S49)) and (S47) were used. Introducing the change of
variables $x=c\left(w-1\right)$, $y=t-c$ and $r=z/c$ leads to

$\displaystyle\frac{k!}{c^{k}}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}$
$\displaystyle=\frac{1}{\left(k-1\right)!}\int_{0}^{\infty}\textup{d}r\,e^{-cr}r^{k}\int_{0}^{\infty}\textup{d}x\,e^{x\left(1-r\right)}\int_{x}^{\infty}\textup{d}y\,e^{-y}\left(y+c\right)^{k-1}$
$\displaystyle=\frac{1}{\left(k-1\right)!}\sum_{n=0}^{k-1}{k-1\choose
n}c^{k-1-n}\int_{0}^{\infty}\textup{d}r\,e^{-cr}r^{k}\int_{0}^{\infty}\textup{d}x\,e^{x\left(1-r\right)}\int_{x}^{\infty}\textup{d}y\,e^{-y}y^{n}$
$\displaystyle=\sum_{m=0}^{k-1}\frac{c^{m}}{m!}\sum_{\ell=m}^{k-1}\frac{\ell!}{c^{\ell+1}},$
(S101)

where (S63) was invoked in the last passage and some simple change of
variables were performed. Inverting the order of the summation in (S101)
through
$\sum_{m=0}^{k-1}\sum_{\ell=m}^{k-1}\left(\cdots\right)=\sum_{\ell=0}^{k-1}\sum_{m=0}^{\ell}\left(\cdots\right)$
leads to

$\displaystyle\frac{k!}{c^{k}}\sum_{q=0}^{k-1}\frac{c^{q}}{q!}\frac{1}{k-q}=\sum_{\ell=0}^{k-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=0}^{\ell}\frac{c^{m}}{m!}=e^{c}\sum_{\ell=0}^{k-1}\frac{\Gamma(\ell+1,c)}{c^{\ell+1}},$
(S102)

where (S48) was used.

From (S99) and (S102), one has

$\displaystyle
Q_{2C}(k,k_{0})=\left[e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\right]\left[e^{c}\sum_{\ell=0}^{k-1}\frac{\Gamma(\ell+1,c)}{c^{\ell+1}}\right].$
(S103)

###  XII.3 The coefficient of the quadratic term - the $Q_{2}(k,k_{0})$ term
(Part II)

After inserting (S94), (S97) and (S103) into (S85), one has

$\displaystyle Q_{2}(k,k_{0})$
$\displaystyle=\frac{1}{2}\Omega_{2}(k_{0})-\frac{1}{2}\Omega_{2}(k)+\Omega_{1}(k)\left[\Omega_{1}(k)-\Omega_{1}(k_{0})\right]-\theta(\Delta-2)e^{c}\sum_{n=k_{0}+1}^{k-1}\frac{c^{n}}{n!}\sum_{\ell=k_{0}}^{n-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}+$
$\displaystyle+\theta(\Delta-1)\Omega_{1}(k)e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}+\theta(\Delta-1)\left[e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\right]\left[e^{c}\sum_{\ell=0}^{k-1}\frac{\Gamma(\ell+1,c)}{c^{\ell+1}}\right].$
(S104)

Note that

$\displaystyle-\theta(\Delta-2)e^{c}\sum_{n=k_{0}+1}^{k-1}\frac{c^{n}}{n!}\sum_{\ell=k_{0}}^{n-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}=$
$\displaystyle=-\theta(\Delta-2)e^{c}\sum_{n=k_{0}+1}^{k-1}\frac{c^{n}}{n!}\left[\sum_{\ell=k_{0}}^{n}\frac{\ell!}{c^{\ell+1}}-\frac{n!}{c^{n+1}}\right]\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}$
$\displaystyle=\theta(\Delta-2)e^{c}\left[\frac{1}{c}\sum_{n=k_{0}+1}^{k-1}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}-\sum_{n=k_{0}+1}^{k-1}\frac{c^{n}}{n!}\sum_{\ell=k_{0}}^{n}\frac{\ell!}{c^{\ell+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}\right].$
(S105)

Introducing the change in the summation order
$\sum_{n=k_{0}+1}^{k-1}\sum_{m=n}^{k-1}\left(\cdots\right)=\sum_{m=k_{0}+1}^{k-1}\sum_{n=k_{0}+1}^{m}\left(\cdots\right)$
in the first sum, and splitting the second sum leads to

$\displaystyle-\theta(\Delta-2)e^{c}\sum_{n=k_{0}+1}^{k-1}\frac{c^{n}}{n!}\sum_{\ell=k_{0}}^{n-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}=$
$\displaystyle=\theta(\Delta-2)e^{c}\left\\{\frac{1}{c}\sum_{m=k_{0}+1}^{k-1}\frac{m!}{c^{m+1}}\sum_{n=k_{0}+1}^{m}1-\left[\sum_{n=k_{0}}^{k-1}\frac{c^{n}}{n!}\sum_{\ell=k_{0}}^{n}\frac{\ell!}{c^{\ell+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}-\frac{c^{k_{0}}}{k_{0}!}\sum_{\ell=k_{0}}^{k_{0}}\frac{\ell!}{c^{\ell+1}}\sum_{m=k_{0}}^{k-1}\frac{m!}{c^{m+1}}\right]\right\\}$
$\displaystyle=\theta(\Delta-1)e^{c}\left[\frac{1}{c}\sum_{m=k_{0}}^{k-1}\frac{m!}{c^{m+1}}\left(m-k_{0}+1\right)-\sum_{n=k_{0}}^{k-1}\frac{c^{n}}{n!}\sum_{\ell=k_{0}}^{n}\frac{\ell!}{c^{\ell+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}\right].$
(S106)

In the last passage, since the expression inside the square brackets in (S106)
(last line) vanishes when $\Delta=1$ (or $k=k_{0}+1$), one can replace the the
unit step function $\theta(\Delta-2)$ by $\theta(\Delta-1)$ without causing
any impact on the whole term. Then, changing the order of the summation
through
$\sum_{n=k_{0}}^{k-1}\sum_{\ell=k_{0}}^{n}\sum_{m=n}^{k-1}\left(\cdots\right)=\sum_{\ell=k_{0}}^{k-1}\sum_{m=\ell}^{k-1}\sum_{n=\ell}^{m}\left(\cdots\right)$
implies

$\displaystyle-\theta(\Delta-2)e^{c}\sum_{n=k_{0}+1}^{k-1}\frac{c^{n}}{n!}\sum_{\ell=k_{0}}^{n-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}=$
$\displaystyle=\theta(\Delta-1)e^{c}\left[\frac{1}{c}\sum_{m=k_{0}}^{k-1}\frac{m!}{c^{m+1}}\left(m-k_{0}+1\right)-\sum_{\ell=k_{0}}^{k-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=\ell}^{k-1}\frac{m!}{c^{m+1}}\sum_{n=\ell}^{m}\frac{c^{n}}{n!}\right]$
$\displaystyle=\theta(\Delta-1)e^{c}\left[\frac{1}{c}\sum_{m=k_{0}}^{k-1}\frac{m!}{c^{m+1}}\left(m-k_{0}+1\right)-\sum_{\ell=k_{0}}^{k-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=\ell}^{k-1}\frac{m!}{c^{m+1}}\left(\sum_{n=0}^{m}\frac{c^{n}}{n!}-\sum_{n=0}^{\ell}\frac{c^{n}}{n!}+\frac{c^{\ell}}{\ell!}\right)\right]$
$\displaystyle=\theta(\Delta-1)e^{2c}\left[\sum_{\ell=k_{0}}^{k-1}\frac{\Gamma(\ell+1,c)}{c^{\ell+1}}\sum_{m=\ell}^{k-1}\frac{m!}{c^{m+1}}-\sum_{\ell=k_{0}}^{k-1}\frac{\ell!}{c^{\ell+1}}\sum_{m=\ell}^{k-1}\frac{\Gamma(m+1,c)}{c^{m+1}}\right],$
(S107)

where (S48) and (S51), and a change in summation order
$\sum_{\ell=k_{0}}^{k-1}\sum_{m=\ell}^{k-1}\left(\cdots\right)=\sum_{m=k_{0}}^{k-1}\sum_{\ell=k_{0}}^{m}\left(\cdots\right)$
were used in the last passage. Inserting (S107) back to (S104) yields

$\displaystyle Q_{2}(k,k_{0})$
$\displaystyle=\frac{1}{2}\Big{[}\Omega_{2}(k_{0})-\Omega_{2}(k)\Big{]}+\Omega_{1}(k)\Big{[}\Omega_{1}(k)-\Omega_{1}(k_{0})\Big{]}+\theta(\Delta-1)\Omega_{1}(k)e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}+$
$\displaystyle+\theta(\Delta-1)e^{2c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=k_{0}}^{n}\frac{\Gamma(\ell+1,c)}{c^{\ell+1}}+\theta(\Delta-1)e^{2c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n-1}\frac{\Gamma(\ell+1,c)}{c^{\ell+1}}$
(S108)

after changing the order of one of sums through
$\sum_{\ell=k_{0}}^{k-1}\sum_{n=\ell}^{k-1}\left(\cdots\right)=\sum_{n=k_{0}}^{k-1}\sum_{\ell=k_{0}}^{n}\left(\cdots\right)$
and some trivial relabelling of the indices.

From now on, it is convenient to divide the analysis into the $\Delta>0$ and
$\Delta<0$ cases.

###  XII.4 The coefficient of the quadratic term - the $Q_{2}(k,k_{0})$ term
(case $\Delta>0$)

Define by $Q_{>}$ the coefficient $Q_{2}$ when $k>k_{0}$. From (S59), (S56)
and (S138) when $\Delta>0$, one has

$\displaystyle Q_{>}(k,k_{0})$
$\displaystyle=\sum_{n=k_{0}}^{k-1}\psi(n)+\Omega_{1}(k)e^{c}\sum_{n=k_{0}}^{k-1}\frac{\Gamma(n+1,c)}{c^{n+1}}+e^{2c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=k_{0}}^{n}\frac{\Gamma(\ell+1,c)}{c^{\ell+1}}+$
$\displaystyle+e^{2c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n-1}\frac{\Gamma(\ell+1,c)}{c^{\ell+1}}$
(S109)

after some simplifications. From (S54) and (S56), one has

$\displaystyle\sum_{n=k_{0}}^{k-1}\psi(n)$
$\displaystyle=\sum_{n=k_{0}}^{k-1}\left[-\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\Omega_{1}(\ell)\right]$
$\displaystyle=\sum_{n=k_{0}}^{k-1}\left\\{-\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\left[\Omega_{1}(k)+e^{c}\sum_{m=\ell}^{k-1}\frac{\gamma(m+1,c)}{c^{m+1}}\right]\right\\}$
$\displaystyle=-\Omega_{1}(k)\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}-e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\sum_{m=\ell}^{k-1}\frac{\left[m!-\Gamma(m+1,c)\right]}{c^{m+1}}$
$\displaystyle=-\Omega_{1}(k)\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}+e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\sum_{m=\ell}^{k-1}\frac{\Gamma(m+1,c)}{c^{m+1}}-e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\sum_{m=\ell}^{k-1}\frac{m!}{c^{m+1}}.$
(S110)

Changing the order of the sum through
$\sum_{\ell=0}^{n}\sum_{m=\ell}^{k-1}\left(\cdots\right)=\sum_{m=0}^{n-1}\sum_{\ell=0}^{m}\left(\cdots\right)+\sum_{m=n}^{k-1}\sum_{\ell=0}^{n}\left(\cdots\right)$
in the last term (here, $n<k$), and using (S48) leads to

$\displaystyle\sum_{n=k_{0}}^{k-1}\psi(n)$
$\displaystyle=-\Omega_{1}(k)\sum_{n=k_{0}}^{k-1}\frac{e^{c}\Gamma(n+1,c)}{c^{n+1}}+e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\sum_{m=\ell}^{k-1}\frac{\Gamma(m+1,c)}{c^{m+1}}-$
$\displaystyle-e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{m=0}^{n-1}\frac{e^{c}\Gamma(m+1,c)}{c^{m+1}}-e^{c}\sum_{n=k_{0}}^{k-1}\frac{e^{c}\Gamma(n+1,c)}{c^{n+1}}\sum_{m=n}^{k-1}\frac{m!}{c^{m+1}}$
$\displaystyle=-\Omega_{1}(k)e^{c}\sum_{n=k_{0}}^{k-1}\frac{\Gamma(n+1,c)}{c^{n+1}}+e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\sum_{m=\ell}^{k-1}\frac{\Gamma(m+1,c)}{c^{m+1}}-$
$\displaystyle-e^{2c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{m=0}^{n-1}\frac{\Gamma(m+1,c)}{c^{m+1}}-e^{2c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{m=k_{0}}^{n}\frac{\Gamma(m+1,c)}{c^{m+1}},$
(S111)

where the change of summation order
$\sum_{n=k_{0}}^{k-1}\sum_{m=n}^{k-1}\left(\cdots\right)=\sum_{m=k_{0}}^{k-1}\sum_{n=k_{0}}^{m}\left(\cdots\right)$
(followed by a relabelling of the indices $n\leftrightarrow m$) was performed
in the last term in the passage. Inserting (S111) back to (S109) implies

$\displaystyle
Q_{>}(k,k_{0})=e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\sum_{m=\ell}^{k-1}\frac{\Gamma(m+1,c)}{c^{m+1}}.$
(S112)

After changing the order of the sum through
$\sum_{\ell=0}^{n}\sum_{m=\ell}^{k-1}\left(\cdots\right)=\sum_{m=0}^{n-1}\sum_{\ell=0}^{m}\left(\cdots\right)+\sum_{m=n}^{k-1}\sum_{\ell=0}^{n}\left(\cdots\right)$
(here, $n\leq k-1$) and invoking (S48), one has

$\displaystyle
Q_{>}(k,k_{0})=e^{k_{0}}\sum_{n=k_{0}}^{k-1}\frac{n!}{k_{0}^{n+1}}\sum_{m=0}^{n-1}\frac{e^{k_{0}}\Gamma^{2}(m+1,k_{0})}{m!k_{0}^{m+1}}+e^{k_{0}}\sum_{n=k_{0}}^{k-1}\frac{e^{k_{0}}\Gamma(n+1,k_{0})}{k_{0}^{n+1}}\sum_{m=n}^{k-1}\frac{\Gamma(m+1,k_{0})}{k_{0}^{m+1}}.$
(S113)

The coefficient $Q_{>}(k,k_{0})$ admits an alternative representation. Noting
that

$\displaystyle\sum_{n=k_{0}}^{k-1}\frac{\Gamma(n+1,c)}{c^{n+1}}\sum_{m=n}^{k-1}\frac{\Gamma(m+1,c)}{c^{m+1}}$
$\displaystyle=\sum_{n=k_{0}}^{k-1}\frac{\Gamma(n+1,c)}{c^{n+1}}\sum_{m=k_{0}}^{n}\frac{\Gamma(m+1,c)}{c^{m+1}}$
$\displaystyle=\frac{1}{2}\left[\sum_{n=k_{0}}^{k-1}\frac{\Gamma(n+1,c)}{c^{n+1}}\right]^{2}+\frac{1}{2}\sum_{n=k_{0}}^{k-1}\left[\frac{\Gamma(n+1,c)}{c^{n+1}}\right]^{2},$
(S114)

the $Q_{>}$ function can be cast as

$\displaystyle
Q_{>}(k,k_{0})=\frac{1}{2}\left[\sum_{n=k_{0}}^{k-1}\frac{e^{c}\Gamma(n+1,c)}{c^{n+1}}\right]^{2}-\frac{1}{2}\sum_{n=k_{0}}^{k-1}\left[\frac{e^{c}\Gamma(n+1,c)}{c^{n+1}}\right]^{2}+\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{m=0}^{n}\frac{c^{m+1}}{m!}\left[\frac{e^{c}\Gamma(m+1,c)}{c^{m+1}}\right]^{2}$
(S115)

after some simple manipulations.

###  XII.5 The coefficient of the quadratic term - the $Q_{2}(k,k_{0})$ term
(case $\Delta<0$)

Define by $Q_{<}$ the coefficient $Q_{2}$ when $k<k_{0}$. From (S54), (S56)
and (S59) into (S138) when $\Delta<0$, one has

$\displaystyle Q_{<}(k,k_{0})$
$\displaystyle=-\sum_{n=k}^{k_{0}-1}\psi(n)+\Omega_{1}(k)e^{c}\sum_{n=k}^{k_{0}-1}\frac{\gamma(n+1,c)}{c^{n+1}}$
$\displaystyle=\sum_{n=k}^{k_{0}-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\Omega_{1}(\ell)+\Omega_{1}(k)e^{c}\sum_{n=k}^{k_{0}-1}\frac{\gamma(n+1,c)}{c^{n+1}}.$
(S116)

Since from (S48), (S55) and (S56) the relation

$\displaystyle\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\Omega_{1}(\ell)$
$\displaystyle=\sum_{\ell=0}^{\infty}\frac{c^{\ell}}{\ell!}\Omega_{1}(\ell)-\sum_{\ell=n+1}^{\infty}\frac{c^{\ell}}{\ell!}\Omega_{1}(\ell)$
$\displaystyle=0-\sum_{\ell=n+1}^{\infty}\frac{c^{\ell}}{\ell!}\Omega_{1}(\ell)$
$\displaystyle=-\sum_{\ell=n+1}^{\infty}\frac{c^{\ell}}{\ell!}\left[\Omega_{1}(k)-e^{c}\sum_{m=k}^{\ell-1}\frac{\gamma(m+1,c)}{c^{m+1}}\right]$
$\displaystyle=-\Omega_{1}(k)e^{c}\frac{\gamma(n+1,c)}{n!}+e^{c}\sum_{\ell=n+1}^{\infty}\frac{c^{\ell}}{\ell!}\sum_{m=k}^{\ell-1}\frac{\gamma(m+1,c)}{c^{m+1}}$
(S117)

can be established, one has

$\displaystyle
Q_{<}(k,k_{0})=e^{c}\sum_{n=k}^{k_{0}-1}\frac{n!}{c^{n+1}}\sum_{\ell=n+1}^{\infty}\frac{c^{\ell}}{\ell!}\sum_{m=k}^{\ell-1}\frac{\gamma(m+1,c)}{c^{m+1}}.$
(S118)

Changing the order of the sums through
$\sum_{\ell=n+1}^{\infty}\sum_{m=k}^{\ell-1}\left(\cdots\right)=\sum_{m=k}^{n}\sum_{\ell=n+1}^{\infty}\left(\cdots\right)+\sum_{m=n+1}^{\infty}\sum_{\ell=m+1}^{\infty}\left(\cdots\right)$
and invoking (S48) leads to

$\displaystyle
Q_{<}(k,k_{0})=e^{2c}\sum_{n=k}^{k_{0}-1}\frac{\gamma(n+1,c)}{c^{n+1}}\sum_{m=k}^{n}\frac{\gamma(m+1,c)}{c^{m+1}}+e^{2c}\sum_{n=k}^{k_{0}-1}\frac{n!}{c^{n+1}}\sum_{m=n+1}^{\infty}\frac{\gamma^{2}(m+1,c)}{m!c^{m+1}}.$
(S119)

Then, following a procedure similar that transformed (S113) to (S115), one can
finally cast

$\displaystyle
Q_{<}(k,k_{0})=\frac{1}{2}\left[\sum_{n=k}^{k_{0}-1}\frac{e^{c}\gamma(n+1,c)}{c^{n+1}}\right]^{2}-\frac{1}{2}\sum_{n=k}^{k_{0}-1}\left[\frac{e^{c}\gamma(n+1,c)}{c^{n+1}}\right]^{2}+\sum_{n=k}^{k_{0}-1}\frac{n!}{c^{n+1}}\sum_{m=n}^{\infty}\frac{c^{m+1}}{m!}\left[\frac{e^{c}\gamma(m+1,c)}{c^{m+1}}\right]^{2}.$
(S120)

##  XIII Summary

In the expansion of the first-passage function

$\displaystyle f_{s}^{z}(k|k_{0};z)=1+\alpha
L(k,k_{0})+\alpha^{2}Q(k,k_{0})+\mathcal{O}(\alpha^{3}),$ (S121)

one has

$\displaystyle L(k,k_{0})=\left\\{\begin{array}[]{ccl}\displaystyle-
Me^{c}\sum_{n=k_{0}}^{k-1}\frac{\Gamma(n+1,c)}{c^{n+1}}&,&k>k_{0}\\\ &&\\\
\displaystyle-
Me^{c}\sum_{n=k}^{k_{0}-1}\frac{\gamma(n+1,c)}{c^{n+1}}&,&k<k_{0}\end{array}\right..$
(S125)

and

$\displaystyle Q(k,k_{0})=MQ_{1}(k,k_{0})+M^{2}Q_{2}(k,k_{0}),$ (S126)

where

$\displaystyle Q_{1}(k,k_{0})=\left\\{\begin{array}[]{ccl}\displaystyle
e^{c}\left[\frac{\Gamma(k+1,c)}{c^{k}}-\frac{\Gamma(k_{0}+1,c)}{c^{k_{0}}}\right]&,&k>k_{0}\\\
&&\\\ \displaystyle
e^{c}\left[\frac{\gamma(k_{0}+1,c)}{c^{k_{0}}}-\frac{\gamma(k+1,c)}{c^{k}}\right]&,&k<k_{0}\end{array}\right.$
(S130)

and

$\displaystyle Q_{2}(k,k_{0})=\left\\{\begin{array}[]{ccl}\displaystyle
e^{c}\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{\ell=0}^{n}\frac{c^{\ell}}{\ell!}\sum_{m=\ell}^{k-1}\frac{\Gamma(m+1,c)}{c^{m+1}}&,&k>k_{0}\\\
&&\\\ \displaystyle
e^{c}\sum_{n=k}^{k_{0}-1}\frac{n!}{c^{n+1}}\sum_{\ell=n+1}^{\infty}\frac{c^{\ell}}{\ell!}\sum_{m=k}^{\ell-1}\frac{\gamma(m+1,c)}{c^{m+1}}&,&k<k_{0}\end{array}\right.$
(S134)

or

$\displaystyle Q_{2}(k,k_{0})=$
$\displaystyle=\left\\{\begin{array}[]{ccl}\displaystyle\frac{1}{2}\left[\sum_{n=k_{0}}^{k-1}\frac{e^{c}\Gamma(n+1,c)}{c^{n+1}}\right]^{2}-\frac{1}{2}\sum_{n=k_{0}}^{k-1}\left[\frac{e^{c}\Gamma(n+1,c)}{c^{n+1}}\right]^{2}+\sum_{n=k_{0}}^{k-1}\frac{n!}{c^{n+1}}\sum_{m=0}^{n}\frac{c^{m+1}}{m!}\left[\frac{e^{c}\Gamma(m+1,c)}{c^{m+1}}\right]^{2}&,&k>k_{0}\\\
&&\\\
\displaystyle\frac{1}{2}\left[\sum_{n=k}^{k_{0}-1}\frac{e^{c}\gamma(n+1,c)}{c^{n+1}}\right]^{2}-\frac{1}{2}\sum_{n=k}^{k_{0}-1}\left[\frac{e^{c}\gamma(n+1,c)}{c^{n+1}}\right]^{2}+\sum_{n=k}^{k_{0}-1}\frac{n!}{c^{n+1}}\sum_{m=n}^{\infty}\frac{c^{m+1}}{m!}\left[\frac{e^{c}\gamma(m+1,c)}{c^{m+1}}\right]^{2}&,&k<k_{0}\end{array}\right..$
(S138)


37: Initialize a variable to accumulate MI estimates

38: for each batch in x and y do

39: Compute the MI estimate for the batch using ForwardPass

40: Accumulate the batch MI estimate

41: end for

42: return the average MI over all batches

43:end function

##  C Training Details

###  C.1 The Role of Randomness in DVPF Training

In the DVPF model, we strategically incorporate two key sources of randomness
during the training phase, distinct from the stochasticity introduced by the
reparameterization trick. These sources are vital for maintaining non-
determinism in privacy-related aspects of the model: (i) the addition of noise
to the latent representation, and (ii) the implementation of dropout layers
within the intermediate layers.

####  C.1.1 Integration of Noise in Latent Representation:

The latent representation vector $\mathbf{Z}\in\mathbb{R}^{n}$ is
systematically perturbed by the addition of Gaussian noise. This noise is
encapsulated within the vector $\mathbf{N}$, each component of which adheres
to an independent and identically distributed (i.i.d.) Gaussian distribution.
The variance of this noise distribution is uniformly set to
$\sigma^{2}=\frac{1}{2\pi e}$, thereby ensuring that each element of the
latent vector $\mathbf{Z}$ is subject to noise of identical statistical
characteristics. Formally, the noise vector $\mathbf{N}$ follows the
distribution $\mathcal{N}(0,\sigma^{2}\mathbf{I}_{n})$, with $\mathbf{I}_{n}$
representing the identity matrix of dimensions $n\times n$. The differential
entropy of the noise vector $\mathbf{N}$, denoted as $\mathrm{h}(\mathbf{N})$,
is derived from the general expression for the differential entropy of a
multivariate Gaussian distribution. Given the i.i.d. nature of the components
of $\mathbf{N}$ and the specified variance, the entropy calculation simplifies
to:

$\mathrm{h}\left(\mathbf{N}\right)=\frac{n}{2}\ln\left(2\pi
e\cdot\frac{1}{2\pi e}\right)=\frac{n}{2}\ln(1)=0.$ (45)

The differential entropy of a Gaussian noise vector $\mathbf{N}$ with a
variance of $\sigma^{2}=\frac{1}{2\pi e}$ is mathematically calculated to be
zero. This zero entropy value, in the context of a Gaussian distribution, is a
definitive outcome arising from the specific characteristics of the noise
introduced into the model. It is important to clarify that a zero differential
entropy for a Gaussian distribution does not imply the absence of noise or
variability. Instead, it reflects a precise level of variance ($\sigma^{2}$)
in the noise. In this case, the variance is relatively small, indicating that
the noise introduced into the system is subtle. The addition of this Gaussian
noise to the latent representation $\mathbf{Z}$ in a machine learning model is
a controlled method of introducing stochasticity. This stochasticity, despite
its low variance and zero entropy, plays a role in the model’s training
process. It can help the model become less sensitive to small fluctuations in
the input data, potentially improving the model’s ability to generalize from
the training data to new, unseen data. This generalization is a key goal in
machine learning, particularly in preventing overfitting, where a model
performs well on training data but poorly on new data.

####  C.1.2 Application of Dropout in Intermediate Layers:

In conjunction with the integration of Gaussian noise into the latent
representation, the DVPF model judiciously employs dropout within its
intermediate layers. This method strategically deactivates a subset of neurons
at random during each training iteration. This implementation of dropout
serves a twofold purpose: it introduces an additional layer of randomness
essential for maintaining privacy and reduces the model’s propensity for
overfitting, thereby enhancing its generalization capabilities. Crucially, the
introduction of dropout in the intermediate layers fosters a more robust
network architecture. It mitigates the risk of the model developing a
dependence on specific neuron patterns, a phenomenon that could lead to
deterministic mappings and compromise privacy. Concurrently, this approach
promotes the learning of diverse and redundant pathways within the network,
contributing significantly to the model’s ability to generalize effectively to
new, unseen data. The intermittent removal of neurons aids in diversifying the
internal representations, ensuring that the network does not settle into
predictable pathways, thereby bolstering both the privacy and adaptability of
the model.

###  C.2 Alpha Scheduler

The AlphaScheduler class is implemented to dynamically control a parameter,
$\alpha$, during the training of neural networks. This class is initialized
with several key parameters: the total number of training epochs (num_epochs),
the initial (alpha_start) and final (alpha_end) values of $\alpha$, and the
rate of linear increment during the initial phase of training
(linear_increment). The scheduler’s operation is divided into two distinct
phases. In the initial phase, covering approximately the first third of the
total epochs, $\alpha$ increases linearly. The subsequent phase employs a
logistic growth model, allowing $\alpha$ to approach its final value in a
controlled and gradual manner, thus avoiding abrupt changes that could
negatively impact the training process. AlphaScheduler allows for adjustments
in both the linear growth rate and the steepness of the logistic curve,
facilitating its adaptation to a variety of training scenarios. Moreover, the
scheduler provides functionalities for visualizing the evolution of $\alpha$
across the training epochs and for logging these values, aiding in the
monitoring and fine-tuning of the training regimen.

Furthermore, the gradual increase in the complexity coefficient $\alpha$,
which is related to the encoding-rate or compression bit-rate, facilitates
continuous learning at varying levels of complexity. For a specific
coefficient $\alpha$, it is possible to assess both the utility performance
and the privacy leakage for all $\alpha$ values up to and including this
threshold. Conversely, when training and evaluating our model for a complexity
coefficient exceeding a particular $\alpha$ value, we can efficiently build
upon the previously trained models. This approach not only ensures a seamless
progression in learning complexity but also contributes to the efficiency and
effectiveness of the model training process by leveraging the foundational
work established at lower complexity levels.

###  C.3 Uncertainty Decoder (Conditional Generator):

The decoder employs Feature-wise Linear Modulation (FiLM) to dynamically
modulate the internal representations of each layer based on the attribute
$\mathbf{S}$. This modulation is facilitated by dedicated gamma and beta
generators, implemented as small MLPs within the _film_generator method, which
produce scaling and shifting parameters for each neuron in a layer, directly
from the uncertainty attribute $\mathbf{S}$. These parameters are then applied
to the activations in each layer, enabling the network to adjust its
processing in a manner that is finely attuned to the inherent uncertainty of
each specific input.

##  D Deep Private Feature Extraction/Generation Experiment

Figure D.1: Training the deep variational $\mathsf{GenPF}$ model on Colored-
MNIST dataset, employing the learning scenario ‘End-to-End Raw Data Scratch
Learning’. Figure D.2: Evaluating the performance of the deep variational
GenPF model, trained on the Colored-MNIST dataset, with the digit number as
the sensitive attribute and the digit color as the useful data. Figure D.3:
Evaluating the performance of the deep variational GenPF model, trained on the
Colored-MNIST dataset, with the digit color as the sensitive attribute and the
digit number as the useful data.

Figure D.4: Qualitative evaluation of privacy-preserving synthetic samples
$\mathbf{X}^{\texttt{uncertainty}}$ generated by the conditional generator
$g_{\bm{\varphi}}$, using a custom Colored-MNIST dataset, where the sensitive
attribute under consideration is the digit color. The setting is defined with
$d_{\mathbf{z}}=8$. For scenario (a), the color probabilities are set as
$P_{S}(\mathsf{Red})=\frac{1}{2}$, $P_{S}(\mathsf{Green})=\frac{1}{6}$, and
$P_{S}(\mathsf{Blue})=\frac{1}{3}$. In scenario (b), all probabilities are
equal with
$P_{S}(\mathsf{Red})=P_{S}(\mathsf{Green})=P_{S}(\mathsf{Blue})=\frac{1}{3}$.
Figure D.5: Qualitative evaluation of privacy-preserving synthetic samples
$\mathbf{X}^{\texttt{uncertainty}}$ generated by the conditional generator
$g_{\bm{\varphi}}$, using a custom Colored-MNIST dataset, where the sensitive
attribute under consideration is the digit number. The setting is defined with
$d_{\mathbf{z}}=8$. For scenario (a), the color probabilities are set as
$P_{S}(\mathsf{Red})=\frac{1}{2}$, $P_{S}(\mathsf{Green})=\frac{1}{6}$, and
$P_{S}(\mathsf{Blue})=\frac{1}{3}$. In scenario (b), all probabilities are
equal with
$P_{S}(\mathsf{Red})=P_{S}(\mathsf{Green})=P_{S}(\mathsf{Blue})=\frac{1}{3}$.