nach oben

1981 | Buch

Kapitel lesen Erstes Kapitel lesen

Stochastic Monotonicity and Queueing Applications of Birth-Death Processes

verfasst von: E. A. van Doorn

Verlag: Springer New York

Buchreihe : Lecture Notes in Statistics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Ü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 ≤ t₁ <.....< t_n and any i₁,...., i_n 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 {λ_n,μ_n} 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(⋅) = (p_ij(⋅)), 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 (1957^a, 1959^b) 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 (1959^a) 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) p_ij(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, and by G^* the class of sets of birth-death parameters {λ _n ^* , μ _n ^* : n = 0, 1,...} with μ ₀ ^* > 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 {λ_n,μ_n} ∈ G and {λ _n ^* , μ _n ^* } = f({λ_n,μ_n})∈ 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, 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 = (q₀, q₁,....)^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 p^T(t) = (p₀(t), p₁(t),.....) with p_i(t) = Pr{X(t) = i} and P(t) the transition 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 = (q₀, q₁,.....)^T, where q_n = δ_in for some fixed i and all n. The process is denoted by {X_i(t)} = {X_i (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) = (e_ij(t)), is denoted by e_i (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 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

Titel: Stochastic Monotonicity and Queueing Applications of Birth-Death Processes
verfasst von: E. A. van Doorn
Verlag: Springer New York
Electronic ISBN: 978-1-4612-5883-4
Print ISBN: 978-0-387-90547-1
DOI: https://doi.org/10.1007/978-1-4612-5883-4

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

1. Preliminaries

2. Natural Birth-Death Processes

3. Dual Birth-Death Processes

4. Stochastic Monotonicity: General Results

5. Stochastic Monotonicity: Dependence on the Initial State Distribution

6. The M/M/s Queue Length Process

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

8. Linear Growth Birth-Death Processes

9. The Mean of Birth-Death Processes

10. The Truncated Birth-Death Process

Backmatter