{'fraction_non_alphanumeric': 0.06219833260201843, 'fraction_numerical': 0.023255813953488372, 'mean_word_length': 3.9484326231510383, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximating Laplace transforms of meeting times for some symmetric Markov chains

We study distributions of meeting times for finite symmetric Markov chains. For Markov kernels defined on large state spaces which satisfy certain weak inhomogeneity in return probabilities of points up to large numbers of steps, we obtain approximation, with explicit error bounds, of the Laplace transforms of some meeting times (without scaling) by ratios of Green functions closely related to hitting times of points. In studying this approximation, we identify some key matrix power series in Markov kernels weighted with solutions to a discrete transport-like equation with explicit coefficients, which stems from the viewpoint that meeting time distributions are equivalent to correlations of some linear particle system. Our result applies in particular to random walks on large random regular graphs. It gives a justification of the corresponding practice, among other things, in Allen, Traulsen, Tarnita and Nowak (2012) on approximating certain critical values for the emergence of cooperation when mutation is present.


Introduction
In this paper we investigate distributions of (first) meeting times by two independent continuous-time Markov chains. Meeting times arise as fundamental objects in the study of finite stochastic spatial models in mathematical biology, including, for example, voter models [10,9], Kimura's stepping-stone model and its generalizations [21,30,12,34], and evolutionary games on graphs [6,8]. In contrast to the frequently visited subject in most of these studies on approximating meeting time distributions under large time scales by exponential variables (cf. Keilson [19] and Aldous and Fill [3,Section 3.5.4] for the classical results), our main focus in this paper is on the detailed meeting time distributions up to large times through their Laplace transforms. This direction concerns in particular the biological application of approximating certain critical values for the emergence of cooperation under some evolutionary games. For this, a brief discussion of the background and pointers to the literature will be given in Section 1.1.
Unless otherwise mentioned, we consider throughout this paper irreducible (conservative) Markov kernels Q on finite state spaces E with #E = N > 8 and subject to the symmetry condition: Q(x, y) = Q(y, x) ∀ x, y ∈ E (1.1) as well as the zero-trace condition: For such a Markov kernel Q, we denote by M x,y the (first) meeting time of two independent continuous-time rate-1 Q-chains started at x and y, and hence, M x,x ≡ 0. In addition, we write H x,y for the first hitting time of y by a rate-1 Q-chain X x started at x. One of the conventional treatments of meeting times is based on the validation of the following exact distributional reduction: = H x,y /2. (1.4) Although (1.3) can lead to this important relation and is immediate for some special Markov kernels (the classical examples are random walks on groups), obtaining the reduction (1.3) in general poses some problems. For example, while we restrict our attention to Markov kernels subject to the symmetry condition (1.1) in this paper, it is readily pointed out in Aldous [2, p.188] by the counterexample of random walks on star graphs that (1.3) can fail when the symmetry condition is disobeyed. In addition, it seems that before the present paper, the reduction (1.3) can only be obtained by few arguments which require various strong links among all pointwise transition probabilities, and thus, are insufficient for a further study of whether some "non-global" properties of Markov chains similar to those allowing for the exact equality (1.3) can give an approximating reduction. Our goal in this paper is to determine whether the distributional reduction (1.3) is approximately correct in terms of Laplace transforms, for a class of "weakly inhomogeneous" Markov kernels. (See also Section 1.1 for more on our motivation.) Informally, we consider kernels Q on large, but finite, state spaces E under which pointwise return probabilities are almost identical up to some large numbers of steps, and the presence of few "wild" points which disagree significantly with the majority on such almost homogeneity of finiterange return probabilities is allowed (see our discussion after Theorem 1.1 for the example of large random regular graphs). To formalize this, we choose the largest sets of points which almost agree in s-step return probabilities under Q, for s ∈ Z + , from R γ Q (x, s) {y ∈ E; |Q s (x, x) − Q s (y, y)| ≤ γ}, x ∈ E, γ ∈ [0, 1], (1.5) and consider, for every s 0 ∈ N, the magnitude of for all s ∈ {0, · · · , s 0 }. We stress that no connections between such kernels and those which allow for the conventional distributional reduction of meeting times will be assumed a priori, and the novelty of this paper as we see it lies in the treatment of this missing link in order to understand how Laplace transforms of some meeting times and those of the associated hitting times of points (as in (1.3)) can still be related. See Section 1.2 for further discussions.
To facilitate the present purpose to study meeting times on large sets, let us introduce some meeting times started from pairs of random points independent of the underlying Q-Markov chains. The first natural candidate is the pair of random points (U, V ∞ ) whose coordinates are independent and uniformly distributed on the state space E. See, for example, Durrett [14] for a discussion of the corresponding meeting time M U,V∞ , and Chen, Choi and Cox [9] for its role in diffusion approximation of voter models defined on large sets. On the other hand, if we consider V s for s ∈ N being distributed according to the sstep distribution Q s (U, · ) of the discrete-time Q-chain started at U when we condition on U , then the meeting times M U,Vs have a very different nature. For example, if we consider random walk on a large graph with relatively smaller degree, then informally, M U,Vs for a small s ∈ N is the first meeting time of two Markov chains started with points close to each other (with respect to graph distance) such that the local structure of the underlying graph becomes an essential part of its distribution, whereas M U,V∞ is for starting points far away from each other and should depend much less on the local structure of the graph (see Oliveira [27] and Chen et al. [9,Theorem 4.1] for some rigorous treatments).
For s ∈ N ∪ {∞}, we will call M U,Vs the s-th order meeting time, but put emphasis on the special case s = 1 throughout this paper. There are several reasons why we choose to make this restriction. First, the distributions of M U,V 1 and M U,V∞ always determine each other through an explicit integral equation (cf. Aldous and Fill [3,Proposition 3.21] or Section 3 of Chen et al. [9]). More importantly, since the mass of M U,V∞ always escapes to infinity in the limit of a large state space (see [9,Corollary 3.4]) and our interest here is for meeting times under the natural time scale, the viable object of study need be the distribution of M U,V 1 . Besides, the tail distribution of M U,Vs 0 for finite s 0 can be approximated by that of M U,V 1 if it holds that (1.6) is small for s up to s 0 (Section 5). In accordance with this emphasis on the first-order meeting time and to save notation, we write V for V 1 from now on.
The main result of this paper is given by Theorem 1.1 below. For the statement of the theorem, we define where C ε is a constant which diverges as ε ց 0 and can be chosen to be and ∆ γ Q is defined as in (1.7).
We will discuss the method of proof for Theorem 1.1 in Section 1.2, and start its proof in Section 2, with the conclusion set in Section 4.2.
Observe that the ratio of Green functions on the left-hand side of (1.8) bears a strong resemblance to the Laplace transform E[e −λH U,V /2 ] if we recall (1.4). For this reason, we regard (1.8) as an approximation in a weak sense for the classical distributional reduction (1.3). In addition, this ratio can be written as which depends only on the eigenvalue distribution of Q (see the proof of Lemma 4.2 (iii)). Let us discuss informally some contexts for which Theorem 1.1 may allow for "good" approximation of the Laplace transform of M U,V by the associated ratio of Green functions. The key, of course, is to identify kernels Q such that the associated parameters ∆ γ Q in (1.7) are small. We consider a kernel Q such that the quantity in (1.6) is small for s up to some s 0 , so the task of bounding ∆ γ Q falls upon controlling tr(|Q| s 0 )/N . In this direction, if the eigenvalues of Q are sufficiently bounded away from ±1 except for a small fraction of them, then the normalized trace term tr(|Q| s 0 )/N is small if the magnitude of s 0 can be chosen relatively larger. (See also the role of spectral gaps of Markov chains in obtaining almost exponentiality of hitting times in Aldous and Fill [3,Section 3.5.4].) In fact, if Q is the random walk kernel on a (simple connected) k-regular graph on N vertices with k ≥ 2 and s 0 is even, we can alternatively bound tr(|Q| s 0 )/N by means of partial geometry of the graph and the analogous spectral functional on the infinite k-regular tree. (Here and in what follows, see Biggs [7] for terminology in algebraic graph theory.) Indeed, we have where N (s 0 ) is the number of vertices x in the regular graph such that the subgraph induced by the vertices at graph distance ≤ s 0 /2 from x defines a tree (cf. McKay [23,Lemma 2.2]), and is the Kesten-McKay density [20,23] for the spectral measure of the random walk kernel on the infinite k-regular tree and satisfies lim s→∞ q s f (k) (q)dq = 0. For approximation of the ratio of Green functions as in (1.8) where E (n) denotes expectation with respect to Q (n) .
By Corollary 1.2, we obtain the following particular result for random regular graphs (see, e.g., Wormald [33] for a survey of random regular graphs). A further discussion of this result will be given in Section 1.
almost surely with respect to the randomness that the graphs are chosen.
Here H x,y under E (∞) denotes the first hitting time of y by a rate-1 random walk on the (transient) infinite k-regular tree started at x for any vertices x and y which are adjacent to each other.
The proof of Corollary 1.3 is relegated to Section 4.3. We recall that with probability tending to 1 in the limit of a large graph size, random regular graphs with a fixed degree do not have homogeneity in return probabilities in all numbers of steps (cf. Wormald [33, Section 2.3]). Nonetheless (1.12) holds almost surely with respect to the randomness that the graphs are chosen, as will be explained in Section 4.3.

Application to evolutionary game theory
The present study was in part motivated by Allen, Traulsen, Tarnita and Nowak [6], and let us discuss briefly the role of the meeting times under consideration in their studies. The paper [6] investigates the influence of mutation on forming cliques of strategy types under some evolutionary games. The underlying game players are arranged according to finite vertex-transitive graphs, and their strategy types are updated indefinitely in some Markovian manners. Analogues of the key quantities on some infinite vertex-transitive graphs are also considered in [6]. See Nowak [24] for an authoritative introduction to evolutionary games, Section 1 and 2 in the supplementary information of Nowak, Tarnita and Wilson [25] for an analysis of critical values under general evolutionary games, and the recent survey paper by Allen and Nowak [5] for critical values under games closely related to those in [6] on weighted vertex-transitive graphs.
Allen et al. [6] obtains explicit results on certain critical values for the emergence of cooperation between game players, when special finite vertex-transitive graphs are taken into consideration. This is based on the result that on general finite vertex-transitive graphs, the so-called identity-by-descent probabilities for two game players occupying adjacent vertices [6,Section 2.3] are the only quantities left to be solved for the critical values [6, Appendix C]. These identityby-descent probabilities are equivalent to the Laplace transforms E[e −λMx,y ] of the first meeting times M x,y by independent continuous-time (rate-1) random walks started at adjacent vertices x and y (cf. the algebraic equations in [6, Appendix B]), where λ are strictly positive parameters depending only on the underlying mutation rates. More generally, it is not difficult to check that on regular graphs, the Laplace transforms E[e −λM U,V ] determine the critical values for cooperation under the games in [6] (see [6, Appendix A to C] and Corollary 5.2).
While the same evolutionary games considered in Allen et al. [6] in the absence of mutation allow for rather complete explicit results (see e.g. [26,32,13,8]), we are unable to expect so for the critical values in general when mutation enters because Laplace transforms of meeting times are now involved. Nonetheless, as one special case, Allen et al. [6, Section 2.2 and 3.2] circumvented the difficulty of handling the identity-by-descent probabilities equivalent to E[e −λM U,V ] on general finite regular graphs, by considering large random regular graphs and turning to the analogous identity-by-descent probabilities on infinite regular trees instead (or equivalently, E (∞) [e −λMx,y ] by the notation of Corollary 1.3). See also Szabó and Fáth [31] for related discussions on the application of random regular graphs for evolutionary games on graphs. Corollary 1.2 gives a justification of the practice in Allen et al. [6] discussed above if we assume a fixed mutation rate and take limit of the identity-bydescent probabilities on growing random regular graphs with a constant degree. In fact, by formalizing the discussion on approximating the Laplace transforms of first-order meeting times after Theorem 1.1, a quantitative approximation of the critical values on finite regular graphs with bounded degree and large girth without passing to the limit is now also possible.

Method of proof
We consider a linear analysis for first meeting time distributions. Our point of view starts with the duality between coalescing Markov chains and voter models, and we apply the linear coupling of voter models defined by products of i.i.d. random linear operators acting on initial configurations, which makes some computations natural and straightforward. This coupling of voter models and a study of similarly defined interacting particle systems can be found in Liggett [22, Chapter IX] (see e.g. [15,4,16] for recent studies).
Let us recall coalescing Markov chains, voter models and a particular result of their duality. A system of coalescing Markov chains consists of continuoustime rate-1 Q-Markov chains started at all points of the state space E. They move independently before meeting and together afterward. The associated voter model is a continuous-time rate-N Markov chain (ξ t ) taking values in the space of configurations of two possible "opinions", say 1 and 0, at points of the state space so that, at each epoch time, the opinion of a randomly chosen point, say U ′ , is changed to the opinion of another chosen according to Q(U ′ , · ). We consider the following particular consequence of the duality between the voter model and the coalescing Markov chains: Here, under E ξ , the voter model starts at configuration ξ ∈ {1, 0} E , and E βu means that the initial configuration is randomized according to the random configuration β u which is defined by placing i.i.d. Bernoulli random variables β u (x) with mean u ∈ (0, 1) at all points x. See Liggett [22] for a general account of voter models and coalescing Markov chains. Let us discuss how the duality method is applied for the study of meeting time distributions. It should be clear from the above description that the voter model can be identified as a Markov chain on configurations which is updated sequentially by a family of i.i.d. random linear operators (T n ) independent of the initial configuration. We may assume that the voter model is obtained by time-changing a Markov sequence (ξ n ) by an independent rate-N Poisson process, where (ξ n ) is defined recursively by (1.16) Here, configurations are regarded as column vectors with coordinates indexed by points of E (with respect to a fixed order). (A detailed description of the distribution of these random linear operators is given in the proof of Proposition 2.1.) Write J for the square matrix with entries identically equal to 1/N , and let us use the standard bra-ket notation (see Paratharasy [28]) so that β u | and |β u mean the row vector and the column vector corresponding to the Bernoulli random configuration β u . Then by the independence of the underlying objects defining the voter model started at β u , the discrete-time analogues of the two-point correlations E βu [ξ t (U )ξ t (V ∞ )], which determine the distribution of the ∞-order meeting time M U,V∞ through the duality equation (1.15), can be written as: where L is a (deterministic) linear operator defined by the expected matrix "congruence" It is true that in general, the key matrices L n (J) in (1.17) are complicated, and hence, so are the associated discrete-time two-point correlations there. When, however, the return probabilities Q s (x, x) of the discrete-time Q-chain do not depend on points x for every s ∈ Z + or, simply, Q is walk-regular (see Godsil and McKay [17]), we find a detailed description for L n (J): Here, α is a two-parameter discrete function defined by an explicit partial recurrence equation, which in part takes the form of a discrete transport equation, has a finite-speed of propagation and is defined explicitly in terms of the traces tr(Q s ) of products of Q (see Lemma 3.1 for its definition). In particular, the resulting characterization of the discrete-time two-point correlations is enough for an explicit expression of the Laplace transform of the first-order meeting time, which is essentially due to the connection mentioned above between the distributions of M U,V and M U,V∞ (see Section 4.1 for the details). Then it holds that To establish an approximating equality for (1.20) when walk-regularity of Q fails, we introduce the terms as substitutes of the true correlations in (1.17), where the linear operator L 0 is chosen to be an "approximating" version of L and such that the infinite series expression in (1.19) remains valid with L n (J) replaced by the new products L n 0 (J). (See (3.1) for our choice of L 0 .) For convenience, we will call the above terms approximating correlations in view of (1.17), even though in general their probabilistic interpretation is not clear to us. The main technical issues as a result of adopting these approximation correlations arise essentially in the context of large state spaces. We have to understand the asymptotic behavior of L n 0 (J) for large n with respect to the size of the state space, and bound the errors from replacing L with L 0 in formulating the approximating correlations so that they do not grow too fast up to moderately large times even on large state spaces. The details are given in Section 4.2.
Organization of the paper. In Section 2, we study basic properties of the operator L defined by (1.18), which gives the two-point correlations (1.17) of voter models, from its explicit expression to some related operator norms. Based on the explicit form, we define in Section 3 the operator L 0 in making the approximating correlations (1.21), and study generating functions of the matrices L n 0 (J). We show a preliminary connection among the distribution of M U,V , the true correlations (1.17), and the approximating correlations (1.21) in Section 4.1, and then in Section 4.2, we prove the main approximation theorem (Theorem 1.1) on the distributional reduction of the first-order meeting times. Details of the proof of Corollary 1.3 are given afterward in Section 4.3. We close this paper with some relations between meeting times of all finite orders in Section 5.

Correlations of voter models
Recall the linear operator L defined in (1.18) by a matrix expectation. In this section, we derive its explicit representation and study related operator norms. From now on, we index entries of N × N matrices over C by points of E (with a fixed order as before), and M E stands for the linear space of N × N matrices subject to such convention. In addition, we will consistently use the bra-ket notation for matrix and vector multiplications.
To start with, let us set some matrix notation for the explicit representation of L. We define a linear operator diag on M E by For the present purpose to compute the explicit expression of L, we may assume that the operator T in its definition (1.18) is given by Here, as before, P(U = x, V = y) ≡ 1 N x|Q|y . Then we expand the product T * CT defining L as Taking expectation for both sides of the foregoing equality, we obtain To simplify the right-hand side of the foregoing equality, we use the assumed symmetry of the Markov kernel Q and the equality I = x∈E |x x|, and invoke the operators diag( · ) and J defined above in (2.1) and (2.2), respectively. It follows that (2.5) We obtain the required equation (2.3) from (2.5) after rearrangement. The proof is complete.
We consider some particular cases of (2.3).
In particular, if the s-step return probabilities x|Q s |x do not depend on x for s ∈ Z + , then (2.7) simplifies to Proof. To see (2.6), we apply to (2.3) the fact that QJ = JQ = J, and obtain the required equation: Equation (2.7) is a straightforward consequence of (2.3). For the particular case that x|Q s |x do not depend on x, we note that x|Q s |x is equivalent to the arithmetic mean of the diagonal terms of Q s and so diag(Q s ) = [tr(Q s )/N ]I. It follows that (2.7) can be written as which is (2.8).
Let us turn to some operator norms related to L. We equip M E with the ℓ 1 -norm: and consider the (induced) operator norms The following proposition will be used in Section 4.2 for the proof of Theorem 1.1.

Proposition 2.3.
We have the following bounds: Proof. We note that by (2.3), By (2.10), we have and by (2.11), for x = y, Since |x y| = 1 for all x, y ∈ E, we deduce (i) from (2.12) and (2.13). By (2.10) and (2.11) again, we obtain, respectively, and, for x = y, where (2.16) follows by noting that the summands on the right-hand side of (2.15) are nonzero only if z = x or a = y. By (2.14) and (2.17), we deduce (ii).

Approximating correlations
The matrices L n (J) allow for simple expressions in the walk-regular case. This is pointed out in (1.19) in Section 1, and we will give the proof later on in Lemma 3.1. In general, we can still choose an operator L 0 which is similar to L so that L n 0 (J) gives the same expression (1.19) (with L n (J) replaced) even if the assumption of walk-regularity is not in force. One choice is to replace diag( · ) with [tr( · )/N ]I in the representation (2.3) of L, and consider accordingly for C ∈ M E . We will work with the matrices L n 0 (J) throughout this section, and it will be helpful to keep in mind that they are meant to "approximate" L n (J), in a sense to be made precise in Section 4.  In particular, if Q is walk-regular, then We note that α has a finite speed of propagation, or more precisely, α(n, s) = 0 whenever s ≥ n + 1, and (3.4) takes the form of a discrete transport equation.
Proof of Lemma 3.1. We prove (3.5) by an induction on n ∈ Z + . The case n = 0 follows plainly by the assumed initial condition of α. Suppose that (3.5) is true for some n ∈ Z + . Then we have where the infinite series are only finite sums since α has a finite speed of propagation. By the definition (3.1) of L 0 , we can express L 0 (J) and L 0 (Q s ) on the right-hand side of the foregoing equality by linear combinations of J and Q s (cf. the proof of Corollary 2.2), and get Since tr(I) = N , (3.5) with n replaced by n + 1 follows from the last equality and the definition of α(n + 1, · ) (see (3.2)-(3.4)). By mathematical induction (3.5) is true for all n ∈ Z + . The proof of (3.6) proceeds with an induction on n ∈ N. We need two observations. Notice that when Q is walk-regular, where g ranges over all polynomials over C, and A defines an algebra. In addition, it is plain from the definition (3.1) of L 0 that We are ready to give the proof of (3.6). It holds for n = 1 by (3.7). If (3.6) holds for some n ∈ N, then we get where the second equality follows from (3.8) and (3.9). Hence, by mathematical induction, (3.6) is true for all n ∈ N. The proof is complete.
Next, we derive the generating function of the above discrete function α, using functional calculus for the symmetric matrix Q. Recall that we assume the state space of Q has size N > 8. (3.10) Then G α(ζ, q) converges absolutely for any ζ, q ∈ C with |ζ| < 1 and |q| ≤ 1.
Moreover for such ζ, q, . (3.11) Apply the foregoing theorem to (3.5) by the spectral representation of f (Q) for complex functions f which are analytic around [−1, 1]. We obtain the following corollary immediately.
Corollary 3.3. The generating function of the square matrices L n 0 (J) with respect to exponent n ∈ Z + is given by .
The rest of this section is devoted to the proof of Theorem 3.2. The conclusion will be given at the end of this section.
We begin with an a priori estimate to ensure that the radius of convergence for G α is not degenerate. See also Lemma 4.5 for different estimates. Then (3.13) can be checked by induction on n (recall the initial condition of α) and the foregoing inequalities. The proof is complete.

(3.18)
By linearity of trace, we obtain , from which we deduce the equality (3.11) for ζ, q ∈ C satisfying (3.14). The proof is complete.
From now on, we write C(0, R), D(0, R) and D(0, R) for the circle, the open disc and the close disc, respectively, centered at 0 with radius R ∈ (0, ∞) in the complex plane. We study the denominator of the function on the right-hand side of (3.11). (3.20) Here, meromorphic functions are defined at their removable singularities in the natural way, and the right-hand side of the equality in (3.19) is read as 1/N 2 if ε = 0 (since 1 is an eigenvalue of Q). Moreover, in the above display, the minimum and the maximum are attained at 1 − ε N and −(1 − ε N ), respectively.
Note that M 1 is just the constant map 1/N . Let us make some observations for M q , when q ∈ [−1, 1). By a standard result of Möbius transformations, M q maps C(0, 1 − ε N ) to a nondegenerate circle, say C q , in C because it is nonconstant and analytic in an open set containing D(0, 1). The circle C q is symmetric about the real line because M q is defined by real coefficients, and plainly intersects the real line at and 22) which are distinct strictly positive real numbers. This means that C q is contained in the half plane {ζ ∈ C; ℜ(ζ) > 0}. In addition, note that for each q ∈ [−1, 1), the value in (3.21) is strictly less than the value in (3.22), and M q ( √ −1) has strictly negative imaginary part. We deduce that for q ∈ [−1, 1) and for some a q , b q ∈ (0, ∞) independent of θ. The foregoing equality holds trivially for q = 1 if we set a 1 = 1/N and b 1 = 0. By the special form (3.23) of M q for all q ∈ [−1, 1], the optimization problems in (3.19) and (3.20) take the forms of minimizing and maximizing |A − Be √ −1θ | subject to θ ∈ [0, 2π], for fixed A, B ∈ (0, ∞). For the latter two, solutions are given by θ = 0 and θ = π, respectively. Hence, the equalities in (3.19) and (3.20) follow upon using (3.21) and (3.22). Conclusion for the proof of Theorem 3.2. We have seen that (3.11) holds when ζ, q ∈ C satisfying (3.14), by Lemma 3.5. By a standard result of several complex variables (see, e.g., Hörmander [18, Theorem 2.2.1]) and Lemma 3.6, the function in two complex variables on the right-hand side of (3.11) is analytic in the open polydisc D = {(ζ, q) ∈ C × C; |ζ| < 1, |q| < 1}. Hence, by Cauchy's inequalities for analytic functions in several complex variables [18,Theorem 2.2.7], G α(ζ, q) converges absolutely on the polydisc D. Next, if we fix ζ ∈ C such that |ζ| < 1 and repeat the above argument with respect to the single complex variable q, then the assertion of Theorem 3.2 can be extended up to the boundary case |q| = 1. The proof is complete. From now on, we write S ξ (C) ≡ ξ|C|ξ for all deterministic configurations ξ, and in addition, Bernoulli with mean u).
where the series on the left-hand side converges absolutely.
Proof. We apply λ N +λ × 1 N S ξ to both sides of (3.12) with ζ set to be N/(N + λ). Then notice that and the second term on the right-hand side of (3.12) with ζ set to be N/(N + λ) becomes The equality (4.2) now follows plainly.
Next, we relate the Laplace transform of M U,V to the generating function of 1 N S βu L n 0 (J) (in n) in the following lemma. We define the mean local density p 10 (ξ) of configuration ξ by (ii) For every λ ∈ (0, ∞) and u ∈ (0, 1), where the series on the right-hand side converges absolutely.
Proof. The proof of (i) follows immediately from the fact: for every ξ ∈ {1, 0} E and n ∈ Z + , where p 10 (ξ) is defined by (4.3). The above equation is implicit in the proof of [9, Proposition 3.1 (iii)] since 1 N S ξ L n (J) ≡ E ξ [ξ n (U )ξ n (V ∞ )]. To prove (ii), we resort to the duality equation (1.15) and use the fact that (ξ t ) is equal to (ξ n ) time-changed by an independent Poisson process with rate N . We get where the last equality follows from (i). It remains to prove (iii). On one hand, we note that and so (iii) follows if we can show that The foregoing equality, however, is a consequence of (4.2) if we apply a randomization by β u to both sides of (4.2) and notice To see (4.5), we first compute and similarly, S βu (J) = (N − 1)u 2 + u. Hence, we get Here, we write Then by polynomial approximation, (4.7) implies The equality (4.9) is enough to get (4.5), and the proof is complete.

Approximation
This section is devoted to the proof of Theorem 1.2. Recall the notation S ξ and S βu defined at the beginning of Section 4.1. To prove Theorem 1.1, it is enough to bound by Lemma 4.2 (ii) and (iii). For fixed m ∈ N, we will handle separately and in order the objects: (1) the partial sum of the first term in (4.11) for n ranging from mN + 1 to ∞, (2) the partial sum of the second term in (4.11) for n ranging from mN + 1 to ∞, and (3) the difference in (4.11) with the upper limits ∞ of the two series replaced with mN . The first object described above is easy to deal with.
Proof. First we claim the following inequality: for all n ∈ Z + where the constant C ε is defined by (1.9). By (3.5) and (4.6), we have Note that ∞ s=0 α(n, s) = 0, which can be seen by using the initial condition of α and adding up both sides of (3.2)- (3.4). Hence, by the foregoing display and then the recursive equations (3.2)-(3.4) for α, we get α(n, s)tr(Q s ) tr(I) Q s α(n, s) .
Our claim (4.24) follows upon applying Lemma 4.5 to the right-hand of the foregoing equality.
To finish the proof of (4.23), we use (4.24) and get as stated in in the required inequality (4.23). The proof is complete.
The final stage is on bounding the third object described below (4.11): L j (η n−j ), (4.26) where η n L L n−1 0 (J) − L n 0 (J) satisfies by the definition of η n , and it follows that ε n = L(ε n−1 ) + η n .
We obtain (4.26) by iterating the above equality and using the equality ε 1 = η 1 (recall Corollary 2.2 and (3.1)). Next, we show the explicit form (4.27) of η n . Fix n ∈ N, and recall the definition (3.1) of L 0 . By (3.5) and Corollary 2.2, we have On the other hand, if we express the coefficients α(n, · ) of L n 0 (J) in (3.5) by α(n − 1, · ) using the partial recurrence equations (3.2)-(3.4) obeyed by α, then Comparing the last equalities in the foregoing two displays, we deduce that η n satisfies the required expression (4.27). The proof is complete.
The next lemma is on bounding the square matrices followed by α(n − 1, s) in the expression (4.27). Recall the definition (1.5) of R γ Q (x, s) and the ℓ 1 -norm on M E defined by (2.9).
(for the last trace term, recall the notation (4.8)).
Proof. Fix s ∈ Z + . We will prove (4.28) in four steps.
The first inequality in (4.28) follows from the foregoing display. ( Step 2). Before giving the proof of the second inequality in (4.28), we claim that for any x ∈ E, To see this, consider which gives our claim (4.29). ( Step 3). We claim that For any x ∈ E, where the second inequality follows from the inequality (4.29). Since the last inequality holds for arbitrary x ∈ E, (4.30) follows.
(Step 4). Finally, we claim that Let {ψ q ; q ∈ σ(Q)} be a basis of C E corresponding to the eigenvalues q of Q (σ(Q) denotes the spectrum of Q). We may assume that the eigenfunctions ψ q are orthonormal with respect to the counting measure over E. Then we have where the last equality follows since the unique eigenfunction corresponding to 1 is a constant function. The last inequality gives (4.31). By (4.30) and (4.31), the second inequality in (4.28) follows at once. The proof is complete. Lemma 4.9. For any λ ∈ (0, ∞), u ∈ (0, 1), m ∈ N and γ ∈ [0, 1], we have where ∆ γ Q is defined in (1.7).
To handle the right-hand side of (4.34), we consider the ℓ 1 -norms (defined as in (2.9)) of the matrices followed by α(n − 1, s) in the expression (4.27) for η n . We have where the next to the last equality follows from the fact that Q is a symmetric probability matrix. Then apply Lemma 4.8 to (4.35), and we obtain for ∆ γ Q defined by (1.7). Applying (4.35) to the right-hand side of (4.27), we find that for every n ∈ N, where the last equality follows from Lemma 3.4. By the foregoing inequality and (4.34), we obtain that for all 1 ≤ n ≤ mN , The foregoing inequality is enough to obtain the required inequality (4.32) (recall that the summand with n = 0 is zero).
Conclusion for the proof of Theorem 1.

Application to large random regular graphs
We give the proof of Corollary 1.3 in this section, and fix k ≥ 2. Assume that the state space on which Q (n) lives is given by E n and has size N n ր ∞. It follows from a standard result of random regular graphs that for every s ∈ Z + , lim n→∞ min x∈En [N n − #R 0 Q (n) (x, s)] N n = 0 a.s.
(cf. Wormald [33,Section 2] for the above convergence as well as the present assumption that the random regular graphs are simple and connected). We also know that a.s., the sequence of empirical eigenvalues distributions of Q (n) , namely 1 N n #{r ∈ (−∞, q]; r is an eigenvalue of Q (n) }, q ∈ R, converges weakly to the (normalized) Kesten-McKay distribution with density given by (1.11), and hence, (1.12) holds. See Kesten [20] for the fact that the function in (1.11) is a density of the spectral measure of the random walk kernel on infinite k-regular tree, and McKay [23,Theorem 4.3] for the above convergence of empirical eigenvalue distributions.
To use (1.13) and find the limit of the ratios of Green functions there, we apply the spectral representation (1.10) and deduce that ∞ 0 e −tλ/2 1 {y} (X y t )dt = E (∞) e −λHx,y/2 , almost surely with respect to the randomness that the graphs are chosen, where x and y are any adjacent vertices on the infinite k-regular tree. This proves Corollary 1.3.

Meeting times of higher orders
Let {U n ; n ∈ Z + } and {V n ; n ∈ Z + } be two sequences of Q-chains with U 0 = V 0 so that U 0 has uniform distribution on E, and conditioned on U 0 , the two chains are independent. We assume in addition that {U n } and {V n } are independent of a system of coalescing Q-chains which we may denote it by {X x }. Below we consider meeting times of all orders from a slightly more general point of view, using the pairs (U m , V n ) as starting points.  Proof of Proposition 5.1. By the mass-transport equation Here on the right-hand side of (5.4), the first term and the distribution P(U n = V m , U n = x, V m+1 = y) can be determined respectively as P(U n = V m ) = tr(Q m+n )/N and P(U n = V m , U n = x, V m+1 = y) = P(U n = x, V m+1 = y) − P(U n = V m , U n = x, V m+1 = y) The proof is complete.
Corollary 5.2. If, for some n ∈ Z + , the return probabilities x|Q n |x do not depend on x, then Hence, in the case that Q is walk regular, the distributions of M U,Vn for all n ∈ N can be completely determined by M U,V by iteration and differential calculus.