{'fraction_non_alphanumeric': 0.04821634062140391, 'fraction_numerical': 0.009666283084004603, 'mean_word_length': 4.1944610480175335, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Large Deviation in Continuous Time Random Walks

We discuss large deviation properties of continuous-time random walks (CTRW) and present a general expression for the large deviation rate in CTRW in terms of the corresponding rates for the distributions of steps' lengths and waiting times. In the case of Gaussian distribution of steps' lengths the general expression reduces to a sequence of two Legendre transformations applied to the cumulant generating function of waiting times. The discussion of several examples (Bernoulli and Gaussian random walks with exponentially distributed waiting times, Gaussian random walks with one-sided L\'evy and Pareto-distributed waiting times) reveals interesting general properties of such large deviations.


I. INTRODUCTION
Continuous time random walk (CTRW) introduced by Montroll and Weiss [1] is a generalization of a simple random walk model, in which the steps follow inhomogeneously in time. In the standard variant of the CTRW, times of steps follow a renewal process in which the waiting times for subsequent steps are independent and identically distributed (i.i.d.) random variables. The model is then fully defined by specifying the probability density function (PDF) of waiting times and of spacial displacements in single steps (also being i.i.d. random variables) [2]. In physics, CTRW is used to model systems showing anomalous diffusion, e.g. situations when the mean square displacements (MSD) x 2 (t) does not grow linearly in time, as predicted by the Fick's law, especially in the cases of subdiffution, when x 2 (t) ∝ t α with α < 1. Such anomalous subdiffusion often arises due to the lack of the first moments of the distribution of waiting times. The anomaly in MSD is accompanied by a non-Gaussian shape of PDF of displacements during a given time t. This line of modelling, following the pioneering work [3], is discussed in the review articles [4] and [5], with some newer developments discussed in chapters of collective monographs [6] and [7]. Many recent works have reported weaker type of anomaly, in which the time-dependence of the MSD is linear, but the form of the PDF is pronouncedly non-Gaussian, especially at shorter times. The decay of the tails of the PDFs is often exponential, see e.g. [8][9][10] as well as [11][12][13] and references therein.
In Ref. [12], Barkai and Burov showed that such exponential decay is a universal behavior of far tails in CTRW, presenting the approach based on subordination of random processes and large deviation theory. In Ref. [14], Wang, Barkai, and Burov presented explicit calculations for the case of exponential and Gamma-(Erlang) distributions of waiting times. In the present work we build on this approach and present a general expression for the large deviations' rate function in CTRW, which we use for discussing several examples beyond the ones considered in [12,14], where we consider both the case when the mean WTD is finite and the case when it diverges.
For the case of Gaussian step length distribution, as in [14], the analysis is especially simple, and the general expression reduces to a sequence of two Legendre transformations of a cumulant generating function of waiting times.
The structure of the present work is as follows: In Sec. II we conduct a preliminary discussion of the model and introduce notation used throughout the work. In Sec. III we derive the main result, which we use in the discussion of several examples; first of them already given in this section. In Sec. IV we consider the case with Gaussian step length distribution, for which the expressions are especially simple. Here different further examples with and without mean waiting times are considered, which are enough for understanding the physics behind the large deviations in CTRW. Sec. VI concludes the work. One "derivation" of a known mathematical result on a physical level of rigor, which we consider to be useful for understanding the approach, is placed in the Appendix.

II. PRELIMINARIES AND NOTATION
Continuous time random walk (CTRW) is a random process which ensues due to subordination of a simple random walk (RW) process x(n) to another random process n(t), which gives us the number of steps done by the random walk up to time t, and is called a directing process, or operational time of the CTRW scheme [2]. The process x(n) is called with this respect a parent process of the CTRW (see Refs. [15,16] for a systematic discussion and terminology). The "inverse" process t(n) corresponding to the sum of independent, identically distributed waiting times in CTRW is called a leading process.
Let the PDF of the parent process be p n (x), and the probability to make exactly n steps up to time t be χ n (t). Then the PDF of displacements in CTRW is [2] p(x, t) = ∞ n=0 p n (x)χ n (t).
For long t, the typical number of steps is very large, and arXiv:2012.09656v1 [cond-mat.stat-mech] 17 Dec 2020 the operational time τ = n can be taken to be continuous. In this limit where f (x, τ ) is a continuous approximation to (fluid limit of) p n (x) and T (τ, t) is the same kind of approximation to χ n (t). Eq. (1) is called the integral formula of subordination. In what follows we will only work in this limit. The parent and the leading processes of the CTRW scheme are processes with independent and identically distributed (i.i.d.) increments, i.e. correspond to sums of i.i.d. random variables. Exactly such sums constitute the elementary (and elemental) class of objects studied in the theory of large deviations. Let x n be a sequence of independent random variables, s n = (x 1 +x 2 +...x n )/n be the empirical mean of the first n elements in the sequence, and P n (s) be the probability distribution of s n . Then, under known conditions, there exists the limit called the rate function (RF), or Cramér's function, of large deviations for s n [17][18][19]. The distribution of s n for sufficiently large n is then given, up to a normalization constant, by When making the inverse variable transformation from s n to the sum S n = x 1 + x 2 + ... + x n = ns n of the first n random variables, one sees that its PDF takes the form up to an n-dependent normalization constant. Eq. (2) will be called the large deviation form for the PDF of the corresponding sum. To avoid ambiguity, we will denote the rate functions by scriptized letters. At the beginning, only two PDFs are known: the one of the single step lengths, and the one of the waiting times. Therefore, in our discussion, we will start from the rate functions of sums of independent and identically distributed random variables (step times and step lengths), and derive the properties of all other rate functions from two rate functions: I(t) and R(x), the ones for the leading process and for the parent process (simple RW), which can be readily calculated. The large deviation forms for the PDFs of the corresponding sums are then and To easily manipulate the variables we have to keep the arguments of all non-power-law functions dimensionless.
To do so, we introduce the natural units of length and time. As a natural unit of length one may choose the mean squared displacement in a single step, and as a natural unit of time a characteristic time of a single step. If the mean waiting time for a step exists, we will choose this mean waiting time as the characteristic time. In the cases when the mean waiting time diverges, for the purpose of comparison of different situations, one should choose a characteristic time such that the mean number of steps n(t) made up to time t is the the same for all cases compared. Note that this requirement is fulfilled when choosing the mean waiting time, provided it exists, as a characteristic time, as above. Thus, from here on, all our quantities are dimensionless. The units can be easily restored in the final expressions when necessary. The two derived rate functions, the ones for the directing process and the one for the whole CTRW (a function we seek to know) will be denoted by T (τ ) and X (x), respectively. The large deviation forms for the PDFs of τ and x are: and Before starting our derivation, let us go through some important properties of the rate functions [17][18][19]. The rate functions for the mean of i.i.d. random variables are convex [18]. Cramér's theorem states that the rate function C(x) is the convex conjugate (a Legendre-Fenchel transformation) of the cumulant generation function L(q) = ln e xq of the distribution of x. For the sake of brevity we will call this transformation simply a Legendre transformation, as it is done, say, when transforming a Lagrange to a Hamilton function in mechanics. For strictly convex rate functions (i.e. for all cases discussed in the present work) this transformation is invertible. The inverse of a Legendre transformation is given by a Legendre transformation again (an involution property). Two other properties of rate functions, which are important for what follows, are that the rate function is non-negative, and that it vanishes identically at the value of x = µ corresponding to the mean of the distribution of the single variable. The rate function can be defined on the whole real line (e.g. for a Gaussian distribution of x), on a half-line (like it is for waiting times), or on a finite interval. Outside of its domain of definition (i.e. outside of the domain available for the initial random variables) it is taken to be "literaly infinite", so that the probability to have such values (the ones outside the domain of definition) is strictly zero.
To keep equations concise we will introduce the following nonstandard notation for the Legendre transformation: Let g(x) be a convex function defined on the corresponding interval, and let a function f (z) of variable z be its Legendre transformation defined as The Legendre transformation is an operator which makes a mapping f (x) → g(z). Our notation will keep track of the variable's names in the corresponding functions The direction of the arrow is connected with the order of the symbols: the operator L acts on the function of x standing right from it, and transforms the function f of variable x into a function g of variable z (the names of the variables are changed from right to the left). Since we choose to denote the variable's names in the notation for the operator, we don't have to put them in the functions at all (but we will).
The main result of the present article is as follows: with being the PDF of waiting times (waiting time density, WTD), and D(q) = e qx = ∞ −∞ e qx λ(x)dx with λ(x) being the PDF of displacements in a single step (steps' lengths density, SLD). For a Gaussian distribution of single steps' lengths discussed in [12,14], the result can be put in a closed form involving only the Legendre transformations

III. THE LARGE DEVIATIONS RATE FOR CTRW
Let us now derive the forms, Eq. (7) and (8). Substituting the large deviation forms for PDFs of the parent and directing processes (Eqs. (3) and (5), respectively) into the integral formula of subordination, Eq. (1), one gets On the l.h.s., we introduce the large deviation form of the whole CTRW (Eq. (6)) and change to the new variables z = x/t and ξ = t/τ : Now, we use the relation between the RF for the leading and directing processes, which is given by see Ref. [20]. The proof of this relation (and the discussion of conditions under which it holds) implies a longer chain of mathematical discussions. Although this relation is known, we sketch a simple explanation on the physical level of rigor is given in Appendix A.
Using this relation one gets This integral can then be solved by the Laplace's method [21]. Thus, we can write where the pre-exponential term is disregarded, since it does not contribute to the large deviations when taking the limit lim t→∞ ln[p(x, t)]/t. Equating the arguments of the exponentials, we get which is our main result, Eq. (7). Note that, the infimum was changed for the supremum of the negative of the expression, which will be useful to later relate this quantity to a Legendre transformation in the case of a Gaussian SLD. Since the large deviation rates R(x) and I(t) are readily given by the Legendre transformations of the corresponding cumulant generating functions, the corresponding supremum can be easily calculated for the cases of interest. In what follows, we consider in some detail the case brought to our attention by the works [12,14], namely, the case of Gaussian distribution of single step lengths. For this case, the RF X (z) follows from the cumulant generating function of waiting times by two Legendre transformations (see below). However, first, as an example, let us analyse the simplest random walk, i.e., the Bernoulli one.
A. CTRW with a fixed step length As a first example, let us consider the Bernoulli random walk, with steps of fixed length ±1 taken with probability 1/2, respectively, and the simplest possible leading process, a Poisson process with rate 1, i.e. with ψ(t) = e −t . The Bernoulli random walk is essentially the first example of Refs. [17] and [18]. For this case Applying Stirling formula we get in the first order in N with s = S/N , so that This function is parabolic around 0 and diverges for x → ±1 (and is "literaly infinite" outside of the interval (−1, 1)). The function I(ξ) = L {ξ←q} L(q) corresponding to a Poisson process can be readily calculated (and essentially is known since long ago), and reads The supremum in Eq. (7), for fixed z is achieved at ξ = 1/ √ 1 + z 2 , and X (z) is readily evaluated: which is the function with a quadratic behavior close to z = 0, X (z) z 2 /2 + O(z 4 ), and with the large-z asymptotics being X (z) |z|(1 − ln 2 + ln |z|) (note that the function is not "cut" at a finite value of z, at difference to the large deviation rate of the parent process).

IV. CTRW WITH GAUSSIAN DISTRIBUTION OF STEPS LENGTHS
For the Gaussian distribution of step lengths the large deviations rate for the parent process is given by Introducing this result into Eq. (7), one obtains which is given by a Legendre transformation of the function I(ξ)/ξ taken at the value of the Legendre variable z = −x 2 /2. Using our notation for the Legendre transformations and the fact that I(ξ) = L {ξ←q} L(q) we arrive at the final result in a closed form Eq. (8). Now we use this formula for discussing several important examples and then make some conclusions about the behavior of the large deviation rate functions of CTRW with Gaussian step lengths' distribution for very large deviations (x 1).

A. Exponential waiting times
Let us assume that the waiting times follow a Poisson process, with ψ(t) = e −t and a rate function given by Eq. (10). Now, we define the function and perform the Legendre transformation where W 0 (·) is the Lambert function. Then, according to Eq. (8), we change the variable to z = −x 2 /2 and invert the sign: Using the properties of the Lambert function, the two limits, of small and of large x, can be found. For x >> 1, W 0 (x 2 ) ∼ ln x 2 + ln ln x 2 , and X (x) ∼ |x| 2 ln |x|.
On the other hand, for x << 1, W 0 (x 2 ) ∼ x 2 , and performing a Taylor expansion around zero, one has X (x) ∼ x 2 /2 + O(x 4 ) corresponding to a Gaussian. Fig.  1 shows a comparison between the rate functions for the Bernoulli case with exponential WTD, Eq. (11), and for the Gaussian SLD with exponential WTD, Eq. (12). One can see that, as x → 0, both curves coinside and show a parabolic behavior which is a consequence of the Central Limit Theorem (CLT). For x > 1 the curves diverge, with the one for the Bernoulli RW growing faster. This shows that the large deviation rate of CTRWs is sensitive to the single step length distribution (and can be used as a probe for such). This discussion reproduces the results of Ref. [14].

B. One-sided Lévy law
Now we take ψ(t) to follow a one-sided Lévy law with exponent α. Its Laplace characteristic function f (s) = e −st reads: f (s) = ∞ 0 ψ(t)e −st dt = exp(−σs α ) with 0 < α < 1 (for s > 0) and σ being the scale parameter. To allow for further comparison with the behavior for the Pareto-distributed waiting times, we fix this to be σ = 1/Γ(α + 1). This fixes the characteristic time of a step. The mean number of steps n(t) done during the time t is then Let us denote C L = Γ(α + 1) 1/α . Thus, f (s) = exp[−(s/C L ) α ], so that Now, we perform the Legendre transform: which leads to and now the second Legendre transformation can be performed: Finally, the rate function of displacements reads For α → 1 it tends to a parabolic RF of a Gaussian, for α → 0 to a wedge-like RF of ultraslow diffusion with a purelly exponential PDF tails, see [2].

C. Pareto distributions
Now let us consider two other WTDs, namely the Pareto distributions of types I and II with parameter α (for the sake of brevity these will be sometimes referred to as Pareto I and Pareto II distributions). Both distributions have the same asymptotic behavior for long times, ψ(t) ∝ t −1−α but differ with respect to their short time behavior. The distributions with 0 < α ≤ 1 are fat-tailed and do not possess the mean, the distributions with α > 1 do possess the mean waiting time.
To be able to compare them to each other, and to a Lévy distribution for α ∈ (0, 1), one has to fix the time scale. For α > 1, both Pareto distributions possess a mean waiting time, so the scaling factor is this last quantity. For 0 < α ≤ 1, we scale the distributions in such a way that the mean number of steps n(t) for a given t is the same for the both distributions and exactly the same as for the Lévy case (Eq. (13)). Thus, the Pareto type I WTD ψ(t) is defined as where with Γ(x, y) being an upper incomplete Γ-function. On the other hand, the Pareto type II WTD can be defined as where C II = [Γ(1 + α)Γ(1 − α)] −1/α if α ≤ 1, and C II = (α − 1) if α > 1. Its Laplace transform reads f (s) = αC α II s α e C II s Γ(−α, C II s).
Due to the presence of incomplete Gamma functions, the Legendre transforms have to be performed numerically, by solving algebraic equations. Fig. 2 shows a comparison between the rate functions X (x) of displacements in the CTRW with Gaussian STD and the three following WTDs which do not possess mean waiting time: one-sided Lévy law with α = 0.5, and Pareto I and II distributions, both with α = 0.5, all with the same n(t) as given by Eq. (13). As in the case of the distributions with finite mean waiting times, the curves coinside in the central domain (although now they are not Gaussian but are given by Eq. (14)), but deviate for x large.   3 shows the corresponding comparison between the Pareto type I and Pareto type II WTDs for the cases α = 1.5 and α = 2.5 when they do possess the mean waiting time. In this case the behavior for small x is universally parabolic, as it should be, but the RFs for Pareto type I WTDs universally grow faster at large x than those for Pareto type II WTDs with the same α.
We now discuss in more detail these asymptotic growth properties discussing the domain of very large deviations. The cases of the Pareto distributions give enough physical intuition to understand the general behavior of very large deviations.

V. VERY LARGE DEVIATIONS FOR PARETO WAITING TIME DENSITIES
Physically, the behavior of very large deviations (x 2 → ∞) is dominated by realizations in which the number of steps is unusually large, and thus is governed by the behavior of ψ(t) for very short t. Therefore the two Pareto X (x) P II α = 1.5 P II α = 2.5 P I α = 1.5 P I α = 2. 5   FIG. 3. A comparison of the rate function X (x) for the CTRW with Gaussian SLD and the following WTDs: Pareto I distributions with α = 1.5, 2.5, and Pareto II with α = 1.5, 2.5. Here, the variable x is the quotient between the position and the time. All these WTDs have a mean waiting time. Note the difference in the asymptotic behavior, which for the case of Pareto I is quadratic (Eq. (20)), whereas for the Pareto II is linear with a slowly varying correction (Eq. (22)).
cases serve as examples for the cases when ψ(t) tends to a constant limit for t → 0 (Pareto II), and when it vanishes identically for t → 0 (Pareto I). There is no wonder that the Lévy case with ψ(0) = 0, but shooting up faster than any power of t for non-vanishing but small t, shows the behavior in-between of these two extrema.
Note that the expressions for both Pareto distributions (Eqs. (15) and (17)) are the same for all values of the parameter α, the only difference being the values of the scaling parameters C I and C II . Hence, all subsequent results hold independent of the value of α.

A. Pareto Type I WTD
First, let us consider the Pareto I WTD (Eq. (15)), and let us work with its Laplace transform as given by Eq. (16). The small time behavior (t → 0) of the WTD is mirrired in the asymptotic behavior of its Laplace transform for s → ∞. For the Pareto I PDF this asymptotic behavior is given by which form can alternatively be obtained either by using the asymptotic expansion of the incomplete Gamma function, or by evaluating the corresponding integral for the Laplace transform using the Laplace method. From this form it follows that L(q) = ln α − ln C I − ln(−q) + C I q.
Performing the Legendre transformation we get and finally obtain in the leading order. Now, and the second Legendre transform can be performed: Making the change of variable u = ξ − C I , it can be rewritten as Very large and negative values of the l.h.s. correspond to u → 0, so that To invert this expression, one can apply de Bruijn's Theorem for slowly varying functions, see [22]. Hence, one ends up with and, going back to the variable ξ: Finally, the asymptotic behavior (|x| → +∞) of the rate function for the CTRW has the form which is basically a quadratic behavior with a correction given by a slowly varying function. Note that, apart from the value of the constant C I being a function of α, Eq. (20) does not depends on the parameter α.

B. Pareto Type II WTD
Let us now consider the case of a Pareto II WTD (Eq. (17)), which in the Laplace domain is given by Eq. (18). Following the same procedure as for the Pareto I WTD, let us consider the asymptotic behavior (s → ∞) of Eq. (18) given by (the difference with Eq. (19) is the absence of the exponential cutoff for very large s), which allow us to obtain the asymptotics of the cumulant generating function: Applying the Legendre transformation we get: so that the function I(t) in the leading order is given by Then we construct and perform the second Legendre transformation The values of |x| → ∞ correspond to ξ → 0, so that To invert this expression, one applies again the de Bruijn's Theorem. Hence, the inverse reads Finally, the asymptotic behavior (|x| → +∞) of the rate function for the CTRW is which is an essentially linear behavior, with a correction given by a slowly varying function. This result does not depend on the value of the parameter α at all (and not not only up to the parameter values, like in the Pareto I case).
Then the asymptotic form of L(q) differs from Eq. (21) only by an additional proportionality factor in front of ln(−q): in the limit q → −∞. Therefore, the essentially linear behavior with a slowly varying correction ensues. The difference between the Lévy and Pareto type I cases on one hand and Pareto type II and Erlang cases on the other hand is the fact that for the first class of distributions the WTD vanishes at zero together with all its derivatives, while in the second situation this is no more the case. The full classification of possible behaviors will be discussed elsewhere. The lesson learned from these examples is that the essentially linear behavior of the large deviation rate function in CTRW is not universal but is pertinent to the specific classes of the waiting time distributions. The large deviation behavior of displacements probes the WTD for very short waiting times and is therefore a test for microscopic dynamics of the system.

VI. SUMMARY
In this paper, we presented a general procedure to compute the rate function for large deviations of displacements in CTRW in a general setting, i.e. for any step length distribution and any waiting time distribution. The situation with Gaussian step length distribution is especially simple. In this case the rate function for displacement is given by a sequence of Legendre transforms of the cumulant generating function for waiting times. The general discussion is accompanied by analysing important particular examples like the one-sided Lévy and the Pareto-distributed waiting times. This discussion shows that the large deviation in displacement probe the waiting time density for very short times. The essentially linear behavior of the rate function for very large deviations is specific only for situations in which waiting time density does not vanish too fast when the waiting times approach zero. follows immediately from the fact that I(x) is nonnegative and its derivative for x < z 0 non-positive. The second statement is slightly finer and follows from the the relation g(z) ≥ g(y) + g (y)(z − y) (A4) for convex differentiable functions, which we rewrite as g(y) − yg (y) ≤ g(z) − g (y)z. Now one takes g(y) = I(y) and z = z 0 , so that g(z 0 ) = I(z 0 ) vanishes, and notes that for y > z 0 the derivative g (y) = I (y) is nonnegative. Therefore the prefactors of the exponentials in both integrals on the r.h.s. of Eqs.
(A2) and (A3) are non-negative (essentially, positive for non-degenerated cases). For z < z 0 the function I (z) is monotonically decaying (I (z) < 0), and the argument of the exponential is therefore monotonically growing towards the upper integration boundary. For z > z 0 the function I (z) is monotonically growing (I (z) > 0), and the absolute maximum of the integrand is achieved on the lower integration boundary.
To get the relation between I and T , the argument of the function on the l.h.s. has to be kept constant. Fixing x = t/τ and changing the variable of integration on the r.h.s. to x = t /τ one obtains: