What is a Continuous Time Markov Chain

Continuous-Time Markov Chains

Oliver C. Ibe , in Markov Processes for Stochastic Modeling (Second Edition), 2013

5.6 Reversible CTMCs

A CTMC $\{X(t),-\infty <t<\infty \}$ is said to be a reversible Markov chain if for any fixed $\tau$ and integer $n\ge 0$ the sequence of states $X(t_1),X(t_2),\dots ,X(t_n)$ has the same probabilistic structure as the sequence $X(\tau -t_1),X(\tau -t_2),\dots ,X(\tau -t_n)$ . As discussed in Chapter 4, this means that a sequence of states when looked at backward in time has the same structure as the sequence running forward in time. As in the discrete-time analog discussed in Chapter 4, a CTMC is reversible if

$v_{ij}{p}_i=v_{ji}{p}_j$

As we discussed earlier, in the steady state the local balance condition for a birth and death process $\{X(t),t\ge 0\}$ states that

${\lambda }_i{p}_i={\mu }_{i+1}{p}_{i+1}i=0,1,2,\dots$

Because for a birth and death process $v_{ij}={\lambda }_i$ and $v_{ji}={\mu }_{i+1}$ , we observe that the reversibility condition has been met. Thus, a birth and death process is a reversible CTMC.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124077959000050

Stochastic Processes

J. MEDHI , in Stochastic Models in Queueing Theory (Second Edition), 2003

1.4 Birth-and-Death Processes

The class of all continuous-time Markov chains has an important subclass formed by the birth-and-death processes. These processes are characterized by the property that whenever a transition occurs from one state to another, then this transition can be to a neighboring state only. Suppose that the state space is S = {0,1,2,…,i,…}, then transition, whenever it occurs from state i, can be only to a neighboring state (i − 1) or (i + 1).

A continuous-time Markov chain {X(t), t ∈ T} with state space S = {0,1, 2,…} and with rates

$\begin{array}{c}{q}_{i,i+1}=\begin{array}{cc}{\lambda }_i(\text{say}),& i=0,1,\dots ,\end{array}\\ q_{i,i-1}=\begin{array}{cc}{\mu }_i(\text{say}),& i=1,2,\dots ,\end{array}\\ q_{i,j}=\begin{array}{ccccc}0,& j\ne i\pm 1,& j\ne i,& i=0,1,\dots ,& \text{and}\end{array}\\ q_i=\begin{array}{ccc}({\lambda }_i+{\mu }_i),& i=0,1,\dots ,& {\mu }_0=0,\end{array}\end{array}$

is called

(i)

a pure birth process, if μ_i = 0 for i = 1,2,…,

(ii)

a pure death process, if λ_i = 0, i = 0,1,…, and

(iii)

a birth-and-death-process if some of the λ_i 's and some of the μ′_i 's are positive.

Using (1.3.12) we get the Chapman-Kolmogorov forward equations for the birth-and-death process.

For i, j = 1,2,…,

(1.4.1) ${p^{\prime }}_{ij}(t)=-({\lambda }_j+{\mu }_j)p_{ij}(t)+{\lambda }_{j-1}{p}_{i,j-1}(t)+{\mu }_{j+1}{p}_{i,j+1}(t)$

and

(1.4.2) ${p^{\prime }}_{i0}(t)=-{\lambda }_0{p}_{i0}(t){\mu }_1{p}_{i,1}(t).$

The boundary conditions are

(1.4.3) $\begin{array}{cc}{p}_{i,j}(0+)={\delta }_{ij},& i,j=0,1,\dots .\end{array}$

Denote

$\begin{array}{cc}{P}_j(t)=Pr\{X(t)=j\},& j=0,1,\dots ,t>0\end{array}$

and assume that at time t = 0, the system starts at state i, so that

(1.4.4) $P_j(0)=Pr\{X(0)=j\}={\delta }_{ij},$

then

$P_j(t)=p_{ij}(t),$

and the forward equations can be written as

(1.4.5) ${P^{\prime }}_j(t)=-({\lambda }_j+{\mu }_j)P_j(t)+{\lambda }_{j-1}{P}_{j-1}(t)+{\mu }_{j+1}{P}_{j+1}(t),j=1,2,\dots ,$

(1.4.6) ${P^{\prime }}_0(t)=-{\lambda }_0{P}_0(t)+{\mu }_1{P}_1(t).$

Suppose that all the λ_i 's and μ_i ,'s are nonzero. Then the Markov chain is irreducible. It can be shown that such a chain is non-null persistent and that the limits

$\underset{t\to \infty }{\lim }{p}_{ij}(t)=p_j$

exist and are independent of the initial state i. Then Eqs. (1.4.5) and (1.4.6) become

(1.4.7) $\begin{array}{cc}0=-({\lambda }_j+{\mu }_j)p_j+{\lambda }_{j-1}{p}_{j-1}+{\mu }_{j+1}{p}_{j+1},& j\ge 1\end{array}$

(1.4.8) $0=-{\lambda }_0{p}_0+{\mu }_1{p}_1.$

Define

(1.4.9) $\begin{array}{c}{\pi }_j=\begin{array}{ccc}\frac{{\lambda }_0{\lambda }_1\dots {\lambda }_{j-1}}{{\mu }_1{\mu }_2\dots {\mu }_j},& j\ge 1,& \text{and}\end{array}\\ {\pi }_0=1;\end{array}$

then the solution of the above can be obtained by induction. We have from (1.4.8)

$p_1=\left(\frac{{\lambda }_0}{{\mu }_1}\right)p_0={\pi }_1{p}_0$

and assuming p_k = π_kp ₀ ,k = 1,2,…,j, we get from (1.4.7)

$\begin{array}{c}{p}_{j+1}{\mu }_{j+1}=\begin{array}{cc}{\lambda }_i{\pi }_j{p}_0,& \text{or}\end{array}\\ p_{j+1}={\pi }_{j+1}{p}_0.\end{array}$

Thus, it Σ_k=0 ^∞ π_k < ∞, then

(1.4.10) $\begin{array}{cc}{p}_j=\frac{{\pi }_j}{{\displaystyle \sum {\pi }_k}},& j\ge 0\end{array}.$

Incidentally, Σ π_k < ∞ is a sufficient condition for the birth-and-death process to have all the states non-null persistent (and therefore for the process to be ergodic).

This process is of particular interest in queueing theory as several queueing systems can be modeled as birth-and-death processes. As an example, we consider the simple queue.

1.4.1 Special case: M/M/1 queue

For this queueing model

$\begin{array}{ccc}\begin{array}{l}{\lambda }_j=\lambda ,\\ {\mu }_i=\mu ,\end{array}& \begin{array}{l}i=0,1,2,\dots \\ i=1,2,\dots ,\end{array}& \begin{array}{c}\text{and}\\ {\mu }_0=0;\end{array}\end{array}$

then π_j = (λ/μ)^j and Σπ_k < ∞ iff(λ/π) < 1, and then

(1.4.11) $\begin{array}{c}{\displaystyle \sum {\pi }_k}=1/[1-(\lambda /\mu )]\\ p_j=\begin{array}{cc}[1-(\lambda /\mu )]{(\lambda /\mu )}^j,& j=0,1,2,\dots \end{array}\end{array}$

1.4.2 Pure birth process: Yule-Furry process

If μ_i = 0, i ≥ 0, then we get a pure birth process; further, if λ_i = iλ, for all i, we get the Yule-Furry process for which

(1.4.12) $\begin{array}{c}{P^{\prime }}_j(t)=\begin{array}{ccc}-j\lambda P_j(t)+(j-1)\lambda P_{j-1}(t),& j\ge 1,& \text{and}\end{array}\\ {P^{\prime }}_0(t)=0\end{array}$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124874626500011

Simulation

Sheldon M. Ross , in Introduction to Probability Models (Tenth Edition), 2010

Example 11.20

Consider a continuous-time Markov chain that, upon entering state i, spends an exponential time with rate v_i in that state before making a transition into some other state, with the transition being into state j with probability P_i,j , i ≥ 0, j ≠ i. Suppose that costs are incurred at rate C (i) ≥ 0 per unit time whenever the chain is in state i, i ≥ 0. With X (t) equal to the state at time t, and α being a constant such that 0 α 1, the quantity

$W={\int }_0^{\infty }{e}^{-\alpha t}C\left(\text{x}\left(t\right)\right)dt$

represents the total discounted cost. For a given initial state, suppose we want to use simulation to estimate E[W]. Whereas at first it might seem that we cannot obtain an unbiased estimator without simulating the continuous-time Markov chain for an infinite amount of time (which is clearly impossible), we can make use of the results of Example 5.1, which gives the equivalent expression for E[W]:

$E\left[W\right]=E\left[{\int }_0^{T}C\left(\text{x}\left(t\right)\right)dt\right]$

where T is an exponential random variable with rate α that is independent of the continuous-time Markov chain. Therefore, we can first generate the value of T, then generate the states of the continuous-time Markov chain up to time T, to obtain the unbiased estimator ${\int }_0^{T}C\left(\text{x}\left(t\right)\right)dt$ . Because all the cost rates are nonnegative this estimator is strongly positively correlated with T, which will thus make an effective control variate.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123756862000017

Integrated Population Biology and Modeling, Part A

John Fricks , Ephraim Hanks , in Handbook of Statistics, 2018

2.1.1 The Infinitesimal Definition

A continuous-time Markov chain on the nonnegative integers can be defined in a number of ways. One way is through the infinitesimal change in its probability transition function over time. The probability transition function, which is the continuous-time analogue to the probability transition matrix of discrete Markov chains, is defined as

$\begin{array}{l}\hfill p_{i,j}(t)=P(X(t)=j|X(0)=i)=P(X(t+s)=j|X(s)=i)\end{array}$

The right-hand equality expresses the assumption of time homogeneity; given that the process starts in state i, the probability of arriving in state j after the passage of t time is the same regardless of the current time. We may then give an infinitesimal definition for a general birth–death process. The probability transition function can be implicitly defined by

$\begin{array}{ll}\hfill p_{i,i+1}(t+\mathrm{\Delta })& =\alpha (i)p_{k,i}(t)\mathrm{\Delta }+o(\mathrm{\Delta })\hfill \\ \hfill p_{i,i-1}(t+\mathrm{\Delta })& =\beta (i)p_{k,i}(t)\mathrm{\Delta }+o(\mathrm{\Delta })\hfill \\ \hfill p_{i,i}(t+\mathrm{\Delta })& =(1-\alpha (i)-\beta (i))p_{k,i}(t)\mathrm{\Delta }+o(\mathrm{\Delta })\hfill \end{array}$

where α(i), β(i) are nonnegative functions from the nonnegative integers to the reals, called the birth rate and death rate, respectively, and assuming that the process starts in state k. All other transitions are negligible (i.e., o(Δ)). These can be interpreted in the following way: in a small interval of length delta, the probability of a birth and therefore moving from state i to i + 1 is approximately α(i)Δ. The probability of moving from state i to i − 1 is β(i)Δ. Note that β(0) = 0 to ensure that the process remains on the nonnegative integers. The probability of no net change in the population is (1 − (α(i) − β(i))Δ).

There are several standard examples of these birth–death processes. By selecting the birth rate to be constant (α(i) = κ ₁, β(i) = 0.), the result is a Poisson process. In population models, these are often used to represent an arrival of an individual to a population from some other population, rather than being generated from the population within. An important feature of a Poisson process is that it has independent increments, i.e., X(t) − X(s) is independent of X(v) − X(u) as long as (s, t] and (u, v] do not overlap. The name of the process arises from the fact that X(t) − X(s) is a Poisson random variable with mean κ ₁(t − s). This is one instance where the transition probability function can be found exactly. Another well-known fact about Poisson processes is that the times between events are exponentially distributed with rate κ ₁ or alternatively with mean 1/κ ₁.

A starting point for a more realistic population model is the Yule process (α(i) = κ ₂ i and β(i) = 0) also known as the pure birth process (Yule, 1925). The reasoning behind this model is as follows. Each member of the population will give "birth" to a new organism after an exponential time with rate κ ₂ independent of every other member. This is the standard setup of exponential races (see, e.g., Durrett, 2016). So, if a population starts with i organisms each with an independent exponential time to a birth with rate κ ₂, then after an exponential time with rate κ ₂ i a birth will occur, and the population moves to a population of i + 1. After this birth, the memoryless property of the exponential ensures that each organism that did not generate a new organism has its exponential clock reset. Another way to express this is that in the next small time interval Δ a birth occurs. While this may be a poor model for many natural populations, it is not unreasonable for asexual reproduction of single cell organisms such as bacteria. One complaint might be that a cell that has just divided should not have its "clock" reset and restarted according to an exponential, but would rather need a delay; however, the Markovian model often works well as an approximation if this delay is small relative to the mean 1/κ ₂.

One classical way to study these birth–death processes is through differential equations that implicitly define the probability transition function; these are called the Kolmogorov forward and backward equations. Suppose that we define the matrix valued function M(t) to have entries being the probability transition function defined above, so that

$\begin{array}{l}\hfill M_{i,j}(t)=P(X(t+s)=j|X(s)=i)\end{array}$

Using the Markov property and time homogeneity, we can establish the Chapman–Kolmogorov equations,

$\begin{array}{l}\hfill \mathbf{M}(u+v)=\mathbf{M}(u)\mathbf{M}(v)\end{array}$

(see, e.g., Ross, 2014 for details). Now, if we subtract M(v) from both sides and divide by u and took a limit as u approaches zero from above, we would obtain the Kolmogorov backward equations for a discrete-space continuous-time Markov process,

$\begin{array}{l}\hfill {\mathbf{M}}^{\prime }(v)=\mathbf{Q}\mathbf{M}(v)\end{array}$

where M′(v) is the element-wise derivative of M(v) and

$\begin{array}{l}\hfill \mathbf{Q}=\underset{u\to 0^{+}}{lim}\frac{\mathbf{M}(u)-\mathbf{I}}{u}\end{array}$

The matrix Q is known as the infinitesimal generator. The infinitesimal generator defines the model as the off-diagonal entries contain the transition rates from i to j and the diagonal entries are set to ensure that the rows of the matrix sum to zero, a restriction that ensures the solution has rows that sum to one. By selecting v to be the small variable in the Chapman–Kolmogorov equations and performing a similar limit, we obtain the Kolmogorov forward equations,

$\begin{array}{l}\hfill {\mathbf{M}}^{\prime }(u)=\mathbf{M}(u)\mathbf{Q}\end{array}$

Both of these equations have an initial condition of M(0) = I. The Kolmogorov forward equation is also known as the master equation, especially in the chemistry and physics literature (Gardiner, 2009; Van Kampen, 2007).

Classic texts that includes a discussion of these equations are Karlin and Taylor (1975), Karlin and Taylor (1981), and there are, of course, many other more modern texts that discuss these equations including Durrett (2016), Ross (2014), and many others. In some simple cases, these equations may be solved to find an explicit solution to the probability transition function using Laplace transform methods. In general, this cannot be done, especially for generalizations beyond one dimension. While this literature is historically important and can sometimes be helpful in calculating quantities associated with particular models, it is especially limited when moving beyond one- or two-dimensional models, though some approximations exist in higher dimensions (Fox et al., 2016).

One particular use of the forward/backward equations is in determining stationary distributions when a unique equation exists, by setting the derivative to zero and solving for the probabilities under the constraint that those probabilities sum to one. Specifically, one needs to solve

$\begin{array}{l}\hfill 0=\pi (\mathbf{I}-\mathbf{Q})\end{array}$

where π is a row vector representing the stationary distribution, and we have the additional constraint that π should sum to one (Durrett, 2016; Ross, 2014). For a birth–death process, we have specific criteria for the existence of a stationary distribution based on the transition rates along with a general formula for their form. Beyond one dimension, this can also be a challenging approach.

An important takeaway from this brief discussion is that the probabilistic model for continuous-time Markov processes is generally defined only implicitly even when the parameters governing the process are fully known. Except in some simple cases, the probability transition function, which will form the basis of a likelihood function for these population models, will need to be approximated via simulation, approximating models, numerical schemes for ODEs, etc. This will add an extra layer of complexity and error to any estimation or simulation scheme.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S0169716118300270

Continuous-Time Markov Chains

Sheldon M. Ross , in Introduction to Probability Models (Tenth Edition), 2010

Example 6.11

(A Continuous-Time Markov Chain Consisting of Two States) Consider a machine that works for an exponential amount of time having mean 1/λ before breaking down; and suppose that it takes an exponential amount of time having mean 1/μ to repair the machine. If the machine is in working condition at time 0, then what is the probability that it will be working at time t = 10?

To answer this question, we note that the process is a birth and death process (with state 0 meaning that the machine is working and state 1 that it is being repaired) having parameters

$\begin{array}{l}{\lambda }_0=\lambda ,{\mu }_1=\mu ,\\ {\lambda }_i=0,i\ne 0,{\mu }_i=0,i\ne 1\end{array}$

We shall derive the desired probability, namely, P ₀₀(10) by solving the set of differential equations given in Example 6.10. From Equation (6.9), we obtain

(6.10) ${P^{\prime }}_{00}(t)=\lambda [P_{10}(t)-P_{00}(t)],$

(6.11) ${P^{\prime }}_{10}(t)=\mu P_{00}(t)-\mu P_{10}(t)$

Multiplying Equation (6.10) by μ and Equation (6.11) by λ and then adding the two equations yields

$\mu {P^{\prime }}_{00}(t)+\lambda {P^{\prime }}_{10}(t)=0$

By integrating, we obtain

$\mu P_{00}(t)+\lambda P_{10}(t)=c$

However, since P ₀₀(0) = 1 and P ₁₀(0) = 0, we obtain c = μ and hence,

(6.12) $\mu P_{00}(t)+\lambda P_{10}(t)=\mu$

or equivalently,

$\lambda P_{10}(t)=\mu [1-P_{00}(t)]$

By substituting this result in Equation (6.10), we obtain

$\begin{array}{l}{P^{\prime }}_{00}(t)=\mu [1-P_{00}(t)]-\lambda P_{00}(t)\\ =\mu -(\mu +\lambda )P_{00}(t)\end{array}$

Letting

$h(t)=P_{00}(t)-\frac{\mu }{\mu +\lambda }$

we have

$\begin{array}{l}{h}^{\prime }(t)=\mu -(\mu +\lambda )\left[h(t)+\frac{\mu }{\mu +\lambda }\right]\\ =-(\mu +\lambda )h(t)\end{array}$

or

$\frac{h^{\prime }(t)}{h(t)}=-(\mu +\lambda )$

By integrating both sides, we obtain

$logh(t)=-(\mu +\lambda )t+c$

or

$h(t)=K{e}^{-(\mu +\lambda )t}$

and thus

$P_{00}(t)=K{e}^{-(\mu +\lambda )t}+\frac{\mu }{\mu +\lambda }$

which finally yields, by setting t = 0 and using the fact that P ₀₀(0) = 1,

$P_{00}(t)=\frac{\lambda }{\mu +\lambda }{e}^{-(\mu +\lambda )t}+\frac{\mu }{\mu +\lambda }$

From Equation (6.12), this also implies that

$P_{10}(t)=\frac{\mu }{\mu +\lambda }-\frac{\mu }{\mu +\lambda }{e}^{-(\mu +\lambda )t}$

Hence, our desired probability is as follows:

$P_{00}(10)=\frac{\lambda }{\mu +\lambda }{e}^{-10(\mu +\lambda )}+\frac{\mu }{\mu +\lambda }$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123756862000054

Renewal Theory and Its Applications

Sheldon M. Ross , in Introduction to Probability Models (Tenth Edition), 2010

Example 7.18

Consider a positive recurrent continuous—time Markov chain that is initially in state i. By the Markovian property, each time the process reenters state i it starts over again. Thus returns to state i are renewals and constitute the beginnings of new cycles. By Proposition 7.4, it follows that the long—run

$\text{proportion\hspace{0.17em}of\hspace{0.17em}time\hspace{0.17em}in\hspace{0.17em}state}j=\frac{E[\text{amount\hspace{0.17em}of\hspace{0.17em}time\hspace{0.17em}in}j\text{\hspace{0.17em}during\hspace{0.17em}an}i-i\text{\hspace{0.17em}cycle}]}{{\mu }_{ii}}$

where μ _ii represents the mean time to return to state i. If we take j to equal i, then we obtain

$\text{proportion\hspace{0.17em}of\hspace{0.17em}time\hspace{0.17em}in\hspace{0.17em}state}i=\frac{1/v_i}{{\mu }_{ii}}$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123756862000030

Simulation

Sheldon M. Ross , in Introduction to Probability Models (Twelfth Edition), 2019

11.6.3 Control Variates

Again suppose we want to use simulation to estimate $E[g(\mathbf{X})]$ where $\mathbf{X}=(X_1,\dots ,X_n)$ . But now suppose that for some function f the expected value of $f(\mathbf{X})$ is known—say, $E[f(\mathbf{X})]=\mu$ . Then for any constant a we can also use

$W=g(\mathbf{X})+a(f(\mathbf{X})-\mu )$

as an estimator of $E[g(\mathbf{X})]$ . Now,

$\mathrm{Var}(W)=\mathrm{Var}(g(\mathbf{X}))+a^2\mathrm{Var}(f(\mathbf{X}))+2a\mathrm{Cov}(g(\mathbf{X}),f(\mathbf{X}))$

Simple calculus shows that the preceding is minimized when

$a=\frac{-\mathrm{Cov}(f(\mathbf{X}),g(\mathbf{X}))}{\mathrm{Var}(f(\mathbf{X}))}$

and, for this value of a,

$\mathrm{Var}(W)=\mathrm{Var}(g(\mathbf{X}))-\frac{{[\mathrm{Cov}(f(\mathbf{X}),g(\mathbf{X}))]}^2}{\mathrm{Var}(f(\mathbf{X}))}$

Because $\mathrm{Var}(f(\mathbf{X}))$ and $\mathrm{Cov}(f(\mathbf{X}),g(\mathbf{X}))$ are usually unknown, the simulated data should be used to estimate these quantities.

Dividing the preceding equation by $\mathrm{Var}(g(\mathbf{X}))$ shows that

$\frac{\mathrm{Var}(W)}{\mathrm{Var}(g(\mathbf{X}))}=1-{\mathrm{Corr}}^2(f(\mathbf{X}),g(\mathbf{X}))$

where $\mathrm{Corr}(X,Y)$ is the correlation between X and Y. Consequently, the use of a control variate will greatly reduce the variance of the simulation estimator whenever $f(\mathbf{X})$ and $g(\mathbf{X})$ are strongly correlated.

Example 11.20

Consider a continuous-time Markov chain that, upon entering state i, spends an exponential time with rate $v_i$ in that state before making a transition into some other state, with the transition being into state j with probability $P_{i,j},i⩾0,j\ne i$ . Suppose that costs are incurred at rate $C(i)⩾0$ per unit time whenever the chain is in state $i,i⩾0$ . With $X(t)$ equal to the state at time t, and α being a constant such that $0<\alpha <1$ , the quantity

$W={\int }_0^{\infty }{e}^{-\alpha t}C(X(t))dt$

represents the total discounted cost. For a given initial state, suppose we want to use simulation to estimate $E[W]$ . Whereas at first it might seem that we cannot obtain an unbiased estimator without simulating the continuous-time Markov chain for an infinite amount of time (which is clearly impossible), we can make use of the results of Example 5.1, which gives the equivalent expression for $E[W]$ :

$E[W]=E[{\int }_0^{T}C(X(t))dt]$

where T is an exponential random variable with rate α that is independent of the continuous-time Markov chain. Therefore, we can first generate the value of T, then generate the states of the continuous-time Markov chain up to time T, to obtain the unbiased estimator ${\int }_0^{T}C(X(t))dt$ . Because all the cost rates are nonnegative this estimator is strongly positively correlated with T, which will thus make an effective control variate.   ■

Example 11.21 A Queueing System

Let $D_{n+1}$ denote the delay in queue of the $n+1$ customer in a queueing system in which the interarrival times are independent and identically distributed (i.i.d.) with distribution F having mean ${\mu }_F$ and are independent of the service times, which are i.i.d. with distribution G having mean ${\mu }_G$ . If $X_i$ is the interarrival time between arrival i and $i+1$ , and if $S_i$ is the service time of customer i, $i⩾1$ , we may write

$D_{n+1}=g(X_1,\dots ,X_n,S_1,\dots ,S_n)$

To take into account the possibility that the simulated variables $X_i,S_i$ may by chance be quite different from what might be expected we can let

$f(X_1,\dots ,X_n,S_1,\dots ,S_n)=\sum _{i=1}^n(S_i-X_i)$

As $E[f(\mathbf{X},\mathbf{S})]=n({\mu }_G-{\mu }_F)$ we could use

$g(\mathbf{X},\mathbf{S})+a[f(\mathbf{X},\mathbf{S})-n({\mu }_G-{\mu }_F)]$

as an estimator of $E[D_{n+1}]$ . Since $D_{n+1}$ and f are both increasing functions of $S_i,-X_i,i=1,\dots ,n$ it follows from Theorem 11.1 that $f(\mathbf{X},\mathbf{S})$ and $D_{n+1}$ are positively correlated, and so the simulated estimate of a should turn out to be negative.

If we wanted to estimate the expected sum of the delays in queue of the first $N(T)$ arrivals, then we could use ${\sum }_{i=1}^{N(T)}{S}_i$ as our control variable. Indeed as the arrival process is usually assumed independent of the service times, it follows that

$E\left[\sum _{i=1}^{N(T)}{S}_i\right]=E[S]E[N(T)]$

where $E[N(T)]$ can either be computed by the method suggested in Section 7.8 or estimated from the simulation as in Example 11.18. This control variable could also be used if the arrival process were a nonhomogeneous Poisson with rate $\lambda (t)$ ; in this case,

$E[N(T)]={\int }_0^T\lambda (t)dt■$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128143469000160

Continuous-Time Markov Chains

Sheldon M. Ross , in Introduction to Probability Models (Twelfth Edition), 2019

6.2 Continuous-Time Markov Chains

Suppose we have a continuous-time stochastic process $\{X(t),t\ge 0\}$ taking on values in the set of nonnegative integers. In analogy with the definition of a discrete-time Markov chain, given in Chapter 4, we say that the process $\{X(t),t\ge 0\}$ is a continuous-time Markov chain if for all $s,t\ge 0$ and nonnegative integers $i,j,x(u),0\le u<s$

$\begin{array}{cc}\hfill P\{X(t+s)=& j|X(s)=i,X(u)=x(u),0\le u<s\}\hfill \\ \hfill =& P\{X(t+s)=j|X(s)=i\}\hfill \end{array}$

In other words, a continuous-time Markov chain is a stochastic process having the Markovian property that the conditional distribution of the future $X(t+s)$ given the present $X(s)$ and the past $X(u),0\le u<s$ , depends only on the present and is independent of the past. If, in addition,

$P\{X(t+s)=j|X(s)=i\}$

is independent of s, then the continuous-time Markov chain is said to have stationary or homogeneous transition probabilities.

All Markov chains considered in this text will be assumed to have stationary transition probabilities.

Suppose that a continuous-time Markov chain enters state i at some time, say, time 0, and suppose that the process does not leave state i (that is, a transition does not occur) during the next ten minutes. What is the probability that the process will not leave state i during the following five minutes? Since the process is in state i at time 10 it follows, by the Markovian property, that the probability that it remains in that state during the interval [10,15] is just the (unconditional) probability that it stays in state i for at least five minutes. That is, if we let $T_i$ denote the amount of time that the process stays in state i before making a transition into a different state, then

$P\{T_i>15|T_i>10\}=P\{T_i>5\}$

or, in general, by the same reasoning,

$P\{T_i>s+t|T_i>s\}=P\{T_i>t\}$

for all $s,t\ge 0$ . Hence, the random variable $T_i$ is memoryless and must thus (see Section 5.2.2) be exponentially distributed.

In fact, the preceding gives us another way of defining a continuous-time Markov chain. Namely, it is a stochastic process having the properties that each time it enters state i

(i)

the amount of time it spends in that state before making a transition into a different state is exponentially distributed with mean, say, $1/v_i$ , and

(ii)

when the process leaves state i, it next enters state j with some probability, say, $P_{ij}$ . Of course, the $P_{ij}$ must satisfy

$\begin{array}{cc}\hfill P_{ii}=& 0,\text{all}i\hfill \\ \hfill \sum _j{P}_{ij}=& 1,\text{all}i\hfill \end{array}$

In other words, a continuous-time Markov chain is a stochastic process that moves from state to state in accordance with a (discrete-time) Markov chain, but is such that the amount of time it spends in each state, before proceeding to the next state, is exponentially distributed. In addition, the amount of time the process spends in state i, and the next state visited, must be independent random variables. For if the next state visited were dependent on $T_i$ , then information as to how long the process has already been in state i would be relevant to the prediction of the next state—and this contradicts the Markovian assumption.

Example 6.1 A Shoe Shine Shop

Consider a shoe shine establishment consisting of two chairs—chair 1 and chair 2. A customer upon arrival goes initially to chair 1 where his shoes are cleaned and polish is applied. After this is done the customer moves on to chair 2 where the polish is buffed. The service times at the two chairs are assumed to be independent random variables that are exponentially distributed with respective rates ${\mu }_1$ and ${\mu }_2$ . Suppose that potential customers arrive in accordance with a Poisson process having rate λ, and that a potential customer will enter the system only if both chairs are empty.

The preceding model can be analyzed as a continuous-time Markov chain, but first we must decide upon an appropriate state space. Since a potential customer will enter the system only if there are no other customers present, it follows that there will always either be 0 or 1 customers in the system. However, if there is 1 customer in the system, then we would also need to know which chair he was presently in. Hence, an appropriate state space might consist of the three states 0, 1, and 2 where the states have the following interpretation:

$\begin{array}{cc}\hfill \mathit{State}\hfill & \mathit{Interpretation}\hfill \\ \hfill 0\hfill & \text{system is empty}\hfill \\ \hfill 1\hfill & \text{a customer is in chair 1}\hfill \\ \hfill 2\hfill & \text{a customer is in chair 2}\hfill \end{array}$

We leave it as an exercise for you to verify that

$\begin{array}{cc}\hfill & v_0=\lambda ,v_1={\mu }_1,v_2={\mu }_2,\hfill \\ \hfill & P_{01}=P_{12}=P_{20}=1■\hfill \end{array}$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128143469000111

BioModel Engineering with Petri Nets

Mary Ann Blätke , ... Wolfgang Marwan , in Algebraic and Discrete Mathematical Methods for Modern Biology, 2015

Numerical Methods

As long as the underlying semantics of a stochastic Petri net is described by a finite CTMC of manageable size, it can be analyzed using standard stochastic analysis techniques such as transient analysis, steady-state analysis, or (exact) model checking. Transient analysis means to compute the transient probabilities to be in a certain state at a specific time point using, for example, the uniformization method. Steady-state analysis computes the steady-state probabilities using, for example, Jacobi iteration or Gaussian-Seidel iteration. In numerical model checking, behavioral properties can be checked, which have been expressed in, for example, CSL—a stochastic counterpart of CTL, where the path quantifiers are replaced by probabilities.

For illustration, we perform transient analysis for the two introductory examples ${\mathcal{SPN}}_1$ and ${\mathcal{SPN}}_2$ ; see Figures 7.14 and 7.15.

Figure 7.14. Transient analysis for ${\mathcal{SPN}}_1$ in Figure 7.10 for N  =   10 (left) and N  =   100 (right). The 3D plots show the evolution of the probability distribution of the token number on A up to time point 5.

Figure 7.15. Transient analysis for ${\mathcal{SPN}}_2$ in Figure 7.12 for N  =   10 (left) and N  =   100 (right). The 3D plots in the first row show the evolution of the probability distribution of the fraction of tokens on A up to time point 50. The second row gives the cumulative probability distributions, sharpening the effect; compare the closed-form solution in Figure 7.13b.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128012130000071

Game theoretic modeling and dependability analysis of small cell relays under bandwidth spoofing attack in 5G wireless communication network

K.C. Lalropuia , Vandana Gupta , in The Handbook of Reliability, Maintenance, and System Safety through Mathematical Modeling, 2021

4.1 Numerical illustration

Availability: Availability of a system is characterized by the probability that the system is working properly when needed for use. In the proposed SCR attack model, a CTMC is used as the underlying stochastic process to characterize the lifetime of the SCR. Therefore, we obtain the steady state probabilities of the proposed model using SHARPE software [40]. Note that in the proposed model, the SCR network is available in the states 0, 1, 2, and 5. Thus, we determine SSA of the SCR under attack as

(5.18) $SSA={\pi }_0+{\pi }_1+{\pi }_2+{\pi }_5$

where π _k is the steady state probability that the network under attack is in state k. Based on the parameter values in Table 5.6 and setting λ ₄₀  =   0.001 we get the value of SSA as SSA  =   0.697. Note that the parameter values are chosen for the purpose of numerical illustration only.

Table 5.6. Parameters and their values (per hour).

Parameter	Value	Parameter	Value
λ 01	0.50000	λ 25	0.00040
λ 12	0.00060	λ 51	0.00094
λ 21	0.00060	λ 52	0.00094
λ 13	0.00020	λ 54	0.00003
λ 34	0.00003	λ 64	0.00300
λ 23	0.00020	λ 53	0.00020
λ 14	0.00003	λ 63	0.00040
λ 24	0.00003	λ 62	0.00220
λ 30	0.00500	λ 61	0.00220
λ 56	0.05950	λ 15	0.00040

MTTF: This is a common measure for the reliability of a system and is the average length of time that the system is expected to be in operation. To obtain the MTTF of the SCR, we remove the arc from the failed state (F) to the normal state (N) in Fig. 5.2, resulting in an absorbing Markov chain in which the state F is the absorbing state. We then compute the MTTF of the SCR under bandwidth spoofing attack by solving the absorbing CTMC. For example, on implementing the Algorithm 1 with $\nu \left(r,a,m\right)$   =   −9 and $\nu \left(r,\tau ,\tau \right)=-9$ , $r\in \left\{P,C\right\}$ , we get $x_a^{P^{\ast }}=0.595$ , $x_a^{C^{\ast }}=0.450,$ $y_m^{P^{\ast }}=0.405,$ and $y_m^{C^{\ast }}=\mathrm{0.550.}$ Substituting, these parameter values in the sixth and seventh row of the rate matrix Q with θ ₅  =   0.7 and θ ₆  =   0.8, β ₅₁  =   0.0033, ψ ₅₂  =   0.0033, ψ ₆₁  =   0.005, ψ ₆₂  =   0.005, β ₅₆  =   0.33, and β ₆₄  =   0.03, and using the parameter values in Table 5.6, we obtain the MTTF as MTTF  =   6112.339   h.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128195826000058

osmondficurnesion.blogspot.com

Source: https://www.sciencedirect.com/topics/mathematics/continuous-time-markov-chain

Share this post