Continuous Time Markov Chain Two Machines Preempt

Exponentially Distributed Time

Continuous-Time Markov Chains

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

Example 6.16

Consider a set of n components along with a single repairman. Suppose that component i functions for an exponentially distributed time with rate λ _i and then fails. The time it then takes to repair component i is exponential with rate μ _i , i = 1,…,n. Suppose that when there is more than one failed component the repairman always works on the most recent failure. For instance, if there are at present two failed components—say, components 1 and 2 of which 1 has failed most recently—then the repairman wll be working on component 1. However, if component 3 should fail before 1's repair is completed, then the repairman would stop working on component 1 and switch to component 3 (that is, a newly failed component preempts service).

To analyze the preceding as a continuous-time Markov chain, the state must represent the set of failed components in the order of failure. That is, the state will be i ₁, i ₂,…, i_k if i ₁, i ₂,…, i_k are the k failed components (all the other n − k being functional) with i ₁ having been the most recent failure (and is thus presently being repaired), i ₂ the second most recent, and so on. Because there are k! possible orderings for a fixed set of k failed components and $\left(\begin{array}{l}n\\ k\end{array}\right)$ choices of that set, it follows that there are

$\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)k!=\sum _{k=0}^n\frac{n!}{\left(n-k\right)!}=n!\sum _{i=0}^n\frac{1}{i!}$

possible states.

The balance equations for the limiting probabilities are as follows:

(6.23) $\begin{array}{l}\left({\mu }_{i_1}+\sum _{\begin{array}{c}i\ne i_j\\ j=\mathrm{1,\dots ,}k\end{array}}{\lambda }_i\right)P\left(i_1,\mathrm{\dots },i_k\right)=\sum _{\begin{array}{c}i\ne i_j\\ j=\mathrm{1,\dots ,}k\end{array}}P\left(i,i_1,\mathrm{\dots },i_k\right){\mu }_i+P\left(i_2,\mathrm{\dots },i_k\right){\lambda }_{i_1},\\ \sum _{i=1}^n{\lambda }_{i}P\left(\phi \right)=\sum _{i=1}^{n}P\left(i\right){\mu }_i\end{array}$

where ϕ is the state when all components are working. The preceding equations follow because statei ₁,…, i_k can be left either by a failure of any of the additional components or by a repair completion of component i ₁. Also, that state can be entered either by a repair completion of component i when the state is i, i ₁, …, i_k or by a failure of component i ₁ when the state is i ₂, …, i_k .

However, if we take

(6.24) $P\left(i_1,\mathrm{\dots },i_k\right)=\frac{{\lambda }_{i_1}{\lambda }_{i_2}\mathrm{\dots }{\lambda }_{i_k}}{{\mu }_{i_1}{\mu }_{i_2}\mathrm{\dots }{\mu }_{i_k}}P\left(\phi \right)$

then it is easily seen that Equations (6.23) are satisfied. Hence, by uniqueness these must be the limiting probabilities with P(ϕ) determined to make their sum equal 1. That is,

$P\left(\phi \right)={\left[1+\sum _{i_1,\mathrm{\dots },i_k}\frac{{\lambda }_{i_1}\mathrm{\dots }{\lambda }_{i_k}}{{\mu }_{i_1}\mathrm{\dots }{\mu }_{i_k}}\right]}^{-1}$

As an illustration, suppose n = 2 and so there are five states ϕ, 1, 2, 12, 21. Then from the preceding we would have

$\begin{array}{l}P\left(\phi \right)={\left[1+\frac{{\lambda }_1}{{\mu }_1}+\frac{{\lambda }_2}{{\mu }_2}+\frac{2{\lambda }_1{\lambda }_2}{{\mu }_1{\mu }_2}\right]}^{-1},\\ P\left(1\right)=\frac{{\lambda }_1}{{\mu }_1}P\left(\phi \right),\\ P\left(2\right)=\frac{{\lambda }_2}{{\mu }_2}P\left(\phi \right),\\ P\left(\mathrm{1,2}\right)=P\left(\mathrm{2,1}\right)=\frac{{\lambda }_1{\lambda }_2}{{\mu }_1{\mu }_2}P\left(\phi \right)\end{array}$

It is interesting to note, using Equation (6.24), that given the set of failed components, each of the possible orderings of these components is equally likely.

Read full chapter

URL:

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

SPECIAL RANDOM VARIABLES

Sheldon M. Ross , in Introduction to Probability and Statistics for Engineers and Scientists (Fourth Edition), 2009

EXAMPLE 5.6b

A crew of workers has 3 interchangeable machines, of which 2 must be working for the crew to do its job. When in use, each machine will function for an exponentially distributed time having parameter λbefore breaking down. The workers decide initially to use machines A and B and keep machine C in reserve to replace whichever of A or B breaks down first. They will then be able to continue working until one of the remaining machines breaks down. When the crew is forced to stop working because only one of the machines has not yet broken down, what is the probability that the still operable machine is machine C?

Read full chapter

URL:

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

Renewal Theory and Its Applications

Sheldon Ross , in Introduction to Probability Models (Eleventh Edition), 2014

7.8 Computing the Renewal Function

The difficulty with attempting to use the identity

$m(t)={\displaystyle \sum _{n=1}^{\infty }}{F}_n(t)$

to compute the renewal function is that the determination of $F_n(t)=P\{X_1+\cdots +X_n⩽t\}$ requires the computation of an $n$ -dimensional integral. Following, we present an effective algorithm that requires as inputs only one-dimensional integrals.

Let $Y$ be an exponential random variable having rate $\lambda$ , and suppose that $Y$ is independent of the renewal process $\{N(t)\text{,}t⩾0\}$ . We start by determining $E[N(Y)]$ , the expected number of renewals by the random time $Y$ . To do so, we first condition on $X_1$ , the time of the first renewal. This yields

(7.30) $E[N(Y)]={\int }_0^{\infty }E[N(Y)\mid X_1=x]f(x)\mathit{dx}$

where $f$ is the interarrival density. To determine $E[N(Y)\mid X_1=x]$ , we now condition on whether or not $Y$ exceeds $x$ . Now, if $Y<x$ , then as the first renewal occurs at time $x$ , it follows that the number of renewals by time $Y$ is equal to 0. On the other hand, if we are given that $x<Y$ , then the number of renewals by time $Y$ will equal 1 (the one at $x$ ) plus the number of additional renewals between $x$ and $Y$ . But by the memoryless property of exponential random variables, it follows that, given that $Y>x$ , the amount by which it exceeds $x$ is also exponential with rate $\lambda$ , and so given that $Y>x$ the number of renewals between $x$ and $Y$ will have the same distribution as $N(Y)$ . Hence,

$\begin{array}{cc}\hfill E[N(Y)\mid X_1=x\text{,}Y<x]=& 0\text{,}\hfill \\ \hfill E[N(Y)\mid X_1=x\text{,}Y>x]=& 1+E[N(Y)]\hfill \end{array}$

and so,

$\begin{array}{cc}\hfill E[N(Y)\mid X_1=x]=& E[N(Y)\mid X_1=x\text{,}Y<x]P\{Y<x\mid X_1=x\}\hfill \\ \hfill & +E[N(Y)\mid X_1=x\text{,}Y>x]P\{Y>x\mid X_1=x\}\hfill \\ \hfill =& E[N(Y)\mid X_1=x\text{,}Y>x]P\{Y>x\}\hfill \\ \hfill & \mathrm{since}Y\mathrm{and}{X}_1\text{are independent}\hfill \\ \hfill =& (1+E[N(Y)])e^{-\lambda x}\hfill \end{array}$

Substituting this into Equation (7.30) gives

$E[N(Y)]=(1+E[N(Y)]){\int }_0^{\infty }{e}^{-\lambda x}f(x)\mathit{dx}$

or

(7.31) $E[N(Y)]=\frac{E[e^{-\lambda X}]}{1-E[e^{-\lambda X}]}$

where $X$ has the renewal interarrival distribution.

If we let $\lambda =1/t$ , then Equation (7.31) presents an expression for the expected number of renewals (not by time $t$ , but) by a random exponentially distributed time with mean $t$ . However, as such a random variable need not be close to its mean (its variance is $t^2$ ), Equation (7.31) need not be particularly close to $m(t)$ . To obtain an accurate approximation suppose that $Y_1\text{,}{Y}_2\text{,}\dots \text{,}{Y}_n$ are independent exponentials with rate $\lambda$ and suppose they are also independent of the renewal process. Let, for $r=1\text{,}\dots \text{,}n$ ,

$m_r=E[N(Y_1+\cdots +Y_r)]$

To compute an expression for $m_r$ , we again start by conditioning on $X_1$ , the time of the first renewal:

(7.32) $m_r={\int }_0^{\infty }E[N(Y_1+\cdots +Y_r)\mid X_1=x]f(x)\mathit{dx}$

To determine the foregoing conditional expectation, we now condition on the number of partial sums ${\sum }_{i=1}^j{Y}_i\text{,}j=1\text{,}\dots \text{,}r$ , that are less than $x$ . Now, if all $r$ partial sums are less than $x$ —that is, if ${\sum }_{i=1}^r{Y}_i<x$ —then clearly the number of renewals by time ${\sum }_{i=1}^r{Y}_i$ is 0. On the other hand, given that $k\text{,}k<r$ , of these partial sums are less than $x$ , it follows from the lack of memory property of the exponential that the number of renewals by time ${\sum }_{i=1}^r{Y}_i$ will have the same distribution as 1 plus $N(Y_{k+1}+\cdots +Y_r)$ . Hence,

(7.33) $\begin{array}{cc}\hfill & E\left.\left[N(Y_1+\cdots +Y_r)\right|X_1=x\text{,}k\text{of the sums}{\displaystyle \sum _{i=1}^j}{Y}_i\text{are less than}x\right]\hfill \\ \hfill & =\left\{\begin{array}{cc}0\text{,}\hfill & \mathrm{if}k=r\hfill \\ 1+m_{r-k}\text{,}\hfill & \mathrm{if}k<r\hfill \end{array}\right.\hfill \end{array}$

To determine the distribution of the number of the partial sums that are less than $x$ , note that the successive values of these partial sums ${\sum }_{i=1}^j{Y}_i\text{,}j=1\text{,}\dots \text{,}r$ , have the same distribution as the first $r$ event times of a Poisson process with rate $\lambda$ (since each successive partial sum is the previous sum plus an independent exponential with rate $\lambda$ ). Hence, it follows that, for $k<r$ ,

(7.34) $\begin{array}{cc}\hfill & P\left\{k\text{of the partial sums}{\displaystyle \sum _{i=1}^j}\left.Y_i\text{are less than}x\right|X_1=x\right\}\hfill \\ \hfill & =\frac{e^{-\lambda x}{(\lambda x)}^k}{k!}\hfill \end{array}$

Upon substitution of Equations (7.33) and (7.34) into Equation (7.32), we obtain

$m_r={\int }_0^{\infty }{\displaystyle \sum _{k=0}^{r-1}}(1+m_{r-k})\frac{e^{-\lambda x}{(\lambda x)}^k}{k!}f(x)\mathit{dx}$

or, equivalently,

(7.35) $m_r=\frac{{\displaystyle {\sum }_{k=1}^{r-1}}(1+m_{r-k})E\left[X^k{e}^{-\lambda X}\right]({\lambda }^k/k!)+E\left[e^{-\lambda X}\right]}{1-E\left[e^{-\lambda X}\right]}$

If we set $\lambda =n/t$ , then starting with $m_1$ given by Equation (7.31), we can use Equation (7.35) to recursively compute $m_2\text{,}\dots \text{,}{m}_n$ . The approximation of $m(t)=E[N(t)]$ is given by $m_n=E[N(Y_1+\cdots +Y_n)]$ . Since $Y_1+\cdots +Y_n$ is the sum of $n$ independent exponential random variables each with mean $t/n$ , it follows that it is (gamma) distributed with mean $t$ and variance ${\mathit{nt}}^2/n^2=t^2/n$ . Hence, by choosing $n$ large, ${\sum }_{i=1}^n{Y}_i$ will be a random variable having most of its probability concentrated about $t$ , and so $E\left[N\left({\sum }_{i=1}^n{Y}_i\right)\right]$ should be quite close to $E[N(t)]$ . (Indeed, if $m(t)$ is continuous at $t$ , it can be shown that these approximations converge to $m(t)$ as $n$ goes to infinity.)

Example 7.32

Table 7.1 compares the approximation with the exact value for the distributions $F_i$ with densities $f_i\text{,}i=1\text{,}2\text{,}3$ , which are given by

$\begin{array}{cc}\hfill f_1(x)=& {\mathit{xe}}^{-x}\text{,}\hfill \\ \hfill 1-F_2(x)=& 0.3e^{-x}+0.7e^{-2x}\text{,}\hfill \\ \hfill 1-F_3(x)=& 0.5e^{-x}+0.5e^{-5x}■\hfill \end{array}$

Table 7.1. Approximating $m(t)$

${\mathbf{F}}_{\mathbf{i}}$		Exact	Approximation
i	t	$\mathit{m}(t)$	n $=$   1	n $=$   3	n $=$   10	n $=$   25	n $=$   50
1	1	0.2838	0.3333	0.3040	0.2903	0.2865	0.2852
1	2	0.7546	0.8000	0.7697	0.7586	0.7561	0.7553
1	5	2.250	2.273	2.253	2.250	2.250	2.250
1	10	4.75	4.762	4.751	4.750	4.750	4.750
2	0.1	0.1733	0.1681	0.1687	0.1689	0.1690	—
2	0.3	0.5111	0.4964	0.4997	0.5010	0.5014	—
2	0.5	0.8404	0.8182	0.8245	0.8273	0.8281	0.8283
2	1	1.6400	1.6087	1.6205	1.6261	1.6277	1.6283
2	3	4.7389	4.7143	4.7294	4.7350	4.7363	4.7367
2	10	15.5089	15.5000	15.5081	15.5089	15.5089	15.5089
3	0.1	0.2819	0.2692	0.2772	0.2804	0.2813	—
3	0.3	0.7638	0.7105	0.7421	0.7567	0.7609	—
3	1	2.0890	2.0000	2.0556	2.0789	2.0850	2.0870
3	3	5.4444	5.4000	5.4375	5.4437	5.4442	5.4443

Read full chapter

URL:

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

Special Random Processes

Oliver C. Ibe , in Fundamentals of Applied Probability and Random Processes (Second Edition), 2014

12.8.1 Birth and Death Processes

Birth and death processes are a special type of continuous-time Markov chains. Consider a continuous-time Markov chain with states 0,   1,   2,   …. If p _ij   =   0 whenever j  ≠ i  −   1 or j  ≠ i  +   1, then the Markov chain is called a birth and death process. Thus, a birth and death process is a continuous-time Markov chain with states 0,   1,   2,   …, in which transitions from state i can only go to either state i  +   1 or state i  −   1. That is, a transition either causes an increase in state by one or a decrease in state by one. A birth is said to occur when the state increases by one, and a death is said to occur when the state decreases by one. For a birth and death process, we define the following transition rates from state i:

$\begin{array}{c}{\mathit{\lambda }}_{\mathit{i}}={\mathit{v}}_{\mathit{i}}{\mathit{p}}_{\mathit{i}\left(\mathit{i}+1\right)}\\ {\mathit{\mu }}_{\mathit{i}}={\mathit{v}}_{\mathit{i}}{\mathit{p}}_{\mathit{i}\left(\mathit{i}-1\right)}\end{array}$

Thus, λ _i is the rate at which a birth occurs when the process is in state i and μ _i is the rate at which a death occurs when the process is in state i. The sum of these two rates is v _i   = λ _i   + μ _i , which is the rate of transition out of state i. The state-transition-rate diagram of a birth and death process is shown in Figure 12.17. It is called a state-transition-rate diagram as opposed to a state-transition diagram because it shows the rate at which the process moves from state to state and not the probability of moving from one state to another. Note that μ ₀  =   0, since there can be no death when the process is in empty state.

Figure 12.17. State-Transition-Rate Diagram for Birth and Death Process

The actual state-transition probabilities when the process is in state i are p _{i(i  +   1)} and p _{i(i  −   1)}. By definition, p _{i(i  +   1)}  = λ _i /(λ _i   + μ _i ) is the probability that a birth occurs before a death when the process is in state i. Similarly, p _{i(i  −   1)}  = μ _i /(λ _i   + μ _i ) is the probability that a death occurs before a birth when the process is in state i.

Recall that the rate at which the probability of the process being in state i changes with time is given by

$\frac{{\mathit{dp}}_{\mathit{i}}\left(\mathit{t}\right)}{\mathit{dt}}=-{\mathit{v}}_{\mathit{i}}{\mathit{p}}_{\mathit{i}}\left(\mathit{t}\right){\displaystyle \sum _{\mathit{j}\ne \mathit{i}}{\mathit{p}}_{\mathit{ij}}}+{\displaystyle \sum _{\mathit{j}\ne \mathit{i}}{\mathit{p}}_{\mathit{j}}\left(\mathit{t}\right){\mathit{p}}_{\mathit{ji}}{\mathit{v}}_{\mathit{j}}}=-\left({\mathit{\lambda }}_{\mathit{i}}+{\mathit{\mu }}_{\mathit{i}}\right){\mathit{p}}_{\mathit{i}}(\mathit{t})+{\mathit{\mu }}_{\mathit{i}+1}{\mathit{p}}_{\mathit{i}+1}(\mathit{t})+{\mathit{\lambda }}_{\mathit{i}-1}{\mathit{p}}_{\mathit{i}-1}(\mathit{t})$

In the steady state,

$\underset{\mathit{t}\to \mathit{\infty }}{lim}\left\{\frac{{\mathit{dp}}_{\mathit{i}}\left(\mathit{t}\right)}{\mathit{dt}}\right\}=0$

which gives

(12.32) $\left({\mathit{\lambda }}_{\mathit{i}}+{\mathit{\mu }}_{\mathit{i}}\right){\mathit{p}}_{\mathit{i}}\left(\mathit{t}\right)={\mathit{\mu }}_{\mathit{i}+1}{\mathit{p}}_{\mathit{i}+1}\left(\mathit{t}\right)+{\mathit{\lambda }}_{\mathit{i}-1}{\mathit{p}}_{\mathit{i}-1}\left(\mathit{t}\right)$

The equation states that the rate at which the process leaves state i either through a birth or a death is equal to the rate at which it enters the state through a birth when the process is in state i  −   1 or through a death when the process is in state i  +   1.

If we assume that the limiting probabilities $\underset{\mathit{t}\to \mathit{\infty }}{lim}{\mathit{p}}_{\mathit{ij}}\left(\mathit{t}\right)={\mathit{p}}_{\mathit{j}}$ exist, then from the above equation we obtain the following:

(12.33a) $\left({\mathit{\lambda }}_{\mathit{i}}+{\mathit{\mu }}_{\mathit{i}}\right){\mathit{p}}_{\mathit{i}}={\mathit{\mu }}_{\mathit{i}+1}{\mathit{p}}_{\mathit{i}+1}+{\mathit{\lambda }}_{\mathit{i}-1}{\mathit{p}}_{\mathit{i}-1}$

(12.33b) ${\displaystyle \sum _{\mathit{i}}{\mathit{p}}_{\mathit{i}}=1}$

This is called the balance equation because it balances (or equates) the rate at which the process enters state i with the rate at which it leaves state i.

Example 12.15

A machine is operational for an exponentially distributed time with mean 1/ λ before breaking down. When it breaks down, it takes a time that is exponentially distributed with mean 1/μ to repair it. What is the fraction of time that the machine is operational (or available)?

Solution:

This is a two-state birth and death process. Let U denote the up state and D the down state. Then, the state-transition-rate diagram is shown in Figure 12.18.

Figure 12.18. State-Transition-Rate Diagram for Example 12.15

Let p _U denote the steady-state probability that the process is in the operational state, and let p _D denote the steady-state probability that the process is in the down state. Then the balance equations become

$\begin{array}{c}{\mathit{\lambda p}}_{\mathit{U}}=\mathit{\mu }{\mathit{p}}_{\mathit{D}}\\ {\mathit{p}}_{\mathit{U}}+{\mathit{p}}_{\mathit{D}}=1\Rightarrow {\mathit{p}}_{\mathit{D}}=1-{\mathit{p}}_{\mathit{U}}\end{array}$

Substituting for p _D in the first equation gives p _U   = μ/(λ  + μ).

Example 12.16

Customers arrive at a bank according to a Poisson process with rate λ. The time to serve each customer is exponentially distributed with mean 1/μ. There is only one teller at the bank, and an arriving customer who finds the teller busy when she arrives will join a single queue that operates on a first-come, first-served basis. Determine the limiting-state probabilities given that μ  > λ.

Solution:

This is a continuous-time Markov chain in which arrivals constitute births and service completions constitute deaths. Also, for all i, λ _i   = λ and μ _i   = μ. Thus if p _k denotes the steady-state probability that there are k customers in the system, the balance equations are as follows:

$\begin{array}{c}\mathit{\lambda }{\mathit{p}}_0=\mathit{\mu }{\mathit{p}}_1\Rightarrow {\mathit{p}}_1=\left(\frac{\mathit{\lambda }}{\mathit{\mu }}\right){\mathit{p}}_0\\ \left(\mathit{\lambda }+\mathit{\mu }\right){\mathit{p}}_1=\mathit{\lambda }{\mathit{p}}_0+\mathit{\mu }{\mathit{p}}_2\Rightarrow {\mathit{p}}_2=\left(\frac{\mathit{\lambda }}{\mathit{\mu }}\right){\mathit{p}}_1={\left(\frac{\mathit{\lambda }}{\mathit{\mu }}\right)}^2{\mathit{p}}_0\\ \left(\mathit{\lambda }+\mathit{\mu }\right){\mathit{p}}_2=\mathit{\lambda }{\mathit{p}}_1+\mathit{\mu }{\mathit{p}}_3\Rightarrow {\mathit{p}}_3=\left(\frac{\mathit{\lambda }}{\mathit{\mu }}\right){\mathit{p}}_2={\left(\frac{\mathit{\lambda }}{\mathit{\mu }}\right)}^3{\mathit{p}}_0\end{array}$

In general it can be shown that

${\mathit{p}}_{\mathit{k}}={\left(\frac{\mathit{\lambda }}{\mathit{\mu }}\right)}^{\mathit{k}}{\mathit{p}}_0\mathit{k}=0,1,2,\dots$

Now,

${\displaystyle \sum _{\mathit{k}=0}^{\mathit{\infty }}{\mathit{p}}_{\mathit{k}}}=1={\mathit{p}}_0{\displaystyle \sum _{\mathit{k}=0}^{\mathit{\infty }}{\left(\frac{\mathit{\lambda }}{\mathit{\mu }}\right)}^{\mathit{k}}}=\frac{{\mathit{p}}_0}{1-\frac{\mathit{\lambda }}{\mathit{\mu }}}$

where the equality follows from the fact that μ  > λ. Thus,

$\begin{array}{c}{\mathit{p}}_0=1-\frac{\mathit{\lambda }}{\mathit{\mu }}\\ {\mathit{p}}_{\mathit{k}}=\left(1-\frac{\mathit{\lambda }}{\mathit{\mu }}\right){\left(\frac{\mathit{\lambda }}{\mathit{\mu }}\right)}^{\mathit{k}}\mathit{k}=0,1,2,\dots \end{array}$

Read full chapter

URL:

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

DEVS Markov Modeling and Simulation

Bernard P. Zeigler , ... Ernesto Kofman , in Theory of Modeling and Simulation (Third Edition), 2019

21.8 Relations Between DEVS CTM and DTM

From fundamental Markov theory, CTM is equivalent to DTM in the limit of small time step. The DEVS extension of each type introduces an external transition function which has elapsed time in state as an argument. However, only CTM can provide elapsed time that represents sojourn time in state. This is because the time advance function randomly selects the sojourn time using the correct computation. On the other hand, the external transition function in the DTM case can only supply the time step value being employed. We can get the actual sojourn time by adding a stopwatch which starts when a state is first entered and stops when the state is changed.

Exercise 21.24

Show how to add stopwatch functionality to a DEVS DTM by adding a state variable that accumulates the transition count while holding in a state.

Thus, as in Table 21.4, with both DEVS CTM and DEVS DTM as defined, the DEVS CTM has more capability than the DEVS DTM. Adding the stopwatch to the DEVS DTM gives it the same capability as DEVS CTM. In contrast, if we restrict the external transition function to not depend on elapsed time, then both types are equivalent.

Table 21.4. Behavioral comparison of CTM and DTM with/without auxiliary timing.

DEVS DTM\DEVS CTM	As defined	No elapsed time dependence
As defined	DEVS CTM > DEVS DTM	DEVS CTM = DEVS DTM
With stopwatch	DEVS CTM = DEVS DTM	DEVS CTM = DEVS DTM

21.8.1 Example: DEVS Markov Coupled Model

The following example employs DEVS Markov models as components and investigates the different types of models that characterize the resultants and their behaviors. The example is a coupled model of a DEVS CTM with a DEVS Markov (fixed transition time) model representing the usual timed situation in reality. Also the latter is replaced by a DEVS CTM where the timer is allowed to be a random element and the resulting types of models and behaviors are investigated.

Mobile Worker  At any time, a worker is located in a locality with variability in the available jobs. Having just arrived to a locality, the worker begins a search for employment. Finding a job, the worker stays in the job until losing it. At that point she remains unemployed until finding a new one. The worker allows a fixed amount of time to find such a job and leaves the area in search of new employment if a new job does not materialize within that time. In Fig. 21.12 we represent such a worker with states inJob, JobLess, and JobSearch together with a timer that alerts the worker to start a search after a fixed time. Also this timer is replaced by one which has an exponentially distributed time duration.

Figure 21.12. Mobile Worker.

a)

Coupled model for the timed mobile worker containing worker and timer components where the timer is the CTM alternative

b)

CTM of mobile worker

c)

Fixed duration alternative for timer (set to 3 days)

d)

CTM alternative for timer (exponential duration with mean of 3)

e)

Part of the state diagram of the coupled model – starting with (inJob, Expired), the loss of job with output StartTimer! leads to (JobLess, Timing); then, depending on which happens first, finding job or timer timeout, transition back to (inJob, Expired) or (JobSearch, Expired).

21.8.2 DEVS Hidden Markov Models

We return to characterize the hidden Markov model in Fig. 21.8 noting that it is of the form of a Cascade Composition presented in Section 15.9. The structure of the resultant model can be characterized as in Fig. 21.13. Using the terminology of Section 15.9, the front component is correlated with a partition on the state set of the resultant defined by the equivalence classes of the states mapped to the same front component state. State trajectories remain within an equivalent class and are governed by a back component which is a DEVS Markov model associated with the equivalent class. Output equivalence classes are orthogonal to the blocks of the state mapping so that outputs can't reveal the state of the front block. Switching between such classes is governed by the front component which is the hidden Markov model.

Figure 21.13. Hidden Markov Model.

The mapping can be characterized as a multi-step homomorphism of stochastic timed models (Chapter 9).

Exercises

1.

Write a CTM DEVS model for the mobile worker and a DEVS model for the fixed duration timer.

2.

Write a coupled model of with components in the previous exercise.

3.

Write a CTM DEVS model for the variable duration timer and substitute it for the timer in the coupled model.

4.

Show that the Probability Transition Structure underlying the coupled model state diagram in E can be shown to be isomorphic to the atomic DEVS CTM in F where the correspondence merely projects out the state of the worker from the paired state of the worker and timer.

5.

Argue that the coupled model with fixed duration timer is not equivalent to a CTM.

6.

If instead of immediately jumping to the JobSearch state when the timer expires, the worker waits for the time remaining and jumps to JobSearch instead. Show that this is an example of a DEVS Markov model where the elapsed time is being used and prove (or disprove) that the resultant is not equivalent to a DEVS CTM.

21.8.3 Example: Dynamic Structure via Variable Transition Probability

The dynamic structure capability of DEVS (Chapter 1) can be applied to DEVS Markov models to vary the underlying PTS and TTS structures. This allows more granular control of probabilities and transition times than is possible within fixed structure models. For example, the DEVS CTM model in Fig. 21.14 uses a "tunnel" sequence to lower the probability of death with longer remission. The DEVS Markov model in Fig. 21.15 employs the sojourn time of the initial state to lower the probability in a more granular manner.

Figure 21.14. Tunnel sequence approach to temporal dependence of transition probability.

Figure 21.15. Sojourn time approach to temporal dependence of transition probability.

Exercise 21.25

Show how to implement the change in PTS in Fig. 21.15 based on the sojourn time of the initial state. Hint: obtain the sojourn time as the time advance of the initial state and define a function to map the values obtained to the probability of transition of GreaterThan2Years to Death in the PTS.

The flow chart in Fig. 21.16 illustrates the control flow for the internal transitions for an atomic DEVS Markov model based on a pair of PTS and TTS.

Figure 21.16. Flow chart to illustrate DEVS Markov atomic model.

To illustrate the implementation of dynamic structure change, Fig. 21.16 considers that the PTS or TTS structures can depend on some index such as elapsed time or input value. Moreover, the current value of the index is incorporated into the state as a state variable. Thus, when the index is changed to a new value, the value is stored to help determine the values of the PTS and/or TTS. This might happen due to internal or external transitions. Dependence, of this kind, on external input values has been associated with Markov Decision Processes and Markov Agent Models. The DEVS ability for an external event to supply the elapsed time as index appears to be novel but can be considered to be the natural feature that exploits the coupling capability of coupled models having DEVS Markov model components. That is, if we allow such models to be influenced by elapsed time in external transitions then the resultants of coupled models will also depend on the global time advance (or residence time in the last global state) and hence will be Semi-Markov in nature. Furthermore, any change in the PTS or TTS structures amounts to dynamic structure change since it changes the basic properties of the model's transition definitions.

Read full chapter

URL:

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

Continuous-Time Markov Chains

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

5.3 Birth and Death Processes

Birth and death processes are a special type of CTMC. Consider a CTMC with states $0,1,2,\dots$ . If $p_{ij}=0$ whenever $j\ne i-1$ or $j\ne i+1$ , then the Markov chain is called a birth and death process. Thus, a birth and death process is a CTMC with states $0,1,2,\dots$ , in which transitions from state i can only go to either state $i+1$ or state $i-1$ . That is, a transition either causes an increase in state by one or a decrease in state by one. A birth is said to occur when the state increases by one, and a death is said to occur when the state decreases by one. For a birth and death process, we define the following transition rates from state i:

$\begin{array}{ll}\hfill {\lambda }_i& =v_i{p}_{i(i+1)}\hfill \\ \hfill {\mu }_i& =v_i{p}_{i(i-1)}\hfill \end{array}$

Thus, ${\lambda }_i$ is the rate at which a birth occurs when the process is in state i and ${\mu }_i$ is the rate at which a death occurs when the process is in state i. The sum of these two rates is ${\lambda }_i+{\mu }_i=v_i$ , which is the rate of transition out of state i. The state-transition-rate diagram of a birth and death process is shown in Figure 5.3. It is called a state-transition-rate diagram as opposed to a state-transition diagram because it shows the rate at which the process moves from state to state and not the probability of moving from one state to another. Note that ${\mu }_0=0$ , because there can be no death when the process is in empty state.

Figure 5.3. State-transition-rate diagram for birth and death process.

The actual state-transition probabilities when the process is in state i are $p_{i(i+1)}$ and $p_{i(i-1)}$ . By definition, $p_{i(i+1)}={\lambda }_i/({\lambda }_i+{\mu }_i)$ is the probability that a birth occurs before a death when the process is in state i. Similarly, $p_{i(i-1)}={\mu }_i/({\lambda }_i+{\mu }_i)$ is the probability that a death occurs before a birth when the process is in state i.

Recall from Eq. (5.1) that the rate at which the probability of the process being in state i changes with time is given by

$\begin{array}{ll}\hfill \frac{\mathrm{d}{p}_i(t)}{\mathrm{d}t}& =-v_i{p}_i(t)\sum _{j\ne i}{p}_{ij}+\sum _{j\ne i}{p}_j(t)p_{ji}{v}_j\hfill \\ \hfill & =-({\lambda }_i+{\mu }_i)p_i(t)+{\mu }_{i+1}{p}_{i+1}(t)+{\lambda }_{i-1}{p}_{i-1}(t)\hfill \end{array}$

Thus, for the birth and death process we have that

$\begin{array}{l}\frac{\mathrm{d}{p}_0(t)}{\mathrm{d}t}=-{\lambda }_0{p}_0(t)+{\mu }_1{p}_1(t)\\ \hfill \frac{\mathrm{d}{p}_i(t)}{\mathrm{d}t}=-({\lambda }_i+{\mu }_i)p_i(t)+{\mu }_{i+1}{p}_{i+1}(t)+{\lambda }_{i-1}{p}_{i-1}(t)i>0\end{array}$

In the steady state,

$\underset{t\to \infty }{\lim }\left\{\frac{\mathrm{d}{p}_i(t)}{\mathrm{d}t}\right\}=0$

If we assume that the limiting probabilities $\underset{t\to \infty }{\lim }{p}_{ij}(t)=p_j$ exist, then from the preceding equation we obtain the following:

$\begin{array}{ll}\hfill {\lambda }_0{p}_0& ={\mu }_1{p}_1\hfill \\ \hfill ({\lambda }_i+{\mu }_i)p_i& ={\mu }_{i+1}{p}_{i+1}+{\lambda }_{i-1}{p}_{i-1}\hfill \\ \hfill \sum _i{p}_i& =1\hfill \end{array}i=1,2,\dots$

The equation states that the rate at which the process leaves state i either through a birth or a death is equal to the rate at which it enters the state through a birth when the process is in state $i-1$ or through a death when the process is in state $i+1$ . This is called the balance equation because it balances (or equates) the rate at which the process enters state i with the rate at which it leaves state i.

Example 5.2

A machine is operational for an exponentially distributed time with mean $1/\lambda$ before breaking down. When it breaks down, it takes a time that is exponentially distributed with mean $1/\mu$ to repair it. What is the fraction of time that the machine is operational (or available)?

Solution

This is a two-state birth and death process. Let U denote the up state and D the down state. Then, the state-transition-rate diagram is shown in Figure 5.4.

Figure 5.4. State-transition-rate diagram for Example 5.2.

Let $p_U$ denote the steady-state probability that the process is in the operational state, and let $p_D$ denote the steady-state probability that the process is in the down state. Then the balance equations become

$\begin{array}{ll}\hfill \lambda p_U& =\mu p_D\hfill \\ \hfill p_U+p_D& =1\Rightarrow p_D=1-p_U\hfill \end{array}$

Substituting $p_D=1-p_U$ in the first equation gives $p_U=\mu /(\lambda +\mu )$ .

Example 5.3

Customers arrive at a bank according to a Poisson process with rate $\lambda$ . The time to serve each customer is exponentially distributed with mean $1/\mu$ . There is only one teller at the bank, and an arriving customer who finds the teller busy when she arrives will join a single queue that operates on a first-come-first-served basis. Determine the limiting-state probabilities given that $\mu >\lambda$ .

Solution

This is a CTMC in which arrivals constitute births and service completions constitute deaths. Also, for all i, ${\mu }_i=\mu$ and ${\lambda }_i=\lambda$ . Thus, if $p_k$ denotes the steady-state probability that there are k customers in the system, the balance equations are as follows:

$\begin{array}{ll}\hfill \lambda p_0& =\mu p_1\Rightarrow p_1=\left(\frac{\lambda }{\mu }\right)p_0\hfill \\ \hfill (\lambda +\mu )p_1& =\lambda p_0+\mu p_2\Rightarrow p_2=\left(\frac{\lambda }{\mu }\right)p_1={\left(\frac{\lambda }{\mu }\right)}^2{p}_0\hfill \\ \hfill (\lambda +\mu )p_2& =\lambda p_1+\mu p_3\Rightarrow p_3=\left(\frac{\lambda }{\mu }\right)p_2={\left(\frac{\lambda }{\mu }\right)}^3{p}_0\hfill \end{array}$

Similarly, it can be shown that

$p_k={\left(\frac{\lambda }{\mu }\right)}^k{p}_{0}k=0,1,2,\dots$

Now,

$\sum _{k=0}^{\infty }{p}_k=1=p_0\sum _{k=0}^{\infty }{\left(\frac{\lambda }{\mu }\right)}^k=\frac{p_0}{1-\frac{\lambda }{\mu }}$

Thus,

$\begin{array}{ll}\hfill p_0& =1-\frac{\lambda }{\mu }\hfill \\ \hfill p_k& =\left(1-\frac{\lambda }{\mu }\right){\left(\frac{\lambda }{\mu }\right)}^{k}k=0,1,2,\dots \hfill \end{array}$

5.3.1 Local Balance Equations

Recall that the steady-state solution of the birth and death process is given by

$\begin{array}{ll}\hfill {\lambda }_0{p}_0& ={\mu }_1{p}_1\hfill \\ \hfill ({\lambda }_i+{\mu }_i)p_i& ={\mu }_{i+1}{p}_{i+1}+{\lambda }_{i-1}{p}_{i-1}i=1,2,\dots \hfill \\ \hfill \sum _i{p}_i& =1\hfill \end{array}$

For $i=1$ , we obtain $({\lambda }_1+{\mu }_1)p_1={\mu }_2{p}_2+{\lambda }_0{p}_0$ . Because we know from the first equation that ${\lambda }_0{p}_0={\mu }_1{p}_1$ , this equation becomes

${\lambda }_1{p}_1={\mu }_2{p}_2$

Similarly, for $i=2$ , we have that $({\lambda }_2+{\mu }_2)p_2={\mu }_3{p}_3+{\lambda }_1{p}_1$ Applying the last result we obtain

${\lambda }_2{p}_2={\mu }_3{p}_3$

Repeated application of this method yields the general result

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

This result states that when the process is in the steady state, the rate at which it makes a transition from state i to state $i+1$ , which we refer to the rate of flow from state i to state $i+1$ , is equal to the rate of flow from state $i+1$ to state i. This property is referred to as local balance condition. Recall that it is an application of the reversibility property discussed in Chapter 4. Direct application of the property allows us to solve for the steady-state probabilities of the birth and death process recursively as follows:

$\begin{array}{lll}\hfill p_i& =\hfill & \frac{{\lambda }_{i-1}}{{\mu }_i}{p}_{i-1}\hfill \\ \hfill & =\hfill & \frac{{\lambda }_{i-1}{\lambda }_{i=2}}{{\mu }_i{\mu }_{i-1}}{p}_{i-2}\hfill \\ \hfill & \hfill & ⋮\hfill \\ \hfill & =\hfill & \frac{{\lambda }_{i=1}{\lambda }_{i=2}\cdots {\lambda }_0}{{\mu }_i{\mu }_{i-1}\cdots {\mu }_1}{p}_0\hfill \\ \hfill 1& =\hfill & p_0\left[1+\sum _{i=1}^{\infty }\frac{{\lambda }_{i-1}{\lambda }_{i=2}\cdots {\lambda }_0}{{\mu }_i{\mu }_{i-1}\cdots {\mu }_1}\right]\hfill \\ \hfill p_0& =\hfill & {\left[1+\sum _{i=1}^{\infty }\frac{{\lambda }_{i-1}{\lambda }_{i=2}\cdots {\lambda }_0}{{\mu }_i{\mu }_{i-1}\cdots {\mu }_1}\right]}^{-1}\hfill \\ \hfill p_i& =\hfill & \frac{{\lambda }_{i=1}{\lambda }_{i=2}\cdots {\lambda }_0}{{\mu }_i{\mu }_{i-1}\cdots {\mu }_1}{\left[1+\sum _{i=1}^{\infty }\frac{{\lambda }_{i-1}{\lambda }_{i=2}\cdots {\lambda }_0}{{\mu }_i{\mu }_{i-1}\cdots {\mu }_1}\right]}^{-1}i\ge 1\hfill \end{array}$

When ${\lambda }_i=\lambda$ for all i and ${\mu }_i=\mu$ for all i, we obtain the result

$p_0={\left[1+\sum _{i=1}^{\infty }{\left(\frac{\lambda }{\mu }\right)}^i\right]}^{-1}$

The sum converges if and only if $\lambda /\mu <1$ , which is equivalent to the condition that $\lambda <\mu$ . Under this condition we obtain the solutions

$\begin{array}{ll}\hfill p_0& =1-\frac{\lambda }{\mu }\hfill \\ \hfill p_i& =\left(1-\frac{\lambda }{\mu }\right){\left(\frac{\lambda }{\mu }\right)}^{i}i\ge 1\hfill \end{array}$

In Chapter 6, we will refer to this special case of the birth and death process as an M/M/1 queueing system.

5.3.2 Transient Analysis of Birth and Death Processes

Recall from Eq. (5.6) that

$\frac{\mathrm{d}p(t)}{\mathrm{d}t}=p(t)Q$

For the birth and death process we have that

$Q=\left[\begin{array}{llllll}\hfill -{\lambda }_0& {\lambda }_0\hfill & 0\hfill & 0\hfill & 0\hfill & \cdots \hfill \\ \hfill {\mu }_1& -({\lambda }_1+{\mu }_1)\hfill & {\lambda }_1\hfill & 0\hfill & 0\hfill & \cdots \hfill \\ \hfill 0& {\mu }_2\hfill & -({\lambda }_2+{\mu }_2)\hfill & {\lambda }_2\hfill & 0\hfill & \cdots \hfill \\ \hfill 0& 0\hfill & {\mu }_3\hfill & -({\lambda }_3+{\mu }_3)\hfill & {\lambda }_3\hfill & 0\hfill \\ \hfill \cdots & \cdots \hfill & \cdots \hfill & \cdots \hfill & \cdots \hfill & \cdots \hfill \end{array}\right]$

From this we obtain the following system of differential equations:

$\begin{array}{ll}\hfill \frac{\mathrm{d}{p}_0(t)}{\mathrm{d}t}& =-{\lambda }_0{p}_0(t)+{\mu }_1{p}_1(t)\hfill \\ \hfill \frac{\mathrm{d}{p}_i(t)}{\mathrm{d}t}& =-({\lambda }_i+{\mu }_i)p_i(t)+{\mu }_{i+1}{p}_{i+1}(t)+{\lambda }_{i-1}{p}_{i-1}(t)i>0\hfill \end{array}$

Read full chapter

URL:

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

Disease Modelling and Public Health, Part B

Anuj Mubayi , in Handbook of Statistics, 2017

2.3.1 Quantifying Case-Underreporting Levels

We derive a metric to quantify local measure of underreporting and actual disease incidence using a mathematical model. In the model, the transmission of vector-borne disease is assumed to be a results of interacting human–vector populations that incorporates the appropriate epidemiological states, transmission mechanisms, and epidemiological and contact parameters. Usually for neglected diseases data are scarce and hence, there are large variations in infectiousness, length of incubation, and treatment periods (depends on the treatment regime). These variations can be well captured by "staged-progression models" (SPM) or "linear chain trick" (Feng et al., 2007; Hyman et al., 1999). That is, we consider class-stages for the latent and infectious individuals, latent vectors, and individuals who get treatment at public and private health facilities. We include two groups of treated classes: patients undergoing treatment at public health facilities and patients treated at nongovernmental or private health care clinics (see Fig. 4). We model underreporting through the proportion p that captures the fraction of patients undergoing treatment in public health facilities. The remaining proportion 1 − p of infectious patients get treatment at private health clinics and are unreported. We assume that average treatment rate at private health clinics is, in general, q times the average treatment rate at public health facilities, where q ∈ [0, 1]; q = 1 means that the length of the treatment period in public and private treatment facilities are the same, q = 0.75 implies that average treatment length in private facilities is 4/3 (i.e., 1/q) times longer.

Fig. 4. Flow chart of stage progression model with structured treatment regiems.

Once a susceptible individual gets infected through the bite of an infected sandfly, he/she becomes latent and progresses through the n ₁ latent stages (E _i ; i = 1, …, n ₁) before becoming infectious. In our model, $E(t)={\sum }_{i_1=1}^{n_1}{E}_{i_1}(t)$ . A latent individual spends an exponentially distributed time in each latent stage which is independent of the time spent in every other stage. Thus, he/she remains latent for a Γ( n ₁; n ₁ γ _h )-distributed time where Γ refers to the gamma distribution. That is, the expected length of the intrinsic latent period is 1/γ _h with standard deviation of $1/({\gamma }_h\sqrt{n_1})$ . Similarly, it is assumed for infectious and treatment periods. We also assume stages in latent and infectious states in vectors.

The rate of infection for susceptible hosts is modeled via $F_h(t)={\lambda }_h\frac{Z(t)}{N_v(t)}$ where λ _h = mCβ _hv , m is the per capita average number of sandfies (assumed constant), C is the mean rate of bites per sandfly, β _hv is a transmission probability per bite from an infectious sandfly and Z/N _v is the proportion of infectious sandflies in the population (i.e., the probability that a bite is made by an infectious sandfly). Here, we are assuming that both N _v and N _h are constant. The proportion of bites of susceptible sandflies biting infectious humans is modeled as the proportion of infectious humans in the population $\frac{{\sum }_{j_1=1}^{m_1}{I}_{j_1}(t)}{N_h}$ , assuming sandflies bite any host with equal probability. The infection rate of susceptible sandflies is $F_v(t)={\lambda }_v\frac{{\sum }_{j_1=1}^{m_1}{I}_{j_1}(t)}{N_h(t)}$ , where λ _v = Cβ _vh , β _vh is the transmission probability per bite from an infectious human to a susceptible sandfly (Chowell et al., 2007). The model defined here uses the well-known fact that a Γ(n, v)-distribution is equivalent to the distribution of the sum of n independent Exp(v)-distributions. From Fig. 4, the rate of reporting of cases is $p{m}_1{\eta }_h{I}_{m_1}^{*}$ , where $I_{m_1}^{*}$ represents endemic state of infected compartment (Mubayi et al., 2010). Hence, the underreporting proportion is given by

$\begin{array}{l}\hfill p=\frac{\text{Reported cases per unit of time}}{\left(\frac{m_1{\eta }_h}{k_1{\alpha }_h+{\mu }_h}\right)P_1^{m_1-1}{P}_2^{n_1}(1-P_1)\left(1-\frac{1-B_1}{A_1}\right)},\end{array}$

where $A=P_2^{n_1}$ , $B={\sum }_{i=0}^{m_1-1}{P}_1^i$ , $A_1=\frac{{\lambda }_{v}AB}{{\lambda }_{v}AB+{\mu }_v}$ , $B_1=\frac{{\lambda }_h{P}_3^{n_2}}{{\lambda }_h{P}_3^{n_2}+{\mu }_h}$ , $P_1=\frac{m_1{\eta }_h}{m_1{\eta }_h+{\mu }_h}$ , $P_2=\frac{n_1{\gamma }_h}{n_1{\gamma }_h+{\mu }_h}$ , and $P_3=\frac{n_2{\gamma }_v}{n_2{\gamma }_v+{\mu }_v}$ and the reproduction number of the system is

$\begin{array}{l}\hfill R_c=\sqrt{\frac{B_1}{1-A_1}\cdot \frac{A_1}{1-B_1}}\end{array}$

The true or adjusted incidence of a region is

$\begin{array}{ll}\mathit{Adjusted}\mathit{incidence}=& \mathit{Reported}\mathit{incidence}\mathit{(public}\mathit{facilities)}\hfill \\ & +\mathit{Unreported}\mathit{incidence}\mathit{(private}\mathit{facilities)}\hfill \end{array}$

and then using adjusted incidence high-risk districts can be identified if the adjusted proportion of cases in the district (as compared to other districts) is greater than proportion of population in that district.

Read full chapter

URL:

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

Queueing Theory

Sheldon Ross , in Introduction to Probability Models (Eleventh Edition), 2014

8.8 A Finite Source Model

Consider a system of $m$ machines, whose working times are independent exponential random variables with rate $\lambda$ . Upon failure, a machine instantly goes to a repair facility that consists of a single repairperson. If the repairperson is free, repair begins on the machine; otherwise, the machine joins the queue of failed machines. When a machine is repaired it becomes a working machine, and repair begins on a new machine from the queue of failed machines (provided the queue is nonempty). The successive repair times are independent random variables having density function $g$ , with mean

${\mu }_R={\int }_0^{\infty }\mathit{xg}(x)\mathit{dx}$

To analyze this system, so as to determine such quantities as the average number of machines that are down and the average time that a machine is down, we will exploit the exponentially distributed working times to obtain a Markov chain. Specifically, let $X_n$ denote the number of failed machines immediately after the $n$ th repair occurs, $n⩾1$ . Now, if $X_n=i>0$ , then the situation when the $n$ th repair has just occurred is that repair is about to begin on a machine, there are $i-1$ other machines waiting for repair, and there are $m-i$ working machines, each of which will (independently) continue to work for an exponential time with rate $\lambda$ . Similarly, if $X_n=0$ , then all $m$ machines are working and will (independently) continue to do so for exponentially distributed times with rate $\lambda$ . Consequently, any information about earlier states of the system will not affect the probability distribution of the number of down machines at the moment of the next repair completion; hence, $\{X_n\text{,}n⩾1\}$ is a Markov chain. To determine its transition probabilities $P_{i\text{,}j}$ , suppose first that $i>0$ . Conditioning on $R$ , the length of the next repair time, and making use of the independence of the $m-i$ remaining working times, yields that for $j⩽m-i$

$\begin{array}{cc}\hfill P_{i\text{,}i-1+j}=& P\{j\text{failures during}R\}\hfill \\ \hfill =& {\int }_0^{\infty }P\{j\text{failures during}R\mid R=r\}g(r)\mathit{dr}\hfill \\ \hfill =& {\int }_0^{\infty }\left(\begin{array}{c}\hfill m-i\hfill \\ \hfill j\hfill \end{array}\right){(1-e^{-\lambda r})}^j{(e^{-\lambda r})}^{m-i-j}g(r)\mathit{dr}\hfill \end{array}$

If $i=0$ , then, because the next repair will not begin until one of the machines fails,

$P_{0\text{,}j}=P_{1\text{,}j}\text{,}j⩽m-1$

Let ${\pi }_j\text{,}j=0\text{,}\dots \text{,}m-1$ , denote the stationary probabilities of this Markov chain. That is, they are the unique solution of

$\begin{array}{cc}\hfill {\pi }_j=& {\displaystyle \sum _i}{\pi }_i{P}_{i\text{,}j}\text{,}\hfill \\ \hfill {\displaystyle \sum _{j=0}^{m-1}}{\pi }_j=& 1\hfill \end{array}$

Therefore, after explicitly determining the transition probabilities and solving the preceding equations, we would know the value of ${\pi }_0$ , the proportion of repair completions that leaves all machines working. Let us say that the system is "on" when all machines are working and "off" otherwise. (Thus, the system is on when the repairperson is idle and off when he is busy.) As all machines are working when the system goes back on, it follows from the lack of memory property of the exponential that the system probabilistically starts over when it goes on. Hence, this on–off system is an alternating renewal process. Suppose that the system has just become on, thus starting a new cycle, and let $R_i\text{,}i⩾1$ , be the time of the $i$ th repair from that moment. Also, let $N$ denote the number of repairs in the off (busy) time of the cycle. Then, it follows that $B$ , the length of the off period, can be expressed as

$B={\displaystyle \sum _{i=1}^N}{R}_i$

Although $N$ is not independent of the sequence $R_1\text{,}{R}_2\text{,}\dots$   , it is easy to check that it is a stopping time for this sequence, and thus by Wald's equation (see Exercise 13 of Chapter 7) we have

$E[B]=E[N]E[R]=E[N]{\mu }_R$

Also, since an on time will last until one of the machines fails, and since the minimum of independent exponential random variables is exponential with a rate equal to the sum of their rates, it follows that $E[I]$ , the mean on (idle) time in a cycle, is given by

$E[I]=1/(m\lambda )$

Hence, $P_B$ , the proportion of time that the repairperson is busy, satisfies

$P_B=\frac{E[N]{\mu }_R}{E[N]{\mu }_R+1/(m\lambda )}$

However, since, on average, one out of every $E[N]$ repair completions will leave all machines working, it follows that

${\pi }_0=\frac{1}{E[N]}$

Consequently,

(8.58) $P_B=\frac{{\mu }_R}{{\mu }_R+{\pi }_0/(m\lambda )}$

Now focus attention on one of the machines, call it machine number 1, and let $P_{1\text{,}R}$ denote the proportion of time that machine 1 is being repaired. Since the proportion of time that the repairperson is busy is $P_B$ , and since all machines fail at the same rate and have the same repair distribution, it follows that

(8.59) $P_{1\text{,}R}=\frac{P_B}{m}=\frac{{\mu }_R}{m{\mu }_R+{\pi }_0/\lambda }$

However, machine 1 alternates between time periods when it is working, when it is waiting in queue, and when it is in repair. Let $W_i\text{,}{Q}_i\text{,}{S}_i$ denote, respectively, the $i$ th working time, the $i$ th queueing time, and the $i$ th repair time of machine 1, $i⩾1$ . Then, the proportion of time that machine 1 is being repaired during its first $n$ working–queue–repair cycles is as follows:

$\begin{array}{cc}\hfill & \text{proportion of time in the first}n\text{cycles that machine 1 is being repaired}\hfill \\ \hfill =& \frac{{\displaystyle {\sum }_{i=1}^n}{S}_i}{{\displaystyle {\sum }_{i=1}^n}{W}_i+{\displaystyle {\sum }_{i=1}^n}{Q}_i+{\displaystyle {\sum }_{i=1}^n}{S}_i}\hfill \\ \hfill =& \frac{{\displaystyle {\sum }_{i=1}^n}{S}_i/n}{{\displaystyle {\sum }_{i=1}^n}{W}_i/n+{\displaystyle {\sum }_{i=1}^n}{Q}_i/n+{\displaystyle {\sum }_{i=1}^n}{S}_i/n}\hfill \end{array}$

Letting $n\to \infty$ and using the strong law of large numbers to conclude that the averages of the $W_i$ and of the $S_i$ converge, respectively, to $1/\lambda$ and ${\mu }_R$ , yields

$P_{1\text{,}R}=\frac{{\mu }_R}{1/\lambda +\overline{Q}+{\mu }_R}$

where $\overline{Q}$ is the average amount of time that machine 1 spends in queue when it fails. Using Equation (8.59), the preceding gives

$\frac{{\mu }_R}{m{\mu }_R+{\pi }_0/\lambda }=\frac{{\mu }_R}{1/\lambda +\overline{Q}+{\mu }_R}$

or, equivalently, that

$\overline{Q}=(m-1){\mu }_R-(1-{\pi }_0)/\lambda$

Moreover, since all machines are probabilistically equivalent it follows that $\overline{Q}$ is equal to $W_Q$ , the average amount of time that a failed machine spends in queue. To determine the average number of machines in queue, we will make use of the basic queueing identity

$L_Q={\lambda }_a{W}_Q={\lambda }_a\overline{Q}$

where ${\lambda }_a$ is the average rate at which machines fail. To determine ${\lambda }_a$ , again focus attention on machine 1 and suppose that we earn one per unit time whenever machine 1 is being repaired. It then follows from the basic cost identity of Equation (8.1) that

$P_{1\text{,}R}=r_1{\mu }_R$

where $r_1$ is the average rate at which machine 1 fails. Thus, from Equation (8.59), we obtain

$r_1=\frac{1}{m{\mu }_R+{\pi }_0/\lambda }$

Because all $m$ machines fail at the same rate, the preceding implies that

${\lambda }_a={\mathit{mr}}_1=\frac{m}{m{\mu }_R+{\pi }_0/\lambda }$

which gives that the average number of machines in queue is

$L_Q=\frac{m(m-1){\mu }_R-m(1-{\pi }_0)/\lambda }{m{\mu }_R+{\pi }_0/\lambda }$

Since the average number of machines being repaired is $P_B$ , the preceding, along with Equation (8.58), shows that the average number of down machines is

$L=L_Q+P_B=\frac{m^2{\mu }_R-m(1-{\pi }_0)/\lambda }{m{\mu }_R+{\pi }_0/\lambda }$

Read full chapter

URL:

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

Queueing Theory

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

8.8 A Finite Source Model

Consider a system of m machines, whose working times are independent exponential random variables with rate λ. Upon failure, a machine instantly goes to a repair facility that consists of a single repairperson. If the repairperson is free, repair begins on the machine; otherwise, the machine joins the queue of failed machines. When a machine is repaired it becomes a working machine, and repair begins on a new machine from the queue of failed machines (provided the queue is nonempty). The successive repair times are independent random variables having density function g, with mean

${\mu }_R={\int }_0^{\infty }xg(x)dx$

To analyze this system, so as to determine such quantities as the average number of machines that are down and the average time that a machine is down, we will exploit the exponentially distributed working times to obtain a Markov chain. Specifically, let $X_n$ denote the number of failed machines immediately after the nth repair occurs, $n\ge 1$ . Now, if $X_n=i>0$ , then the situation when the nth repair has just occurred is that repair is about to begin on a machine, there are $i-1$ other machines waiting for repair, and there are $m-i$ working machines, each of which will (independently) continue to work for an exponential time with rate λ. Similarly, if $X_n=0$ , then all m machines are working and will (independently) continue to do so for exponentially distributed times with rate λ. Consequently, any information about earlier states of the system will not affect the probability distribution of the number of down machines at the moment of the next repair completion; hence, $\{X_n,n\ge 1\}$ is a Markov chain. To determine its transition probabilities $P_{i,j}$ , suppose first that $i>0$ . Conditioning on R, the length of the next repair time, and making use of the independence of the $m-i$ remaining working times, yields that for $j\le m-i$

$\begin{array}{cc}\hfill P_{i,i-1+j}=& P\{j\text{failures during}R\}\hfill \\ \hfill =& {\int }_0^{\infty }P\{j\text{failures during}R|R=r\}g(r)dr\hfill \\ \hfill =& {\int }_0^{\infty }\left(\begin{array}{c}\hfill m-i\hfill \\ \hfill j\hfill \end{array}\right){(1-e^{-\lambda r})}^j{(e^{-\lambda r})}^{m-i-j}g(r)dr\hfill \end{array}$

If $i=0$ , then, because the next repair will not begin until one of the machines fails,

$P_{0,j}=P_{1,j},j\le m-1$

Let ${\pi }_j,j=0,\dots ,m-1$ , denote the stationary probabilities of this Markov chain. That is, they are the unique solution of

$\begin{array}{cc}\hfill {\pi }_j=& \sum _i{\pi }_i{P}_{i,j},\hfill \\ \hfill \sum _{j=0}^{m-1}{\pi }_j=& 1\hfill \end{array}$

Therefore, after explicitly determining the transition probabilities and solving the preceding equations, we would know the value of ${\pi }_0$ , the proportion of repair completions that leaves all machines working. Let us say that the system is "on" when all machines are working and "off" otherwise. (Thus, the system is on when the repairperson is idle and off when he is busy.) As all machines are working when the system goes back on, it follows from the lack of memory property of the exponential that the system probabilistically starts over when it goes on. Hence, this on–off system is an alternating renewal process. Suppose that the system has just become on, thus starting a new cycle, and let $R_i,i\ge 1$ , be the time of the ith repair from that moment. Also, let N denote the number of repairs in the off (busy) time of the cycle. Then, it follows that B, the length of the off period, can be expressed as

$B=\sum _{i=1}^N{R}_i$

Although N is not independent of the sequence $R_1,R_2,\dots$   , it is easy to check that it is a stopping time for this sequence, and thus by Wald's equation (see Exercise 13 of Chapter 7) we have

$E[B]=E[N]E[R]=E[N]{\mu }_R$

Also, since an on time will last until one of the machines fails, and since the minimum of independent exponential random variables is exponential with a rate equal to the sum of their rates, it follows that $E[I]$ , the mean on (idle) time in a cycle, is given by

$E[I]=1/(m\lambda )$

Hence, $P_B$ , the proportion of time that the repairperson is busy, satisfies

$P_B=\frac{E[N]{\mu }_R}{E[N]{\mu }_R+1/(m\lambda )}$

However, since, on average, one out of every $E[N]$ repair completions will leave all machines working, it follows that

${\pi }_0=\frac{1}{E[N]}$

Consequently,

(8.58) $P_B=\frac{{\mu }_R}{{\mu }_R+{\pi }_0/(m\lambda )}$

Now focus attention on one of the machines, call it machine number 1, and let $P_{1,R}$ denote the proportion of time that machine 1 is being repaired. Since the proportion of time that the repairperson is busy is $P_B$ , and since all machines fail at the same rate and have the same repair distribution, it follows that

(8.59) $P_{1,R}=\frac{P_B}{m}=\frac{{\mu }_R}{m{\mu }_R+{\pi }_0/\lambda }$

However, machine 1 alternates between time periods when it is working, when it is waiting in queue, and when it is in repair. Let $W_i,Q_i,S_i$ denote, respectively, the ith working time, the ith queueing time, and the ith repair time of machine 1, $i\ge 1$ . Then, the proportion of time that machine 1 is being repaired during its first n working–queue–repair cycles is as follows:

$\begin{array}{cc}\hfill & \text{proportion of time in the first}n\text{cycles that machine 1 is being repaired}\hfill \\ \hfill & =\frac{{\sum }_{i=1}^n{S}_i}{{\sum }_{i=1}^n{W}_i+{\sum }_{i=1}^n{Q}_i+{\sum }_{i=1}^n{S}_i}\hfill \\ \hfill & =\frac{{\sum }_{i=1}^n{S}_i/n}{{\sum }_{i=1}^n{W}_i/n+{\sum }_{i=1}^n{Q}_i/n+{\sum }_{i=1}^n{S}_i/n}\hfill \end{array}$

Letting $n\to \infty$ and using the strong law of large numbers to conclude that the averages of the $W_i$ and of the $S_i$ converge, respectively, to $1/\lambda$ and ${\mu }_R$ , yields

$P_{1,R}=\frac{{\mu }_R}{1/\lambda +\overline{Q}+{\mu }_R}$

where $\overline{Q}$ is the average amount of time that machine 1 spends in queue when it fails. Using Eq. (8.59), the preceding gives

$\frac{{\mu }_R}{m{\mu }_R+{\pi }_0/\lambda }=\frac{{\mu }_R}{1/\lambda +\overline{Q}+{\mu }_R}$

or, equivalently, that

$\overline{Q}=(m-1){\mu }_R-(1-{\pi }_0)/\lambda$

Moreover, since all machines are probabilistically equivalent it follows that $\overline{Q}$ is equal to $W_Q$ , the average amount of time that a failed machine spends in queue. To determine the average number of machines in queue, we will make use of the basic queueing identity

$L_Q={\lambda }_a{W}_Q={\lambda }_a\overline{Q}$

where ${\lambda }_a$ is the average rate at which machines fail. To determine ${\lambda }_a$ , again focus attention on machine 1 and suppose that we earn one per unit time whenever machine 1 is being repaired. It then follows from the basic cost identity of Eq. (8.1) that

$P_{1,R}=r_1{\mu }_R$

where $r_1$ is the average rate at which machine 1 fails. Thus, from Eq. (8.59), we obtain

$r_1=\frac{1}{m{\mu }_R+{\pi }_0/\lambda }$

Because all m machines fail at the same rate, the preceding implies that

${\lambda }_a=m{r}_1=\frac{m}{m{\mu }_R+{\pi }_0/\lambda }$

which gives that the average number of machines in queue is

$L_Q=\frac{m(m-1){\mu }_R-m(1-{\pi }_0)/\lambda }{m{\mu }_R+{\pi }_0/\lambda }$

Since the average number of machines being repaired is $P_B$ , the preceding, along with Eq. (8.58), shows that the average number of down machines is

$L=L_Q+P_B=\frac{m^2{\mu }_R-m(1-{\pi }_0)/\lambda }{m{\mu }_R+{\pi }_0/\lambda }$

Read full chapter

URL:

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

Special Random Variables

Sheldon M. Ross , in Introduction to Probability and Statistics for Engineers and Scientists (Fifth Edition), 2014

5.6 Exponential Random Variables

A continuous random variable whose probability density function is given, for some λ > 0, by

$f\left(x\right)=\{\begin{array}{ll}\text{λ}{e}^{-\text{λ}x}\hfill & ifx\ge 0\hfill \\ 0\hfill & ifx<0\hfill \end{array}$

is said to be an exponential random variable (or, more simply, is said to be exponentially distributed) with parameter λ. The cumulative distribution function F(x) of an exponential random variable is given by

$\begin{array}{ll}F\left(x\right)\hfill & =P\left\{X\le x\right\}\hfill \\ \hfill & ={\displaystyle {\int }_0^x\text{λ}{e}^{-\text{λ}y}dy}\hfill \\ \hfill & \begin{array}{ll}=1-e^{-\text{λ}x},\hfill & x\ge 0\hfill \end{array}\hfill \end{array}$

The exponential distribution often arises, in practice, as being the distribution of the amount of time until some specific event occurs. For instance, the amount of time (starting from now) until an earthquake occurs, or until a new war breaks out, or until a telephone call you receive turns out to be a wrong number are all random variables that tend in practice to have exponential distributions (see Section 5.6.1 for an explanation).

The moment generating function of the exponential is given by

$\begin{array}{ll}\varphi \left(t\right)\hfill & =E\left[e^{tX}\right]\hfill \\ \hfill & ={\displaystyle {\int }_0^{\infty }{e}^{tX}\text{λ}{e}^{-\text{λ}x}dx}\hfill \\ \hfill & =\text{λ}{\displaystyle {\int }_0^{\infty }{e}^{-\left(\text{λ}-t\right)x}dx}\hfill \\ \hfill & \begin{array}{ll}=\frac{\text{λ}}{\text{λ}-t},\hfill & t<\text{λ}\hfill \end{array}\hfill \end{array}$

Differentiation yields

$\begin{array}{ll}{\varphi }^{\prime }\left(t\right)\hfill & =\frac{\text{λ}}{{\left(\text{λ}-t\right)}^2}\hfill \\ {\varphi }^{″}\left(t\right)\hfill & =\frac{2\text{λ}}{{\left(\text{λ}-t\right)}^3}\hfill \end{array}$

and so

$\begin{array}{ll}\hfill E\left[X\right]& ={\varphi }^{\prime }\left(0\right)=1/\text{λ}\hfill \\ \hfill \text{V}\text{a}\text{r}\left(X\right)& ={\varphi }^{″}\left(0\right)-{\left(E\left[X\right]\right)}^2\hfill \\ \hfill & =2/{\text{λ}}^2-1/{\text{λ}}^2\hfill \\ \hfill & =1/{\text{λ}}^2\hfill \end{array}$

Thus λ is the reciprocal of the mean, and the variance is equal to the square of the mean.

The key property of an exponential random variable is that it is memoryless, where we say that a nonnegative random variable X is memoryless if

(5.6.1) $\begin{array}{ll}P\left\{X>s+t|X>t\right\}=P\left\{X>s\right\}\hfill & \text{for}\text{all}s,t\ge 0\hfill \end{array}$

To understand why Equation 5.6.1 is called the memoryless property, imagine that X represents the length of time that a certain item functions before failing. Now let us consider the probability that an item that is still functioning at age t will continue to function for at least an additional time s. Since this will be the case if the total functional lifetime of the item exceeds t  + s given that the item is still functioning at t, we see that

$P\left\{\text{additional\hspace{0.17em}functional\hspace{0.17em}life\hspace{0.17em}of}t\text{-unit-old\hspace{0.17em}item\hspace{0.17em}exceeds}s\right\}=P\left\{X>t+s|X>t\right\}$

Thus, we see that Equation 5.6.1 states that the distribution of additional functional life of an item of age t is the same as that of a new item — in other words, when Equation 5.6.1 is satisfied, there is no need to remember the age of a functional item since as long as it is still functional it is "as good as new."

The condition in Equation 5.6.1 is equivalent to

$\frac{P\left\{X>s+t,X>t\right\}}{P\left\{X>t\right\}}=P\left\{X>s\right\}$

or

(5.6.2) $P\left\{X>s+t\right\}=P\left\{X>s\right\}P\left\{X>t\right\}$

When X is an exponential random variable, then

$\begin{array}{ll}P\left\{X>x\right\}=e^{-\text{λ}x},\hfill & x>0\hfill \end{array}$

and so Equation 5.6.2 is satisfied (since $e^{-\text{λ}\left(s+t\right)}=e^{-\text{λ}s}{e}^{-\text{λ}t}$ ). Hence, exponentially distributed random variables are memoryless (and in fact it can be shown that they are the only random variables that are memoryless).

Example 5.6a

Suppose that a number of miles that a car can run before its battery wears out is exponentially distributed with an average value of 10,000 miles. If a person desires to take a 5,000-mile trip, what is the probability that she will be able to complete her trip without having to replace her car battery? What can be said when the distribution is not exponential?

Solution

It follows, by the memoryless property of the exponential distribution, that the remaining lifetime (in thousands of miles) of the battery is exponential with parameter λ   =   1/10. Hence the desired probability is

$\begin{array}{ll}P\left\{\text{r}\text{e}\text{m}\text{a}\text{i}\text{n}\text{i}\text{n}\text{g}\text{l}\text{i}\text{f}\text{e}\text{t}\text{i}\text{m}\text{e}>5\right\}\hfill & =1-F\left(5\right)\hfill \\ \hfill & =e^{-5\text{λ}}\hfill \\ \hfill & =e^{-1/2}\approx .604\hfill \end{array}$

However, if the lifetime distribution F is not exponential, then the relevant probability is

$P\left\{\text{l}\text{i}\text{f}\text{e}\text{t}\text{i}\text{m}\text{e}>t+5|\text{l}\text{i}\text{f}\text{e}\text{t}\text{i}\text{m}\text{e}>t\right\}=\frac{1-F\left(t+5\right)}{1-F\left(t\right)}$

where t is the number of miles that the battery had been in use prior to the start of the trip. Therefore, if the distribution is not exponential, additional information is needed (namely, t) before the desired probability can be calculated.■

For another illustration of the memoryless property, consider the following example.

Example 5.6b

A crew of workers has 3 interchangeable machines, of which 2 must be working for the crew to do its job. When in use, each machine will function for an exponentially distributed time having parameter λ before breaking down. The workers decide initially to use machines A and B and keep machine C in reserve to replace whichever of A or B breaks down first. They will then be able to continue working until one of the remaining machines breaks down. When the crew is forced to stop working because only one of the machines has not yet broken down, what is the probability that the still operable machine is machine C?

Solution

This can be easily answered, without any need for computations, by invoking the memoryless property of the exponential distribution. The argument is as follows: Consider the moment at which machine C is first put in use. At that time either A or B would have just broken down and the other one — call it machine 0 — will still be functioning. Now even though 0 would have already been functioning for some time, by the memoryless property of the exponential distribution, it follows that its remaining lifetime has the same distribution as that of a machine that is just being put into use. Thus, the remaining lifetimes of machine 0 and machine C have the same distribution and so, by symmetry, the probability that 0 will fail before C is $\frac{1}{2}$ .■

The following proposition presents another property of the exponential distribution.

Proposition 5.6.1

If X ₁, X ₂,…, X_n are independent exponential random variables having respective parameters λ₁, λ₂,…, λ _n , then min(X ₁,X ₂,…,X_n ) is exponential with parameter ${\displaystyle {\sum }_{t=1}^n{\text{λ}}_i}$ .

Proof

Since the smallest value of a set of numbers is greater than x if and only if all values are greater than x, we have

$\begin{array}{ll}P\left\{\min \left(X_1,X_2,\dots ,X_n\right)>x\right\}\hfill & =P\left\{X_1>x,X_2>x,\dots ,X_n>x\right\}\hfill \\ \hfill & \begin{array}{ll}={\displaystyle \prod _{i=1}^{n}P\left\{X_i>x\right\}}\hfill & \text{b}\text{y}\text{i}\text{n}\text{d}\text{e}\text{p}\text{e}\text{n}\text{d}\text{e}\text{n}\text{c}\text{e}\hfill \end{array}\hfill \\ \hfill & ={\displaystyle \prod _{i=1}^n{e}^{-{\text{λ}}_{i}x}}\hfill \\ \hfill & =e^{-{\displaystyle {\sum }_{i=1}^n{\text{λ}}_{i}x}}\hfill \end{array}$

■

Example 5.6c

A series system is one that needs all of its components to function in order for the system itself to be functional. For an n-component series system in which the component lifetimes are independent exponential random variables with respective parameters λ₁, λ₂,…, λ _n , what is the probability that the system survives for a time t?

Solution

Since the system life is equal to the minimal component life, it follows from Proposition 5.6.1 that

$P\left\{\text{s}\text{y}\text{s}\text{t}\text{e}\text{m}\text{l}\text{i}\text{f}\text{e}\text{e}\text{x}\text{c}\text{e}\text{e}\text{d}\text{s}t\right\}=e^{-{\displaystyle {\sum }_i{\text{λ}}_{i}t}}$

■

Another useful property of exponential random variables is that cX is exponential with parameter λ/c when X is exponential with parameter λ, and c > 0. This follows since

$\begin{array}{ll}P\left\{cX\le x\right\}\hfill & =P\left\{X\le x/c\right\}\hfill \\ \hfill & =1-e^{-\text{λ}x/c}\hfill \end{array}$

The parameter λ is called the rate of the exponential distribution.

5.6.1 *The Poisson Process

Suppose that "events" are occurring at random time points, and let N(t) denote the number of events that occurs in the time interval [0, t]. These events are said to constitute a Poisson process having rate λ, λ > 0, if

(a)

N(0) = 0

(b)

The number of events that occur in disjoint time intervals are independent.

(c)

The distribution of the number of events that occur in a given interval depends only on the length of the interval and not on its location.

(d)

$\underset{h\to 0}{\lim }\frac{P\left\{N\left(h\right)=1\right\}}{h}=\text{λ}$

(e)

$\underset{h\to 0}{\lim }\frac{P\left\{N\left(h\right)\ge 2\right\}}{h}=0$

Thus, Condition (a) states that the process begins at time 0. Condition (b), the independent increment assumption, states for instance that the number of events by time t [that is, N(t)] is independent of the number of events that occurs between t and t  + s [that is, N(t  + s) – N(t)]. Condition (c), the stationary increment assumption, states that probability distribution of N(t  + s) – N(t) is the same for all values of t. Conditions (d) and (e) state that in a small interval of length h, the probability of one event occurring is approximately λh, whereas the probability of 2 or more is approximately 0.

We will now show that these assumptions imply that the number of events occurring in any interval of length t is a Poisson random variable with parameter λt. To be precise, let us call the interval [0, t] and denote by N(t) the number of events occurring in that interval. To obtain an expression for P{N(t)   = k}, we start by breaking the interval [0, t] into n nonoverlapping subintervals each of length t/n (Figure 5.10). Now there will be k events in [0, t] if either

Figure 5.10.

(i)

N(t) equals k and there is at most one event in each subinterval;

(ii)

N(t) equals k and at least one of the subintervals contains 2 or more events.

Since these two possibilities are clearly mutually exclusive, and since Condition (i) is equivalent to the statement that k of the n subintervals contain exactly 1 event and the other n – k contain 0 events, we have that

(5.6.3) $\begin{array}{ll}P\left\{N\left(t\right)=k\right\}=\hfill & P\{k\text{of\hspace{0.17em}the}n\text{subintervals\hspace{0.17em}contain\hspace{0.17em}exactly\hspace{0.17em}1\hspace{0.17em}event}\hfill \\ \hfill & \text{a}\text{n}\text{d}\text{t}\text{h}\text{e}\text{o}\text{t}\text{h}\text{e}\text{r}n-k\text{c}\text{o}\text{n}\text{t}\text{a}\text{i}\text{n}0\text{e}\text{v}\text{e}\text{n}\text{t}\text{s}\}+P\{N\left(t\right)=k\hfill \\ \hfill & \text{and\hspace{0.17em}at\hspace{0.17em}least\hspace{0.17em}1\hspace{0.17em}subinterval\hspace{0.17em}contains\hspace{0.17em}2\hspace{0.17em}or\hspace{0.17em}more\hspace{0.17em}events}\}\hfill \end{array}$

Now it can be shown, using Condition (e), that

(5.6.4) $\begin{array}{c}P\left\{N\left(t\right)=k\text{\hspace{0.17em}and\hspace{0.17em}at\hspace{0.17em}least\hspace{0.17em}1\hspace{0.17em}subinterval\hspace{0.17em}contains\hspace{0.17em}2\hspace{0.17em}or\hspace{0.17em}more\hspace{0.17em}events}\right\}\\ \to 0\text{a}\text{s}n\to \infty \end{array}$

Also, it follows from Conditions (d) and (e) that

$\begin{array}{ll}\hfill P\left\{\text{exactly\hspace{0.17em}1\hspace{0.17em}event\hspace{0.17em}in\hspace{0.17em}a\hspace{0.17em}subinterval}\right\}& \approx \frac{\text{λ}t}{n}\hfill \\ \hfill P\left\{\text{0\hspace{0.17em}events\hspace{0.17em}in\hspace{0.17em}a\hspace{0.17em}subinterval}\right\}& \approx 1-\frac{\text{λ}t}{n}\hfill \end{array}$

Hence, since the number of events that occur in different subintervals are independent [from Condition (b)], it follows that

(5.6.5) $\begin{array}{l}P\left\{k\text{of}\text{the}\text{subintervals}\text{contain}\text{exactly}\text{1}\text{event}\text{and}\text{the}\text{other}n-k\text{contain\hspace{0.17em}0}\text{events}\right\}\hfill \\ \approx \left(\begin{array}{c}n\\ k\end{array}\right){\left(\frac{\text{λ}t}{n}\right)}^k{\left(1-\frac{\text{λ}t}{n}\right)}^{n-k}\hfill \end{array}$

with the approximation becoming exact as the number of subintervals, n, goes to ∞. However, the probability in Equation 5.6.5 is just the probability that a binomial random variable with parameters n and p  =   λt/n equals k. Hence, as n becomes larger and larger, this approaches the probability that a Poisson random variable with mean nλt/n  =   λt equals k. Hence, from Equations 5.6.3, 5.6.4, and 5.6.5, we see upon letting n approach ∞ that

$P\left\{N\left(t\right)=k\right\}=e^{-\text{λ}t}\frac{{\left(\text{λ}t\right)}^k}{k!}$

We have shown:

Proposition 5.6.2

For a Poisson process having rate λ

$\begin{array}{cc}P\left\{N\left(t\right)=k\right\}=e^{-\text{λ}t}\frac{{\left(\text{λ}t\right)}^k}{k!},& k=0,1,\dots \end{array}$

That is, the number of events in any interval of length t has a Poisson distribution with mean λt.

For a Poisson process, let X ₁ denote the time of the first event. Further, for n > 1, let X_n denote the elapsed time between (n – 1)st and the nth events. The sequence (X_n , n  =   1,2,…} is called the sequence of interarrival times. For instance, if X ₁  =   5 and X ₂  =   10, then the first event of the Poisson process would have occurred at time 5 and the second at time 15.

We now determine the distribution of the X_n . To do so, we first note that the event {X ₁ > t} takes place if and only if no events of the Poisson process occur in the interval [0, t], and thus,

$P\left\{X_1>t\right\}=P\left\{N\left(t\right)=0\right\}=e^{-\text{λ}t}$

Hence, X ₁ has an exponential distribution with mean 1/λ. To obtain the distribution of X ₂, note that

$\begin{array}{ll}P\left\{X_2>t|X_1=s\right\}\hfill & =P\left\{0\text{e}\text{v}\text{e}\text{n}\text{t}\text{s}\text{i}\text{n}(s,s+t]|X_1=s\right\}\hfill \\ \hfill & =P\left\{0\text{e}\text{v}\text{e}\text{n}\text{t}\text{s}\text{i}\text{n}(s,s+t]\right\}\hfill \\ \hfill & =e^{-\text{λ}t}\hfill \end{array}$

where the last two equations followed from independent and stationary increments. Therefore, from the foregoing we see that X₂ is also an exponential random variable with mean 1/λ, and furthermore, that X ₂ is independent of X ₁. Repeating the same argument yields:

Proposition 5.6.3

X ₁, X ₂,… are independent exponential random variables, each with mean 1/λ.

5.6.2 *The Pareto Distribution

If X is an exponential random variable with rate λ, then

$Y=\alpha e^X$

is said to be a Pareto random variable with parameters α and λ. The parameter λ > 0 is called the index parameter, and α is called the minimum parameter (because P(Y ≥ α)   =   1). The distribution function of Y is derived as follows: For y ≥ α,

$\begin{array}{ll}P\left\{Y>y\right\}\hfill & =P\left\{\alpha e^X>y\right\}\hfill \\ \hfill & =P\left\{e^X>y/\alpha \right\}\hfill \\ \hfill & =P\left\{X>\log \left(y/\alpha \right)\right\}\hfill \\ \hfill & =e^{{-}^{\text{λ}\log \left(y/\alpha \right)}}\hfill \\ \hfill & =e^{-\log \left({\left(y/\alpha \right)}^{\text{λ}}\right)}\hfill \\ \hfill & ={\left(\alpha /y\right)}^{\text{λ}}\hfill \end{array}$

Hence, the distribution function of Y is

$\begin{array}{ll}{F}_Y\left(y\right)=1-P\left(Y>y\right)=1-{\alpha }^{\text{λ}}{y}^{-\text{λ}},\hfill & y\ge \alpha \hfill \end{array}$

Differentiating the distribution function yields the density function of Y:

$\begin{array}{ll}{f}_Y\left(y\right)=\text{λ}{\alpha }^{\text{λ}}{y}^{-\left(\text{λ}+1\right)},\hfill & y\ge \alpha \hfill \end{array}$

It can be shown (see Problem 5-49) that E[Y]   =   ∞ when λ ≤ 1. When λ > 1, the mean is obtained as follows.

$\begin{array}{ll}E\left[Y\right]\hfill & ={\displaystyle {\int }_{\alpha }^{\infty }y\text{λ}{\alpha }^{\text{λ}}{y}^{-\left(\text{λ}+1\right)}dy}\hfill \\ \hfill & =\text{λ}{\alpha }^{\text{λ}}{\displaystyle {\int }_{\alpha }^{\infty }{y}^{-\text{λ}}dy}\hfill \\ \hfill & ={\alpha }^{\text{λ}}\frac{\text{λ}}{1-\text{λ}}{y}^{1-\text{λ}}{|}_{\alpha }^{\infty }\hfill \\ \hfill & ={\alpha }^{\text{λ}}\frac{\text{λ}}{\text{λ}-1}{\alpha }^{1-\text{λ}}\hfill \\ \hfill & =\alpha \frac{\text{λ}}{\text{λ}-1}\hfill \end{array}$

An important feature of Pareto distributions is that for y ₀ > α the conditional distribution of a Pareto random variable Y with parameters α and λ, given that it exceeds y ₀, is the Pareto distribution with parameters y ₀ and λ. To verify this, note for y > y ₀ that

$P\left\{Y>y|Y>y_0\right\}=\frac{P\left\{Y>y,Y>y_0\right\}}{P\left\{Y>y_0\right\}}=\frac{P\left\{Y>y\right\}}{P\left\{Y>y_0\right\}}=\frac{{\alpha }^{\text{λ}}{y}^{-\text{λ}}}{{\alpha }^{\text{λ}}{y}_0^{-\text{λ}}}=y_0^{\text{λ}}{y}^{-\text{λ}}$

Thus, the conditional distribution is indeed Pareto with parameters y ₀ and λ.

One of the earliest uses of the Pareto was as the distribution of the annual income of the members of a population. In fact, it has been widely supposed that incomes in many populations can be modeled as coming from a Pareto distribution with index parameter λ   =   log(5)/log(4) ≈ 1.161. Under this supposition, it turns out that the total income of the top 20 percent of earners is 80 percent of the population's total income earnings, and that the top 20 percent of these high earners earn 80 percent of the total of all high earners income, and that the top 20 percent of these very high earners earn 80 percent of the total of all very high earners income, and so on.

To verify the preceding claim, let y _.8 be the 80 percentile of the Pareto distribution. Because F_Y (y)   =   1 – (α/y)^λ, we see that .8   = F(y _.8)   =   1 – (α/y _.8)^λ, showing that

$\begin{array}{lll}{\left(\alpha /y_{.8}\right)}^{\text{λ}}=.2\hfill & or\hfill & {\left(y_{.8}/\alpha \right)}^{\text{λ}}=5\hfill \end{array}$

and thus

$y_{.8}=\alpha 5^{1/\text{λ}}$

Now suppose, from this point on, that λ   =   log(5)/log(4), and note that log(4)   =   (1/λ) log(5)   =   log(5^1/λ), showing that 4   =   5^1/λ, or equivalently that 1/λ   =   log₅(4). Hence,

$y_{.8}=\alpha 5^{{\log }_5(4)}=4\alpha$

The average income of a randomly chosen individual in the top 20 percent is E[Y|Y > y _.8], which is easily obtained by using that the conditional distribution of Y given that it exceeds y _.8 is Pareto with parameters y _.8 and λ. Using the previously derived formula for E[Y], this yields that

$E\left[Y|Y>y_{.8}\right]=y_{.8}\frac{\text{λ}}{\text{λ}-1}=4\alpha \frac{\text{λ}}{\text{λ}-1}$

To obtain E[Y|Y < y _.8], the average income of a randomly chosen individual in the bottom 80 percent, we use the identity

$E\left[Y\right]=E\left[Y|Y<y_{.8}\right](.8)+E\left[Y|Y>y_{.8}\right]\left(.2\right)$

Using the previously derived expressions for E[Y] and E[Y|Y > y _.8], the preceding equation yields that

$\alpha \frac{\text{λ}}{\text{λ}-1}=\frac{4}{5}E\left[Y|Y<y_{.8}\right]+\frac{4}{5}\alpha \frac{\text{λ}}{\text{λ}-1}$

showing that

$E\left[Y|Y<y_{.8}\right]=\frac{\alpha }{4}\frac{\text{λ}}{\text{λ}-1}$

Thus,

$E\left[Y|Y<y_{.8}\right]=\frac{1}{16}E\left[Y|Y>y_{.8}\right]$

Hence, the average earnings of someone in the top 20 percent of income earned is 16 times that of someone in the lower 80 percent, thus showing that, although there are 4 times as many people in the lower earning group, the total income of the lower income group is only 20 percent of the total earnings of the population. (On average, for every 5 people in the population, 4 are in the lower 80 percent and 1 is in the upper 20 percent; the 4 in the lower earnings group earn on average a total of $4\frac{a}{4}\frac{\text{λ}}{\text{λ}-1}=a\frac{\text{λ}}{\text{λ}-1}$ , whereas the one in the higher income group earns on average $4a\frac{\text{λ}}{\text{λ}-1}$ . Thus, 4 out of every 5 dollars of the population's total income is earned by someone in the highest 20 percent.)

Because the conditional distribution of a high income earner (that is, one who earns more than y _.8) is Pareto with parameters y _.8 and λ, it also follows from the preceding that 80 percent of the total of the earnings of this group are earned by the top 20 percent of these high earners, and so on.

The Pareto distribution has been applied in a variety of areas. For instance, it has been used as the distribution of

(a)

the file size of internet traffic (under the TCP protocol);

(b)

the time to compete a job assigned to a supercomputer;

(c)

the size of a meteorite;

(d)

the yearly maximum one day rainfalls in different regions.

Read full chapter

URL:

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

hoyleexcume.blogspot.com

Source: https://www.sciencedirect.com/topics/mathematics/exponentially-distributed-time

Share this post