# Understanding random-walk dynamical phase coexistence through waiting times

David C. Stuhrmann  Department of Physics, Stockholm University,
Roslagstullsbacken 21, SE-106 91 Stockholm, Sweden  Francesco Coghi
<EMAIL_ADDRESS>Nordita, KTH Royal Institute of Technology and Stockholm
University, Hannes Alfvéns väg 12, SE-106 91 Stockholm, Sweden

###### Abstract

We study the appearance of first-order dynamical phase transitions (DPTs) as
‘intermittent’ co-existing phases in the fluctuations of random walks on
graphs. We show that the diverging time scale leading to critical behaviour is
the waiting time to jump from one phase to another. This time scale is crucial
for observing the system’s relaxation to stationarity and demonstrates
ergodicity of the system at criticality. We illustrate these results through
three analytical examples which provide insights into random walks exploring
random graphs.

Introduction. Random walks are arguably the most versatile model [1, 2] to
describe various transport processes in natural and artificial environments
described as complex networks, including spreading of infections, propagation
of information, search algorithms, and community detection [3, 4, 5, 6, 7, 8].
Often, studies focus on dynamical observables whereby a single random walker
hops on a graph and accumulates information related to some characteristics of
the states visited over time. Among these dynamical observables we list first-
passage times, currents, occupation times and entropy production rates.
Although the typical behaviour of these dynamical observables obtained for
long times is nowadays of easy interpretation, fluctuations and rare events,
which are important over finite observation times, are less understood. In
particular, among all possible rare events, dynamical phase transitions are
strongly relevant.

Dynamical phase transitions (DPTs) are considered as changes in the random-
walk fluctuation mechanisms. These have been observed in various models of
single and many-particle interacting systems, involving the limit of certain
parameters [9]. These are large system sizes [10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23], large particle numbers [24, 25] and system volumes
[26, 27], or parameters associated to stochastic resetting [28, 29, 30, 31,
32, 33], or again small rate/weak noise limits [34, 35, 36, 37] and strong
driving fields [38] of driven particle models. Recently, DPTs were observed in
association with anomalous scaling of large deviations too [39, 40, 41].

DPTs are considered to arise whenever a non-analytic (critical) behaviour
appears in large deviation functions, e.g., scaled cumulant generating
functions (SCGFs) or rate functions. This critical behaviour is surely a
necessary condition, unlike time-reversal symmetry breakings [26, 15, 16, 17],
manifesting the divergence of a relevant time-scale in the system. In the
context of Markov processes, such a diverging time scale may arise as
consequence of metastability [42, 43, 44, 45] whereby the system slowly
relaxes from a state that appears stationary at short times towards another
that is genuinely stationary.

Nonetheless, it is important to note that a non-differentiable point in a
large deviation function is not enough to demonstrate a transition, such as
phase coexistence, in the fluctuations of a dynamical observable. In systems
that possess a well-defined free energy and adhere to the Landau theory of
phase transitions, such as equilibrium systems, this issue does not arise.
However, when examining the time-dependent dynamics of a system and
considering a large deviation function, the latter might not exhibit all the
characteristics of a free energy, except in several cases as demonstrated in
[34, 16, 17], despite sharing the same mathematical form. Therefore, in such a
scenario, in order to link a kink in a SCGF to a physical transition one needs
to better understand the phenomenology of the model being analysed [18, 9,
21], which may or may not show equilibrium-like phases.

In this paper, we show that when a non-differentiable point appears in the
SCGF of a time-additive observable of a random walk, the relevant diverging
time scale—akin to a correlation length in equilibrium statistical
mechanics—supporting the co-existence of two phases is the waiting time to
jump from a phase to the other. Having two co-existing phases is intended at
the level of single random-walk trajectories being ‘intermittent’, i.e., the
random walker keeps hopping from a phase to the other. In such a scenario, we
will show that by opportunely re-scaling the large deviation functions with
the jump waiting time, the kink in the SCGF disappears, restoring a fully
analytic function and the large deviation principle for the observable under
examination. This means that the system once observed with the right time
scale is still ergodic and therefore the walker visits all regions of the
state space. We illustrate our findings through three analytical examples. Two
of these are borrowed from a previous publication [22], while one is entirely
original. We believe these examples help to understand fluctuations of random
walks exploring random graphs [14, 19, 46], as described toward the end of the
paper.

Model set up, large deviations, and the driven process. We consider an
$n$-time-step random walk (RW) $X=(X_{1},X_{2},\cdots,X_{\ell},\cdots,X_{n})$
on a finite connected and undirected graph $G=(V,E)$ characterised by a set of
states $V$ of finite size $N$ and a set of edges $E$. The RW dynamics is
determined by the $N\times N$ stochastic transition matrix
$\Pi=\left\\{\pi_{ij}\right\\}$ giving the probability $\pi_{ij}$ of the RW to
move from $X_{\ell}=i$ at time $\ell$ to $X_{\ell+1}=j$ at time $\ell+1$. If
$i$ and $j$ are not connected $\pi_{ij}=0$, otherwise $0<\pi_{ij}\leq 1$.

At each time step $\ell$ the RW collects a certain ‘cost’ (or ‘reward’,
‘observable’) related to the state of the system visited, namely
$f(X_{\ell})$. We focus on the dynamical observable that characterises the
mean cost visited by a random walk trajectory,

$C_{n}=\frac{1}{n}\sum_{\ell=1}^{n}f(X_{\ell})\ ,$ (1)

with $f$ a bounded function. Because the RW is ergodic—this is guaranteed by
the properties of the graph $G$ [47, 48]—$C_{n}$ converges to the ergodic
average

$\sum_{i\in V}\rho_{i}f(i)\coloneqq c^{*}\ ,$ (2)

where $\rho=\\{\rho_{i}\\}$ is the stationary distribution of the RW. For a
finite observation time, the observable $C_{n}$ is a random variable of the
random walk process and its distribution $P_{N,n}(C_{n}=c)\coloneqq
P_{N,n}(c)$ is known to take the large deviation form [49, 47, 48]

$P_{N,n}(c)=e^{-nI_{N}(c)+o(n)}\ ,$ (3)

with the time-leading behaviour given by the non-negative large deviation rate
function $I_{N}(c)$ and $o(n)$ denoting corrections smaller than linear in
$n$.

The large deviation rate function $I_{N}(c)$ can be hard to derive if the
distribution $P_{N,n}(c)$ is unknown. In such a case, the rate function can be
calculated by means of the so-called Gärtner–Ellis theorem [49, 47, 48]. This
states that given a differentiable scaled cumulant generating function (SCGF)

$\Psi_{N}(s)=\lim_{n\rightarrow\infty}\frac{1}{n}\ln\mathbb{E}\left[e^{nsC_{n}}\right]\
,$ (4)

the rate function $I_{N}$ can be obtained via the following Legendre
transform:

$I_{N}(c)=s^{*}c-\Psi_{N}(s^{*})\,,$ (5)

where $s^{*}$ is the unique root of $\Psi_{N}^{\prime}(s)=c$ [47]. In
particular, given that the RW $X$ is ergodic, the form of the SCGF simplifies
to

$\Psi_{N}(s)=\ln\zeta_{s},$ (6)

where $\zeta_{s}$ is the dominant eigenvalue of the so-called tilted matrix
$\tilde{\Pi}_{s}=\left\\{\left(\tilde{\pi}_{s}\right)_{ij}\right\\}$, with
components

$\left(\tilde{\pi}_{s}\right)_{ij}=\pi_{ij}e^{sf(i)}\ .$ (7)

The large deviation picture is complete once we understand how fluctuations
$C_{n}=c$ are created in time. To do so, we construct the driven process [50,
51, 52] which, in this context, is a biased RW [51, 19] whose transition
probability matrix is given by

$\left(\pi_{s}\right)_{ij}=\frac{\left(\tilde{\pi}_{s}\right)_{ij}r_{s}(j)}{r_{s}(i)e^{\Psi_{N}(s)}}\
,$ (8)

where $r_{s}$ is the right eigenvector associated with $\zeta_{s}$. Under this
process, the observable $C_{n}$ is asymptotically distributed according to the
canonical form

$P^{(s)}_{N,n}(C_{n}=c)=\frac{e^{nsc}P_{N,n}(c)}{\mathbb{E}\left[e^{nsC_{n}}\right]}\
.$ (9)

The driven process is well defined for finite $N$, still Markovian, and
ergodic and can be interpreted as the effective dynamics of the subset of
paths of the original RW leading to a fluctuation
$C_{n}=c=\Psi_{N}^{\prime}(s)$ [19, 46].

Dynamical phase transitions: phase coexistence. Thanks to the
Perron–Frobenious theorem, at finite $N$, the SCGF (4) and the rate function
(5) are both analytic functions [47, 48]. However, there is no general theorem
that guarantees that for infinite $N$

$\Psi(s)\coloneqq\lim_{N\rightarrow\infty}\Psi_{N}(s)\,,$ (10)

and its Legendre transform $I(c)$ are analytic. As mentioned in the
introduction, there are many cases described in the literature where large
deviation functions show singular points for such a limit.

Often, these singularities are interpreted as DPTs, viz. changes in the
mechanisms that generate particular fluctuations of the observable $C_{n}$. In
studying transitions, we follow a common practice used for equilibrium
systems, as proposed by Ehrenfest [53]. Even for time-dependent models, we use
the non-continuous derivative of the SCGF to determine the order of the
transition. 111Sometimes scientists define the order of the DPT by looking at
the rate function rather than the SCGF. The SCGF $\Psi(s)$ is, arguably,
closer in form to a Helmoltz (canonical) free energy although this, strictly
speaking, would be obtained by dividing $-\Psi(-s)$ by the Laplace parameter
$s$ [47]. We do not do that because $\Psi(s)$ is already, conveniently,
convex. Furthermore, because of the Legedre transform (5) connecting the SCGF
to the rate function, a DPT of order $n$ in the SCGF will be interpreted as of
order $n+1$ in the rate function.. For this reason, a non-differentiable point
$s_{c}$ in the SCGF $\Psi(s)$ is often referred to be a first-order DPT and
therefore to signal an abrupt change in the fluctuations of $C_{n}$ and,
consequentially, the emergence of phase coexistence. However, it has recently
been pointed out that such singular response of the SCGF is not strictly
related with coexisting phases.

Indeed, other scenarios could arise, such as that of a slow system, or a pure
ergodicity-breaking transition [18, 21]. Applied to our context, in the former
case, the random walker is simply extremely slow in moving from a phase to the
other and the overall picture is that one of a RW slowly leaving a metastable
state and being absorbed by a stable one. In the latter, we assist to the
breaking of the large deviation principle for the observable under examination
and therefore trajectories either visit one phase or the other (no mixing).
Albeit their different physical interpretations, all these scenarios are
commonly described by the blow-up of a characteristic time scale, namely
$\tau(N)$, for $N\rightarrow\infty$.

Fully characterising the time scale $\tau(N)$ allows one to properly re-scale
the Laplace parameter $s$ around $s_{c}$, the SCGF $\Psi(s)$, and the rate
function $I(c)$ as

$\displaystyle\bar{s}(s)$ $\displaystyle=\tau(N)(s+s_{c})$ (11)
$\displaystyle\bar{\Psi}_{N}(\bar{s})$
$\displaystyle=\tau(N)\left(\Psi_{N}(s(\bar{s}))-\Psi(s_{c})\right)$ (12)
$\displaystyle\bar{I}_{N}(c)$ $\displaystyle=\tau(N)I(c)\,,$ (13)

such that $\bar{s}$ and $\bar{\Psi}_{N}(\bar{s})$ are now centered around $0$
and we can re-write (3) at leading order in $n$ and for an observation time
$n\gg\tau(N)$ 222This, in turn, explains the order of the limits taken, which
often do not commute. as $P_{N,n}(c)\approx e^{-\bar{n}\bar{I}_{N}(c)}$ with a
new ‘speed’ given by $\bar{n}\coloneqq n/\tau(N)$. The system restores a large
deviation principle and does not experience ergodicity breaking if the
functions (12) and (13) are smooth for $N\rightarrow\infty$.

Incidentally, from (9) we can obtain the rate function and, by Legendre
transform, the SCGF of the driven process which read

$\displaystyle I^{(s^{*})}_{N}(c)$
$\displaystyle=I_{N}(c)-s^{*}c+\Psi_{N}(s^{*})$ (14)
$\displaystyle\Psi^{(s^{*})}_{N}(s)$
$\displaystyle=\Psi_{N}(s+s^{*})-\Psi_{N}(s^{*})\,,$ (15)

having replaced $s$ with $s^{*}$ in (9). Therefore, $\bar{\Psi}_{N}(\bar{s})$
in (12) and $\bar{I}_{N}(c)$ in (13) represent the $\tau(N)$-rescaled
versions, for $s^{*}=s_{c}$, of (15) and (14) respectively. In other words,
the function $\bar{I}(c)$ is the limiting (for $N\rightarrow\infty$) rate
function associated with the observable $C_{n}$ of the driven process at
$s_{c}$, opportunely rescaled by the diverging time scale $\tau(N)$. The
latter provides an indication of the required simulation time for the driven
process to relax and yield reliable statistics of $C_{n}$.

Finally, we argue that in the case of a two-phase coexistence, signalled by a
non-differentiable point in the SCGF $\Psi(s)$, the relevant time scale
$\tau(N)$ is played by the waiting time to jump from a phase of the system to
the other. In the following, we discuss three illustrative examples of RWs
exploring graphs. For these, phase coexistence in the fluctuations of $C_{n}$
is visualised by simulating the driven process in the vicinity of the critical
parameter $s_{c}$ for large values of the parameter $N$ and checking that RW
trajectories are intermittent between the two phases (see, for instance, Fig.
2).

Example 1: Two-state Random Walk. We start by considering a two-state RW. We
name the two states ‘chain’ and ‘bulk’ and define the transition matrix to be

$\Pi=\begin{pmatrix}\frac{1}{2}&\frac{1}{2}\\\
\frac{1}{N}&1-\frac{1}{N}\end{pmatrix}\,,$ (16)

such that, by increasing $N$, the RW spends on average more time in the
‘bulk’. [Notice that the parameter $N$ here is not the size of the graph (as
considered when setting up the model). However, it will play the same role.]
Finally, the observable considered is (1) with $f(\text{chain})=1/N$ and
$f(\text{bulk})=1$.

Typically, according to (2), the RW collects a cost
$c^{*}=(2+N^{2})/(2N+N^{2})$ which approaches $1$ for large $N$. SCGF (4) and
rate function (3) characterising the long-time fluctuations of this observable
have already been studied in [22]. In the limit $N\rightarrow\infty$ the SCGF
$\Psi(s)$ develops a kink at $s=s_{c}\coloneqq-\ln 2$ which leads to a linear
section in $I(c)$ (see black curves in the panels (a) and (b) of Fig. 1). For
$s<s_{c}$, fluctuations arise from a longer time spent in ‘chain’, while for
$s>s_{c}$, fluctuations arise from a longer time spent in ‘bulk’.

Figure 1: Two-state RW: SCGFs $\Psi_{N}(s)$ in (a) and rate functions
$I_{N}(c)$ in (b) at increasing values of $N$ (coloured curves) along with
their limiting functions $\Psi(s)$ and $I(c)$ (dark grey curves). Re-scaled
versions $\bar{\Psi}_{N}(\bar{s})$ and $\bar{I}_{N}(c)$ (coloured curves),
along with their limits $\bar{\Psi}(\bar{s})$ and $\bar{I}(c)$ (dark grey
curves) in (c) and (d).

At the critical value $s_{c}$, the walker will spend half its time in ‘chain’
and the other half in ‘bulk’. In particular, in the long-time limit an
intermittent behaviour will arise whereby the walker, after spending a certain
amount of time in ‘chain’, will hop onto ‘bulk’ and vice-versa. For such a
simple model, there is no other way the RW can create the fluctuation
associated with $s_{c}$. We capture this intermittent behaviour in Fig. 2 by
simulating the driven process (8) with $s=s_{c}$ for finite but increasingly
larger values of $N$.

Figure 2: From (a) to (d), intermittent trajectories visiting ‘bulk’ and
‘chain’ at increasing values of $N$ for the two-state RW model. The larger the
$N$ the longer the waiting time to visit the other phase.

Evidently, the larger the $N$ the longer the time the RW waits before hopping
to the other phase. This is the relevant—arguably the only for this model—time
scale $\tau(N)$ that diverges for $N\rightarrow\infty$ and that leads to the
appearance of a kink in the SCGF at $s_{c}$. The derivation of this effective
time scale was accomplished in a previous work [22]—without much physical
insights—by considering a general power-law form of $\tau(N)$, analytically
expanding (12) in $N$ and selecting the correct exponent for the power law
such that the leading order of the expansion
$\bar{\Psi}(\bar{s})\coloneqq\lim_{N\rightarrow\infty}\bar{\Psi}_{N}(\bar{s})$
is not trivial. For a detailed explanation of the derivation, we refer the
reader to [22]. In the bottom panels (c) and (d) of Fig. 1 we display
$\bar{\Psi}_{N}(\bar{s})$, its Legendre transform $\bar{I}_{N}(c)$ and their
respective limits $\bar{\Psi}(\bar{s})=\bar{s}+\sqrt{4+\bar{s}^{2}}-2$ and
$\bar{I}(c)$. Because of the smoothness of these last functions, in the time
scale defined by $\tau(N)$ a large deviation principle is restored and
fluctuations can be studied at $s_{c}$.

In Fig. 3(a) we plot $\tau(N)=\sqrt{N}$ and compare it with the mean waiting
time to hop from ‘chain’ to ‘bulk’ and vice-versa at increasing values of $N$.
The average value of this quantity is obtained by simulating a driven process
at $s=s_{c}$, counting the transitions unidirectionally between the states,
and dividing the simulation time by the number of transitions. Furthermore, we
remark that $\tau(N)$ has the same scaling form of the relaxation time of the
driven process for $s=s_{c}$ calculated as the negative inverse of the
spectral-gap logarithm of (8) (not displayed in Fig. 3(a) as fully overlapping
$\tau(N)$—modulo $N$-independent prefactors). Evidently, $\tau(N)$ well
matches numerical simulations providing evidence that the critical time scale
in a phase-coexistence scenario is determined by the waiting time between
jumps.

Figure 3: Time re-scalings $\tau(N)$ for the models investigated (black solid
lines) compared with mean waiting times—in (c), these are multiplied by the
$N$-independent prefactor $1.37$—to hop from one phase to the other for
simulations of driven processes at $s=s_{c}$. For each $N$ we run $100$
simulations of $n=10^{6}$ time steps (average marked as a solid coloured line
within one standard deviation).

Example 2: Bulk-Chain Random Walk. We now focus on a slightly more complicated
model. Differently from the previous case, the fluctuation at the critical
point can arise through two different mechanisms and we will show that the
dominant one is an intermittent behaviour supporting phase coexistence.

We analyse an unbiased RW with transition matrix

$\pi_{ij}=\frac{a_{ij}}{k_{i}}\,,$ (17)

with $A=\left\\{a_{ij}\right\\}$ representing the adjacency matrix of a graph
of $N$ nodes, i.e., $a_{ij}=1$ if states $i$ and $j$ are connected and
$a_{ij}=0$ otherwise, and $k_{i}=\sum_{j=1}^{N}a_{ij}$ representing the
connectivity of state $i$. The graph is composed by a fully connected bulk of
$N-2$ nodes and a single chain of $2$ nodes with connectivity $2$ and $1$ (we
name this structure ‘dangling chain’). Because of symmetry, the graph has only
$4$ qualitatively-different nodes. These are: the node of degree $1$ at the
edge of the chain, the node of degree $2$ in the middle of the chain, the node
of degree $N-2$ (gateway from now on) connecting bulk and chain, and a
representative node of the bulk of degree $N-3$. On such a structure, the
unbiased RW collects a cost of the form (1) with $f(X_{\ell})=k_{X_{\ell}}/N$.

As $N$ increases, the RW spends more time in the bulk of the graph. The
ergodic value, denoted by $c^{*}$, can be calculated and is given by
$c^{*}=(-18+23N-8N^{2}+N^{3})/(N(10-5N+N^{2}))$. In large graphs, the RW tends
to get lost in the bulk for a simple entropic reason: the higher the number of
neighbors, the harder to find the dangling chain. Fluctuations of this model
were already studied and we refer to [22] for details on the calculations. In
the panels (a) and (b) of Fig. 4 we report the SCGF $\Psi_{N}(s)$, the rate
function $I_{N}(c)$, and their limiting behaviour for $N\rightarrow\infty$.
Evidently, a kink appears at $s_{c}\coloneqq-(\ln 2)/2$. Similarly to the
previous case, for $s<s_{c}$, the RW favours the dangling chain, while for
$s>s_{c}$, it favours the bulk. At the critical value, it splits its time
equally between both phases.

Figure 4: Bulk-Chain RW: SCGFs $\Psi_{N}(s)$ in (a) and rate functions
$I_{N}(c)$ in (b) at increasing values of $N$ (coloured curves) along with
their limiting functions $\Psi(s)$ and $I(c)$ (dark grey curves). Re-scaled
versions $\bar{\Psi}_{N}(\bar{s})$ and $\bar{I}_{N}(c)$ (coloured curves),
along with their limits $\bar{\Psi}(\bar{s})$ and $\bar{I}(c)$ (dark grey
curves) in (c) and (d).

For this particular model there are two distinct ways the RW can split its
time between bulk and dangling chain. On the one hand, the RW could keep
hopping back and forth from the node of degree $2$ and the gateway. On the
other hand, it could spend some time in the dangling chain, then hop to the
bulk and spend some time there before jumping back. Although both mechanisms
are possible, the latter is more probable than the former. We checked this
both estimating the probability of the two different events per unit time (as
suggested in [21]) and by running simulations of the driven process at $s_{c}$
for increasingly larger values of $N$.

We find that trajectories are intermittent in this case too. As they are
qualitatively equivalent to the previous case we refer back to Fig. 2 for
illustration purposes. The larger the $N$ the longer the waiting time of the
RW before it visits the other phase. By analytically expanding (12) in $N$ as
mentioned for the previous example we calculate $\tau(N)=N$ and the re-scaled
function $\bar{\Psi}(\bar{s})$ (its form is lengthy and not reported here, see
[22]). We plot the latter, its Legendre transform, and numerical realisations
for finite $N$ given by (12) and (13) in the panels (c) and (d) of Fig. 4.
Numerical realisations smoothly approach $\bar{\Psi}(\bar{s})$ endorsing the
idea that at the relevant time scale $\tau(N)$ no critical behaviour emerges.

Eventually, in Fig. 3(b), we compare the form $\tau(N)=N$—corresponding to the
relaxation time scale of the driven process in this case too—with numerical
simulations of the driven process waiting time at the critical value $s_{c}$
for different values of $N$. Numerical simulations strongly support the
theory, providing further evidence that the waiting time is the key factor
leading to a diverging time scale and dynamical phase coexistence.

Example 3: Three-state Random Walk. We consider a novel model of a RW over
three states named ‘chain1’, ‘chain2’, and ‘bulk’, characterised by the
following transition matrix:

$\Pi=\begin{pmatrix}0&1&0\\\ \frac{1}{2}&0&\frac{1}{2}\\\ 0&\frac{\bar{k}}{\ln
N}&1-\frac{\bar{k}}{\ln N}\end{pmatrix}\,,$ (18)

with $\bar{k}$ and $N$ being two positive parameters of the model such that
$\bar{k}\leq\ln N$. Like the previous models, we can visualise the underlying
graph as a dangling chain (composed by ‘chain1’ and ‘chain2’ states) linked to
a bulk, which in this case is composed of a single self-looped state. Just
like the Bulk-Chain RW model, increasing the value of $N$ reduces the
probability for the random walker to transition from the bulk to the dangling
chain. However, due to the logarithmic dependence on $N$ (which will be
motivated in the following), this transition is relatively easier compared to
the Bulk-Chain RW model. Finally, the RW collects also in this case an
observable of the form (1) with $f(\text{chain1})=1$, $f(\text{chain2})=2$,
and $f(\text{bulk})=\bar{k}$.

The long-time behaviour of the observable $C_{n}$ is given by
$c^{*}=(\bar{k}(5+\ln N))/(3\bar{k}+\ln N)$ and fluctuations can be studied
with large deviation theory as outlined above. The SCGF $\Psi_{N}(s)$ in (4)
can be calculated analytically but its form is lengthy and since it is not
useful here is not displayed. Its limit for $N\rightarrow\infty$ in (10) can
also be calculated and reads

$\Psi(s)=\begin{cases*}\frac{3s-\ln 2}{2}&if \, $s<s_{c}$\\\ \bar{k}s&if \,
$s>s_{c}$\end{cases*}\,,$ (19)

with a kink at

$s_{c}=\frac{\ln 2}{3-\bar{k}}\,.$ (20)

These functions, along with their transforms, i.e., $I_{N}(c)$ and $I(c)$, are
displayed in the panels (a) and (b) of Fig. 5. Once again, when $s>s_{c}$, the
RW will spend more time in the bulk ($c>c^{*}$), while for $s<s_{c}$ the RW
favours the dangling chain ($c<c^{*}$).

Figure 5: Three-state RW: SCGFs $\Psi_{N}(s)$ in (a) and rate functions
$I_{N}(c)$ in (b) at increasing values of $N$ (coloured curves) along with
their limiting functions $\Psi(s)$ and $I(c)$ (dark grey curves). Re-scaled
versions $\bar{\Psi}_{N}(\bar{s})$ and $\bar{I}_{N}(c)$ (coloured curves),
along with their limits $\bar{\Psi}(\bar{s})$ and $\bar{I}(c)$ (dark grey
curves) in (c) and (d).

At the critical value $s_{c}$ the RW will spend half its time in the dangling
chain and the other half in the bulk. Even in this case intermittent behaviour
arises as leading mechanism to generate fluctuations around the critical point
$s_{c}$. We check this numerically by simulating the driven process (8) for
increasingly larger values of $N$ and plot the trajectories in Fig. 6.

Figure 6: From (a) to (d), intermittent trajectories visiting ‘bulk’ and
‘chain’ at increasing values of $N$ for the three-state RW model. The larger
the $N$ the longer the waiting time to visit the other phase, although because
of the logarithmic scale the change is less evident with respect to the two-
state RW of Fig. 2.

Even in this scenario, as the value of $N$ increases, the RW experience longer
waiting times before transitioning to the other phase.

We derive $\bar{\Psi}(\bar{s})$ as leading-in-$N$ behaviour of (12) and the
time scale $\tau(N)$. Analytically, we proceed by considering the
characteristic equation for the dominant eigenvalue $\lambda=e^{\Psi_{N}(s)}$
of the tilted matrix (7), i.e.,

$(e^{\bar{k}s}-\lambda)(e^{3s}-2\lambda^{2})-\frac{e^{\bar{k}s}\ln\bar{k}}{\ln
N}\left(e^{3s}+e^{2s}\lambda-2\lambda^{2}\right)=0\,.$ (21)

We replace $s$ and $\Psi_{N}(s)$ as functions of $\bar{s}$ and
$\bar{\Psi}_{N}(\bar{s})$ inverting the relations given in (11) and (12)
respectively. Then, we make an educated guess and also replace
$\tau(N)=\left(\ln N\right)^{\alpha}$ with $\alpha>0$ and keep only the first
order in $(\ln N)^{-\alpha}$ of (21). The value of $\alpha=1/2$—the smallest
possible—and the smooth function $\bar{\Psi}(\bar{s})$ are found imposing that
the zero of the leading term of (21) is not the kinked function in (19).
Figures (c) and (d) of Fig. 5 display the plots of $\bar{\Psi}(\bar{s})$ and
$\bar{I}$, along with their finite-$N$ approximations (12) and (13)
respectively. The smoothness of the limiting functions suggests, once again,
that there is a proper time scale in the large deviations such that no
critical behaviour is observed.

Eventually, we compare in Fig. 3(c) the scaling $\tau(N)=\left(\ln
N\right)^{1/2}$ with the mean waiting time computed numerically by simulating
driven processes with fixed $s=s_{c}$ for increasingly larger values of $N$.
Once again, $\tau(N)$ corresponds to the relaxation time scale of the driven
process and its form well matches numerical simulations of the waiting time
multplied by an $N$-independent prefactor. We conclude that the waiting time
is the leading diverging time scale supporting phase coexistence in the first-
order DPT.

Implications for Erdös–Rényi random graphs. We have discussed three models
that aim to capture the characteristics of a simplified version of an unbiased
RW exploring an Erdös–Rényi (ER) random graph. An ER graph is created by
randomly connecting a fixed number $N$ of nodes. The probability of connecting
two nodes is determined by $\bar{k}/N$, where $\bar{k}$ represents the average
connection of the graph. After generating the graph, only its largest
connected component is retained and used as a base structure for a RW
collecting a cost as in (1).

Large deviation theory has recently been employed to study this model [14,
19]. In the case where $\bar{k}$ is sufficiently small, indications of a DPT
have been identified between a phase characterised by bulk delocalisation and
another phase where the RW localises along dangling chains. However, no formal
proof has been provided thus far for the existence of this DPT in the
infinite-size ER graph ensemble.

The two-state and the Bulk-Chain RW models had previously been introduced [22]
as analytical models aimed at explaining the delocalisation-localisation DPT
in ER graphs. Our three-state RW takes a further step in this direction. In
the Bulk-Chain RW, increasing the size of $N$ expands the bulk by adding fully
connected nodes. However, this does not accurately reflect the behaviour of
adding a node in an ER graph, where the new node is not fully connected but,
on average, maintains the same number of connections $\bar{k}$. Nevertheless,
the presence of the new node increases the distance between a random node in
the bulk and a node with degree $1$ in a dangling chain. Since the average
shortest distance between any two nodes of a random graph increases
logarithmically with $N$, our third model considers the probability of
transitioning from the bulk to the dangling chain to be inversely proportional
to $\ln N$. Meanwhile, we maintain a constant cost (1) accumulated by the RW
while visiting the bulk phase, which is equal to $\bar{k}$.

Indeed, this new model aligns more closely with the exploration of an ER
random graph. Our three-state RW exhibits a delocalisation-localisation DPT
that occurs at the critical value (20), which is inversely proportional to
$\bar{k}$. This is expected in the ER graph too: the larger the $\bar{k}$ the
more connected the bulk, the smaller the tilting $s$ to escape it. However,
what is particularly striking about this transition is its speed, which goes
like $(\ln N)^{1/2}$ and indicates the RW undergoes an exceptionally slow
change in behaviour as $N$ increases.

Conclusion. We have investigated the appearance of first-order dynamical phase
transitions in large deviation functions of simple discrete-time and space
dynamical systems. The key finding of our study is that a kink in the scaled
cumulant generating function of a time-additive observable for a random walk
indicates phase coexistence when the dominant diverging time scale is the
waiting time for the random walk to transition between phases. The
characterisation of such a time scale allows us to properly re-scale large
deviation functions and therefore rule out non-ergodic behaviour. We have
shown this with three illustrative examples that work towards a better
understanding of a potential delocalisation-localisation dynamical phase
transition in random walks on Erdös–Rényi random graphs. Our results suggest
that such a transition may appear at a remarkably slow rate, scaling as
$O((\ln N)^{1/2})$, which poses significant challenges for numerical studies.
Finally, we note that our work could serve as a theoretical ground to
accelerate the learning process in numerical sampling schemes of large
deviations near dynamical phase transitions [56, 57, 58, 59].

Acknowledgements. The authors are grateful to Supriya Krishnamurthy for
support during the work. FC thanks Stephen Whitelam for insightful discussions
at the Lawrence Berkeley National Lab and Giorgio Carugno and Hugo Touchette
for valuable feedback on a first draft of the paper.

## References

  * Grimmet and Stirzaker [2001] G. Grimmet and D. Stirzaker,  _Probability and Random Processes_ (Oxford University Press, Oxford, 2001).
  * Gregory and Vlada [2010] L. Gregory and L. Vlada,  _Random Walk: A Modern Introduction_ (Cambridge University Press, Cambrdige, 2010).
  * Hughes [1995] B. D. Hughes,  _Random walks and random environments: Random walks_ (Oxford University Press, 1995).
  * Noh and Rieger [2004] J. D. Noh and H. Rieger, Random walks on complex networks, Physical Review Letters 92, 118701 (2004).
  * Yang  _et al._ [2005] M. Yang, B. Wang, Y.-X. Han, R. Burioni, and D. Cassi, Random walks on graphs: ideas, techniques and results, Journal of Physics A: Mathematical and General 38, R45 (2005).
  * Barrat  _et al._ [2008] A. Barrat, M. Barthélemy, and A. Vespignani,  _Dynamical Processes on Complex Networks_ (Cambridge University Press, 2008) pp. 1–347.
  * Newman [2010] M. E. J. Newman,  _Networks: An Introduction_ (Oxford University Press, 2010) pp. 1–784.
  * Masuda  _et al._ [2017] N. Masuda, M. A. Porter, and R. Lambiotte, Random walks and diffusion on networks, Physics Reports 716-717, 1 (2017).
  * Whitelam [2021] S. Whitelam, Comment on the literature definition(s) of ‘dynamical phase transition’, arXiv:2112.09107v1 (2021).
  * Bodineau and Derrida [2005] T. Bodineau and B. Derrida, Distribution of current in nonequilibrium diffusive systems and phase transitions, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 72, 066110 (2005).
  * Bertini  _et al._ [2005] L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio, and C. Landim, Current Fluctuations in Stochastic Lattice Gases, Physical Review Letters 94, 030601 (2005).
  * Garrahan  _et al._ [2007] J. P. Garrahan, R. L. Jack, V. Lecomte, E. Pitard, K. Van Duijvendijk, and F. van Wijland, Dynamical first-order phase transition in kinetically constrained models of glasses, Physical Review Letters 98, 195702 (2007).
  * Vaikuntanathan  _et al._ [2014] S. Vaikuntanathan, T. R. Gingrich, and P. L. Geissler, Dynamic phase transitions in simple driven kinetic networks, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 89, 062108 (2014).
  * De Bacco  _et al._ [2016] C. De Bacco, A. Guggiola, R. Kühn, and P. Paga, Rare events statistics of random walks on networks: localisation and other dynamical phase transitions, Journal of Physics A: Mathematical and Theoretical 49, 184003 (2016).
  * Shpielberg and Akkermans [2016] O. Shpielberg and E. Akkermans, Le Chatelier Principle for Out-of-Equilibrium and Boundary-Driven Systems: Application to Dynamical Phase Transitions, Physical Review Letters 116, 240603 (2016).
  * Baek  _et al._ [2017] Y. Baek, Y. Kafri, and V. Lecomte, Dynamical Symmetry Breaking and Phase Transitions in Driven Diffusive Systems, Physical Review Letters 118, 030604 (2017).
  * Baek  _et al._ [2018] Y. Baek, Y. Kafri, and V. Lecomte, Dynamical phase transitions in the current distribution of driven diffusive channels, Journal of Physics A: Mathematical and Theoretical 51, 105001 (2018).
  * Whitelam [2018] S. Whitelam, Large deviations in the presence of cooperativity and slow dynamics, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 97, 062109 (2018).
  * Coghi  _et al._ [2019] F. Coghi, J. Morand, and H. Touchette, Large deviations of random walks on random graphs, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 99, 022137 (2019).
  * Buča  _et al._ [2019] B. Buča, J. P. Garrahan, T. Prosen, and M. Vanicat, Exact large deviation statistics and trajectory phase transition of a deterministic boundary driven cellular automaton, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 100, 020103(R) (2019).
  * Whitelam and Jacobson [2021] S. Whitelam and D. Jacobson, Varied phenomenology of models displaying dynamical large-deviation singularities, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 103, 032152 (2021).
  * Carugno  _et al._ [2023] G. Carugno, P. Vivo, and F. Coghi, Delocalization-localization dynamical phase transition of random walks on graphs, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 107, 024126 (2023).
  * Gutiérrez and Pérez-Espigares [2021a] R. Gutiérrez and C. Pérez-Espigares, Dynamical phase transition to localized states in the two-dimensional random walk conditioned on partial currents, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 104, 044134 (2021a).
  * Nemoto  _et al._ [2019] T. Nemoto, É. Fodor, M. E. Cates, R. L. Jack, and J. Tailleur, Optimizing active work: Dynamical phase transitions, collective motion, and jamming, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 99, 022605 (2019).
  * Agranov  _et al._ [2023] T. Agranov, M. E. Cates, and R. L. Jack, Tricritical Behavior in Dynamical Phase Transitions, Physical Review Letters 131, 017102 (2023).
  * Bunin  _et al._ [2012] G. Bunin, Y. Kafri, and D. Podolsky, Non-differentiable large-deviation functionals in boundary-driven diffusive systems, Journal of Statistical Mechanics: Theory and Experiment 2012, L10001 (2012).
  * Proesmans  _et al._ [2020] K. Proesmans, R. Toral, and C. Van den Broeck, Phase transitions in persistent and run-and-tumble walks, Physica A: Statistical Mechanics and its Applications 552, 121934 (2020).
  * Harris and Touchette [2017] R. J. Harris and H. Touchette, Phase transitions in large deviations of reset processes, Journal of Physics A: Mathematical and Theoretical 50, 10LT01 (2017).
  * Zamparo [2019] M. Zamparo, Large deviations in renewal models of statistical mechanics, Journal of Physics A: Mathematical and Theoretical 52, 495004 (2019).
  * Coghi and Harris [2020] F. Coghi and R. J. Harris, A large deviation perspective on ratio observables in reset processes: robustness of rate functions, Journal of Statistical Physics 179, 131 (2020).
  * Zamparo [2022] M. Zamparo, Statistical fluctuations under resetting: rigorous results, Journal of Physics A: Mathematical and Theoretical 55, 484001 (2022).
  * Mori  _et al._ [2022] F. Mori, K. S. Olsen, and S. Krishnamurthy, Entropy production of resetting processes, Physical Review Research , 023103 (2022).
  * Zamparo and Semeraro [2023] M. Zamparo and M. Semeraro, Large deviations for quadratic functionals of stable Gauss-Markov chains and entropy production, Journal of Mathematical Physics 64, 23302 (2023).
  * Baek and Kafri [2015] Y. Baek and Y. Kafri, Singularities in large deviation functions, Journal of Statistical Mechanics: Theory and Experiment 2015, P08026 (2015).
  * Tsobgni Nyawo and Touchette [2016] P. Tsobgni Nyawo and H. Touchette, Large deviations of the current for driven periodic diffusions, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 94, 032101 (2016).
  * Proesmans and Derrida [2019] K. Proesmans and B. Derrida, Large-deviation theory for a Brownian particle on a ring: a WKB approach, Journal of Statistical Mechanics: Theory and Experiment 2019, 023201 (2019).
  * Di Gaetano  _et al._ [2023] L. Di Gaetano, G. Carugno, F. Battiston, and F. Coghi, Dynamical fluctuations in a minimal model of higher-order networks, arXiv:2303.18169v1 (2023).
  * Espigares  _et al._ [2013] C. P. Espigares, P. L. Garrido, and P. I. Hurtado, Dynamical phase transition for current statistics in a simple driven diffusive system, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 87, 032115 (2013).
  * Nickelsen and Touchette [2018] D. Nickelsen and H. Touchette, Anomalous scaling of dynamical large deviations, Physical Review Letters 121, 090602 (2018).
  * Smith [2022] N. R. Smith, Anomalous scaling and first-order dynamical phase transition in large deviations of the Ornstein-Uhlenbeck process, Physical Review E 105, 014120 (2022).
  * Stella  _et al._ [2023] A. L. Stella, A. Chechkin, and G. Teza, Anomalous Dynamical Scaling Determines Universal Critical Singularities, Physical Review Letters 130, 207104 (2023).
  * Larralde and Leyvraz [2005] H. Larralde and F. Leyvraz, Metastability for Markov processes with detailed balance, Physical Review Letters 94, 160201 (2005).
  * Larralde  _et al._ [2006] H. Larralde, F. Leyvraz, and D. P. Sanders, Metastability in Markov processes, Journal of Statistical Mechanics: Theory and Experiment 2006, P08013 (2006).
  * Macieszczak  _et al._ [2016] K. Macieszczak, M. Guta, I. Lesanovsky, and J. P. Garrahan, Towards a theory of metastability in open quantum dynamics, Physical Review Letters 116, 240404 (2016).
  * Macieszczak  _et al._ [2021] K. Macieszczak, D. C. Rose, I. Lesanovsky, and J. P. Garrahan, Theory of classical metastability in open quantum systems, Physical Review Research 3, 033047 (2021).
  * Gutiérrez and Pérez-Espigares [2021b] R. Gutiérrez and C. Pérez-Espigares, Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 103, 022319 (2021b).
  * Touchette [2009] H. Touchette, The large deviation approach to statistical mechanics, Physics Reports 478, 1 (2009).
  * Dembo and Zeitouni [2010] A. Dembo and O. Zeitouni,  _Large Deviations Techniques and Applications_ , Stochastic Modelling and Applied Probability, Vol. 38 (Springer Berlin Heidelberg, 2010).
  * den Hollander [2000] F. den Hollander,  _Large Deviations_ (American Mathematical Society, 2000).
  * Chetrite and Touchette [2013] R. Chetrite and H. Touchette, Nonequilibrium microcanonical and canonical ensembles and their equivalence, Physical Review Letters 111, 120601 (2013).
  * Chetrite and Touchette [2015a] R. Chetrite and H. Touchette, Nonequilibrium Markov processes conditioned on large deviations, Annales Henri Poincare 16, 2005 (2015a).
  * Chetrite and Touchette [2015b] R. Chetrite and H. Touchette, Variational and optimal control representations of conditioned and driven processes, Journal of Statistical Mechanics: Theory and Experiment 2015, P12001 (2015b).
  * Ehrenfest [1933] P. Ehrenfest,  _Phasenumwandlungen im ueblichen und erweiterten Sinn, classifiziert nach den entsprechenden Singularitaeten des thermodynamischen Potentiales_ (NV Noord-Hollandsche Uitgevers Maatschappij, 1933).
  * Note [1] Sometimes scientists define the order of the DPT by looking at the rate function rather than the SCGF. The SCGF $\Psi(s)$ is, arguably, closer in form to a Helmoltz (canonical) free energy although this, strictly speaking, would be obtained by dividing $-\Psi(-s)$ by the Laplace parameter $s$ [47]. We do not do that because $\Psi(s)$ is already, conveniently, convex. Furthermore, because of the Legedre transform (5) connecting the SCGF to the rate function, a DPT of order $n$ in the SCGF will be interpreted as of order $n+1$ in the rate function.
  * Note [2] This, in turn, explains the order of the limits taken, which often do not commute.
  * Nemoto  _et al._ [2017] T. Nemoto, R. L. Jack, and V. Lecomte, Finite-Size Scaling of a First-Order Dynamical Phase Transition: Adaptive Population Dynamics and an Effective Model, Physical Review Letters 118, 115702 (2017).
  * Ferré and Touchette [2018] G. Ferré and H. Touchette, Adaptive sampling of large deviations, Journal of Statistical Physics 172, 1525 (2018).
  * Coghi and Touchette [2023] F. Coghi and H. Touchette, Adaptive power method for estimating large deviations in Markov chains, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 107, 034137 (2023).
  * Yan  _et al._ [2022] J. Yan, H. Touchette, and G. M. Rotskoff, Learning nonequilibrium control forces to characterize dynamical phase transitions, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 105, 024115 (2022).