1 Version: 2013/1/31 Hitting Time Distribution for Skip-Free Markov Chains: A Simple Proof Wenming Hong1 Ke Zhou2 3 1 0 Abstract 2 n a J A well-known theorem for an irreducible skip-free chain with absorbing 0 state d, under some conditions, is that the hitting (absorbing) time of 3 state d starting from state 0 is distributed as the sum of d independent geometric (or exponential) random variables. The purposeof this paper ] R is to present a direct and simple proof of the theorem in the cases of P both discrete and continuous time skip-free Markov chains. Our proof . h is to calculate directly the generation functions (or Laplace transforms) t a of hitting times in terms of the iteration method. m [ Keywords: skip-free, random walk, birth and death chain, absorbing 1 time, hitting time, eigenvalues, recurrence equation. v Mathematics Subject Classification (2010): 60E10, 60J10, 60J27, 0 60J35. 8 1 7 1 Introduction . 1 0 The skip-free Markov chain on Z+ is a process for which upward jumps may be only of unit 3 size, and there is no restriction on downward jumps. If a chain start at 0, and we suppose d is 1 : an absorbing state. An interesting property for the chain is that the hitting time of state d is v distributed as a sum of d independent geometric (or exponential) random variables. i X There are many authors give out different proofs to the results. For the birth and death r a chain, the well-known results can be traced back to Karlin and McGregor [7], Keilson [8], [9]. Kent and Longford [10] proved the result for the discrete time version (nearest random walk) although they have not specified the result as usual form (section 2, [10]). Fill [4] gave the first stochastic proof to both nearest random walk and birth and death chain cases via duality which was established in [2]. Diaconis and Miclo [3] presented another probabilistic proof for birth and death chain. Very recently, Gong, Mao and Zhang [6] gave a similar result in the case that the state space is Z+, they use the well established result to determine all the eigenvalues or the spectrum of the generator. 1School of Mathematical Sciences & Laboratory of Mathematics and Complex Systems, Beijing Normal Uni- versity,Beijing 100875, P.R.China. Email: [email protected] 2 School of Mathematical Sciences & Laboratory of Mathematics and Complex Systems, Beijing Normal University,Beijing 100875, P.R. China. Email:[email protected] 2 For the skip-free chain, Brown and Shao [1] first proved the result in continuous time situa- tion. By using the duality, Fill [5] gave a stochastic proof to both discrete and continuous time cases. The purpose of this paper is to present a direct and simple proof of the theorem in the cases of both discrete and continuous time skip-free Markov chains. Our proof is to calculate di- rectly the generation functions (or Laplace transforms) of hitting times in terms of the iteration method. Theorem 1.1. For the discrete-time skip-free random walk: Consider an irreducible skip-free random walk with transition probability P on {0,1,··· ,d} started at 0, suppose d is an absorbing state. Then the hitting time of state d has the gen- eration function d−1 (1−λ )s i ϕ (s) = , d (cid:20) 1−λ s (cid:21) Yi=0 i where λ0,··· ,λd−1 are the d non-unit eigenvalues of P. In particular, if all of the eigenvalues are real and nonnegative, then the hitting time is dis- tributed as the sum of d independent geometric random variables with parameters 1−λ . i Theorem 1.2. For the skip-free birth and death chain: Consider an irreducible skip-free birth and death chain with generator Q on {0,1,··· ,d} started at 0, suppose d is an absorbing state. Then the hitting time of state d has the Laplace transform d−1 λ i ϕ (s)= , d 1−λ s Yi=0 i where λ are the d non-zero eigenvalues of −Q. i In particular, if all of the eigenvalues are real and nonnegative, then the hitting time is distributed as the sum of d independent exponential random variables with parameters λ . i 2 Proof of Theorem 1.1 Define the transition probability matrix P as r p 0 0  q1,0 r1 p1  P =  ... ... ... ... ...  ,    qd−1,0 qd−1,1 qd−1,2 ··· rd−1 pd−1     1   (d+1)×(d+1) and for 0 ≤ n≤ d−1, P denote the first n+1 rows and first n+1 lines of P. n Let τ be the hitting time of state i+j starting from i. By the Markov property, we have i,i+j τi,i+j = τi,i+1+τi+1,i+2+···+τi+j−1,i+j. (2.1) If f (s) is the generation function of τ , i,i+1 i,i+1 f (s) =Esτi,i+1 for 0≤ i ≤ d−1, i,i+1 3 (2.1) says that fi,i+j(s)= fi,i+1(s)·fi+1,i+2(s)·····fi+j−1,i+j(s), for 1≤ j ≤ d−i. Let g (s) = 1, g (s) = pipi+1···pi+j−1sj, for 1 ≤ j ≤ d−i. 0,0 i,i+j f (s) i,i+j Lemma 2.1. Define I as a (n+1)×(n+1) identity matrix. We have n g (s) = det(I −sP ), for 0 ≤ n ≤ d−1. (2.2) 0,n+1 n n Proof. We will give a key recurrence to proof this lemma. By decomposing the first step ,the generation function of τ satisfy n,n+1 fn,n+1(s)= rnsfn,n+1(s)+pns+qn,n−1sfn−1,n+1(s)+qn,n−2sfn−2,n+1(s)+ (2.3) ···+q sf (s). n,0 0,n+1 Recall the definition of g (s), substitute it into the formula above, we have i,i+j g0,n+1(s)= (1−rns)g0,n(s)−qn,n−1s2pn−1g0,n−1(s)−qn,n−2s3pn−2pn−1g0,n−2(s)− (2.4) ···−qn,0sn+1p0p1···pn−1g0,0(s). Usethenotation A todenotethealgebraic complement oftheposition(i+1,j+1) inI −sP . i,j n n By expanding the bottom row of the matrix, we obtain det(In−sPn) = (1−rns)An,n−qn,n−1sAn,n−1−qn,n−2sAn,n−2−···−qn,0sAn,0. (2.5) By some calculation, we can deduce An,n = det(In−1−sPn−1), An,0 = p0p1···pn−1sn, and for 1 ≤ i< n, An,n−i = pn−ipn−i+1···pn−1sidet(In−i−1−sPn−i−1). Now we prove the lemma by induction. At first, g (s)= det(I −sP )= 1−r s. If (2.2) holds 0,1 0 0 0 for n < k, we calculate g (s). By (2.4), 0,k+1 g0,k+1(s) = (1−rks)det(Ik−1−sPk−1)−qk,k−1s2pk−1det(Ik−2−sPk−2)− qk,k−2s3pk−2pk−1det(Ik−3−sPk−3)−···−qk,0sk+1p0p1···pk−1. Formula (2.5) tell us that g (s) = det(I −sP ). The proof is complete. (cid:3) 0,k+1 k k Proof of Theorem 1.1 Denote ϕ (s) the generation function of τ , then ϕ (s) = f (s). By d 0,d d 0,d (2.1) and (2.2) , we have ϕd(s) = f0,1(s)f1,2(s)···fd−1,d(s) = p0p1···pd−1sd = p0p1···pd−1sd . g0,d(s) det(Id−1−sPd−1) 4 It is easy to prove that 1 is the unique unit eigenvalue of P, and for i= 0,2···d−1, λ are the i d non-unit eigenvalues. So det(Id−1−sPd−1) = (1−λ0s)(1−λ1s)···(1−λd−1s). By Lemma 2.1 and the definition of g (s), 0,d p0p1···pd−1 = s−df0,d(s)det(Id−1−sPd−1) = s−df0,d(s)(1−λ0s)(1−λ1s)···(1−λd−1s). Let s = 1, because f is a generation function, f (1) = 1. Then 0,d 0,d p0p1···pd−1 = (1−λ0)(1−λ1)···(1−λd−1). As a consequence we have ϕ (s) = (1−λ0)(1−λ1)···(1−λd−1)sd d (1−λ0s)(1−λ1s)···(1−λd−1s) d−1 (1−λ )s i = . (cid:20) 1−λ s (cid:21) Yi=0 i (cid:3) 3 Proof of Theorem 1.2 Denote the generator Q of the skip-free Markov chain as −γ α 0 0  β1,0 −γ1 α1  Q =  ... ... ... ... ...  ,    βd−1,0 βd−1,1 βd−1,2 ··· −γd−1 αd−1     0   (d+1)×(d+1) and for 0 ≤ n ≤d−1, Q denote the sub-matrix of the first n+1 rows and firstn+1 lines of Q. n τ be the hitting time of state i+j starting from i. The idea of proof is similar as Theorem i,i+j 1.1. We just give a briefly description here. It is well known that the skip-free chain on the finite state has an simple structure. The processstartati,itstaytherewithanExponential(γ )time,thenjumpstoi+1withprobability i αi, to i−k with probability βi,i−k (1 ≤ k ≤ i). Let f (s) be the Laplace transform of τ , γi γi i,i+j i,i+j f (s) = Ee−esτi,i+j. i,i+j Recall that if a random variable ξ ∼ Eexponential (θ), θ Ee−sξ = . θ+s 5 By decomposing the trajectory at the first jump, γn αn γn βn,n−1 γn βn,n−2 fn,n+1(s)= + fn−1,n+1(s)+ fn−2,n+1(s)+ γ +s γ γ +s γ γ +s γ n n n n n n e γ β e e n n,0 ···+ f (s) 0,n+1 γ +s γ n n αn βn,n−1 e βn,n−2 βn,0 = + fn−1,n+1(s)+ fn−2,n+1(s)+···+ f0,n+1(s). γ +s γ +s γ +s γ +s n n n n e e e Define αiαi+1···αi+j−1 g (s) = 1, g (s)= , for 1 ≤ j ≤ d−i. 0,0 i,i+j f (s) i,i+j e e The following lemma can be proved by useethe method similar as Lemma 2.1, we omit the details. Lemma 3.1. g (s) = det(sI −Q ), for 0 ≤ n ≤ d−1. 0,n+1 n n Then we can calculaete the Laplace transform of τ0,d, recall that λ0,...,λd−1 are the d non- zero eigenvalues of −Q, we can see they are not equal to 0 easily. And we have α0α1···αd−1 = λ0λ1···λd−1. So ϕd(s) = f0,1(s)f1,2(s)···fd−1,d(s) d−1 e α0α1e···αd−1 e λi = = det(sId−1−Qd−1) Yi=0 1−λis complete the proof. (cid:3) References [1] Brown, M. and Shao, Y. S. Identifying coefficients in the spectral representation for first passage time distributions. Probab. Eng. Inform. Sci. 1 (1987), 69–74. [2] Diaconis, P. and Fill, J.A. Strongstationary times via a new form of duality. Ann. Probab. 18 (1990), 1483–1522. [3] Diaconis, P. and Miclo, L. On times to quasi-stationarity for birth and death processes. J. Theoret. Probab. 22 (2009), 558–586. [4] Fill, J. A. The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof. J. Theoret. Probab. 22 (2009), 543–557. [5] Fill, J. A. On hitting times and fastest strong stationary times for skip-free and more general chains. J. Theoret. Probab. 22 (2009), 587–600. 6 [6] Gong, Y. Mao, Y. H and Zhang, C. Hitting time distributions for denumerable birth and death processes. J. Theoret. Probab. 25 (2012), 950–980. [7] Karlin, S. and McGregor, J. Coincidence properties of birth and death processes. Pacific J. Math. 9 (1959), 1109–1140. [8] Keilson, J. Log-concavity and log-convexity in passage time densities for of diffusion and birth-death processes. J. Appl. Probab. 8 (1971), 391–398. [9] Keilson, J. Markov Chain Models—Rarity and Exponentiality. Springer, New York, 1979. [10] Kent, J. T. and Longford, N. T An eigenvalue decomposition for first hitting times in random walk. Z. Wahrscheinlichkeitstheorie verw. Gebiete 63 (1983), 71–84.