Skip to main content
main-content

Über dieses Buch

A stochastic process {X(t): 0 S t < =} with discrete state space S c ~ is said to be stochastically increasing (decreasing) on an interval T if the probabilities Pr{X(t) > i}, i E S, are increasing (decreasing) with t on T. Stochastic monotonicity is a basic structural property for process behaviour. It gives rise to meaningful bounds for various quantities such as the moments of the process, and provides the mathematical groundwork for approximation algorithms. Obviously, stochastic monotonicity becomes a more tractable subject for analysis if the processes under consideration are such that stochastic mono tonicity on an inter­ val 0 < t < E implies stochastic monotonicity on the entire time axis. DALEY (1968) was the first to discuss a similar property in the context of discrete time Markov chains. Unfortunately, he called this property "stochastic monotonicity", it is more appropriate, however, to speak of processes with monotone transition operators. KEILSON and KESTER (1977) have demonstrated the prevalence of this phenomenon in discrete and continuous time Markov processes. They (and others) have also given a necessary and sufficient condition for a (temporally homogeneous) Markov process to have monotone transition operators. Whether or not such processes will be stochas­ tically monotone as defined above, now depends on the initial state distribution. Conditions on this distribution for stochastic mono tonicity on the entire time axis to prevail were given too by KEILSON and KESTER (1977).

Inhaltsverzeichnis

Frontmatter

1. Preliminaries

Abstract
By a Markov process we shall understand a continuous time stochastic process {X(t): 0 ≤ t < ∞} which has a denumerable state space S and which possesses the Markov property, i.e., for every n ≥ 2, 0 ≤ t1 <.....< tn and any i1,...., in in S one has
$$\Pr \left\{ {X\left( {{t_{n}}} \right) = \left| {X\left( {{t_{1}}} \right) = {i_{{1,....,}}}} \right.X\left( {{t_{{n - 1}}}} \right) = {i_{{n - 1}}}} \right\} = \Pr \left\{ {X\left( {{t_{n}}} \right) = {i_{n}}\left| {X\left( {{t_{{n - 1}}}} \right)} \right.{i_{{n - 2}}}} \right\}$$
(1.1.1)
, The process is supposed to be temporally homogeneous, i.e., for every i, j in S the conditional probability Pr{X(t+s) = j| X(s) = i} does not depend on s. In this case we may put
$$Pi\left( t \right) = \Pr \left\{ {X\left( t \right) = i} \right\},\sum\limits_{i} {{P_{{i\left( t \right)}}}} = 1.$$
(1.1.2)
t ≥ 0.
E. A. van Doorn

2. Natural Birth-Death Processes

Abstract
Let {λnn} be a set of birth-death parameters, A the associated generator (1.4.2) and {X(t): 0 ≤ t < ∞} a birth-death process with generator A. In this and the following chapters we shall be concerned with natural birth-death processes only, i.e., A is assumed to satisfy the conditions C(A) and D(A). The state -1 will be disregarded and the term transition matrix will be used for the matrix P(⋅) = (pij(⋅)), where i, j = 0, 1,....... Since the properties to be discussed in this chapter are independent of the initial distribution of the process, we shall often identify the birth-death process {X(t)} with its transition matrix P(.). KARLIN and McGREGOR (1957a, 1959b) have proved the following important feature of the transition matrix P(⋅) of a natural birth-death process: (2.1.1) P(t) is strictly totally positive (STP) for t > 0, which means that every subdeterminant of P(t) is strictly positive for t > 0. KARLIN and McGREGOR (1959a) showed that property (2.1.1) is characteristic for birth-death processes in the class of Markov processes as defined in section 1.1. An immediate conclusion from (2.1.1) is (2.1.2) pij(t) > 0 i, j = 0, 1,...; t > 0.
E. A. van Doorn

3. Dual Birth-Death Processes

Abstract
By G we shall denote the class of sets of birth-death parameters {λn, μn: n = 0, 1....} with μ0 = 0, and by G* the class of sets of birth-death parameters {λ n * , μ n * : n = 0, 1,...} with μ 0 * > 0. The mapping f: G → G* defined by
$$f\left( {\left\{ {{\lambda _{{n,{\mu _{n}}}}}} \right\}} \right) = \left\{ {\lambda _{n}^{ * },\mu _{n}^{ * }} \right\}$$
(3.3.1)
where
$$\lambda _{n}^{ * } = {\mu _{{n + 1}}},\mu _{n}^{ * } = {\lambda _{n}}$$
(3.1.2)
clearly establishes a 1 – 1 correspondence between the elements of G and G*. Now let {λnn} ∈ G and {λ n * , μ n * } = f({λnn})∈ G* be two related sets of birth-death parameters and {πn}, respectively {π n * }, the associated potential coefficients. The following identities are easily verified in view of (1.3.3) and (3.1.2).
$$n_{m}^{ * } = {\lambda _{o}}/{\lambda _{n}}{\pi _{n}}$$
(3.1.3)
and(3.1.4)
$${\pi _{n}} = \mu _{0}^{ * }/\mu _{n}^{ * }\pi _{n}^{ * }$$
(3.1.4)
E. A. van Doorn

4. Stochastic Monotonicity: General Results

Abstract
Let {λn, μn: n = 0, 1......}, with μ0 = 0, be the set of parameters of a natural birth-death process {X(t) : 0 ≤ t < ∞} where 0 is a reflecting barrier. The initial distribution vector of {X(t)} will be denoted by q = (q0, q1,....)T, i.e.,
$${q_{i}} = {p_{i}}\left( 0 \right) = \Pr \left\{ {X\left( 0 \right) = i} \right\}$$
(1)
otherwise the notation of section 1.4 will be used. We have
$$\underline {q \geqslant \underline 0 ,\underline {{q^{T}}\underline 1 } } = 1,$$
(4.1.1)
where vector inequality is defined by (1.2.15) and 0 and 1 are the column vectors consisting of 0’s and 1’s, respectively. We recall that
$$\underline {{P^{T}}\left( t \right)P\left( s \right)}$$
(4.1.2)
where pT(t) = (p0(t), p1(t),.....) with pi(t) = Pr{X(t) = i} and P(t) the transi­tion matrix of {X(t)}. More generally one has
$$\underline {{P^{T}}} \left( t \right)\underline 1 = 1,$$
(4.1.3)
From (1.4.14) and (4.1.1) it follows that for all t ≥ 0
$$\underline {{P^{T}}\left( t \right)} \underline 1 = 1,$$
(4.1.4)
so that p(t) is indeed a probability distribution vector.
E. A. van Doorn

5. Stochastic Monotonicity: Dependence on the Initial State Distribution

Abstract
In the first three sections of this chapter we consider a natural birth-death process for which 0 is a reflecting barrier with initial distribution vector q = (q0, q1,.....)T, where qn = δin for some fixed i and all n. The process is denoted by {Xi(t)} = {Xi (t): 0 ≤ t < ∞} and the corresponding time dependent vector defined by (4.1.7), which, according to (4.1.10), is the ith row of the matrix E(t) = (eij(t)), is denoted by ei (t), i.e.,
$$ \underline e \left( t \right) = {\left( {{e_{i0}}\left( t \right),{\kern 1pt} {e_{i1}}\left( t \right),......} \right)^T} $$
.
E. A. van Doorn

6. The M/M/s Queue Length Process

Abstract
In this chapter we consider the birth-death process {X(t): 0 ≤ t < ∞} with parameters
$$ \begin{gathered} {\lambda _n} = \lambda \quad \quad \quad \quad n = 0,1, \ldots \ldots \hfill \\ {\mu _n} = n\mu \quad \quad \quad n = 0,1, \ldots ,s - 1 \hfill \\ = s\mu \quad \quad \quad \quad n = s,s + 1, \ldots , \hfill \\ \end{gathered} $$
(6.1.1)
which is the queue length process in an M/M/s queueing system.
E. A. van Doorn

7. A Queueing Model Where Potential Customers are Discouraged by Queue Length

Abstract
We consider the birth-death process {X(t): 0 ≤ t < ∞} with parameters
$$ \begin{gathered} {\lambda _n} = \lambda /(n + 1)\quad \quad \quad \quad \quad n = 0,1, \ldots \ldots \hfill \\ {\mu _n} = 0\quad \quad \quad \quad \quad \quad \quad \quad n = 0 \hfill \\ = \mu \quad \quad \quad \quad \quad \quad \quad \quad \quad n = 1,2, \ldots \ldots , \hfill \\ \end{gathered} $$
(7.1.1)
which serves as a single server queueing model where potential customers are discouraged by queue length (cf. Conolly (1975), Hadidi (1975) and Natvig (1974, 1975)).
E. A. van Doorn

8. Linear Growth Birth-Death Processes

Abstract
In this chapter our subject will be birth-death processes with parameters
$$ \begin{array}{*{20}{c}}{{\lambda _n} = \alpha+\lambda n\quad n = 0,1,...}\\{{\mu _n} = \beta+\mu n\quad n = 0,1,...\quad .}\\ \end{array} $$
(1)
Such processes occur naturally in the study of biological reproduction and population growth (see, e.g., GOEL and RICHTER-DYN (1974)).
E. A. van Doorn

9. The Mean of Birth-Death Processes

Abstract
Consider a natural birth-death process {X(t): 0 ≤ t < ∞} with µ0 = 0 and let m(t) denote the first moment of X(t), i.e.,
$$ m(t) = \sum\limits_{j = 0}^\infty{j{P_j}(t).} $$
(9.1.1)
E. A. van Doorn

10. The Truncated Birth-Death Process

Abstract
A truncated birth-death process is a temporally homogeneous Markov process {X(t): 0 ≤ t < ∞} on a finite state space S̅= {-1, 0, 1,...., N, N+1}, say, with transition probability functions
$$ {P_{ij}}(t) = \Pr \left\{ {X\left( {t + s)} \right) = j\left| {X\left( s \right)} \right. = i} \right\} $$
(10.1.1)
which satisfy the conditions
$$ {P_{ - 1.j}}(t) = {\delta _{ - 1,j}}\quad j \in \overline S ,t \geqslant 0, $$
(10.1.2)
$$ {P_{N + 1,j}}(t) = {\delta _{N + 1,j}}\quad j \in \overline S ,t \geqslant 0 $$
(10.1.3)
and for i ∈ S = {0, 1,..., N},
$$ \begin{array}{*{20}{c}}{{P_{i,i + 1}}(t) = {\lambda _i}t + o(t)}\\{{P_{ii}}(t) = 1 - \left( {{\lambda _i} + {\mu _i}} \right)t + o(t)} \\{{P_{i,i - 1}}(t) = {\mu _i}t + o(t)} \\\end{array} $$
(10.1.4)
as t → 0, where λi and µi, i ∈ S, are non-negative constants. Throughout this chapter we assume λi > 0 for i ∈ S\{N} and µi > 0 for i ∈ S\{0}.
E. A. van Doorn

Backmatter

Weitere Informationen