Laurent Miclo

On absorption times and Dirichlet eigenvalues

Keywords: irreducible and reversible subMarkovian matrices, exit or absorption times, Dirichlet eigenvalues, mixtures, geometric laws, exponential distributions, strong random times, local equilibria, intertwining, birth and death chains and processes 60J10 secondary: 60J27, 37A30, 31C25, 60J80

This paper gives a stochastic representation in spectral terms for the absorption time T of a finite Markov chain which is irreducible and reversible outside the absorbing point. This yields quantitative informations on the parameters of a similar representation due to O'Cinneide for general chains admitting real eigenvalues. In the discrete time setting, if the underlying Dirichlet eigenvalues (namely the eigenvalues of the Markov transition operator restricted to the functions vanishing on the absorbing point) are nonnegative, we show that T is distributed as a mixture of sums of independent geometric laws whose parameters are successive Dirichlet eigenvalues (starting from the smallest one). The mixture weights depend on the starting law. This result leads to a probabilistic interpretation of the spectrum, in terms of strong random times and local equilibria through a simple intertwining relation. Next this study is extended to the continuous time framework, where geometric laws have to be replaced by exponential distributions having the (opposite) Dirichlet eigenvalues of the generator as parameters. Returning to the discrete time setting we consider the influence of negative eigenvalues which are given another probabilistic meaning. These results generalize results of Karlin and McGregor and Keilson for birth and death chains.

Introduction

This paper shows that the time to absorption of a reversible Markov chain has a stochastic representation in spectral terms. It gives quantitative informations on the parameters of a similar representation due to O'Cinneide [START_REF] Art | Phase-type distributions and invariant polytopes[END_REF] for general chains admitting real eigenvalues. In continuous time, the absorption time is distributed as a mixture of sums of independent exponentials having the underlying eigenvalues as parameters. This generalizes results of Karlin and McGregor [START_REF] Karlin | Coincidence properties of birth and death processes[END_REF] and Keilson [START_REF] Keilson | Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes[END_REF] for birth and death chains.

We begin with the case of discrete time. Let S be a finite set endowed with a probability transition matrix P . We make the following irreducibility and reversibility assumptions:

(A1): There exists a particular point ∈ S which is absorbing (i.e. P ( , ) = 1) and such that { } is the unique irreducible class of P (or equivalently, for any x ∈ S, there exists a path going from x to , x = x 0 , x 1 , ..., x p = , satisfying P (x i , x i+1 ) > 0 for i ∈ 0, p -1 ). Let S S \ { }, we assume furthermore that the subMarkovian restriction P ( P (x, y)) x,y∈S of P to S is irreducible (namely, any pair of points from S can be joined by a path).

(A2): P is reversible with respect to some positive probability measure π on S: ∀ x, y ∈ S, π(x)P (x, y) = π(y)P (y, x)

Let m 0 be a probability measure on S, we consider X (X n ) n∈N a homogeneous Markov chain on S whose initial distribution is m 0 and whose transitions are given by P . We are interested in the absorption time

T inf{n ∈ N : X n = }
which is almost surely finite by the first irreducibility hypothesis.

To describe its law, we need to introduce the corresponding Dirichlet eigenvalues, which are the eigenvalues of the restriction of P to the space of functions f : S → R satisfying the Dirichlet condition f ( ) = 0. Equivalently, they are the eigenvalues of P ,

1 > θ 0 > θ 1 ≥ θ 2 ≥ • • • ≥ θ N -1 > -1
where N = card(S). The fact that they are real numbers comes from the reversibility assumption. They belong to (-1, 1) because { } is the unique irreducible class of P . The inequality θ 0 > θ 1 (and also θ 0 ≥ |θ N -1 |) is a consequence of the irreducibility of P and of the Perron-Frobenius theorem.

To get a simple statement below, we assume that all these eigenvalues are nonnegative: (A3): θ N -1 ≥ 0. For 0 ≤ i ≤ N -1, we denote by G(θ i , θ i+1 , ..., θ N -1 ) the convolution of geometric distributions of parameters θ i , θ i+1 , ..., θ N -1 . More precisely, this is the law of τ i + τ i+1 + • • • + τ N -1 , where the τ j , for j ∈ i, N -1 , are independent random variables and satisfy One of our main results can now be stated (see the paragraph after Theorem 2 below for a discussion of the links with the representation due to O'Cinneide [START_REF] Art | Phase-type distributions and invariant polytopes[END_REF]):

Theorem 1 Under the assumptions (A1), (A2) and (A3), there exists a probability measure a (a 0 , ..., a N -1 ), with a 0 > 0, such that T is distributed as M G (θ, a).

The probability measure a strongly depends on the initial distribution m 0 of X. Let us write a(m 0 ), then a commutes with the operation of taking mixtures: if m 0 and m 0 are two probabilities on S and α ∈ [0, 1], then a(αm 0 + (1 -α)m 0 ) = αa(m 0 ) + (1 -α)a(m 0 ). Thus to prove the above theorem, it is sufficient to deal with the case where m 0 is a Dirac mass at some initial point x ∈ S, nevertheless it will be more fruitful to treat the general situation directly. There is an explicit formula for a:

∀ i ∈ 0, N -1 , a i = m 0   j∈ i+1,N -1 P -θ j 1 -θ j   1 -P 1 -θ i (S) (1)
but to see that it is nonnegative, we will need a non-immediate linear algebra result due to Micchelli and Willoughby [START_REF] Micchelli | On functions which preserve the class of Stieltjes matrices[END_REF]. In Remark 7 below, we will see how this expression simplifies in the important case i = 0. If P is not assumed to be irreducible (then the inequality θ 0 > θ 1 is not necessarily satisfied), we can decompose S into the corresponding irreducibility classes for P , say S 1 , ..., S r , and apply the previous theorem to the Markovian transition matrices Pi ( P (x, y)) x,y∈S i { } , for i ∈ 1, r , to get a similar result (except for the assertion a 0 > 0), with a mixture of sum of geometric variables of parameters certain successive Dirichlet eigenvalues of the P i ( P (x, y)) x,y∈S i , for i ∈ 1, r .

It is also possible to describe the law of T when some of the eigenvalues are negative, but the corresponding statement is more involved and we refer the reader to Section 6 below. The case of nonnegative eigenvalues is already sufficient to deduce a similar result in the continuous time setting. Let S = S { } be a finite set, endowed with L a Markov generator matrix (i.e. the off-diagonal entries are nonnegative and the rows sum up to zero). In analogy to what we have done before, we assume that (B1): { } is the unique recurrence class of L, so in particular is an absorbing point (namely the row L( , •) is null) and the S × S submatrix L of L (or from a functional point of view, the restriction of the operator L to functions vanishing in ) is irreducible.

(B2): L is reversible with respect to some positive probability measure π on S: ∀ x, y ∈ S, π(x)L(x, y) = π(y)L(y, x)

Let m 0 be a probability measure on S, we consider X (X t ) t≥0 a homogeneous Markov process on S whose initial distribution is m 0 , whose infinitesimal generator is L and whose trajectories are cadlag, namely they are right-continuous and admit left-limits. We are interested in the absorption time

T inf{t ≥ 0 : X t = }
which is almost surely finite by the irreducibility hypothesis.

To describe its law, we need to introduce the corresponding Dirichlet eigenvalues, which are the eigenvalues of the restriction of -L to the space of functions vanishing at . They are just the eigenvalues of -L,

0 < λ 0 < λ 1 ≤ • • • ≤ λ N -1
where N = card(S). As above, the fact that they are real numbers comes from the reversibility assumption and they are positive because { } is the unique recurrence class of L. The inequality λ 0 < λ 1 is a consequence of the irreducibility of L and of the Perron-Frobenius theorem. Alternatively, one can come back to the previous situation by considering the semigroup ( Pt ) t≥0 (exp(t L)) t≥0 . Then for any t > 0, Pt satisfies the above discrete time hypotheses and we have for its eigenvalues

∀ 0 ≤ i ≤ N -1, θ i (t) = exp(-tλ i )
which in particular are positive: θ N -1 (t) > 0.

For 0 ≤ i ≤ N -1, we denote by E(λ i , λ i+1 , ..., λ N -1 ) the convolution of exponential distributions of parameters λ i , λ i+1 , ..., λ N -1 . More precisely, this is the law of

τ i + τ i+1 + • • • + τ N -1
, where the τ j , for j ∈ i, N -1 , are independent r.v. and satisfy

∀ j ∈ i, N -1 , ∀ t ≥ 0, P[ τ j ≥ t] = exp(-λ j t)
Again, we denote λ (λ 0 , ..., λ N -1 ) and for a probability measure a (a 0 , ..., a N -1 ) on 0, N -1 , we introduce M E (λ, a) the mixture of the distributions E(λ i , λ i+1 , ..., λ N -1 ), for i ∈ 0, N -1 , with respective weights given by a, i.e.

M E (λ, a)
0≤i≤N -1

a i E(λ i , λ i+1 , ..., λ N -1 )
As a consequence of previous result, we get Theorem 2 Under the continuous time assumptions (B1) and (B2), there exists a probability measure a (a 0 , ..., a N -1 ), with a 0 > 0, such that T is distributed as M E (θ, a).

That T is distributed as a mixture of convolutions of exponential laws is known and due to O'Cinneide [START_REF] Art | Phase-type distributions and invariant polytopes[END_REF]. Under the relaxed assumption that the eigenvalues of L are real, he showed that there exist M ≥ N , a probability measure a = (a i ) i∈ 0,M -1 and positive parameters l = (l i ) i∈ 0,M -1 such the law of T is described by

M E (l, a)
0≤i≤M -1

a i E(l i , l i+1 , ..., l M -1 )
O'Cinneide [START_REF] Art | Phase-type distributions and invariant polytopes[END_REF] also indicated that, once the exponential distributions have been replaced by geometric distributions, the same representation can also be deduced in discrete time by resorting to techniques from [START_REF] Art | Characterization of phase-type distributions[END_REF]. These results belong to the realm of phase type distributions (they correspond to general laws of absorbing time of finite Markov chains), which are important in the computational probability approach to queueing theory, because they lead to matrix algorithms which are tractable in practice. This field of investigation was initiated by Neuts [START_REF] Neuts | Matrix-geometric solutions in stochastic models[END_REF] but it is out of the scope of the present article to present it. We refer the interested reader to the above references and to the bibliography therein (see also for instance Commault and Mocanu [START_REF] Commault | Phase-type distributions and representations: some results and open problems for system theory[END_REF] or He and Zhang [START_REF] He | Spectral polynomial algorithms for computing bi-diagonal representations for phase type distributions and matrix-exponential distributions[END_REF][START_REF] He | P H-invariant polytopes and Coxian representations of phase type distributions[END_REF] for more recent works on the subject). We just mention briefly a few features. The view point of phase type distributions is the opposite of our approach: for queueing theorists the law of T is given (this is the distribution of the arrival or service times) and they want to find a corresponding generator L with the smallest possible state space. The information (under the reversibility assumption) that we can take M = N is important since it reduces the size of a representation in terms of a simple Markov chain. Note that in the general case of real eigenvalues, one may have to take M > N , as it is shown by an example due to Botta, Harris and Marchal [START_REF] Botta | Characterizations of generalized hyperexponential distribution functions[END_REF]. Further, to estimate the minimal M seems a difficult task. The identification of the parameters as eigenvalues given in Theorem 2 is also relevant. But above all, our proof is completely different from the invariant polytope method of O'Cinneide [START_REF] Art | Phase-type distributions and invariant polytopes[END_REF] and it sheds a new probabilistic insight on his result. We hope we will be able to extend our approach (where reversibility is only needed in next section) to recover the full validity of O'Cinneide's representation and maybe to better understand the general case where complex eigenvalues enter the game (see the nice review of O'Cinneide [START_REF] Art | Phase-type distributions: open problems and a few properties[END_REF] for very motivating open problems in this direction).

An immediate application of Theorems 1 and 2, is to provide easy bounds on absorption times. Thus in continuous time (respectively in discrete time, with nonnegative eigenvalues), T is always stochastically bounded above by a sum of exponential laws (resp. geometric laws) of parameters the corresponding Dirichlet eigenvalues. For instance, in discrete time with nonnegative eigenvalues, we get with the notation introduced before Theorem 1, for any n ∈ N * ,

P[T ≥ n] ≤ P[τ 1 + • • • + τ N -1 ≥ n] = m∈ n,∞ n 0 +•••+n N -1 =m, n j ∈N * j∈ 0,N -1 (1 -θ j )θ n j -1 j
This formula can be deduced using a divided differences computation (see also [START_REF] Art | Characterization of phase-type distributions[END_REF] in Section 6).

For simplicity, assume that all the eigenvalues are distinct, then we have

n 0 +•••+n N -1 =m, n j ∈N * j∈ 0,N -1 θ n j -1 j = i∈ 0,N -1 θ N +m i j∈ 0,k \{i} (θ i -θ j )
and we recover the standard bound

P[T ≥ n] ≤ i∈ 0,N -1 θ N +n i j∈ 0,k \{i} (θ i -θ j )
Similar computations hold for continuous time. Unfortunately, these bounds are not very sharp in general, unless if a 0 is not negligible. Indeed, lower bound on a 0 will be important in deducing interesting quantitative informations on absorption time for specific models, but we will not investigate this subject here. Another strong motivation to study the quantity a 0 is that it can be used to deduce cut-off phenomenon in the separation distance (at least in the absorbing setting instead of convergence to equilibrium, but they are related, see also a remark below). Indeed, if a 0 is sufficiently close to 1 (or at least if the probability measure a is concentrated near 0), the strategy of Diaconis and Saloff-Coste [START_REF] Diaconis | Separation cut-offs for birth and death chains[END_REF] can be applied: they only work with birth and death chains because they needed the structure of the law of (dual) absorbing times. The later can also be useful for cut-off in total variation, see the recent preprint of Ding, Lubetzky and Peres [START_REF] Ding | Total-variation cutoff in birth-and-death chains[END_REF].

Below we obtain more structural results, we present an intertwining relation between the absorbing chain or process and a special kind of chain or process, which is nonreversible. Nevertheless, the corresponding transition probability kernel, or generator, belongs to K or L, respectively a certain kind of closure of reversible and irreducible (as before) transition probabilities with nonnegative eigenvalues, or generators, absorbing in (see sections 4 and 5 for the exact definitions). This will enable us to deduce that the class of distributions

M G (a, θ) with 1 > θ 0 ≥ θ 1 ≥ • • • ≥ θ N -1 ≥ 0 (re- spectively M E (a, λ) with 0 < λ 0 ≤ λ 1 ≤ • • • ≤ λ N -1
) and any probability measure a on 0, N -1 , is exactly the set of laws of absorption times of Markov chains (resp. processes) starting from S and associated to a transition matrix belonging to K (resp. to a generator belonging to L). This characterization goes further than the result obtained by Kent [START_REF] Kent | The appearance of a multivariate exponential distribution in sojourn times for birth-death and diffusion processes[END_REF] in this direction, even when restricted to birth and death processes.

Theorems 1 and 2 and their proofs permit a better probabilistic understanding of the fact that under certain circumstances, the absorption time is distributed as a sum of exponential laws (or geometrical laws in discrete time with nonnegative eigenvalues) of parameters the corresponding Dirichlet eigenvalues. This is true for birth and death processes (or monotone chains) starting from one end of a finite segment and absorbing at the other end and we recover the results Karlin and McGregor [START_REF] Karlin | Coincidence properties of birth and death processes[END_REF] and Keilson [START_REF] Keilson | Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes[END_REF], see for instance [START_REF] Diaconis | On times to quasi-stationarity for birth and death processes[END_REF] or Fill [START_REF] Allen | The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof[END_REF] for references and the historical background on the subject. The proof will be based on two ideas, one is the construction of strong random times (generalizing strong stationary times) in the spirit of the work of Aldous and Diaconis [START_REF] Aldous | Strong uniform times and finite random walks[END_REF]. The other one is a stability result on symmetric matrices with nonnegative entries due to Micchelli and Willoughby [START_REF] Micchelli | On functions which preserve the class of Stieltjes matrices[END_REF], that we learned from two recent preprints of Fill [START_REF] Allen | The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof[END_REF][START_REF] Allen | On hitting times and fastest strong stationary times for skip-free processes[END_REF]. The ingredient linking these two tools is the notion of local equilibrium, which appeared in [START_REF] Diaconis | On times to quasi-stationarity for birth and death processes[END_REF], but was not fully exploited there.

One limitation of our approach is that we are only able to deal with reversible chains or processes, while Theorem 1 and 2 sometimes also hold for nonreversible chains or processes, e.g. for skip-free ones, see the paper of Fill [START_REF] Allen | On hitting times and fastest strong stationary times for skip-free processes[END_REF]. We hope to better understand this situation in future work. An easy potential extension concerns reversible Markov chains or processes with more general state space, specially diffusions (see for instance the papers [START_REF] Kent | Eigenvalue expansions for diffusion hitting times[END_REF][START_REF] Kent | The spectral decomposition of a diffusion hitting time[END_REF] of Kent), but this subject will not be developped here. Another even more interesting variation relates to convergence to equilibrium for reversible Markov chains or processes. Indeed, a similar approach can be applied for truly irreducible chains or processes (where the whole state space is the unique recurrence class), so that Theorems 1 and 2 equally hold for strong stationary times (for a background on this field, see for instance the paper of Aldous and Diaconis [START_REF] Aldous | Strong uniform times and finite random walks[END_REF], Diaconis and Fill [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF] or Fill [START_REF] Allen | Strong stationary duality for continuous-time Markov chains[END_REF]) with the standard (Neumann) eigenvalues. This will be the matter of a forthcoming paper.

One may be tempted, say in the continuous time setting, to obtain a more "spatial" interpretation of the exponential variables appearing in Theorem 2, for instance by seeing their partial sums as reaching times of some level sets of the state space. But this is not true in general. We have seen in [START_REF] Diaconis | On times to quasi-stationarity for birth and death processes[END_REF] that in the simple situation of birth and death process, starting from one end of a finite interval and absorbed at the other end, the partial sums of exponential variables correspond to stopping times of the process in certain distributions (called the local equilibria, whose supports are the naturally increasing subinterval), but they are not reaching times. The kind of stopping times needed, called strong randomized stopping times, will be introduced in next section. Still in the above case of birth and death processes, the local equilibria can be related to the left-eigenvectors of the generator (see [START_REF] Diaconis | On times to quasi-stationarity for birth and death processes[END_REF]), but we have not been able to take advantage of that, in particular to deduce a probabilistic or geometric proof of the result of Micchelli and Willoughby [START_REF] Micchelli | On functions which preserve the class of Stieltjes matrices[END_REF]. In the same spirit, the well-known eigenvalue expansion for the distributions of the process at fixed times enables to get the law of the absorption time as a "mixture" of exponential laws, but with signed weights. The interest of Theorem 2 is to provide a truly probabilistic decomposition.

The plan of the paper is the following: in the next section we study a particular kind of strong random time. In section 3, we take advantage of these and of a linear algebra result to define local equilibrium distributions associated to the initial probability measure m 0 , which lead to the proof of Theorem 1. In section 4 we go further and build an intertwining relation. We deduce the similar results for continuous time in section 5 and we deal with negative eigenvalues in section 6. In the last section, we consider two antagonistic examples, one is birth and death processes and the other one is chains or processes with a constant probability or rate to go to the absorbing point.

Strong random times

In the next three sections, we will be working in the discrete time framework. This section is devoted to the construction of a special kind of strong random time which will serve as an elementary brick in building intertwinings.

Let X (X n ) n∈N be any homogeneous Markov chain taking values in a finite state space S. We denote by P its transition matrix and by m 0 its initial distribution (seen as a row vector).

By definition, a strong random time τ is an almost surely finite randomized stopping time for X (namely a stopping time with respect to the filtration generated by X enlarged with some independent randomness) such that τ and X τ are independent. Our principal result here is Proposition 3 Assume there exist θ ∈ (0, 1) and a probability measure µ on S such that

m 0 P = θm 0 + (1 -θ)µ
Then there exists a strong random time τ , distributed as a geometric law of parameter θ, such that X τ admits µ as law.

Formally, this result also holds for θ = 0, since we can then take τ ≡ 1. For θ = 1 (in which case m 0 is invariant for P ), the natural extension of the above statement would lead to τ ≡ +∞, so X τ cannot be defined in general, which also reflects the fact that µ is not determined by the above equation in this situation. But if µ = m 0 , one can take τ ≡ 0.

Proof

The starting idea of the following construction comes from a paper of Aldous and Diaconis [START_REF] Aldous | Strong uniform times and finite random walks[END_REF], see the proof of their Proposition 3.2.b. They were looking for a fastest strong stationary time (namely a strong random time τ such that X τ is distributed according to an invariant measure for P and which is stochastically minimal among all such times). Let us define

∀ x ∈ S, s(x) 1 - m 1 µ (x) = θ 1 - m 0 µ (x) ∈ R {-∞}
where m 1 m 0 P is the law of X 1 . This quantity is related to the "distance" in separation between m 1 and µ, but this feature will not be explicitely used in what follows. At time 1, knowing X 0 and X 1 , we take τ = 1 with probability (1 -θ)/(1 -s(X 1 )), namely we generate a Bernoulli random variable with parameter (1 -θ)/(1 -s(X 1 )) (conditionally independent of X, knowing the latter parameter, this is where additional noise is required) to decide if τ = 1 or not. Since s(X 1 ) ≤ θ, one would have checked that the previous parameter belongs to [0, 1]. So we can write

P[τ = 1|X 0 , X 1 ] = 1 -θ 1 -s(X 1 )
and in particular

P[τ = 1|X 1 ] = 1-θ 1-s(X 1 ) . Let us check that ∀ x ∈ S, P[τ = 1, X τ = x] = (1 -θ)µ(x) (2)
Indeed, we have for any x ∈ S,

P[τ = 1, X τ = x] = P[τ = 1, X 1 = x] = P[τ = 1|X 1 = x]P[X 1 = x] = 1 -θ 1 -s(x) m 1 (x) = 1 -θ 1 -s(x) (θm 0 (x) + (1 -θ)µ(x)) = 1 -θ 1 -s(x) θ m 0 µ (x) + (1 -θ) µ(x) = 1 -θ 1 -s(x) (1 -s(x))µ(x)
Thus ( 2) is satisfied, at least for x ∈ S such that µ(x) = 0, so that the above operations are justified. But if µ(x) = 0 and m 1 (x) > 0, we have directly that P[τ = 1, X 1 = x] = 0, because s(x) = -∞, and the equality (2) also holds in this situation. This is also trivially true if m 1 (x) = 0. It follows from (2) that P[τ = 1] = (1 -θ) and that the conditional law of X 1 on {τ = 1} is µ. We also deduce that the conditional law L(X 1 |τ > 1) is equal to m 0 . This observation is the key to the iterative construction, since we are led back to the initial situation, in some sense after having removed the µ part of m 1 . More rigorously, by iteration of the above procedure, at any time n ∈ N, n ≥ 2, knowing X 0 , X 1 , ..., X n and that the value of τ has not yet been fixed, i.e. τ > n, we take τ = n with probability (1 -θ)/(1 -s(X n )), using additional randomness as before, if necessary. The proposition will be proven if we show that for any n ∈ N * ,

∀ x ∈ S, P[τ = n, X n = x] = (1 -θ)θ n-1 µ(x) (3)
This is proved by induction on n. To facilitate this, consider the equality

L(X n |τ > n) = m 0 (4)
We have already seen that ( 3) and ( 4) are satisfied with n = 1, so let us assume they are true for any n ∈ N * smaller than some N ∈ N * , we are going to deduce them with n replaced by N + 1.

Begin by computing for x ∈ S,

P[τ = N + 1, X N +1 = x] = P[τ = N + 1|X N +1 = x, τ > N ]P[X N +1 = x, τ > N ] = 1 -θ 1 -s(x) P[X N +1 = x, τ > N ] = 1 -θ 1 -s(x) y∈S P[X N = y, τ > N ]P (y, x)
where in the last line, we have used that the event {τ > N } depends on X only through (X m ) 0≤m≤N , so we can apply the Markov property. By the induction assumption, we have for any y ∈ S,

P[X N = y, τ > N ] = P[X N = y|τ > N ]P[τ > N ] = m 0 (y)(1 -P[τ ≤ N ]) = m 0 (y)θ N
where we took into account that (3) implies that

P[τ = n] = (1 -θ)θ n-1 for n ∈ 1, N . So we obtain y∈S P[X N = y, τ > N ]P (y, x) = θ N y∈S m 0 (y)P (y, x) = θ N m 1 (x) = θ N (1 -s(x))µ(x)
Putting all the previous computations together, we get (3) with n replaced by n + 1 (except for x ∈ S such that µ(x) = 0, where (3) has to be checked directly). It remains to compute that for any x ∈ S,

P[X N +1 = x|τ > N + 1] = P[X N +1 = x, τ > N + 1] P[τ > N + 1] = θ -N -1 P[X N +1 = x, τ > N + 1] = θ -N -1 P[X N +1 = x, τ = N + 1, τ > N ] = θ -N -1 P[τ = N + 1|X N +1 = x, τ > N ]P[X N +1 = x, τ > N ] = θ -N -1 1 - 1 -θ 1 -s(x) P[X N +1 = x, τ > N ] = θ -N -1 θ -s(x) 1 -s(x) P[X N +1 = x, τ > N ] = θ -N m 0 (x) µ(x) P[X N +1 = x, τ > N ] 1 -s(x)
but as above, we have

P[X N +1 = x, τ > N ] = θ N (1 -s(x))µ(x)
, so replacing it in the previous expression it appears that ( 4) is satisfied with n replaced by N + 1.

Remark 4 a) Contrary to the fastest strong stationary time considered in Aldous and Diaconis [START_REF] Aldous | Strong uniform times and finite random walks[END_REF], the new strong random time constructed in Proposition 3 does not require a lot of information about the time marginal laws of the chain X. In fact only m 0 and θ are needed. b) Notice that for a given m 0 , the previous result can be applied to any θ ∈ (0, θ * ] ∩ (0, 1), with θ * = min x∈S m 0 P (x)/m 0 (x). The next section will help us to choose θ in a convenient way. c) Note that if x ∈ S is such that m 0 (x) = 0, then s(x) = θ (even if µ(x) = 0, by virtue of the implicitly enforced convention that 0 • ∞ = 0), so for any n ∈ N,

P[τ = n + 1|X n+1 = x, τ > n] = 1
Thus the strong random time τ constructed above is always bounded above by the first hitting time of the complementary set of the support of m 0 .

There is a case which is of special interest. Let us come back to the notation of the introduction, so we replace P by P and S by S = S { }. But we now only make the first irreducibility assumption on P . Then there exists a unique distribution m 0 which is positive on S and satisfies

m 0 P = θ 0 m 0 + (1 -θ 0 )δ
where θ 0 ∈ (0, 1) is the largest eigenvalue of the restriction of P to functions vanishing on (these properties of θ 0 and m 0 are insured by the Perron-Frobenius theorem, reversibility is not needed). It is indeed the renormalized positive left eigenvector associated to the eigenvalue θ 0 of P and it is called the quasi-stationary distribution of P , because for any n ∈ N, the restriction of m 0 P n to S is just θ n 0 m 0 . Note that the function s introduced in the above proof is given by

∀ x ∈ S, s(x) = θ , if x = -∞ , if x ∈ S
so τ is in fact the hitting time of and we recover the well-known fact that it is distributed as a geometric law of parameter θ 0 (see for instance Section 6.5 of Chapter 3 of the book of Aldous and Fill [START_REF] Aldous | Reversible Markov chains and random walks on graphs[END_REF]).

To profit fully from Proposition 3, it is important that no assumption is made on the respective supports of m 0 and µ.

Local equilibria

We will prove Theorem 1 here, through the use of a sequence of local equilibria, going from the initial condition m 0 to the quasi-stationary measure in N -1 steps, before collapsing to δ . Again we consider the discrete time framework presented in the introduction. We begin by recalling a linear algebra result of Micchelli and Willoughby [START_REF] Micchelli | On functions which preserve the class of Stieltjes matrices[END_REF]:

Theorem 5 Let B be a symmetric S × S matrix whose entries are nonnegative and let b 0 ≤ b 1 ≤ • • • ≤ b N -1 be its eigenvalues. Then for any l from 0, N -1 , the matrix i∈ 0,l (B -b i ) has nonnegative entries.

The symmetry condition can be weakened to a reversibility condition, asking for the existence of a positive vector µ (µ(x)) x∈S such that

∀ x, y ∈ S, µ(x)B(x, y) = µ(y)B(y, x)
where we have written B = (B(x, y)) x,y∈S . Then let D denote the diagonal matrix with ( µ(x)) x∈S as diagonal and define B = DBD -1 . The latter matrix is symmetric and its entries are nonnegative, furthermore it has the same eigenvalues as B. Thus for any l ∈ 0, N -1 , the matrix

i∈ 0,l (B -b i ) = D -1 i∈ 0,l ( B -b i )D
has also nonnegative entries.

Unless otherwise stated, from now on we assume that all the eigenvalues of P are nonnegative. We can now define the local equilibria associated to the initial condition m 0 . First we consider for any l ∈ 0, N ,

µ l m 0 i∈ 0,l-1 P -θ N -1-i 1 -θ N -1-i
in particular µ 0 = m 0 and the Cayley-Hamilton theorem shows that µ N = 0. From Theorem 5, applied to the reversible matrix P , we get that all these row vectors are nonnegative and thus can be considered as nonnegative measures on S. We note that their total mass is non-increasing: for any i ∈ 0, N -1 , since P is subMarkovian, we have

P -θ N -1-i 1 -θ N -1-i 1 S ≤ 1 S
(where 1 S is the indicator function of S), so integrating this inequality with respect to µ i , we get

µ i+1 [S] ≤ µ i [S]. Next we define ∀ i ∈ 0, N -1 , d i 1 - µ i+1 [S] µ i [S] ∈ [0, 1] (in particular d i = 1 if µ i [S]
= 0, since then we also have µ i+1 [S] = 0) and

I min{i ∈ 0, N -1 : µ i+1 [S] = 0} = min{i ∈ 0, N -1 : d i = 1}
We will show later on that I = N -1, but for the moment, we introduce for any i ∈ 0, I , the probability measures

µ i   j∈ 0,i-1 (1 -d j ) -1   µ i
which are called local equilibria. Let also take the convention that µ i δ for i ∈ I + 1, N . Their interest comes from the following observation Lemma 6 For any i ∈ 0, N -1 , we have

µ i P = θ N -i-1 µ i + (1 -θ N -i-1 )((1 -d i )µ i+1 + d i δ )

Proof

By construction, we have for any i ∈ 0, N -1 ,

µ i (P -θ N -i-1 ) = (1 -θ N -i-1 ) µ i+1
which can be rewritten

µ i P = θ N -i-1 µ i + (1 -θ N -i-1 )(1 -d i )µ i+1
For i ∈ 0, I , µ i is a probability measure on S and so µ i P is the restriction to S of the probability measure µ i P on S. To get the formula of the lemma, we add the missing mass, which must be at . For i ∈ I + 1, N , this formula reduces to δ = δ .

The proof of Theorem 1 is now quite straightforward, since it is sufficient to successively apply Proposition 3 to the local equilibria, via Lemma 6. More precisely, starting from m 0 = µ 0 , we construct a strong random time τ N -1 through Proposition 3, with θ = θ N -1 and µ = (1 -d 0 )µ 1 + d 0 δ . We have that τ N -1 is distributed as a geometric law G(θ N -1 ) and according to Remark 4 c), with probability d 0 and independently from τ N -1 , τ N -1 coincides with T , the hitting time of , and with probability 1 -d 0 , X τ N -1 is distributed according to the second local equilibrium µ 1 .

Let us define the shifted chain X (1) ( X

n ) n∈N (X τ N -1 +n ) n∈N . (1)
Due to the fact that τ N -1 is a strong random time, X (1) is independent from τ N -1 and is a Markov chain whose transition matrix is P and with (1 -d 1 )µ 1 + d 1 δ as initial distribution. Let us consider X (1) which is just X (1) conditioned by X

(1) 0 = . It is a Markov chain admitting P as transition matrix and µ 1 as initial distribution. Apply Proposition 3, with m 0 = µ 1 , θ = θ N -2 and µ = (1 -d 1 )µ 2 + d 1 δ , to construct a strong random time τ N -2 for X (1) , which is distributed as G(θ N -2 ) and is independent of τ N -1 . The proof goes on by an obvious iteration and in the end (the procedure has to stop, because I ≤ N -1, due to the fact that µ N = 0), we get Theorem 1 with

∀ i ∈ 0, N -1 , a N -1-i d i j∈ 0,i-1 (1 -d j ) (5)
Indeed, one can define a random variable A with distribution a = (a 0 , a 1 , ..., a N -1 ) (see the discussion before Theorem 1) in the following way: let us denote X (1) , X (2) , ..., the shifted Markov chains constructed iteratively through the previous procedure, then take

A N -min{i ∈ 1, N : X (i) 0 = }
Then for any i ∈ 1, N , the event {A = i} is independent of τ N -1 , ..., τ N -i (which are also independent among themselves). This is sufficient to insure that T = j∈ N -A,N -1 τ j is distributed according to M G (a, θ).

The only point which remains to be proven is that a 0 > 0. This is a consequence of the well-known fact that for any initial distribution m 0 on S,

lim n→∞ 1 n ln(P[T > n]) = -ln(θ 0 ) (6)
(indeed, one can be brought back to the case where the initial distribution is the quasi-stationary probability measure by noticing that the quantities lim n→∞ 1 n ln(P x [T > n]) exist and do not depend on the starting point x ∈ S by the irreducibility assumption). But if J = min{j ∈ 0, N -1 : a j > 0}, and if T is distributed according to M G (a, θ), then we have that

∀ 0 ≤ u < 1 θ J , E[u T ] < +∞
so the fact that θ 0 > θ 1 shows that J = 0. Furthermore, since

a 0 = d N -1 j∈ 0,N -2 (1 -d j ) = j∈ 0,N -2 (1 -d j )
we also get that d j < 1 for all j ∈ 0, N -2 , so I = N -1. Thus µ N -1 is a probability measure on S, and since Lemma 6 shows that

µ N -1 P = θ 0 µ N -1 + (1 -θ 0 )δ
it follows that µ N -1 is the quasi-stationary probability measure associated to P (recall its definition given in Remark 4c).

Remark 7 Formula (5) simplifies if the definition of the d j , for j ∈ 0, N -1 , is inserted and the telescoping product is simplified:

∀ i ∈ 0, N -1 , a N -1-i = µ i (S) -µ i+1 (S) = m 0   j∈ 0,i-1 P -θ N -1-j 1 -θ N -1-j   1 -P 1 -θ N -1-i (S)
which is the formula (1) announced in the introduction. Thus the law of T can be explicitely given in terms of the initial distribution, the product P n , for n ∈ 1, N -1 , and the eigenvalues of P . At least for small state space, this is easy to implement. Note also that it can be used to recover that a 0 > 0 and to give an expression for this quantity. Let (ν i ) i∈ 0,N -1 be an orthogonal basis of left-eigenvectors (=measures) associated to the eigenvalues (θ i ) i∈ 0,N -1 of P in L 2 (π), where π is the reversible probability measure mentioned in the introduction. In particular ν 0 is proportional to the quasi-stationary distribution, let us call it ν.

Let us decompose m 0 , on this basis, m 0 i∈ 0,N -1 b i ν i . Then formula (1) for i = 0 is just

a 0 =   j∈ 1,N -1 θ 0 -θ j 1 -θ j   b 0 ν 0 (S) So a 0 > 0 is equivalent to b 0 > 0, but b 0 = m 0 , ν 0 L 2 (π)
> 0 because π and ν 0 are positive on S and m 0 is a probability measure on S. Indeed, in terms of the quasi-stationary distribution, we have

b 0 = x∈S m 0 (x)ν(x) π(x) x∈S ν 2 (x) π(x)
and

a 0 =   j∈ 1,N -1 θ 0 -θ j 1 -θ j   x∈S m 0 (x)ν(x) π(x) x∈S ν 2 (x) π(x)
This formula may be useful in applications where the evaluation of a 0 will be important.

Remark 8 It is the sequence of local equilibria (µ i ) i∈ 0,N -1 which has a meaning, not the notion of local equilibrium by itself. Indeed, we can go a little further: let say that a finite sequence of probabilities on S, (µ i ) i∈ M,N -1 , with M ∈ 0, N -1 , is an M -sequence of local equilibria going from µ M to δ , if the relations of Lemma 6 are satisfied for i ∈ M, N -1 , with a sequence (d i ) i∈ M,N -1 of numbers from [0, 1] and with µ N = δ . The above proof shows that if the initial distribution of X is µ M , then the law of T is a mixture of the distributions G(θ i , θ i+1 , ..., θ N -1-M ), for i ∈ 0, N -1 -M , which gives positive weight to G(θ 0 , θ 1 , ..., θ N -1-M ). This is even true under the weakened assumption that θ N -1-M ≥ 0, so the eigenvalues θ N -M , θ N -M +1 , ..., θ N -1 can be negative.

In particular if M = N -1, µ N -1 must be the quasi-stationary probability measure and we know by the Perron-Frobenius theorem that θ 0 is nonnegative. So we recover the fact that if the initial distribution of X is the quasi-stationary probability measure, then the distribution of T is a geometric law of parameter θ 0 . Note that the reversibility hypothesis can be dispensed with in this special case, since we don't need Theorem 5 to check that µ N = δ is nonnegative. It also appears that to write the law of T in the form M G (θ, a) may not be very clever and that it is better to introduce for M ∈ 0, N -1 , the distributions

M G (M, θ, a) 0≤i≤N -1-M a i G(θ i , θ i+1 , ..., θ N -1-M )
where a is a probability measure on 0, N -1 -M . Now the law of T may not be uniquely represented as M G (M, θ, a). Indeed, we may have

M G (M, θ, a) = M G (M , θ, a ) with M = M and a = a . For instance, taking into account the previous example, M G (N -1, θ, 1) = G(θ 0 ), for any M ∈ 0, N -2 , we can find a probability measure a M on 0, N -1 -M such that G(θ 0 ) = M G (M, θ, a M ).
To simplify the expression for the law of T , one has to try to find the largest M such that there exists an M -sequence of local equilibria going from m 0 to δ . Note also that for given M ∈ 0, N -1 and a nonnegative θ = (θ 0 , ..., θ N -1 ), the mapping a = (a 0 , ..., a N -1-M ) → M G (θ, a) is one to one. This can be proven by considering the corresponding moment generating functions (or rather its meromorphic extension to C).

Finally notice that from a complexity point of view, once the eigenvalues are known, (µ i ) i∈ 0,N -1 , (d i ) i∈ 0,N -1 and (a i ) i∈ 0,N -1 are not difficult to obtain via Lemma 6 and ( 5), indeed at most N iterations of P are necessary. To obtain the largest M such that the law of T can be represented in the form M G (M, θ, a), at most (N -1)N/2 steps are needed, since we have first to try with M = N -1, next M = N -2 etc. to verify if we can associate to m 0 an M -sequence of local equilibria through Lemma 6.

Intertwining

Our goal here is to construct an intertwining relation between X and a Markov chain of a special kind. This is indeed the main result of this paper, as it gives a probabilistic interpretation of Theorem 1.

More precisely, let P be an absorbing transition matrix on S, as in the introduction, and let θ 0 > θ 1 ≥ • • • ≥ θ N -1 ≥ 0 be its eigenvalues, assumed to be nonnegative. For a given initial distribution m 0 , consider the associated sequences of local equilibria (µ i ) i∈ 0,N -1 and of real numbers from [0, 1], (d i ) i∈ 0,N -1 , as in Lemma 6. Recall that for i ∈ 0, N -2 , d i < 1 and that

d N -1 = 1. Next introduce an absorbing Markov chain Y (Y n ) n∈N on Ē 0, N -1 { }
, starting from 0 and with transition matrix Q given by

∀ i, j ∈ Ē, Q(i, j)            θ N -1-i , if i = j ∈ 0, N -1 d i (1 -θ N -1-i ) , if i ∈ 0, N -1 and j = (1 -d i )(1 -θ N -1-i ) , if i ∈ 0, N -2 and j = i + 1 1 , if i = j = 0 , otherwise (7)
(for X as well as for Y , we denote the absorbing point, this should not lead to confusion). The behaviour of the Markov chain Y is easy to understand: it tries to go to the next neighbour on the right, or stay at the same place, except that it can also be killed (i.e. go to the absorbing point) and the respective probabilities for these actions are (1

-d i )(1-θ N -1-i ), θ N -1-i and d i (1-θ N -1-i ) when the current position is i ∈ 0, N -2 . This is also true if i = N -1 since d N -1 = 1,
so from there the Markov chain either stays at the same place, with probability θ 0 , or is killed, with probability 1 -θ 0 . But for i ∈ 0, N -2 , the probability to go to the right is positive. With this interpretation, for i ∈ 0, N -1 , d i can be called the chance of death immediately after moving from the i th local equilibrium. Let us furthermore denote by Λ the | Ē| × |S| matrix defined by

∀ i ∈ Ē, ∀ x ∈ S, Λ(i, x) µ i (x) , if i ∈ 0, N -1 δ (x) , if i = ( 8
)
Its interest comes from the following intertwining relation Lemma 9 For Q and Λ defined at [START_REF] Diaconis | Separation cut-offs for birth and death chains[END_REF] and ( 8), we have the intertwining relation

Λ P = QΛ

Proof

This is just a rewriting of Lemma 6: fix some i ∈ 0, N -1 and x ∈ S. On one hand we have

Λ P (i, x) = y∈S Λ(i, y) P (y, x) = µ i P (x)
and on the other hand,

QΛ(i, x) = θ N -1-i Λ(i, x) + (1 -d i )(1 -θ N -1-i )Λ(i + 1, x) + d i (1 -θ N -1-i )Λ( , x) = (θ N -i-1 µ i + (1 -θ N -i-1 )((1 -d i )µ i+1 + d i δ ))(x)
from where we get the equality Λ P (i, x) = QΛ(i, x). Consider finally the case where i = . Then the previous equality reads δ (x) = δ (x).

This intertwining relation and the fact that we have for the initial laws

L(Y 0 )Λ = m 0 = L(X 0 )
enables use of a result of Diaconis and Fill [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF] asserting we can intertwine X in Y in the following sense: there exists a coupling of X and Y such that the chain (X n , Y n ) n∈N is Markovian and such that for any time n ∈ N, we have for the conditional law of

X n knowing Y 0 , Y 1 , ..., Y n , L(X n |Y 0 , Y 1 , ..., Y n ) = Λ(Y n , •)
In some sense Y indicates which local equilibrium has been reached by X and in this respect, it is interesting to know that if a trajectory (X n ) n∈N is given, it is possible to construct (Y n ) n∈N from it in a progressive way, using also independent randomness (for more details, see Diaconis and Fill [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF]). Under the above coupling, let us denote

T X inf{n ∈ N : X n = } T Y inf{n ∈ N : Y n = }
It is clear that T X has the same law as T and that T Y is distributed according to M G (θ, a), with the probability measure a given by [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF]. So the next result gives another proof of Theorem 1:

Lemma 10 We have a.s. that T X = T Y .

Proof

Let n ∈ N be given, we have that

P[T X ≤ n, T Y ≤ n] = E[δ (X n )δ (Y n )] = E[E[δ (X n )|Y 0 , ..., Y n ]δ (Y n )] = E[Λ(Y n , )δ (Y n )] = Λ( , )E[δ (Y n )] = P[T Y ≤ n] so it follows that {T X ≤ n} is a.s. included in {T Y ≤ n}.
Since this is true for any n ∈ N, we get that T X ≤ T Y a.s. But for any n ∈ N, we compute in a similar way that

P[T X ≤ n, T Y > n] = E[Λ(Y n , )1 0,N -1 (Y n )] = 0
and as a consequence T X = T Y a.s.

Thus for any absorbing Markov chain satisfying the hypotheses of the introduction, the absorption time is distributed according to a law of the form M G (θ, a), with θ ∈ Θ and a ∈ A, where

Θ {θ = (θ i ) i∈ 0,N -1 ∈ [0, 1) N : θ 0 > θ 1 ≥ θ 2 ≥ • • • ≥ θ N -1 } A {a = (a i ) i∈ 0,N -1 ∈ P( 0, N -1 ) : a 0 > 0}
where from now on P(E) will denote the set of probability measures on E, for any finite set E.

Conversely, we can wonder if for an a priori given θ ∈ Θ and a ∈ A, one can find an absorbing Markov chain satisfying the assumptions of the introduction and such that the law of its absorption time is distributed according to M G (θ, a). Then the set of laws of such absorption times would exactly be M G {M G (θ, a) : θ ∈ Θ, a ∈ A}. We do not conjecture that this assertion is true, because we believe more restrictions should be put on the admissible pairs (θ, a), for instance maybe that for any i ∈ 1, N -1 , a i > 0 ⇒ a i-1 > 0. Nevertheless, the above chain Y can be used to get a result in this direction. Let K be the closure of the set of Markov transition matrices P on S whose unique recurrence class is { } and such that the restriction P of P to S × S is irreducible, reversible and admits nonnegative eigenvalues. Note that the elements of K are still transition matrices absorbing at . Here we are interested in K, the set of matrices P from K such that {∞} is the unique recurrence class of P . If m 0 ∈ P(S) and P ∈ K are given, we can associate to them a Markov chain, starting from m 0 with transition matrix P . Let us write L(m 0 , P ) for the law on N * of the corresponding absorption time. We also need to introduce

M G {M G (θ, a) : θ ∈ Θ, a ∈ P( 0, N -1 )} with Θ {θ = (θ i ) i∈ 0,N -1 ∈ [0, 1) N : θ 0 ≥ θ 1 ≥ θ 2 ≥ • • • ≥ θ N -1 } Proposition 11
The set of distributions L(m 0 , P ), when m 0 runs through P(S) and P runs through K, coincides with M G .

Proof

We begin with the inclusion {L(m 0 , P ) :

m 0 ∈ P(S), P ∈ K} ⊂ M G (9)
Let P ∈ K be given and ( P (r) ) r∈N be a sequence of transition matrices as in the introduction and converging to P . For any fixed r ∈ N, we consider 1 > θ

(r) 0 > θ (r) 1 ≥ • • • ≥ θ (r)
N -1 ≥ 0 the eigenvalues of the restriction P (r) of P (r) to S × S. Let us also fix an initial distribution m 0 ∈ P(S). Lemma 6 enables us to associate to m 0 and P (r) a sequence of local equilibria (µ (r) i ) i∈ 0,N -1 from P(S) and a sequence of real numbers from [0, 1), (d

(r) i ) i∈ 0,N -2 .
As in the beginning of this section, we construct from them two matrices Q(r) and Λ (r) so that

Λ (r) P (r) = Q(r) Λ (r) (10)
Up to the extraction of a subsequence, we can assume by standard compactness arguments, that there exist 1 ≥ θ 0 ≥ θ 1 ≥ • • • ≥ θ N -1 ≥ 0, a sequence (µ i ) i∈ 0,N -1 of probabilities from P(S) and a sequence of real numbers from [0, 1], (d i ) i∈ 0,N -2 such that

∀ i ∈ 0, N -1 , lim r→∞ θ (r) i = θ i ∀ i ∈ 0, N -1 , lim r→∞ µ (r) i = µ i ∀ i ∈ 0, N -2 , lim r→∞ d (r) i = d i
Thus if we construct Q and Λ from (θ i ) i∈ 0,N -1 , (d i ) i∈ 0,N -2 and (µ i ) i∈ 0,N -1 as above, we get, by passing to the limit in ( 10)

Λ P = QΛ
We note that the first line of Λ is m 0 (since this is also true for Λ (r) , for all r ∈ N), so using again a result of Diaconis and Fill [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF], we can intertwine, as above, a Markov chain X starting from m 0 and admitting P as transition matrix with a Markov chain Y starting from δ 0 and admitting Q as transition matrix. Lemma 10 is still valid and we deduce that L(m 0 , P ) is equally the distribution of the hitting time T Y of by Y . But the latter can now be a.s. infinite and one easily checks that it is a.s. finite if and only if θ 0 < 1. To deduce this property, we have to take into account that the only recurrence class of P is { }. Indeed, this latter assumption implies that 1 cannot be an eigenvalue of P , the restriction of P to S × S. But by a standard finite dimensional pertubation result (see for instance the book [START_REF] Kato | Perturbation theory for linear operators[END_REF] of Kato), we have that the eigenvalues of the matrices P (r) converge to the eigenvalues of P , so in particular θ 0 is the largest eigenvalue of P and thus θ 0 < 1. Now it is clear from the structure of Q that the distribution of T Y belongs to M G and this observation concludes the proof of [START_REF] Egleston | The nonnegative inverse eigenvalue problem[END_REF].

We now come to the reverse inclusion {L(m 0 , P) : m 0 ∈ P(S), P ∈ K} ⊃ M G [START_REF] Allen | The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof[END_REF] Let θ (θ i ) i∈ 0,N -1 ∈ Θ and a ∈ P( 0, N -1 ) be given. We have first to verify that we can find a sequence (d (r) i ) i∈ 0,N -2 of real numbers from [0, 1], such that

∀ i ∈ 0, N -1 , a N -1-i d i j∈ 0,i-1 (1 -d j )
Seeing a as a probability measure on 0, N -1 , let

I max{i ∈ 0, N -1 : a( 0, I -1 ) = 0}
so I = 0 is equivalent to a 0 > 0. Next we define

∀ i ∈ 0, N -2 , d i a N -1-i a( 0, N -1 -i ) , if i ≤ N -I -1 1 , otherwise (12)
and we immediately check that the above relation between a and (d i ) i∈ 0,N -2 is satisfied. Now we have at our disposition all the ingredients to construct the matrix Q given in [START_REF] Diaconis | Separation cut-offs for birth and death chains[END_REF]. Furthermore, it is quite obvious that L(δ 0 , Q) = M G (θ, a). So to end the proof of [START_REF] Allen | The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof[END_REF], it remains to check that Q ∈ K. First we remark that since 1

> θ 0 ≥ θ 1 ≥ • • • ≥ θ N -I-1 ≥ 0 and d N -I-1 = 1, the path (0, 1, 2, ..., N -I -1,
) is admissible for Q, as well as the one-step paths (i, ), for i ∈ N -I, N -1 , because 1 > θ i ≥ 0 and d i = 1. So { } is the unique recurrence class for Q. Next we define, for ∈ (0, 1/2), a new absorbing transition matrix Q by taking

∀ i, j ∈ Ē, Q (i, j)                            , if i ∈ 1, N -1 and j = i -1 , if i ∈ N -I -1, N -2 and j = i + 1 (1 -)θ N -1-i , if i = j ∈ 0, N -I -1 (1 -2 )θ N -1-i , if i = j ∈ N -I, N -1 (1 -)d i (1 -θ N -1-i ) , if i ∈ 0, N -I -1 and j = (1 -2 )(1 -θ N -1-i ) , if i ∈ N -I, N -1 and j = (1 -)(1 -d i )(1 -θ N -1-i ) , if i ∈ 0, N -I -2 and j = i + 1 1 , if i = j = 0 , otherwise
As usual, let Q be the restriction of Q to 0, N -1 2 . It is an irreducible subMarkovian matrix of birth and death type and thus Q is reversible. Let us denote by

1 > θ 0 ( ) > θ 1 ( ) > θ 2 ( ) > • • • > θ N -1 ( ) > -1
the eigenvalues of Q (they are well-known to be all distinct in the context of irreducible subMarkovian birth and death chains). It may happen that some of them are negative. This is for instance the case, as soon as N ≥ 1, if all the θ i , for i ∈ 0, N -1 , are zero and if a = δ N -1 , in which case Q = (δ 1 (|i -j|)) i,j∈ 0,N -1 (it has some negative eigenvalue, because it is symmetric, not null and its trace is zero). So let us rather consider

Q α( )Id + (1 -α( )) Q with α( ) max(0, -θ N -1 ( )) ∈ [0, 1). Since lim →0 + Q = Q, we also have lim →0 + θ N -1 ( ) = θ N -1
and by consequence lim →0 + α( ) = 0. Thus we get lim

→0 + Q = Q So finally Q ∈ K,
because all the transition matrices Q , for ∈ (0, 1/2), satisfy the assumption of the introduction.

Remarks 12

1) The end of the above proof shows that the matrix Q constructed from P in (7) belongs to K. Clearly, Q is not reversible, since moves to the left are not permitted on 1, N -1 . Also notice that since Q, the restriction of Q to 0, N -1 2 (respectively Q) is upper triangular, its eigenvalues are immediate to compute and are given by the entries of the diagonal of Q (resp. Q). But if some of these eigenvalues are equal, Q (resp. Q) is not necessary diagonalizable, e.g. this is the case for the following matrix

Q   θ 1 0 0 θ 1 0 0 1   for any θ ∈ [0, 1).
2) Let ( P (r) ) r∈N be a sequence from K converging to P ∈ K and (m (r) 0 ) r∈N be a sequence from P(S) converging to m 0 ∈ P(S). Then for large r, L(m (r) 0 , P (r) ) is weakly convergent to L(m 0 , P ), because this is equivalent to

∀ k ∈ N * , lim r→∞ L(m (r) 0 , P (r) )[k] = L(m 0 , P )[k]
and to get these limits, just write L(m (r) 0 , P (r) )[k] as a finite sum of products of k + 1 entries from m (r) 0 or P (r) . Assume that there exists m 0 ∈ P(S) such that L(m 0 , P ) = M G (θ, a) with a 0 > 0. Then by considering the moment generating functions of the L(m 0 , P (r) ), for r ∈ N, and of L(m 0 , P ), we can deduce the convergence for large r ∈ N of the eigenvalues of P (r) to the eigenvalues of P . This gives a probabilistic alternative to the reference to classical perturbation theory in the proof of Proposition 11.

3) Let K denote the set of P ∈ K which are weakly irreducible, in the sense that we cannot decompose S into a non trivial partition S = S 1 S 2 such that the restrictions of P to S 1 × S 2 and to S 2 × S 1 are null. We also introduce

M G {M G (θ, a) : θ ∈ Θ, a ∈ P( 0, N -1 ) with a 0 > 0} It seems possible that {L(m 0 , P ) : m 0 ∈ P(S), P ∈ K} = M G
In the same spirit, note that due to the example of Botta, Harris and Marchal [START_REF] Botta | Characterizations of generalized hyperexponential distribution functions[END_REF] alluded to in the introduction, Theorems 1 and 2 are no longer true when the reversibility condition is replaced by the assumption that all the eigenvalues of P are nonnegative. It follows that there are such subMarkovian matrices P that cannot be approached by reversible subMarkovian matrices (but maybe this is true for real-diagonalizable subMarkovian matrices). To understand better this phenomenon, maybe it would be interesting to investigate carefully the case of skip-free chains considered by Fill [START_REF] Allen | On hitting times and fastest strong stationary times for skip-free processes[END_REF].

Continuous time

We now return to the continuous-time framework presented in the introduction. We will not develop a specific continuous time approach, instead we extend the previous results by considering discrete time skeletons of the underlying semi-group.

More precisely, as already mentioned in the introduction, under the hypotheses made in the continuous-time setting, for any δ > 0, the absorbing transition matrix Pδ = exp(δ L) satisfies the previous discrete time assumptions: { } is the unique recurrent class of Pδ and its restriction P δ to S × S, which coincides with exp(δL), is irreducible and reversible with respect to the same positive probability measure π on S. Let X = (X t ) t≥0 be a Markov process with cadlag trajectories, starting from m 0 with generator L. Then X (δ) (X δn ) n∈N is a Markov chain starting from m 0 with transition matrix Pδ . Recall that we are interested in T , the absorption time of X, and let us denote

T (δ) inf{n ∈ N : X δn = }
the absorption time of X (δ) .

The key to Theorem 2 is the simple observation that Lemma 13 As δ goes to 0 + , δT (δ) converges a.s. to T , in particular in the weak sense,

lim δ→0 + L(δT (δ) ) = L(T )

Proof

Since the trajectories of X are cadlag, for any s ≥ 0, X T +s = , at least outside the negligible event where T = +∞, so

T ≤ δT (δ) ≤ T + δ Let θ (δ) = (θ (δ)
i ) i∈ 0,N -1 be the eigenvalues of P δ , with multiplicities and in nonincreasing order. Since θ (δ) i = exp(-δλ i ) for all i ∈ 0, N -1 , they are positive, so we can apply Theorem 1 to get a probability measure a (δ) on 0, N -1 such that

L(T (δ) ) = M G (θ (δ) , a (δ) ) ( 13
)
By compactness of P( 0, N -1 ), a probability measure a can be found on 0, N -1 and a decreasing sequence (δ (r) ) r∈N of positive real numbers converging to 0, such that lim r→∞ a (δr) = a.

In conjunction with the above lemma. The next result enables us to conclude the proof of Theorem 2, except for the assertion that a 0 > 0.

Lemma 14 In the sense of weak convergence,

lim r→∞ L(δ r T (δr) ) = M E (λ, a)

Proof

In view of [START_REF] He | Spectral polynomial algorithms for computing bi-diagonal representations for phase type distributions and matrix-exponential distributions[END_REF] and by definition of the laws M G (θ (δ) , a (δ) ) and M E (λ, a), it is sufficient to show that if for some fixed l > 0, R (δ) is distributed according to G(exp(-δl)), with δ > 0, then lim

δ→0 + L(δR (δ) ) = L(R)
where R is distributed according to an exponential distribution of parameter l. This convergence can be proven through the use of Laplace transforms, or from a more probabilistic point of view, by noticing that R (δ) has the same distribution as R/δ , which denote the smallest integer larger or equal to R/δ.

By resorting to Laplace transforms, one can see that the mapping

P( 0, N -1 ) a → M E (λ, a ) ∈ P(R + )
is one to one, so we get a posteriori that lim

δ→0 + a (δ) = a
To finish the proof of Theorem 2, we must show that a 0 > 0. Indeed, use similar arguments to those given in discrete time: it is well-known that for any initial distribution m 0 on S,

lim t→+∞ 1 t ln(P[T > t]) = -λ 0
(this can be easily deduced from the similar discrete time result ( 6) through finite skeletons). But if J = min{j ∈ 0, N -1 : a j > 0}, and if T is distributed according to M E (λ, a), then

∀ 0 ≤ l < λ J , E[exp(lT )] < +∞
so from the fact that λ 0 < λ 1 , we conclude that J = 0, i.e. a 0 > 0.

More structural results can be deduced by exhibiting an intertwining relation. Again start with skeleton subchains. For any δ > 0, associate to the initial law m 0 and to the absorbing transition matrix Pδ , a sequence (µ N -1 = 1, as in Lemma 6. By compactness of P(S) and of [0, 1], we can find a sequence (µ i ) i∈ 0,N -1 of probabilities on S, a sequence (d i ) i∈ 0,N -1 of real numbers from [0, 1] and a decreasing sequence (δ (r) ) r∈N of positive real numbers converging to 0, such that lim r→∞ (µ

(δr) i ) i∈ 0,N -1 = (µ i ) i∈ 0,N -1 lim r→∞ (d (δr) i ) i∈ 0,N -1 = (d i ) i∈ 0,N -1 (in particular d N -1 = 1). Next introduce an absorbing generator K on Ē 0, N -1 { } given by ∀ i, j ∈ Ē, K(i, j)            -λ N -1-i , if i = j ∈ 0, N -1 d i λ N -1-i , if i ∈ 0, N -1 and j = (1 -d i )λ N -1-i , if i ∈ 0, N -2 and j = i + 1 1 , if i = j = 0 , otherwise (14)
and a Markov kernel Λ from Ē to S given by

∀ i ∈ Ē, ∀ x ∈ S, Λ(i, x) µ i (x) , if i ∈ 0, N -1 δ (x) , if i =
Their interest comes from the following intertwining relation

Lemma 15

We have the intertwining relation

Λ L = KΛ

Proof

For δ > 0, let Q(δ) and Λ (δ) be the matrices associated to (θ

(δ) i ) i∈ 0,N -1 , (µ (δ) i ) i∈ 0,N -1 and (d (δ) i ) i∈ 0,N -1 as in the beginning of section 4. So Λ (δ) Pδ = Q(δ) Λ (δ)
and by consequence

Λ (δ) Pδ -Id δ = Q(δ) -Id δ Λ (δ)
Now by replacing δ by δ r and by letting r go to infinity, we get the needed relation.

Notice that the first row of Λ is m 0 , since this is also true for Λ (δ) , for any δ > 0. These facts lead us to consider a particular absorbing cadlag Markov process Y (Y t ) t≥0 on Ē, starting from 0 and whose generator is K. Indeed, Fill [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF] has shown that under the above intertwining relation and the equality L(Y 0 )Λ = L(X 0 ), X and Y can be intertwined: there exists a coupling of X and Y such that the process (X t , Y t ) t≥0 is Markovian, and such that for any time t ≥ 0, the conditional law of X t knowing (Y s ) 0≤s≤t is given by

L(X t |(Y s ) 0≤s≤t ) = Λ(Y t , •)
As in discrete time, heuristically Y indicates which probability measure among {µ i : i ∈ 0, N -1 } (whose elements can also be interpreted as local equilibria) has been reached by X, and in this respect, it is interesting to know that if a trajectory (X t ) t≥0 is given, it is possible to construct (Y t ) t≥0 from it in a progressive way, using also independent randomness (for more details, see Fill [START_REF] Allen | Strong stationary duality for continuous-time Markov chains[END_REF]).

Under the above coupling, let us denote

T X inf{t ≥ 0 : X t = } T Y inf{t ≥ 0 : Y t = }
It is clear that T X has the same law as T and that T Y is distributed according to M E (θ, a ), with the probability measure a given by

∀ i ∈ 0, N -1 , a N -1-i d i j∈ 0,i-1 (1 -d j )
The last assertion is a consequence of the traditional description of the evolution of a finite cadlag homogeneous Markov process using exponential times and the embedded Markov chain (which records the successive different positions taken by the process).

Next remark that the proof of Lemma 10 is also valid in continuous time, so under the above coupling T X = T Y a.s. In particular it follows that a = a and since we have already seen that a 0 > 0, it follows that

∀ i ∈ 0, N -2 , d i ∈ [0, 1)
We can deduce a posteriori that it was not necessary to take subsequences: first taking into account [START_REF] Allen | On hitting times and fastest strong stationary times for skip-free processes[END_REF] (with I = 0), we obtain

lim δ→0 + (d (δ) i ) i∈ 0,N -1 = (d i ) i∈ 0,N -1
Next Lemma 15 implies that

∀ i ∈ 0, N -1 , µ i L = -λ N -i-1 µ i + λ N -i-1 ((1 -d i )µ i+1 + d i δ ) (15)
which shows that the local equilibria can be iteratively determined by this relation and the fact that µ 0 = m 0 . So it follows that

lim δ→0 + (µ (δ) i ) i∈ 0,N -1 = (µ i ) i∈ 0,N -1
Finally, by similar arguments, it is also possible to extend Proposition 11. Let L be the closure of the set of generator matrices L on S whose unique recurrence class is { } and such that the restrictions L of L to S × S are irreducible and reversible. Next let L be the set of matrices L in L such that {∞} is the unique recurrence class of L. If m 0 ∈ P(S) and L ∈ L are given, associate to them a cadlag Markov process, starting from m 0 with generator L. Let us write L(m 0 , L) for the law on R + of the corresponding absorption time. Quite naturally, also introduce

M E {M E (λ, a) : θ ∈ Λ, a ∈ P( 0, N -1 )} with Λ {λ = (λ i ) i∈ 0,N -1 ∈ (R * + ) N : λ 0 ≤ λ 1 ≤ λ 2 ≤ • • • ≤ λ N -1 }
Then we have

Proposition 16

The set of distributions L(m 0 , L), when m 0 runs through P(S) and L runs through L, coincides with M E .

Negative eigenvalues

We return to the discrete time setting and investigate the peculiar features coming from the existence of negative eigenvalue(s). They will lead to an implicit description of the law of the absorption time involving simple probabilistic quantities and to an explicit formulation (but maybe less easy to manipulate) in terms of local equilibria and death proportions.

As in the introduction, P is a Markov transition matrix on S such that { } is the unique recurrence class and such that the restriction P of P to S × S is irreducible and reversible. So we can consider (θ i ) i∈ 0,N -1 the eigenvalues of P in nonincreasing order, a priori they belong to (-1, 1). We are also given m 0 an initial distribution on S and X a Markov chain starting from m 0 whose transitions are described by P . We are interested in the absorption time T X inf{n ∈ N : X n = }. To describe its distribution, introduce the number of negative eigenvalues

I inf{i ∈ 0, N -1 : θ N -1-i ≥ 0}
and we assume that I ≥ 1 (by Perron-Frobenius theory, we know that θ 0 ≥ 0, so I ≤ N -1), namely that we are no longer in the situation where all the eigenvalues are nonnegative. A first observation is that the beginning of the construction of the local equilibria is easier in this situation. Indeed, for any i ∈ 0, I -1 , ( P -θ N -1-i Id S )/(1 -θ N -1-i ) is a Markov transition matrix, as a convex combination of P and the S × S identity matrix Id S . So we don't need the result of Micchelli and Willoughby [START_REF] Micchelli | On functions which preserve the class of Stieltjes matrices[END_REF] to see that the family of measures ( m i ) i∈ 0,I defined by

∀ i ∈ 0, I , m i m 0 j∈ 0,i-1 P -θ N -1-j Id S 1 -θ N -1-j (16)
is in fact a family of probabilities on S. As before, we can decompose them into

∀ i ∈ 0, I , m i = m i (S)µ i + m i ( )δ
where µ i is a probability measure on S (in particular, µ 0 = m 0 ). Since is absorbing, the map 0, I i → m i (S) is nonincreasing, so we write

∀ i ∈ 0, I , m i (S) = j∈ 0,i-1 (1 -d j )
with (d i ) i∈ 0,I-1 a family of numbers from [0, 1]. In fact it is not possible that for some i ∈ 0, I -1 , d i = 1, otherwise we would have m 0 P i = δ and this would lead to a contradiction to the irreducibility of P . This implies that X can stay inside S for arbitrarily large times (but with an exponentially smaller and smaller probability as time is running on). The families (µ i ) i∈ 0,I of probabilities on S and (d i ) i∈ 0,I of numbers from [0, 1), are uniquely determined by µ 0 = m 0 and the iterative relations

∀ i ∈ 0, I , µ i P = θ N -1-i µ i + (1 -θ N -1-i )((1 -d i )µ i+1 + d i δ ) (17)
But since θ N -1-i < 0 for i ∈ 0, I -1 , Lemma 6 is of no help here. Another probabilistic interpretation is needed. The heuristic principle is that negative eigenvalues make the chain X run "too fast" and we have to slow it down. To do so, let (B i ) i∈ 0,I-1 be independent Bernoulli random variables of respective parameters (1/(1 -θ N -1-i )) i∈ 0,I-1 :

∀ i ∈ 0, I -1 , P[B i = 1] = 1 1 -θ N -1-i = 1 -P[B i = 0]
The family (B i ) i∈ 0,I-1 is assumed to be independent of X. Next, define the time change

∀ i ∈ N, S(i) j∈ 0,i-1 B j , if i ∈ 0, I S(I) + i -I , if i ≥ I + 1
which is independent of X and consider the chain Y (Y i ) i∈N given by

∀ i ∈ N, Y i X S(i)
It is in fact an inhomogeneous Markov chain with initial distribution m 0 and transition matrix at

time i ∈ N    P -θ N -1-i Id S 1 -θ N -1-i , if i ∈ 0, I -1 P , if i ≥ I Let T Y inf{n ∈ N : Y n = }
be the absorption time of Y (even if this chain is inhomogeneous). Its law is easy to describe, but we first need to extend the families (µ i ) i∈ 0,I and (d i ) i∈ 0,I into (µ i ) i∈ 0,N -1 and (d i ) i∈ 0,N -1 by using the iterative relations [START_REF] Keilson | Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes[END_REF] equally for i ∈ I +1, N -1 . For the same reason as above, for i ∈ I+1, N -2 , d i ∈ [0, 1), but to have that the µ i belong to P(S), for i ∈ I + 1, N -1 , we need to use the result of Micchelli and Willoughby [START_REF] Micchelli | On functions which preserve the class of Stieltjes matrices[END_REF] recalled in Theorem 5. Indeed, up to a normalizing factor, µ i is just m 0 j∈ 0,i-1 (P -θ N -1-j Id S )/(1 -θ N -1-j ). We also end up with d N -1 = 1 and by convention we take µ N = δ . Next consider θ + (θ + i ) i∈ 0,N -1 (where for any r ∈ R, r + = r ∨ 0) and let a (a i ) i∈ 0,N -1 be the probability measure defined from the death proportions (d i ) i∈ 0,N -1 as in [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF], in particular a 0 > 0. The next assertion can be seen as a generalization of Theorem 1.

Proposition 17

The law of T Y is M G (θ + , a). Now it is easy to deduce Proposition 17. Indeed, the proof of Lemma 10 is still valid and shows that L(T Y ) = L(T Z ). It is quite clear that T Z is distributed as M G (θ + , a). We remark that the families (µ i ) i∈ 0,N -1 and (d i ) i∈ 0,N -1 retain their interpretations as local equilibria and death proportions, but with respect to the speeded up Markov chain Y , not X.

But we are interested in T X , not in T Y . By construction of Y , it appears that T X = S(T Y ), nevertheless this relation does not seem easy to exploit in general, since S and T Y are not independent. Let S -1 be the generalized inverse of S:

∀ n ∈ N, S -1 (n) inf{k ∈ N : S(k) ≥ n}
Then it is immediate to see that we also have

T Y = S -1 (T X ) (19)
and since T X and S -1 are independent, this equality and Proposition 17 implicitely determine the law of T X :

Lemma 19 The law L(T X ) ∈ P(N * ) is uniquely determined by the fact that if T is distributed as L(T X ) and is independent of S, then S -1 (T ) has M G (θ + , a) as law.

Proof

It is sufficient to write that for any n ∈ N * , we have

M G (θ + , a)[n] = P[S -1 (T ) = n] = k∈ 1,n P[S -1 (k) = n, T = k] = k∈ 1,n P[S -1 (k) = n]P[T = k]
(notice that for any k ∈ N, S -1 (k) ≥ k), and since for any n ∈ N * , P[S -1 (n) = n] > 0 these identities enable to compute iteratively P[T = n] for any n ∈ N * .

We could deduce from the above proof an explicit formula for the law of T X , but there is a simpler way to deduce it.

Proposition 20 For any n ∈ N * ,

P[T X = n] = k∈ 1,n b n,k M G (θ + , a)[k] (20)
where for any k ∈ 1, n , b n,k j∈ 0,(k-1)∧(I-1)

(1 -θ N -1-j ) i 0 +•••+i (k-1)∧(I-1) =n-k θ i 0 N -1 θ i 1 N -2 • • • θ i (k-1)∧(I-1) N -1-(k-1)∧(I-1)
In particular (b n,k ) n∈N * ,k∈ 1,n only depends on the negative eigenvalues, while M G (θ + , a) is defined in terms of the nonnegative eigenvalues.

Proof

To simplify the notation, let us denote for any k ∈ N, θ k = θ N -1-k ∧ 0 (with the convention that θ k = 0 for all k ≥ N ). Next consider the polynomial in the z variable defined by

Q k (z) j∈ 0,k-1 z -θ j 1 -θ j
Then write for any n ∈ N,

z n = k∈ 0,n c n,k Q k (z) (21)
with for any k ∈ 0, n ,

c n,k j∈ 0,k-1 (1 -θ j ) i 0 +•••+i k =n-k θ i 0 0 θ i 1 1 • • • θ i k k (22)
(in particular c 0,0 = 1). To get these formulas, use the observations that for any n ∈ N and k ∈ 0, n ,

z n+1 = zz n and XQ k (z) = (1 -θ k )Q k+1 (z) + θ k Q k (z)
, which can be translated into the iterative relations

c n+1,0 = c n,0 θ 0 c n+1,k = c n,k-1 (1 -θ k-1 ) + c n,k θ k , for k ∈ 1, n c n+1,n+1 = c n,n (1 -θ n )
If the θ n , for n ∈ N, were nonnegative, we would recognize that c n,k = P[R n = k], where (R n ) n∈N is a Markov chain on N starting from 0 whose transitions are described by

∀ n ∈ N, P[R n+1 = R n + 1|R n ] = 1 -θ Rn = 1 -P[R n+1 = R n |R n ]
and [START_REF] Neuts | Matrix-geometric solutions in stochastic models[END_REF] would follow without difficulty. But conversely, one can directly check by an elementary combinatorial argument that the above iterative relations are satisfied if, for n ∈ N and k ∈ 0, n , we take c n,k as defined in [START_REF] Neuts | Matrix-geometric solutions in stochastic models[END_REF], without any assumption on the signs of the θ n , for n ∈ N.

Next we can translate (21) into information about absorption time: for any time n ∈ N * , we have

P[T X ≤ n] = P[X n = ] = m 0 P n 1 { } = m 0   k∈ 1,n c n,k Q k ( P )   1 { } = k∈ 1,n c n,k m 0 Q k ( P )1 { } = k∈ 1,n c n,k P[Y k = ] = k∈ 1,n c n,k P[T Y ≤ k]
So using that for any n ∈ N * , P[T = n] = P[T ≤ n] -P[T ≤ n -1], with T = T X or T = T Y , we obtain

P[T X = n] = k∈ 1,n b n,k P[T Y = k] with for any k ∈ 1, n , b n,k c n,n + j∈ k,n-1 c n,j -c n-1,j
To recover the formula given in the proposition, we notice that by the above iterative relations,

c n,j -c n-1,j = c n-1,j-1 (1 -θ j-1 ) -c n-1,j (1 -θ j ) so b n,k = c n,n -c n-1,n-1 (1 -θ n-1 ) + c n-1,k-1 (1 -θ k-1 ) = c n-1,k-1 (1 -θ k-1 )
We get the announced result, by taking into account that θ j = 0 for j ≥ I.

One can give a reduced formula for the (b n,k ) n∈N * ,k∈ 1,n appearing in the above proposition, at least if all the negative eigenvalues are distinct. For n ∈ N, let p n (x) x n be the n th monomial, then in terms of divided difference, we have for any k ∈ 0, n , and any real numbers (1 -θ N -1-j ) i∈ 0,(k∧I)-1

x 0 < x 1 < • • • < x k , i 0 +•••+i k =n x i 0 0 x i 1 1 • • • x i k k = p n+k [x 0 , x 1 , ..., x k ] (23)
θ n-k-1+k∧I N -1-i j∈ 0,(k∧I)-1 \{i} θ N -1-i -θ N -1-j
One has to be careful about the decomposition of the law of T X given in Proposition 20, since some of the terms of the sum can be negative. Indeed, b n,k is nonpositive if n -k is odd and nonnegative otherwise. Nevertheless, it seems that some partial sums are positive, see the third point in the remarks below.

Remarks 21

1) The probability measure a = (a i ) i∈ 0,N -1 which appears in Propositions 17 and 20 satisfies a i > 0 ⇒ a i-1 > 0, for any i ∈ N -I, N -1 . In fact, if a i > 0 then d N -1-i > 0, which means there exists an element x ∈ S in the support of m N -1-i such that P (x, ) > 0, but since m N -i is the transportation of m N -1-i through the Markov matrix ( P -θ i Id S )/(1 -θ i ) whose diagonal is positive, x also belongs to the support of m N -i , so d N -i > 0 and a i-1 > 0. We believe that this condition may be true in general for i ∈ 1, N -1 , that is why we alluded to it in the previous section. It would be a consequence of the property that the mapping associating to i ∈ 0, N -1 the support of µ i is nondecreasing.

2) Let Θ sM be the set of eigenvalues (θ i ) i∈ 0,N -1 in nonincreasing order of irreducible and reversible N × N subMarkovian matrices. It seems it is not easy to characterize Θ sM , since this is related to the famous nonnegative inverse eigenvalue problem, see for instance the overview given by Egleston, Lenker, Terry and Narayan [START_REF] Egleston | The nonnegative inverse eigenvalue problem[END_REF].

3) Suppose given a family θ = (θ i ) i∈ 0,N -1 ∈ Θ sM and a probability measure a = (a i ) i∈ 0,N -1 on 0, N -1 , satisfying that for any i ∈ 1, N -1 , a i > 0 ⇒ a i-1 > 0 (or equivalently if a is given by [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF], that for any i ∈ 0, N -2 , d i > 0 ⇒ d i+1 > 0). In a similar spirit to what we have done in the previous section and at least under the above restriction on a, it seems possible that we can find a Markov chain as in the present section, whose absorption time is distributed as in Proposition 17. We assume for the remainder of these remarks that such a Markov chain exists, denoted X (θ,a) . For simplicity, we also make the assumption that the death proportions (d i ) i∈ 0,N -1 associated to our original Markov chain X satisfy the condition ∀ i ∈ 0, N -2 , d i > 0 ⇒ d i+1 > 0. 4) Let J ≥ I be defined by

J inf{i ∈ 0, N -1 : θ N -1-i > 0}
and for any j ∈ 0, J , let us decompose the sum of Proposition 17 into

P[T X = n] = k∈ 1,n∧j b n,k M G (θ + , a)[k] + k∈ j+1,n b n,k M G (θ + , a)[k] (24)
Then the last sum is nonnegative and it can be written in the following form

k∈ j+1,n b n,k M G (θ + , a)[k] = M G (θ + , a)[ j + 1, ∞ ]P[T X (θ,ǎ) = n] (25)
where the probability measure ǎ is defined as a, but in terms of the modified death proportions ď ( ďi ) i∈ 0,N -1 given by

∀ i ∈ 0, N -1 , ďi 0 , if i ∈ 0, j -1 d i , otherwise
Let us also denote d = (d i ) i∈ 0,N -1 and write Z (d) for the chain Z constructed after Proposition 17, to indicate explicitely its dependence on the vector d. From the fact that j ∈ 0, J , it follows that

∀ k ∈ j + 1, ∞ , P[T Z (d) = k|T Z (d) ≥ j + 1] = P[T Z ( ď) = k]
and this can be rewritten in the form

∀ k ∈ j + 1, ∞ , P[T Z (d) = k] = P[T Z (d) ≥ j + 1]P[T Z ( ď) = k] = M G (θ + , a)[ j + 1, ∞ ]M G (θ + , ǎ)[k]
Furthermore we have for any k ∈ 0, j , M G (θ + , ǎ)[k] = 0, so if we apply Proposition 17 to the Markov chain X (θ,ǎ) , we get (25).

5) In the above considerations, let us take j = I. It is tempting to believe that the conditional law of T X knowing that T Y > I is the law of T X (θ,ǎ) , so we can identify the quantity in [START_REF] Art | Phase-type distributions: open problems and a few properties[END_REF] as P[T X = n, T Y > I] and it would follow that the first sum in the r.h.s. of (24) (with j = I) is equal to P[T X = n, T Y ≤ I]. But this is not true, since the latter sum can be negative. Indeed, assume that d I > 0 and let a be the probability measure on 0, N -1 defined as a, but in terms of the modified death proportions d ( d i ) i∈ 0,N -1 given by

∀ i ∈ 0, N -1 , d i    0 , if i ∈ 0, I -2 1/2 , if i = I -1 d i , otherwise
Then we get that M G (θ + , a)[k] = 0 for any k ∈ 1, I -1 and M G (θ + , a)[I] > 0, so that for n ≥ I, the sign of

k∈ 1,n∧I b n,k M G (θ + , a)[k] = b n,I M G (θ + , a)[I] is (-1) n-I .
There is one situation where the implicit formula ( 19) can be simplified. Put an unoriented graph structure on S by saying that x, y ∈ S are neighbours if P (x, y) > 0 or P (y, x) > 0. We denote by ρ the corresponding distance and assume that the support of m 0 is included in {x ∈ S : ρ(x, ) > I}.

Then we have that d i = 0 for all i ∈ 0, I -1 (this is equivalent to the above condition), so a.s. T Y > I and we can write

T Y = T X + I -S(I) (26)
Let ψ be the moment generating function of the law M G (θ + , a) and ϕ be the moment generating function of I -S(I) (which is a sum of N independent Bernoulli random variables of respective parameters (-θ N -1-i /(1 -θ N -1-i )) i∈ 0,I-1 ). Then the moment generating function of T X is given by

∀ u ∈ [0, 1], E[u T X ] = ψ(u) ϕ(u) (27)
We will encounter such a situation in next section. More generally, it is natural to try to decompose T X as a mixture by conditioning with respect to the σ-field generated by {T X > S(I)} = {T Y > I}. Indeed, conditioned by the event {T Y > I}, (Y I+n ) n∈N is a homogeneous Markov chain with initial distribution µ I and transition kernel is P . Thus according to the proof of Lemma 18, the law of T Y -I conditioned by {T Y > I} is the distribution of the absorption time for a Markov chain Z on I, N -1 { } starting from I and whose transitions are described by the restriction to ( I, N -1 { }) 2 of the matrix Q defined in [START_REF] Kent | Eigenvalue expansions for diffusion hitting times[END_REF]. So we have L(T X -S(I)|T X > S(I)) = M G ( θ, ǎ) where θ = (θ i ) i∈ 0,N -1-I and ǎ is the probability measure on 0, N -1 -I defined by

∀ i ∈ 0, N -1 -I , ǎN-1-I-i d I+i j∈ I,I+i-1 (1 -d j )
Unfortunately the conditional law L(T X |T X > S(I)) is not easy to deduce, because on {T X > S(I)}, T X and S(I) are no longer independent in general. Let us introduce the Markov kernel K from N * to 0, I describing the conditional law L(S(I)|T X -S(I)). Let us also consider ν the probability measure on 0, I which is the distribution of T X conditioned on {T X ≤ S(I)}. Then to sample according to L(T X ) one has to do the following: first to draw a Bernoulli variable B of parameter m I (S) = j∈ 0,I-1 (1 -d j ). If B = 1, one samples T according to M G ( θ, ǎ) and adds to T a variable distributed according to K(T, •). If B = 0, one samples according to ν. In particular, it appears that T X is stochastically dominated by I + T , where T is distributed according to the mixture

  1 - j∈ 0,I-1 (1 -d j )   δ 0 + j∈ 0,I-1 (1 -d j )M G ( θ, ǎ)
But a better bound can be obtained by noticing directly that T X is stochastically dominated by T Y . Both of these bounds are independent of the negative eigenvalues.

Examples

We present three illustrations of the previous results: finite birth and death chains which are absorbed at one end of their state space interval, the situation of constant probability/rate of absorption and the case N = 2 in continuous time. Their common point is that the death proportions can be easily computed (at least when the initial point is the non-absorbing end in the birth and death setting). We hope to consider in future studies more serious applications, where estimates of death proportions are more involved (even if from a complexity point of view, they only ask for the knowledge of (m 0 P n ( )) n∈ 1,N -1 , once the Dirichlet eigenvalues are known, see remark 7).

• We begin with the birth and death setting, which was the first motivation for this investigation (see [START_REF] Diaconis | On times to quasi-stationarity for birth and death processes[END_REF] and in particular the end of its introduction for historical background). We take S = 0, N -1 and write = N , where N ∈ N * . First consider the discrete time situation, where the absorbing transition matrix P satisfies ∀ i, j ∈ 0, N , P (i, j) > 0 ⇐⇒ |i -j| = 1 and i = N

Then its restriction P to 0, N -1 2 is irreducible and reversible, with respect to the measure π defined by

∀ i ∈ 0, N -1 , π(i) j∈ 0,i-1 P (j, j + 1) P (j + 1, j) (28)
As usual, let (θ i ) i∈ 0,N -1 be the eigenvalues of P , in decreasing order (here they are all of multiplicity 1). Then we recover the following well-known result:

Corollary 22 Assume that the eigenvalues are nonnegative, i.e. θ N -1 ≥ 0, and that the initial distribution m 0 is δ 0 . Then T X is distributed as a sum of independent geometric distributions of respective parameters the θ i , for i ∈ 0, N -1 .

Indeed, for any n ∈ 0, N -1 , the support of P n (0, •) is included in 0, n , so Lemma 6 shows that the death proportions d i , for i ∈ 0, N -2 , are null. In particular, we get that the probability measure a defined by ( 5) is just δ 0 . So Proposition 22 is an immediate consequence of Theorem 1.

The above arguments can also be applied when there are some negative eigenvalues (see equation ( 17)). Taking into account the discussion after Remarks 21, in particular (26) and (27), we get Corollary 23 Without any assumptions on the sign of the eigenvalues, the moment generating function of T X , when X is starting from 0, is given by

∀ u ∈ [0, 1], E[u T X ] = i∈ 0,N -1 (1 -θ i )u 1 -θ i u
This has the probabilistic interpretation that if we add to T X an independent sum of independent Bernoulli random variables of respective parameters (θ - i /1+θ - i ) i∈ 0,N -1 then we get a random variable distributed as a sum of independent geometric random variables of parameters (θ + i ) i∈ 0,N -1 .

Let us come back to the case of nonnegative eigenvalues. For more general initial distributions m 0 ∈ P( 0, N -1 ) than δ 0 , the law of T X is a "true" mixture of sum of geometric distributions (which can sometimes be simplified, for instance if m 0 is the quasi-stationary law, we get a geometric law of parameter θ 0 , see Remark 8). Indeed, if I 0 max{i ∈ 0, N -1 : m 0 (i) > 0}, then L(T X ) is a mixture of the distributions G(θ 0 , θ 1 , ..., θ N -1 ), G(θ 1 , θ 2 , ..., θ N -1 ), ..., G(θ I 0 , θ I 0 +1 , ..., θ N -1 ), with the notation of the introduction, since we must have d i = 0 for i ∈ 0, N -2 -I 0 . The situation becomes more involved if there exists some negative eigenvalues. But if we have

I 0 < N -1 -I,
where I is the number of negative eigenvalues, then according to (26), there exists a probability measure a = (a i ) i∈ 0,I 0 such that

∀ u ∈ [0, 1], E[u T X ] = i∈ 0,I 0 a i j∈ i,N -1
(1 -θ j )u 1 -θ j u

Let us now deal with the continuous time situation, which is simpler. Suppose L is a generator on 0, N satisfying ∀ i, j ∈ 0, N , L(i, j) > 0 ⇐⇒ |i -j| = 1 and i = N

As above, its restriction L to 0, N -1 2 is irreducible and reversible with respect to the measure π defined as in (28), with P replaced by L. We denote by (λ i ) i∈ 0,N -1 the eigenvalues of -L in increasing order. Then we have the equivalent of Proposition 22:

Corollary 24 Assume that the Markov process X starts from 0. Then T X is distributed as a sum of independent exponential distributions of respective parameters the λ i , for i ∈ 0, N -1 .

This is an immediate consequence of the recursive formula [START_REF] Karlin | Coincidence properties of birth and death processes[END_REF], which implies that the death proportions d i are null for i ∈ 0, N -2 . We also recover the local equilibria that were considered in [START_REF] Diaconis | On times to quasi-stationarity for birth and death processes[END_REF]:

∀ i ∈ 0, N -1 , µ i = δ 0 j∈ 0,i-1 L -λ N -1-i Id 0,N -1 λ N -1-i
even if they were not described so explicitely there. As above, for more general initial distribution m 0 ∈ P( 0, N -1 ), L(T X ) is a mixture of the sums of exponential distributions E(λ 0 , λ 1 , ..., λ N -1 ), E(λ 1 , λ 2 , ..., λ N -1 ), ..., E(λ I 0 , λ 2 , ..., λ N -1 ), where I 0 max{i ∈ 0, N -1 : m 0 (i) > 0}.

• We now come to the example of constant absorption probability. It is characterized by the existence of a ∈ (0, 1) such that ∀ x ∈ S, P (x, ) = 1 -a This is equivalent to the fact that P can be written under the form P = a P , where P is a Markov transition matrix on S. Under our usual assumption that P is irreducible and reversible, P is also irreducible and reversible. Let ( θ i ) i∈ 0,N -1 be its eigenvalues in nonincreasing order, which now belong to [-1, 1]. Thus ∀ i ∈ 0, N -1 , θ i = a θ i and since θ 0 = 1, we get a = θ 0 . In this situation, whatever the initial distribution m 0 ∈ P(S), the absorption time T X is distributed as the geometric law G(θ 0 ). This is an immediate consequence of the fact that at each time n ∈ N, if the chain has not yet been absorbed, then it has a chance 1 -θ 0 to be absorbed at next step, independent of the underlying position. Taking into account [START_REF] Keilson | Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes[END_REF] (for all i ∈ 0, N -1 ), it follows that we have for the death proportions

∀ i ∈ 0, N -1 , d i = 1 -θ 0 1 -θ N -1-i
Let a = (a i ) i∈ 0,N -1 be the weight given by (5):

∀ i ∈ 0, N -2 , a i = 1 -θ 0 1 -θ i j∈ 0,N -2-i θ 0 -θ N -1-j 1 -θ N -1-j (29)
If all the eigenvalues are assumed to be nonnegative, we get the identity G(θ 0 ) = i∈ 0,N -1 a i G(θ i , θ i+1 , ..., θ N -1 )

If there are some negative eigenvalues, we end up with a result even more surprising. Let Θ M be the set of eigenvalues (θ i ) i∈ 0,N -1 in nonincreasing order of irreducible and reversible N × N Markovian matrices. If (θ i ) i∈ 0,N -1 is an a priori given family of numbers with θ 0 ∈ (0, 1) and such that (θ i /θ 0 ) i∈ 0,N -1 belongs to Θ M and if in [START_REF] Kent | The appearance of a multivariate exponential distribution in sojourn times for birth-death and diffusion processes[END_REF] we put the weight a defined by (29), we obtain G(θ 0 )[n] = (1 -θ 0 )θ n-1 0 . Indeed, let P be an irreducible and reversible S × S Markovian matrix admitting (θ i /θ 0 ) i∈ 0,N -1 as eigenvalues. It is then sufficient to apply [START_REF] Kent | The appearance of a multivariate exponential distribution in sojourn times for birth-death and diffusion processes[END_REF] with the absorbing transition matrix P naturally constructed from its S × S-restriction P = θ 0 P . Again the continuous time equivalent is simpler. Let L be an absorbing generator satisfying our usual hypotheses and assume that there exists a constant a > 0 such that ∀ x ∈ S, L(x, ) = a Necessarily a = λ 0 and independently from the initial distribution m 0 ∈ P(S), the absorption time T X is distributed as an exponential distribution E(λ 0 ). Computing the death proportions via [START_REF] Karlin | Coincidence properties of birth and death processes[END_REF], we obtain the identity

E(λ 0 ) = 0≤i≤N
Let also be given a probability measure m 0 (e, f ) on S. Using the formula

m 0 L = -λ 1 m 0 + λ 1 ((1 -d 0 )µ 1 + d 0 δ )
where µ 1 is a probability measure on S, it follows that m 0 L( ) = eb + f d = λ 1 d 0 , i.e.

d 0 = eb + f d λ 1 (32)
With these quantities, the law of the absorption time of the corresponding Markov process is given by (1 -d 0 )E(λ 0 ) * E(λ 1 ) + d 0 E(λ 1 )

Conversely, we wonder if for any real numbers 0 < λ 0 < λ 1 and 0 ≤ d 0 < 1, we can find a, b, c, d, e, f as above such that (30), (31) and (32) are satisfied. This is indeed true and even if we only consider birth and death processes, namely satisfying the restriction b = 0.

a + (c) 1 2 (λ 0 + λ 1 -c -(c -λ 0 -λ 1 ) 2 -4λ 0 λ 1 )
As c goes from 0 to ( √ λ 1 -√ λ 0 ) 2 , a -(c) (respectively a + (c)) goes from λ 0 to √ λ 0 λ 1 (resp. from λ 1 to √ λ 0 λ 1 ). To end the proof, we note that the third equation of the above proposition permits to choice d 0 in the range [0, d/λ 1 ] = [0, λ 0 /a], so all values of d 0 in [0, 1) can be reached, since λ 0 /a -(c) converges to 1 -as c goes to 0 + . The fact that birth and death processes lead to the same set of laws of absorption times as in the general case (always under assumptions (B1) and (B2)) is specific to N = 2, because for N ≥ 3, we may have multiple eigenvalues in the general case, but not for birth and death processes. We wonder if for N ≥ 3, the set of laws of absorption times of birth and death processes is dense in the set of general absorption times.

i

  ) i∈ 0,N -1 of local equilibria on S and a sequence (d (δ) i ) i∈ 0,N -2 of real numbers from [0, 1), with the convention that d (δ)

  k \{i} x i -x j thus for any n ∈ N * and k ∈ 1, n , b n,k = j∈ 0,(k-1)∧(I-1)

- 1 a 1 λ j -λ 0 λ j •

 11j i E(λ i , λ i+1 , ..., λ N -1 ) with∀ i ∈ 0, N -2 , a i = λ 0 λ i j∈i+1,N -To finish, we investigate the case N = 2 in continuous time, to determine the set of laws of absorption time in this very simple situation. So we consider the state space S = {0, 1, } endowed with the generator matrix L 0, c > 0 and b ∨ d > 0, to insure the validity of assumption (B1). Note that (B2) is automatically satisfied here. The eigenvalues of L = -(a + b) b + c + d -(a + b + c + d) 2 -4(bd + cb + da)) b + c + d + (a + b + c + d) 2 -4(bd + cb + da))

Proposition 25 = f d λ 1 Proof

 251 Given 0 < λ 0 < λ 1 and 0 ≤ d 0 < 1 there exist a > 0, c > 0, d > 0 and f ∈[0, 1] c + d -(a + c + d) 2 -4da) c + d + (a + c + d) 2 -4da) d 0The two first equations of the proposition are equivalent toad = λ 0 λ 1 a + c + d = λ 0 + λ 1and this leads to the following second order equation in a:a 2 + (c -λ 0 -λ 1 )a + λ 0 λ 1 = 0 (33) Its discriminant (c -λ 0 -λ 1 ) 2 -4λ 0 λ 1 = (c -( λ 1 -λ 0 ) 2 )(c -( λ 1 + λ 0 ) 2 )must be nonnegative, so we must have c ∈ R * + \ ((√ λ 1 -√ λ 0 ) 2 , ( √ λ 1 + √ λ 0 ) 2 ).Requiring furthermore that equation (33) must have a positive solution implies that c ∈ (0, ( √ λ 1 -√ λ 0 ) 2 ] and for these values of c, we get two positive solutions (which is double for c= ( √ λ 1 -√ λ 0 ) 2 ), a -(c) 1 2 (λ 0 + λ 1 -c -(c -λ 0 -λ 1 ) 2 -4λ 0 λ 1 )

To prove this result, consider an intertwining between the inhomogeneous Y and a homogeneous Markov chain Z constructed as in the beginning of section 4, but with θ replaced by θ + . More precisely, Z takes values in Ē 0, N -1 { }, starts from 0 and its transition matrix Q is given by

Again we denote by Λ the Markov kernel from Ē to S defined in [START_REF] Ding | Total-variation cutoff in birth-and-death chains[END_REF].

Then we have

Lemma 18 There exists a Markovian coupling between Y and Z such that for any time n ∈ N, the conditional law of

, but since Y is not homogeneous, the intertwining cannot be reduced to an intertwining property between transition matrices. First construct (Y i , Z i ) i∈ 0,I in the following way: Begin by considering (Y ) i∈ 0,I as before. Next, define

Let us check the assertion of the above lemma for n ∈ 0, I . If Z n = , then by construction and from the fact that is absorbing, we know that Y n = , so the relation is satisfied. On the other hand, if Z n = , then we just know that Y n = . But [START_REF] Kato | Perturbation theory for linear operators[END_REF] indicates that for n ∈ 0, I , the law of Y n is m n and by construction µ n is the renormalization of the restriction of m n to S, thus we get the relation of the lemma. Next the construction of (Y i , Z i ) i∈ I+1,+∞ is more traditional. Indeed, let E I, N -1 { }, Q be the E × E-restriction of Q and Λ be the E × S-restriction of Λ. These matrices are Markov kernels and we check from the extension of (17) to i ∈ I, N -1 that we have Λ P = Q Λ (see the proof of Lemma 9). Since furthermore we have L(Z I ) Λ = L(Y I ) with L(Z I ) = m I (S)δ I + m I ( )δ ∈ P( E), the arguments of Diaconis and Fill [START_REF] Diaconis | Strong stationary times via a new form of duality[END_REF] enables us to construct a Markov chain

These facts lead us to define (Y i , Z i ) i∈ I+1,+∞ ( Y i , Z i ) i∈ I+1,+∞ , because we then easily deduce the properties announced in the above lemma. In particular, notice that for n ∈ I, +∞ , to condition Y n with respect to (Z 0 , Z 1 , ..., Z n ) is the same as to condition with respect to (Z I , Z I+1 , ..., Z n ) (since (Z 0 , Z 1 , ..., Z I ) is deterministic if Z n = ).

Aknowledgments:

The starting point of this paper comes from a question of Persi Diaconis (one among several ten of equally motivating problems!), asking for a probabilistic interpretation of eigenvalues of Markov kernels. I'm furthermore indepted to Persi Diaconis for all his reading suggestions and support and to Jim Fill who has send his recent preprints [START_REF] Allen | The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof[END_REF][START_REF] Allen | On hitting times and fastest strong stationary times for skip-free processes[END_REF] on the subject. I'm also grateful to the ANR's Chaire d'Excellence program for providing financial support and to the Laboratoire J. A. Dieudonné (UMR 6621) in Nice, where this work was done, for its hospitality. Finally I'm emdebted to the referee, to whom formula (1) is due, among other improvements of the paper.