{'fraction_non_alphanumeric': 0.04678307079142152, 'fraction_numerical': 0.01504080470677548, 'mean_word_length': 3.707840071476435, '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': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Loop-free Markov chains as determinantal point processes

We show that any loop-free Markov chain on a discrete space can be viewed as a determinantal point process. As an application, we prove central limit theorems for the number of particles in a window for renewal processes and Markov renewal processes with Bernoulli noise.


Introduction
Let X be a discrete space. A (simple) random point process P on X is a probability measure on the set 2 X of all subsets of X. P is called determinantal if there exists a |X| × |X| matrix K with rows and columns marked by elements of X, such that for any finite Y = (y 1 , . . . , y n ) ⊂ X one has The matrix K is called a correlation kernel for P. A similar definition can be given for X being any reasonable space; then the measure lives on locally finite subsets of X.
Determinantal point processes (with X = R) have been used in random matrix theory since the early 60s. As a separate class, determinantal processes were first singled out in the mid-70s in [9] where the term fermion point processes was used. The term "determinantal" was introduced at the end of the 90s in [2], and it is now widely accepted. We refer the reader to surveys [1,8,12,15] for further references and details.
Determinantal point processes have been enormously effective for studying scaling limits of interacting particle systems arising in a variety of domains of mathematics and mathematical physics including random matrices, representation theory, combinatorics, random growth models, etc. However, these processes are still considered as "exotic" -the common belief is that one needs a very special probabilistic model to observe a determinantal process.
The main goal of this note is to show that determinantal point processes are much more common. More exactly, we show that for any loop-free Markov chain the induced measure on trajectories is a determinantal point process. (Note that the absence of loops is essential -otherwise trajectories cannot be viewed as subsets of the phase space.) We work in a discrete state space in order to avoid technical difficulties like trajectories that may have almost closed loops, but our construction easily extends to suitable classes of loop-free Markov chains on continuous spaces as well.
Surprisingly, very little is known about arbitrary determinantal point processes. However, in the case when the correlation kernel is self-adjoint, several general results are available, and even more is known when the kernel is both self-adjoint and translation invariant (with X = Z d or R d ). See [1,8,12] and [15] for details.
In our situation, the kernel is usually not self-adjoint, 1 and self-adjoint examples should be viewed as "exotic." One such example goes back to [9], see also [12], Section 2.4: It is a 2-parameter family of renewal processes -processes on Z or R with positive i.i.d. increments. Our result implies that if we do not insist on self-adjointness then any process with positive i.i.d. increments is determinantal.
As an application, we prove a central limit theorem for the number of points in a growing window for renewal processes with Bernoulli noise and for Markov renewal processes (also known as semi-Markov processes) with Bernoulli noise. The proof is a version of the argument from [5,13] adapted to non-self-adjoint kernels.
The key property that allows us to prove the central limit theorem is the boundedness of the operator defined by the correlation kernel in ℓ 2 (X). This boundedness is a corollary of what is known as a "renewal theorem" with a controlled rate of convergence.

Markov chains and determinantal point processes
Let X be a discrete space, and let P = [P xy ] x,y∈X be the matrix of transition probabilities for a discrete time Markov chain on X. That is, P xy ≥ 0 for all x, y ∈ X and y∈X P xy = 1 for any x ∈ X.
Let us assume that our Markov chain is loop-free, i.e., the trajectories of the Markov chain do not pass through the same point twice almost surely. In other words, we assume that (P k ) xx = 0 for any k > 0 and x ∈ X.
This condition guarantees the finiteness of the matrix elements of the matrix Indeed, (P k ) xy is the probability that the trajectory started at x is at y after kth step. Hence, Q xy is the probability that the trajectory started at x passes through y = x, and since there are no loops, we have Q xy ≤ 1. Clearly, Q xx ≡ 0. Theorem 1.1. For any probability measure π = [π x ] x∈X on X, consider the Markov chain with initial distribution π and transition matrix P as a probability measure on trajectories viewed as subsets of X. Then this measure on 2 X is a determinantal point process on X with correlation kernel K xy = π x + (πQ) x − Q yx . 1 In fact, it can be written as a sum of a nilpotent matrix and a matrix of rank 1.
Before proceeding to the proof, let us point out that for any Markov chain {X(n)} on a discrete state space X, its graph {(n, X(n)), n = 1, 2, . . .} is a loop-free Markov chain on X = Z >0 × X. Hence, the graph defines a determinantal point process.
Also, there exists a class of Markov chains {X(n)} such that for each n, X(n) is a random point configuration in some space X 0 , and the graph {(n, X(n))} defines a determinantal point process on Z >0 × X 0 , see e.g. [3,7,16]. (Here X is a suitable space of point configurations in X 0 .) In such a case, the graph carries two types of determinantal structures, the second one on Z >0 × X is afforded by Theorem 1.1.
The author is grateful to one of the referees for these remarks. The proof of Theorem 1.1 is based on the following simple lemma, cf. [12], proof of Theorem 6.
Proof. The determinant in question is an nth degree polynomial in a i 's with the highest coefficient a 1 · · · a n b 1 · · · b n , which vanishes at a 1 = 0, a 2 = c 1 /b 1 , . . . , a n = c n−1 /b n−1 . This implies the statement for b 1 · · · b n = 0, and thus, by continuity for all values of the parameters.
Proof of Theorem 1.1. Let us evaluate the correlation function ρ n (x 1 , . . . , x n ) using the Markov chain. First, let us reorder the points x 1 , . . . , x n in such a way that Q xixj = 0 for i > j. This is always possible because if Q xy > 0 then Q yx = 0, and if Q xy > 0 and Q yz > 0 then Q xz > 0, so we are simply listing the elements of a finite partially ordered set in a nondecreasing order. (For example, we can first list all minimal elements, then all elements that are minimal in the remaining set, etc.) Once the points are ordered as described, using the Markov property we immediately compute Denote by Y a finite subset of X such that if a trajectory of our Markov chain leaves Y then it does not return to Y almost surely. In other words, if Q yz > 0 for some y ∈ Y and z ∈ X \ Y, then Q zy ′ = 0 for any y ′ ∈ Y.
In order to consider the behavior of our Markov chain restricted to Y, it is convenient to contract the complement X \ Y into one "final" state F . Then the transition matrix for the new Markov chain on Y ∪ {F } coincides with P on Y × Y, and for any y ∈ Y Set π y (Y) = Prob{Intersection of the random trajectory with Y starts at y}, π 0 (Y) = Prob{The random trajectory does not intersect Y}.
In what follows, we will use the notation π y and π 0 instead of π y (Y) and π 0 (Y) for the sake of brevity. Let K Y denote the restriction of the matrix K of Theorem 1.1 to Y × Y.

22
A. Borodin Theorem 1.3. In the above notation, we have det Proof. The first statement is a well-known corollary of Theorem 1.1 which can also be easily proved using the inclusion-exclusion principle. Assume that π 0 = 0. For any subset Y of Y choose the ordering (y 1 , . . . , y m ) of its points in the same way as we did in the proof of Theorem 1.1: Hence, where by P Y we mean the restriction of P to Y × Y; and noting the fact that P Y (1 − P Y ) −1 gives the restriction Q Y of Q to Y × Y (here we use the assumption that the trajectories that leave Y do not come back), we reduce the statement of the theorem to the following two relations: The two sides of the first relation represent two ways of computing the probability that y ∈ Y lies on the random trajectory of our Markov chain, and the second relation is easily verified once both sides are multiplied by (1 + L t Y ).

Random point processes with Bernoulli noise
Let X be a discrete set and let P be a random point process on X (that is, P is a probability measure on 2 X ). Given two sequences of numbers we define a new random point process P (p,q) on X as follows. The random point configuration X ⊂ X is being transformed by the following rules: • Each particle x ∈ X is removed with probability p x , and it remains in place with probability 1 − p x ; • At each empty location y ∈ X \ X a new particle appears with probability q y , and the location remains empty with probability 1 − q y ; • The above operations at different locations are independent.
We say that P (p,q) is the process P with Bernoulli noise. Note that replacing the random point configuration X with its complement on the whole space X or on its part (the so-called particle-hole involution) can be viewed as a special case of the Bernoulli noise. We will use the notation D = diag(d x ) for the diagonal matrix with matrix elements Theorem 2.1. For a determinantal point process P on X with correlation kernel K, the process with Bernoulli noise P (p,q) is also determinantal, and its correlation kernel is given by Comments. 1. The theorem implies that if p x + q x ≡ 1 then the noisy process P (p,q) is independent of the initial process P, and it coincides with the product of Bernoulli random variables located at the points x ∈ X with probability of finding a particle at x equal to q x . This fact is easy to see independently. Indeed, 1 − p x and q x are conditional probabilities of finding a particle at x given that the initial process has or does not have a particle there, and p x + q x = 1 implies that these probabilities are equal.
2. The particle-hole involution on X or its part corresponds to taking both p x and q x equal to 1 on the corresponding part of the space.
3. Proof of Theorem 2.1. We will consider the case when p x and q x are not equal to zero for just one x = x 0 ∈ X. The general case is clearly obtained by composition of such transformations. From the definition of Bernoulli noise, we obtain Summing over all X ∈ X that contain a fixed finite set Y (which contains x 0 ) we obtain One readily sees that the above relation is exactly the relation between the symmetric minors of the matrices K (p,q) and K if the corresponding sets of rows and columns contain those marked by x 0 . On the other hand, the correlation functions ρ (p,q) and ρ of P (p,q) and P away from x 0 are clearly identical, and same is true about the symmetric minors of K (p,q) and K not containing the row and the column marked by x 0 .

CLT for number of points in a window of a determinantal process
Let X be a discrete set and P be a determinantal process on X with correlation kernel K. For any finite subset Y of X, let us denote by N Y the number of points of the random point configuration that lie in Y.
Using the definition of the correlation kernel, it is straightforward to verify that where E denotes the expectation with respect to P and K Y is the restriction of K to Y × Y.
The following statement can be essentially extracted from [5,13] and [14]. An important difference though is that here we consider correlation kernels which are not necessarily self-adjoint.

A. Borodin
Theorem 3.1. Assume that the correlation kernel K defines a bounded operator in ℓ 2 (X). Then for any sequence {Y m } of finite subsets of X such that for some strictly positive constants c 1 and c 2 , the following central limit theorem for N Ym holds: for any x ∈ R.
Proof. As is shown in [13], Lemma 1, for k ≥ 2 the lth cumulant of the random variable N Y is a linear combination of expressions of the form Tr(K Y − K m Y ) with m ranging from 2 to l. Using the idea from [13], Lemma 2, we obtain where we used the inequalities | Tr A| ≤ A 1 and AB 1 ≤ A · B 1 . Since the trace norm of a matrix does not exceed the sum of the absolute values of its entries (and matrix elements of an operator are bounded by its norm), we see that Thus, the absolute value of any cumulant of N Ym starting from the second one grows not faster than a fixed constant times |Y m | 2 . Hence, the absolute value of the lth cumulant of the normalized random variable (N Ym − EN Ym )/ Var N Ym is bounded by a constant times In particular, for large enough l it converges to zero as |Y m | → ∞. [14], Lemma 3, completes the proof.

(Delayed) Renewal processes
In this section, we will apply our previous results to one of the simplest examples of loop-free Markov chains -renewal processes. For the sake of simplicity, we will consider only the discrete case. A large portion of our statements can be easily carried over to the continuous setting. Let ξ 0 , ξ 1 , ξ 2 , . . . be a sequence of mutually independent random variables with values in Z >0 , such that ξ 1 , ξ 2 , . . . (but not ξ 0 ) have a common distribution. By definition, the sequence of partial sums forms a delayed renewal process, see, e.g., [6], Volume II, Section VI.6. The word "delayed" refers to a differently distributed ξ 0 . Clearly, {S i } ∞ i=0 is a trajectory of the loop-free Markov chain on Z >0 with the initial distribution and transition probabilities given by Thus, by Theorem 1.1, the sequence {S i } ∞ i=0 forms a determinantal point process on Z >0 . Let us now restrict our attention to the case when the distributions of random variables ξ i have exponentially decaying tails. It is very plausible that the results proved below can be extended to more general classes of distributions.
Definition. We say that a random variable ξ with values in Z >0 belongs to class E if there exists a constant r ∈ (0, 1) such that Prob{ξ = n} ≤ r n for large enough n.

Definition. An integral valued random variable ξ is called aperiodic if
Prob{ξ ∈ N Z} < 1 for any N ≥ 2, that is, the distribution of ξ is not fully supported by N Z.
The main result of this section is the following statement.
Theorem 4.1. The delayed renewal process with aperiodic ξ 1 and ξ 0 , ξ 1 ∈ E, and with arbitrary Bernoulli noise defines a determinantal point process on Z >0 whose correlation kernel may be chosen so that it represents a bounded operator in ℓ 2 (Z >0 ).
The proof is based on the following lemma.

Lemma 4.2. Consider a random variable ξ with values in Z >0 which belongs to E and is aperiodic. Set
Then there exist positive constants c 1 and c 2 such that |f n − (Eξ) −1 | ≤ c 1 e −c2n for all n ≥ 1.

A. Borodin
as z → 1. Thus, f (z) − 1/(g 1 (1 − z)) is holomorphic in a neighborhood of z = 1. In addition to that, the fact that ξ is aperiodic implies that g(z) is not equal to 1 at any point z = 1 of the unit circle. Therefore, the function f (z) − 1/(g 1 (1 − z)) can be analytically continued to a disc of radius greater than 1. This implies the needed estimate.
Proof of Theorem 4.1. By Theorem 2.1, it suffices to prove the statement without Bernoulli noise. Lemma 4.2 applied to ξ = ξ 1 implies that there exist positive constants c 1 and c 2 such that (Here we use the same notation as before: Q = P + P 2 + P 3 + · · ·.) We know that π i 's decay exponentially as i → ∞ because ξ 0 ∈ E. Furthermore, which is easily seen to be exponentially decaying in j → ∞. Thus, the matrix afforded by Theorem 1.1 has the following properties: for certain positive constants. This implies that if we consider the matrix K with matrix elements K ij = e α(i−j) K ij with positive α < min{const 3 , const 5 } then the corresponding operator in ℓ 2 (Z >0 ) will be bounded. On the other hand, the symmetric minors of K and K are clearly the same. Thus, K is the needed correlation kernel. Comments. 1. In the absence of Bernoulli noise, the central limit theorem for N [0,T ] is an easy corollary of the classical central limit theorem for sums of i.i.d. random variables, see, e.g., [6], Volume II, Section XI.5. However, with the presence of Bernoulli noise the statement does not look as obvious.

2.
In concrete examples (including the one mentioned in the previous comment), the asymptotic behavior of the expectation and variance of N Y can often be computed explicitly using the formulas

Markov renewal processes
Markov renewal process (or semi-Markov processes) are hybrids of Markov chains and renewal processes introduced by Lévy and Smith in 1954. An excellent introduction to Markov renewal processes can be found in [10] and [11]. We will use one of the simplest possible settings. Consider a Markov chain on X = S × Z >0 with transition probabilities P ((s 1 , t 1 ) → (s 2 , t 2 )) = P s1s2 (t 2 − t 1 ),

27
where for any s 1 , s 2 ∈ S the function P s1s2 (t) is supported by Z >0 , ∞ t=1 P s1s2 (t) =: P s1s2 ∈ [0, 1], s 1 , s 2 ∈ S, and [P s1s2 ] s1,s2∈S is the matrix of transition probabilities for a Markov chain on S. The projection of thus defined Markov chain on X to the first coordinate is the Markov chain on S sometimes called the "driving" Markov chain. The Markov chain on X is a Markov renewal process. It can be viewed as the driving Markov chain with randomly transformed time scale -the passage time from s 1 to s 2 is a random variable depending on s 1 and s 2 .
Theorem 5.1. Assume that S is finite and the driving Markov chain on S is irreducible. Assume further that whenever P ss ′ = 0, the passage time between s and s ′ (which is equal to t with probability P ss ′ (t)/P ss ′ ) is aperiodic and is in E, and that the initial distribution for the Markov renewal process conditioned on the first coordinate being fixed (and arbitrary) is also in E.
Then the point process on X formed by trajectories of the Markov renewal process, with any Bernoulli noise, is a determinantal point process, and the correlation kernel may be chosen so that it represents a bounded operator in ℓ 2 (X).
Comments. 1. The assumptions of S being finite, the driving chain being irreducible and passage times being aperiodic and in E can probably be relaxed. For example, instead of requiring that all passage times are aperiodic, one can impose the weaker condition of the first return time from any state to itself being aperiodic.
2. Theorem 4.1 is a special case of Theorem 5.1 obtained by considering the set S with a single element.
Proof of Theorem 5.1. If we start the Markov renewal process at any state s then the times of its arrivals to any state s ′ form a delayed renewal process (see the previous section) with the initial delay ξ 0 being the first passage time from s to s ′ and the common distribution of ξ 1 , ξ 2 , . . . being the first return time from s ′ to s ′ . Both ξ 0 and ξ 1 are in E; see Lemma 5.3. Furthermore, the aperiodicity of ξ 1 immediately follows from the assumption of all passage times being aperiodic. Since the initial distribution of our Markov renewal process conditioned on fixing the first coordinate is also in E, when we start from this initial distribution the arrival times to any state also form a delayed renewal process with same renewal time ξ 1 , but generally speaking, different initial delay time ξ 0 , which however is still in E.
Thus, we can apply the arguments used in the proof of Theorem 4.1 to produce an exponential bound on the difference of Q((s, t 1 ) → (s ′ , t 2 )) and a known constant (equal to the inverse of the expectation of the first return time from s ′ to s ′ ).
The remainder of the proof is just the same as in Theorem 4.1: We conjugate the kernel afforded by Theorem 1.1 by a suitable diagonal matrix whose nonzero matrix elements form a geometric progression, and thus get the desired correlation kernel which defines a bounded operator in ℓ 2 (X). It remains to prove the following lemma.  Proof. For any s 1 , s 2 ∈ S such that P s1s2 = 0 set By the hypothesis, all such functions have analytic continuation to a disc of radius larger than some constant R > 1. Denote M = max |z|=R, s1,s2∈S |f s1s2 (z)|.
Note that P s1s2 · · · P sm−1sm is exactly the probability of the driving Markov chain started at s 1 to walk the path s 1 → · · · → s m . Let p be the minimum of all P s1s2 = 0. Since the driving chain is irreducible, for any initial distribution its probability of hitting any given state in the first |S| steps is at least p |S| . Hence, the number of steps in the first passage of the driving chain from any s 1 ∈ S to any s 2 ∈ S is a random variable from E. (Indeed, the probability of this number of steps being at least n is ≤ (1 − p |S| ) [n/|S|] .) Take any a > 0 such that M a < R. For a first passage of the Markov renewal process from s 1 to s 2 that takes time T , either the number of steps of the driving Markov chain is at least [aT ] or it is < [aT ]. The probability of the former event decays exponentially in T by the previous paragraph, while the probability of the latter event, by the estimate above, does not exceed M [aT ] /R T , which also decays exponentially in T by the choice of a.