{'fraction_non_alphanumeric': 0.05604144241119483, 'fraction_numerical': 0.02045209903121636, 'mean_word_length': 3.931984074319841, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Strong Gaussian approximation for cumulative processes

We establish optimal logarithmic rates of convergence in the strong invariance principle for multivariate cumulative processes in the Smith's sense. Exponential probabilistic inequalities of Koml\'{o}s-Major-Tusn\'{a}dy type are obtained. Provided examples include applications to stopped sums and birth and death processes.


Introduction
Cumulative processes were initially introduced by Smith in 1955 [26]. Idea of Smith's construction of regenerative and cumulative processes was to create an opportunity to apply methods of analysis of sums of independent random variables to a wider class of sequences and processes. Smith proved the stability theorem for regenerative processes and LLN and CLT for cumulative processes. The concept of regeneration turned to be very popular in the queueing theory and was renovated after Smith's work in a lot of ways. Markov-modulated processes, batch Markov-arrival processes [2,22], regenerative flows in [1], cumulative processes as defined in [14] represent sub-classes of cumulative processes, introduced by Smith. Special definitions arose in order to find explicit formulae for characteristics of models. But as was shown already by Smith himself and later in studies [1,29] some classes of important theorems, like stability conditions or diffusion approximations, may be proved under general assumptions. Our conditions (A) and (B) below, taken together, are somewhat more restrictive than Smith's definition as we are tackling an almost sure approximation, but rather general and include the most part of examples in literature, e.g. those mentioned above.
Strong Gaussian approximation of random processes presents an important class of limit theorems (almost sure invariance principles), stemming from seminal results by Skorokhod and Strassen [27]. While classical functional limit theorems establish the proximity of properly rescaled random processes formed by partial sums to standard ones (e.g. to the Wiener process) in distribution, strong functional limit theorems provide the ways to estimate the almost sure difference of those two types of random processes.
For example, given a stationary sequence {X 1 , X 2 , . . .} of centered random variables and denoting S n = X 1 + . . . + X n for n ≥ 1, a strong invariance principle (almost sure invariance principle) would typically state that the sequence can be initially defined on a rich enough probability space so that for some Wiener process {W t , t ≥ 0} and some specified σ 2 > 0 (meaning the asymptotic variance of S n ) one has S n − σW n = O(f (n)) a.s., (1) f = {f (n), n ≥ 1} being some non-random increasing sequence in n ≥ 1. For (1) to be non-trivial (e.g. allowing to deduce the law of the iterated logarithm for S n ) r should satisfy f (n) = o( √ n log log n) which was Strassen's statement. Strong Gaussian approximation allows to deduce almost sure limit theorems, such as laws of the iterated logarithm, by using corresponding statements for approximating Gaussian processes. It has been shown that strong invariance principles have important applications to establishment of Darling-Erdős type theorems and integral tests for upper and lower functions [12,28].
One can go further and analyze the rate of convergence in (1), e.g. obtain an estimate of order f (n) = n 1/2−ε with some nonrandom ε > 0. Fundamental results by Komlós, Major and Tusnády [18][19][20] state that the rates f (n) = log n for i.i.d. sequences with finite exponential moments and f (n) = n 1/p if they possess only a moment of order p > 2 are true and non-improvable. These results were achieved by developing the quantile transformation method. These authors give also a more delicate estimate of the rate of Gaussian approximation in terms of probabilistic maximal inequalities. Namely, in the case of finite exponential moments one has for some non-random A, B, C > 0 and all n ≥ 1, x ≥ 0, and similar bounds exist in case of lower moment restrictions. Such bounds imply the convergence results of type (1).
The power and beauty of almost sure (strong) invariance principles prompted extensive research for such results for many classes of random systems. Vector-valued random processes were studied by many authors ( [15] and references therein), in particular, Zaitsev [31] extended (2) to sums of independent random vectors. Berkes and Morrow [4] initiated the exploration of strong approximation for random fields, establishing the rate f (n) = (n 1 . . . n d ) 1/2−ε (here partial sums are indexed by multiindices n = (n 1 , . . . , n d ) ∈ N d ). For renewal processes, exact rates of convergence in the sense of Komlós-Major-Tusnády were established by Csörgő, Horváth and Steinebach [8] and are in agreement with what one has in the i.i.d. setup (in this case, moment conditions are imposed on the innovations). However for systems of dependent random variables, while there have been many results proved (for martingales [10,13,28], associated random systems [5], mixing families [3,[23][24][25] and others), one can rarely attain the optimal convergence rate. In particular, in most cases methods based on the Skorokhod embedding and the approximation of partial sums by those of independent families do not provide the convergence faster that O(n 1/4 ), which is not optimal in case moments greater than fourth exist. However this border was broken in the works by Berkes, Liu and Wu [3] for processes driven by regular enough Bernoulli shifts, by Merlevède and Rio [21] for functionals of Markov chains and by Cuny, Dedecker, Korepanov, Merlevède [11] for mixing dynamical systems.
This paper is devoted to optimal logarithmic rates of convergence in almost sure invariance principle for multivariate cumulative processes. Our goal is to obtain exponential probabilistic inequalities of Komlós-moment restrictions we follow the approach of Merlevède and Rio [21] to geometrically ergodic Markov chains. Their approach is based on the approximation by an auxiliary process formed by a composition of a Wiener and Poisson ones (Lemma 2.4 [21]). Besides, the Zaitsev strong approximation technique [31] is applied. Merlevède and Rio study the sequence of partial sums S n = n i=1 f (ξ j ), n ≥ 1, with a bounded Borel functional f and {ξ n , n ≥ 1} being a geometrically ergodic Markov chain. However their Lemma 2.4 is a powerful tool of its independent interest. In particular, we were able to apply it together with Zaitsev construction to analysis of cumulative processes. Note that random sums S n studied in [21] present a partial case of processes under consideration, as can be seen by taking the Markov chain returns to zero as points of regeneration. Besides, we allow vector-valued processes and dispense with the boundedness condition on the random summands. In the concluding part of the paper we give two corollaries about two important subclasses of cumulative processes. The first one deals with stopped sums. Csörgő, Deheuvels and Horváth [7] obtained the optimal rate in strong invariance principle for such sums in case when the indexing process is independent from summands, while Horváth [16] studied general case and got the convergence rate of order O(n 1/4 (log n) 1/2 (log log n) 1/4 ). We consider stopped sums as in [16] and get the logarithmic rate of convergence as a consequence of our main theorem. The second corollary concerns birth and death processes arising in queueing theory [17].
which is assumed to be separable. For a vector z ∈ R d , by |z| we denote the maximal norm. The principal condition we will require is: There exists an a.s. increasing random sequence {T k , k ≥ 0} such that T 0 = 0 and random elements We need the following notation.
Condition (B) implies that the exponential moments of ξ 1 are finite in some neighbourhood of the origin.

Main result
Standard estimate shows that (3) implies the strong invariance principle, i.e. the relation Proof. Without loss of generality we assume Var(τ 1 ) > 0 as otherwise the statement would be easily derived from the Komlós-Major-Tusnády theorem for i.i.d. summands [19,Theorem 1]. We will use triplets of positive constants (a i , b i , c i ), i ≥ 1, when we want to write an auxiliary estimate of the type Note that we always can confine ourselves to the case t ≥ M, with a fixed number M > 1. For if theorem is proved for that case, then given t ∈ [1, M ), we will be able to write Using this remark we will consider only t ≥ e in what follows. Write Using the remark above, we will consider only t ≥ e. Note that the choice of β implies that we can infer (redefining the initial process on a larger probability space if necessary) that there exist two with some a 1 , b 1 , c 1 > 0.
Arguing as before (2.50) in Merlevède and Rio [21], we can construct also a Poisson process {N (t), t ≥ 0} with parameter λ, measurable with respect to the σ−algebra generated by B and such that the following relations hold: P sup with some a 2 , b 2 , c 2 > 0.
Further, we denote now y(u) = N −1 (u/γ). Then, process m is the inverse of process T and y is the inverse of γN . Therefore in view of the paper of Csörgő, Horváth and Steinebach [8] and particular Corollary 4.2 there, and of (6)- (7), one can construct (enlarging the probability space if necessary) a standard Wiener process W = { W t , t ≥ 0} such that the following statements are simultaneously true: and with some a 3 , b 3 , c 3 > 0. Moreover, process W is measurable with respect to a σ-algebra generated by B plus some random element V independent from all ones considered above.
Lemma 1. For any z ≥ 0 and t ≥ e one has Proof. Consider separately the cases z ≥ c 3 log t and z < c 3 log t, and use (9) for the first one.
with some a 4 , b 4 , c 4 > 0 and all t ≥ e, x > 0; this process is determined by the process B plus some random element V * which is independent from all other random elements considered above. In particular, W * is independent from B and N .
Proof. This is a multi-dimensional version of Lemma 2.4 in [21] and is proved along the lines of that lemma, with the following change. One introduces mutually independent Gaussian random vectors and random functions a j,k = N ((k + 1/2)2 j ) − N (k2 j ), b j,k = N ((k + 1)2 j ) − N ((k + 1/2)2 j ), where the fraction with 0 at the denominator is treated as zero. Then, using that {f j,k } j,k conditionally on N is an orthonormal family plus some set of identically zero functions, one shows that random vectors are jointly Gaussian and EW l W T m = min{l, m}I d for l, m ≥ 0, where I d is the identity matrix. The rest of the proof goes like in [21].

Proof. For a standard scalar Wiener process
as t ≥ e. Finally, if Z is independent from the Poisson process N, for x ≥ 1 we may write Wiener process independent from (W * , W ). Define a Gaussian process where v is the square root of the covariance matrix v 2 , and σ + stands for the Moore-Penrose pseudoinverse matrix to σ. Proof. It suffices to compute the covariance matrix of W 1 , which is equal to and since the components of the random vectors whose covariance matrices are inside the brackets are mutually uncorrelated, using the definition of σ 2 we infer that VarW 1 = I d .
Proof. Note that sup u≤t |Φ 1 (u)| ≤ max k≤m(t)+1 η k , since m(u) is the last renewal point of T happening before u, u ≤ t. Consequently, for a fixed c 6 > 0 we have Using Lemma 1 and assuming a 3 ≥ 1, b 3 ≤ 1 we get e −b3xr/12 + e −xλr/24 . Also, provided that c 6 is so large that c 6 s 1 > 1.
To handle Φ 2 we need a series of auxiliary lemmas. The first of them is a modification of the Lemma 1 in Csörgő and Steinebach [9].
Lemma 8. Suppose that X 1 , X 2 , . . . are i.i.d. centered random variables such that E exp{sX 1 } < ∞ for some s > 0, and let Q n = n j=1 X j (Q 0 = 0). Then for any L > 0 there exist δ = δ(L), a 7 , b 7 , c 7 > 0 (which depend on L, δ and the distribution of X 1 ) such that for any n ∈ N and all x ≥ 0 one has P max j≤n max k≤L log n+δx Proof. Clearly we can consider only non-constant distribution of X 1 . The probability under consideration is not greater than (n + 1) exp −sx − c 7 s log n + L(log ϕ(s)) log n + (log ϕ(s))δx , where ϕ(s) = E exp{sX 1 } > 1. It remains to take c 7 and δ so that inequalities c 7 s > L log ϕ(s) + 1 and δ(log ϕ(s)) < s are ensured.
Proof. Clearly we can consider only one coordinate of S, say the first one. Also, using the remark before (4), we can consider only t ≥ e max{1, µ/2}. Write, for L > 0 and δ > 0, where we have used that 2 log[z] ≥ log z if z ≥ e. Suppose that L has been chosen to ensure L ≥ c 3 + 1 where c 3 is like in (11), and that the numbers δ = δ(L), a 7 , b 7 , c 7 are provided by Lemma 8, applied when X 1 has the distribution of ξ 11 . Then by Lemma 8 we see that J 3 ≤ a 7 e −b7x provided that c 8 is so large that c 8 log t ≥ c 7 log(2t/µ) for all t considered. To prove the statement of the lemma it remains to notice that by Lemma 5 and the relation (11) one has Consider now the case when x lies in a domain of large deviations. Proof. First, by standard properties of Brownian motion one has for any x provided that the pair (x, t) satisfies Lemma's condition. Next, write By (9) and Lemma 1, assuming without loss of generality that a 3 ≥ 1, b 3 ≤ 1, one has To estimate R 2 , by Doob's inequality for non-negative submartingales we get where q := s 1 /6 − r log E exp{s 1 |ξ 1 − κτ 1 |} > 0 by (15). Now we estimate R 3 (and then R 4 is estimated analogously). From (15) it is seen that we can assume r < s/12, in which case we have Theorem now follows from Lemmas 5, 6, 7, 9, 10.
We now turn to some corollaries of Theorem 1. The first one concerns sums of a random amount of random summands.
Proof. It is sufficient to note that S(u) is a cumulative process satisfying the conditions (A) and (B) with T 0 = 0 and T k = m −1 (k − 1), k ≥ 1. Then, η k ≡ |ξ k | and all the conditions of Theorem 1 are fulfilled.
Furthermore, by Van Doorn [30] and  the relation (19) ensures that the Laplace transform of the return time to zero is an analytic function at the origin. Finally, by [6, §I.12] (20) means that the maximum of the birth and death process between two returns to zero has a finite exponential moment. Thus we arrive at the following corollary.
Corollary 2. Consider a birth and death process X satisfying (19) and (20), with initial distributionπ, and let f : R → R be a function growing not faster than a linear one. Then one can redefine X on a probability space (Ω, F , P) supporting a standard Wiener process {W t , t ≥ 0} such that for some positive constants a, b, c, any x > 0 and t ≥ 1 one has where κ f = ∞ n=0 f (n)π n and f (n)f (m)π n (P nm (s) −π m )ds.
Proof. Given the discussion above, it suffices to compute κ f and σ f . However by central limit theorem for Markov chains, κ f = Ef (X 0 ) and