Exponential Holding Times at a State

From an Exit Rate to a Holding-Time Distribution

A generator records how quickly a continuous-time Markov chain leaves each state. At state $i$, the total exit rate is $q_i=-q_{ii}$. That single number determines the distribution of the time until the chain first leaves $i$: when $q_i>0$, the holding time is exponential with rate $q_i$. This gives direct formulas for the probability of remaining in the state, the expected time there, and any fixed quantile of the holding time.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_t)_{t\ge0}$ be a time-homogeneous continuous-time Markov chain with right-continuous paths and countable state space $S$, and let $(\mathcal{F}_t)_{t\ge0}$ be its natural filtration, $\mathcal{F}_t=\sigma(X_s:0\le s\le t)$. Its generator is $Q=(q_{ij})$, with $q_{ij}\ge0$ for $j\ne i$, finite exit rate $q_i=\sum_{j\ne i}q_{ij}=-q_{ii}$, and rows summing to zero. For a chain started at $i$, write $\mathbb{P}_i$ and $\mathbb{E}_i$.

Definition: The first holding time at $i$ is $H_i=\inf\{t>0:X_t\ne i\}$, with $\inf\varnothing=\infty$. Its survival function is $S_i(t)=\mathbb{P}_i(H_i>t)$, for $t\ge0$. The exit-rate interpretation of the generator gives $S_i(h)=1-q_i h+o(h)$ as $h\downarrow0$: over a short interval of length $h$, the probability of a first departure is $q_i h+o(h)$.

The short-time statement concerns the first departure. The Markov property then makes the survival function multiplicative: if the chain has stayed at $i$ up to time $s$, its future, conditional on $\mathcal{F}_s$, has the law of a chain freshly started at $i$. This is the step that turns a local rate into a full distribution.

Theorem (Exponential holding time): Suppose the chain starts at $i$, has the time-homogeneous Markov property, and has a finite constant exit rate $q_i$. If $q_i>0$, then $H_i$ has the exponential distribution with rate $q_i$: $$ \mathbb{P}_i(H_i>t)=e^{-q_i t}\quad(t\ge0),\qquad \mathbb{P}_i(H_i\le t)=1-e^{-q_i t}\quad(t\ge0). $$ If $q_i=0$, then $\mathbb{P}_i(H_i=\infty)=1$.

Proof. For $s,t\ge0$, on $\{H_i>s\}$ the chain is at $i$ at time $s$. The Markov property therefore gives $$ S_i(s+t)=S_i(s)S_i(t). $$ Indeed, the event of staying at $i$ through time $s+t$ requires both staying through time $s$ and, conditional on that history, staying there for a further $t$. By the exit-rate expansion, $S_i(u)=1-q_i u+o(u)$ as $u\downarrow0$. For fixed $t>0$, apply multiplicativity $n$ times: $$ S_i(t)=\bigl(S_i(t/n)\bigr)^n =\left(1-\frac{q_i t}{n}+o(1/n)\right)^n. $$ Taking $n\to\infty$ gives $S_i(t)=e^{-q_i t}$, using the defining exponential limit. This also holds at $t=0$, since $S_i(0)=1$. If $q_i=0$, the same limit is $1$, so $S_i(t)=1$ for every finite $t$; hence $H_i=\infty$ almost surely. If $q_i>0$, the survival function tends to zero as $t\to\infty$, so $H_i$ is finite almost surely, and its distribution function is $1-S_i(t)=1-e^{-q_i t}$. $\square$

Means, Quantiles, and Residual Holding Times

When $q_i>0$, the exponential formula gives several useful summaries. For $0<p<1$, define the $p$-quantile as $t_p=\inf\{t\ge0:\mathbb{P}_i(H_i\le t)\ge p\}$. The mean follows by integrating the survival function; the quantile follows by solving the distribution-function equation.

Consequence: For $q_i>0$ and $0<p<1$, $$ \mathbb{E}_i[H_i]=\frac{1}{q_i},\qquad t_p=\frac{-\ln(1-p)}{q_i},\qquad \mathbb{P}_i(H_i>a)=e^{-q_i a}\quad(a\ge0). $$

To justify the mean formula, write $H_i=\int_0^\infty \mathbf{1}_{\{H_i>t\}}\,dt$. Since the integrand is nonnegative, integration and expectation can be interchanged, giving $\mathbb{E}_i[H_i]=\int_0^\infty\mathbb{P}_i(H_i>t)\,dt=\int_0^\infty e^{-q_i t}\,dt=1/q_i$. For the quantile, the distribution function is continuous and strictly increasing on $t\ge0$, so the infimum in the definition is the unique solution of $1-e^{-q_i t_p}=p$. Rearranging gives $e^{-q_i t_p}=1-p$ and $t_p=-\ln(1-p)/q_i$.

The same survival formula also yields the memoryless property. For $s,t\ge0$, the conditioning event $\{H_i>s\}$ has positive probability when $q_i>0$, and $$ \mathbb{P}_i(H_i>s+t\mid H_i>s) =\frac{e^{-q_i(s+t)}}{e^{-q_i s}} =e^{-q_i t}. $$ Thus, given that no departure has occurred by time $s$, the remaining time has the same distribution as the original holding time. This statement concerns the time to the first departure, not the time to a particular destination.

Worked Example: Survival, Mean, and Quantiles

Suppose a chain starts in state $A$, whose exit rate is $q_A=\tfrac32$ per hour. Find the probability of staying in $A$ for more than $\tfrac23$ hour, the mean holding time, the median, and the 90th percentile.

The exponential holding-time result applies because the exit rate is constant in time while the chain remains at $A$, and it is positive. Substituting $q_A=\tfrac32$ and $t=\tfrac23$ into the survival formula gives $$ \mathbb{P}_A(H_A>\tfrac23)=e^{-(3/2)(2/3)}=e^{-1}. $$ The mean is $$ \mathbb{E}_A[H_A]=\frac{1}{3/2}=\frac23\text{ hour}. $$ For the median, use $p=\tfrac12$: $$ t_{1/2}=\frac{-\ln(1-1/2)}{3/2} =\frac{\ln 2}{3/2} =\frac{2\ln 2}{3}\text{ hour}. $$ For the 90th percentile, use $p=\tfrac9{10}$: $$ t_{9/10}=\frac{-\ln(1-9/10)}{3/2} =\frac{\ln 10}{3/2} =\frac{2\ln 10}{3}\text{ hours}. $$

Check: At the median, the survival probability is $e^{-(3/2)(2\ln 2/3)}=e^{-\ln 2}=\tfrac12$, so the probability of having left by then is $\tfrac12$. At the 90th percentile, survival is $e^{-(3/2)(2\ln 10/3)}=e^{-\ln 10}=\tfrac1{10}$, so the probability of having left is $\tfrac9{10}$.

Worked Example: Reading a Rate Table

Consider a chain on $S=\{A,B,C\}$ with generator $$ Q=\begin{bmatrix} -3&1&2\\ \tfrac12&-\tfrac52&2\\ 0&0&0 \end{bmatrix}. $$ Check the generator row sums and find the holding-time survival probability and mean at $B$, together with its 75th percentile.

The row sums are $-3+1+2=0$, $\tfrac12-\tfrac52+2=0$, and $0+0+0=0$, so the rows satisfy the required zero-sum condition. At $B$, the diagonal entry is $q_{BB}=-\tfrac52$, hence $q_B=-q_{BB}=\tfrac52$. The holding-time survival probability at time $t\ge0$ is therefore $e^{-(5/2)t}$, and the mean is $$ \mathbb{E}_B[H_B]=\frac{1}{5/2}=\frac25. $$ For $p=\tfrac34$, the quantile is $$ t_{3/4}=\frac{-\ln(1-3/4)}{5/2} =\frac{\ln 4}{5/2} =\frac{2\ln 4}{5}. $$

Check: At this quantile, the survival probability is $e^{-(5/2)(2\ln 4/5)}=e^{-\ln 4}=\tfrac14$. Thus the probability of leaving $B$ by that time is $1-\tfrac14=\tfrac34$, as required.

Worked Example: A State with Zero Exit Rate

Consider the generator on $S=\{A,B\}$ $$ Q=\begin{bmatrix} 0&0\\ 2&-2 \end{bmatrix}. $$ Check its row sums and find the holding-time behavior when the chain starts at $A$.

The row sums are $0+0=0$ and $2-2=0$. At $A$, $q_A=-q_{AA}=0$. The zero-rate case of the theorem gives $\mathbb{P}_A(H_A>t)=1$ for every finite $t$, and so $\mathbb{P}_A(H_A=\infty)=1$. Its mean holding time is infinite. For every $0<p<1$, the $p$-quantile is also infinite: the distribution function is zero at every finite $t$, so no finite $t$ has distribution function at least $p$.

Check: The probability of a finite holding time is $\mathbb{P}_A(H_A<\infty)=1-\mathbb{P}_A(H_A=\infty)=0$, consistent with the survival probability remaining $1$ at every finite time. The formulas $1/q_A$ and $-\ln(1-p)/q_A$ are not used here because they require $q_A>0$.

A Common Pitfall: Being at a State Is Not the Same as Staying There

The transition probability $p_{ii}(t)=\mathbb{P}_i(X_t=i)$ is generally not the survival probability $\mathbb{P}_i(H_i>t)$. The first quantity allows the chain to leave $i$ and return before time $t$; the second requires that it has not departed at all. Confusing them can produce an incorrect holding-time calculation.

For a concrete calculation, take $S=\{1,2\}$ and $$ Q=\begin{bmatrix}-1&1\\1&-1\end{bmatrix}. $$ The row sums are $-1+1=0$ and $1-1=0$. The matrix has eigenvalues $0$ and $-2$, so its transition matrix at time $t$ is $$ P(t)=e^{tQ} =\frac12\begin{bmatrix} 1+e^{-2t}&1-e^{-2t}\\ 1-e^{-2t}&1+e^{-2t} \end{bmatrix}. $$ Starting at state $1$, the first holding time has rate $q_1=1$, hence $\mathbb{P}_1(H_1>1)=e^{-1}$. But the probability of being at $1$ at time $1$ is $p_{11}(1)=\tfrac12(1+e^{-2})$, which is larger. In fact, $$ p_{11}(1)-\mathbb{P}_1(H_1>1) =\frac{1+e^{-2}}2-e^{-1} =\frac{(1-e^{-1})^2}{2}>0. $$ The positive difference accounts for paths that have left state $1$ and returned by time $1$. Use the exit rate to calculate the first holding time; use the transition semigroup for the probability of occupying a state at a specified later time.

Check Your Understanding

For each question, identify whether it concerns the first holding time or occupancy at a later time, and show the rate substitution used.

A state has exit rate $4$ per hour. What is the probability that its first holding time exceeds $\tfrac14$ hour?
For exit rate $q_i=\tfrac52$, calculate the mean holding time and the median.
For a state with exit rate $q_i=0$, what are the probability of a finite holding time and the $p$-quantile for $0<p<1$?
Explain why $p_{ii}(t)$ need not equal $\mathbb{P}_i(H_i>t)$.
If $q_i>0$, use the survival formula to calculate $\mathbb{P}_i(H_i>s+t\mid H_i>s)$ for $s,t\ge0$.

Exponential Holding Times at a State

What You'll Learn