Introduction to Stochastic Models E-Book

Marius Iosifescu

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 527

Veröffentlichungsjahr: 2013

Beschreibung

This book provides a pedagogical examination of the way in which stochastic models are encountered in applied sciences and techniques such as physics, engineering, biology and genetics, economics and social sciences. It covers Markov and semi-Markov models, as well as their particular cases: Poisson, renewal processes, branching processes, Ehrenfest models, genetic models, optimal stopping, reliability, reservoir theory, storage models, and queuing systems. Given this comprehensive treatment of the subject, students and researchers in applied sciences, as well as anyone looking for an introduction to stochastic models, will find this title of invaluable use.

Leseprobe

Contents

Preface

Chapter 1: Introduction to Stochastic Processes

1.1. Sequences of random variables

1.2. The notion of stochastic process

1.3. Martingales

1.4. Markov chains

1.5. State classification

1.6. Continuous-time Markov processes

1.7. Semi-Markov processes

Chapter 2: Simple Stochastic Models

2.1. Urn models

2.2. Random walks

2.3. Brownian motion

2.4. Poisson processes

2.5. Birth and death processes

Chapter 3: Elements of Markov Modeling

3.1. Markov models: ideas, history, applications

3.2. The discrete-time Ehrenfest model

3.3. Markov models in genetics

3.4. Markov storage models

3.5. Reliability of Markov models

Chapter 4: Renewal Models

4.1. Fundamental concepts and examples

4.2. Waiting times

4.3. Modified renewal processes

4.4. Replacement models

4.5. Renewal reward processes

4.6. The risk problem of an insurance company

4.7. Counter models

4.8. Alternating renewal processes

4.9. Superposition of renewal processes

4.10. Regenerative processes

Chapter 5: Semi-Markov Models

5.1. Introduction

5.2. Markov renewal processes

5.3. First-passage times and state classification

5.4. Reliability

5.5. Reservoir models

5.6. Queues

5.7. Digital communication channels

Chapter 6: Branching Models

6.1. The Bienaymé-Galton-Watson model

6.2. Generalizations of the B-G-W model

6.3. Continuous-time models

Chapter 7: Optimal Stopping Models

7.1. The classic optimal stopping problem

7.2. Renewal with binary decision

Bibliography

Notation

Index

Dedication

In loving memory of Gheorghe Dan Oprian

(February 14, 1944 – April 17, 2009)

Collaborator and friend

First published 2007 in France by Hermes Science/Lavoisier entitled: Modèles stochastiques © LAVOISIER 2007

First published 2010 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Translated from the French by Vlad Barbu

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.iste.co.uk

www.wiley.com

© ISTE Ltd 2010

The rights of Marius Iosifescu, Nikolaos Limnios and Gheorghe Oprian to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Iosifescu, Marius.

[Modèles stochastiques. English]

Introduction to stochastic models / Marius Iosifescu, Nikolaos Limnios, Gheorghe Oprian.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-057-8

1. Stochastic processes. 2. Stochastic models. I. Limnios, N. (Nikolaos) II. Oprian, Gheorghe. III. Title.

QA274.I5713 2010

519.2’3--dc22

2009051756

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-057-8

Preface

Stochastic models have become a very useful tool, indeed fundamental, for a lot of sciences and applied engineering. Whether it be in theoretical or applied physics, economy or social sciences, engineering or even music, stochastic models are there to help.

Stochastic modeling is mainly based on Markov processes, characterized by the memoryless property, conditioned on their position at present. This is the probabilistic analogue of dynamical systems, where the future position of a moving particle depends only on the current position and speed. The natural generalization of Markov processes to semi-Markov processes offers much more generality, as the sojourn time in a state can have any arbitrary distribution on the real half-line x ≥ 0, and not only an exponential distribution as in the Markovian case. Let us also notice that martingales are increasingly used for real system modeling, especially in financial mathematics and statistics.

This book is based on the book [IOS 84] published in 1984, in Romanian. We will follow the main lines of that book, but will replace quite a lot of the material. We would like to pay tribute to the memory of our co-authors of [IOS 84], Serban Grigorescu (1946–1997) and Gheorghe Popescu (1944–1989), who unfortunately died before fulfilling their creative potential.

Throughout this book, composed of seven chapters, we will focus on Markov and semi-Markov processes and on their particular cases: Poisson and renewal processes.

The aim of our book is to present stochastic models in a simple context, without complicated mathematical tools, but precise nonetheless. Emphasis is placed on comprehension of the main issues, on the development of the results linked to the phenomena discussed, as well as on the specific needs giving rise to these models.

Chapter 1 presents useful families of stochastic processes. We give special attention to martingales, Markov chains, Markov processes, and semi-Markov processes, which will be the “protagonists” of the following chapters.

In Chapter 2 we present some simple stochastic models, like urn models, Brownian motion, Poisson processes and birth and death processes, models which are used in applications individually or combined with other stochastic processes. We should stress that these models alone might be a good introduction to stochastic processes. Although these processes are particular cases of the Markov processes presented in the following chapters, they are studied separately by way of more direct techniques.

Chapter 3 is devoted to the Markovian modeling from a more systematic point of view, starting from the Markov property. The presentation is focused on models like the Ehrenfest chain and various models in genetics, storage problems, and system reliability.

The basic results on renewal models are presented in Chapter 4, together with their main applications, such as replacement and reward models, risk models in insurance and counter models.

In Chapter 5 we describe semi-Markov processes. After several basic theoretical results, we study some of the best known applications for semi-Markov models in fields like: system reliability, reservoir models, queueing systems, and digital communication channels.

In Chapter 6 the branching models are presented, especially the Bienyamé-Galton-Watson model, with the associated computation of extinction probability or of absorption time distribution and the analysis of related asymptotic properties. Some generalizations of this model, as well as some models in continuous time, are also presented.

Finally, Chapter 7 is devoted to optimal stopping models. After a description of the classic problem, the optimal stopping problem for a

Markovian structure is also presented and different resolution methods are proposed. Then we give the optimal stopping problem for a renewal structure.

This book is mainly intended for applied science and engineering students and researchers in applied sciences, but also for anybody interested in an accessible introduction to stochastic models.

We would like to thank our colleagues for their contributions to our discussions, as well as our students from Bucharest and Compiègne, whose questions helped us advance.

Chapter 1

Introduction to Stochastic Processes

In this introductory chapter we present some notions regarding sequences of random variables (r.v.) and the most important classes of random processes.

1.1. Sequences of random variables

Let be a probability space and (An) a sequence of events in .

– The set of ω ∈ Ω belonging to an infinity of An, that is,

is called the upper limit of the sequence (An).

– The set of ω ∈ Ω belonging to all An except possibly to a finite number of them, that is,

is called the lower limit of the sequence (An).

THEOREM 1.1.– (Borel-Cantelli lemma)Let(An)be a sequence of events in .

1. , them

2. and(An)is a sequence of independent events, then

Let (Xn) be a sequence of r.v. and X an r.v., all of them defined on the same probability space . The convergence of the sequence (Xn) to X will be defined as follows:

1. Almost sure

2. In probability if for any ε > 0,

.

3. In distribution(or weekly, or in law) pointwise in every continuity point of FX, where FXn and FX are the distribution functions of Xn and X, respectively.

The relations between these types of convergence are as follows:

[1.1]

The convergence in distribution of r.v. is a convergence property of their distributions (i.e. of their laws) and it is the most used in probability applications. This convergence can be expressed by means of characteristic functions.

THEOREM 1.2.– (Lévy continuity theorem)The sequence(Xn)converges in distribution to X if and only if the sequence of characteristic functions of(Xn)converges pointwise to the characteristic function of X.

EXAMPLE 1.3.– Let X1, X2,… be independent r. v. such that and . We have , but Xn is not almost surely convergent to 1 as n → ∞.

Indeed, for any ∈ > 0 we have

Consequently, .

To analyze the convergence a.s., we recall the following condition: , if and only if, for any ∈ > 0 and 0 <δ< 1, there exists an n0 such that for any n>n0

[1.2]

As for any ∈> 0, δ ∈ (0,1), and we have

it does not exist an n0 such that relation [1.2] is satisfied, so we conclude that Xn does not converge a.s.

and

On the one hand, as

we obtain that . Thus (Xn) does not converge in probability. On the other hand, the characteristic functions of the r.v. , and X are

and, respectively,

so .

Let us consider a sequence of r.v. (Xn,n ≥ 1) and suppose that the expected values , exist. Let

[1.3]

DEFINITION 1.5.– The sequence (Xn,n ≥ 1) is said to satisfy the weak or the strong law of large numbers if , respectively.

Obviously, if a sequence of r.v. satisfies the strong law of large numbers, then it also satisfies the weak law of large numbers.

The traditional name “law of large numbers” that is still in use nowadays should be clearly understood: it is indeed a “true” mathematical theorem! We do indeed still speak of laws of large numbers to express vaguely but correctly the sense of a convergence of frequency toward probability, but we also tend to believe sometimes that a return to equilibrium will always occur in the end, and this is a big error of which we are often unaware.

Let us present now some “classic laws of large numbers.”

THEOREM 1.6.– (Markov)Let (Xn,n ≥ 1) be a sequence of r.v. such that and If

[1.4]

then(Xn, n ≥ 1)satisfies the weak law of large numbers.

PROOF.– Chebyshev’s inequality applied to Yn defined in equation [1.3] yields

and thus we obtain

COROLLARY 1.7.– (Chebyshev)Let(Xn,n ≥ 1)be a sequence of independent r.v. such that If there exists an M, 0 <M< ∞, such that then(Xn,n ≥ 1)satisfies the weak law of large numbers.

PROOF.– In our case we have

and condition [1.4] is verified.

THEOREM 1.8.– (Kolmogorov)Let (Xn, n ≥ 1)be a sequence of independentr.v. such that , and , then (Xn,n ≥ 1)satisfies the strong law of large numbers.

COROLLARY 1.9.– In the settings of Corollary 1.7, the sequence of r.v. (Xn,n ≥ 1)satisfies the strong law of large numbers.

EXAMPLE 1.10.– Let (Xn) be a sequence of i.i.d. r.v. of distribution P.1 For any Borel set B, the r.v. ll (Xn ∈ B) are i.i.d., with common expected value P(B). Using the law of large numbers, Corollary 1.9, we have

This argument justifies the estimation of probabilities by frequencies.

EXAMPLE 1.11.– Let (Xn) be a sequence of r.v. that take the values , , with probabilities and

EXAMPLE 1.12.– Let (Xn) be a sequence of r.v. that take the values , , with probabilities and

We have and , which yields

and

Consequently, the hypotheses of Theorem 1.6 are fulfilled and the sequence (Xn) satisfies the weak law of large numbers.

It is easy to see that in applications we often have to deal with random variables composed of an important number of independent elements. Under very general conditions, such sum variables are normally distributed. This fundamental fact can be mathematically expressed in one of the forms (depending on the conditions) of the central limit theorem. To state the central limit theorem, we consider (Xn, n ≥ 1) a sequence of r.v. and we introduce the following notation:

A central limit theorem gives sufficient conditions for the random variable

to converge in distribution to the standard normal distribution N(0, 1).

We see that, if the r.v. (Xn, n ≥ 1) are independent, then and are standard r.v., because and .

We give now a central limit theorem important in probability and mathematical statistics.

THEOREM 1.13.– Let (Xn, n ≥ 1)be a sequence of independent identically distributed r.v. with mean a and finite positive variance a2. Then, the sequenceof r.v. , is convergent in distribution to the normal distribution N(0,1). Zn is said to be asymptotically normal.

PROOF.- Let φ(t) be the characteristic function of (X1 — a)(hence of all (Xn — a), n ≥ 1). Then the characteristic function of Zn is

THEREFORE, and, using Theorem 1.2, we obtain .

EXAMPLE 1.17.– A restaurant can serve 75 meals a day. We know from experience that 20% of the clients that reserved would not eventually show up.

a) The owner of the restaurant accepts 90 reservations. What is the probability that more than 50 clients show up?

b)How many reservations should the owner of the restaurant accept in order to have a probability greater than or equal to 0.9 that he will be able to serve all the clients who will show up?

a) Consequently,

b) We have to solve the inequality with respect to N. On the one hand, we have

1.2. The notion of stochastic process

A stochastic or a random process is a family of r.v. defined on the same probability space , with values in a measurable space .

The set E can be either or , and in this case is the σ-algebra of Borel sets, or an arbitrary finite or countable infinite discrete set, and in this case .

The index set I is usually (in this case the process is called chain) or , and the parameter t is interpreted as being the time. The function is called a realization or a sample path of the process (see Figure 1.1).

If the evolution of a stochastic process is done by jumps from state to state and if almost all its sample paths are constant except at isolated jump times, then the process is called a jump process.

Figure 1.1.Process with continuous sample path

The stochastic processes can be studied either by means of their finite-dimensional distributions or by considering the type of dependence between the r.v. of the process. In the latter case, the nature of the process is given by this type of dependence.

The distribution of a stochastic process X, i.e. , is specified by the knowledge of its finite-dimensional distributions. For a real-valued

Figure 1.2.Sample path of a jump process

process we define

[1.5]

for any t1, ..., tn ∈ I and x1, ..., xn ∈ .

The process is said to be given if all the finite-dimensional distributions Ft1,...,tn(·, ..., ·), t1, ..., tn ∈ I, are given.

The finite-dimensional distributions must satisfy the following properties:

1) for any permutation (i1, ..., in) of (1, ..., n),

2) for any 1 ≤ k ≤ n and x1, ..., xn ∈ ,

.

DEFINITION 1.19.– (Stochastically equivalent processes in the wide sense) If two stochastic processes X and Y satisfy

for all n ∈ N∗, t1, ..., tn∈ I, and A1, ..., An ∈ E, then they are called stochastically equivalent in the wide sense.

DEFINITION 1.20.– (Stochastically equivalent processes) If two stochastic processes X and Y satisfy

then they are called stochastically equivalent.

DEFINITION 1.21.– (Indistinguishable processes) If two stochastic processes X and Y satisfy

then they are called indistinguishable.

PROPOSITION 1.22.– We have the following implications: X,Y indistinguishable X,Y stochastically equivalent X, Y stochastically equivalent in the wide sense.

PROPOSITION 1.23.– If the processes X and Y are stochastically equivalent and right continuous, then they are indistinguishable.

DEFINITION 1.24.– (Version or modification of a process) If the process Y is stochastically equivalent to the process X, then we say that Y is a version or a modification of the process X.

DEFINITION 1.25.– (Continuous process) Aprocess X with values in aBorel space (E, ∈ ) is said to be continuous a.s. if, for almost all ω, the function is continuous.

PROPOSITION 1.26.– (Kolmogorov continuity criterion) A real process X has a continuous modification if there exist the constants α, β, C > 0, such thatfor all t and s.

1.3. Martingales

1.3.1. Stopping time

Let be a probability space. An increasing sequence of σ-algebras, , is called a filtration of . A sequence (Xn,n ∈ ) of r.v. is said to be F-adapted if Xn is n -measurable for all . Usually, a filtration is associated with the sequence of r.v. , that is, we have n and the sequence will be F-adapted. This is called the natural filtration of .

DEFINITION 1.27.– Let be a filtration of . A stopping time for F(or F-adapted, or F-stopping time) is an r.v. T with values in satisfying one of the following (equivalent) conditions:

If , T is said to be adapted to the sequence . In this case we note .

Properties of stopping times

1.The set is a σ-algebra called the σ-algebra of events prior to T.

2. If S and T are stopping times, then S + T, S ⋀ T, and S ⋁ T are also stopping times.

3.If is a sequence of stopping times, then is also a stopping time.

4.If S and T are stopping times such that S ≤ T, then s ⊆ T.

PROPOSITION 1.29.– (Wald identity)If T is a stopping time with finite expected value, adapted to an i.i.d. and integrable random sequence (Xn,n ∈ ), then

1.3.2. Discrete-time martingales

We will consider in the following that every filtration F is associated with the corresponding random sequence.

DEFINITION 1.30.– A sequence of r.v. (Xn, n ∈ ) is an

1)XnF-martingale if

(a)Xn is F-adapted for all n;

(b)E |Xn | < ∞ for all n ∈ ;

(c) for all n ∈ .

2)F-submartingale if it satisfies (a), (b), and (c) with <.

3)F-supermartingale if it satisfies (a), (b), and (c) with >.

Note that condition (c) is equivalent to .

EXAMPLE 1.32.– Let X be a real r.v. with and let F be an arbitrary filtration. Then, the sequence is a martingale. Indeed,

If Xn is the r.v. defined as the fortune of the gambler after the nth game, we have

On the other hand, the expected value of the loss is

because N is a geometrically distributed r.v. with parameter 1/2 and for n ≥ N. Consequently, the strategy of the player is valid only if his initial fortune is greater than the casino’s.

1.3.3. Martingale convergence

THEOREM 1.34.– (Doob’s convergence theorem)Every supermartingale, submartingale or martingale bounded in L1 converges a.s. to an integrable r.v.

EXAMPLE 1.35.– If X is an r.v. on with finite expected value and is a filtration of , then

THEOREM 1.36.– If(Xn)is an uniformly integrable martingale, i.e.

then there exists X integrable such that , and we have.

A martingale (Xn) for is said to be a square integrable if for all n ≥ 1.

THEOREM 1.37.– (Strong convergence theorem)If (Xn) is a square integrable martingale, then there exists an r.v. X such that .

THEOREM 1.38.– (Stopping theorem)Let(Xn)be a martingale(resp. a submartingale)for(n). If S and T are two stopping times adapted to(n)such that

1)and

2)and

then

1.3.4. Square integrable martingales

Let (Mn, n ≥ 0) be a square integrable martingale, i.e.

The process is a submartingale and Doob’s decomposition gives

where Xn is a martingale, and <M>n is a predictable increasing process, that is, -measurable for all n ≥ 1.

THEOREM 1.39.– If(Mn)is a square integrable martingale, with predictable process<M>n, and if

1)

2)

for all

then

and

where(an)is a sequence increasing to infinity.

1.4. Markov chains

Markov chains and processes represent probabilistic models of great importance for the analysis and study of complex systems. The fundamental concepts of Markov modeling are the state and the transition.

1.4.1. Markov property

It is clear that the situation of a physical system at a certain moment can be completely specified by giving the values of a certain number of variables that describe the system. For instance, a physical system can often be specified by giving the values of its temperature, pressure, and volume; in a similar way, a particle can be specified by its coordinates with respect to a coordinate system, by its mass and speed. The set of such variables is called the state of the system, and the knowledge of the values of these variables at a fixed moment allows us to specify the state of the system, and, consequently, to describe the system at that precise moment.

Usually, a system evolves in time from one state to another, and is thus characterized by its own dynamics. For instance, the state of a chemical system can change due to a modification in the environment temperature and/or pressure, whereas the state of a particle can change because of interaction with other particles. These state modifications are called transitions.

In most of the concrete situations, the observation of the process makes us come to the conclusion that the process is random. Consequently, to a sample path of the process a certain probability

needs to be associated. Elementary techniques of probability theory show that these probabilities can be expressed in terms of the conditional probabilities

for all and for any states i0, i1, . . ., in+1∈ E. This means that it is necessary to know the probability that the system is in a certain state in+1∈ E after the (n + 1)th transition, , knowing its history up to time n. Computing all these conditional probabilities renders the study of a real phenomenon modeled in this way very complicated. The statement that the process is Markovian is equivalent to the simplifying hypothesis that only the last state (i.e. the current state) counts for its future evolution. In other words, for a Markov process we have (the Markov property)

[1.6]

DEFINITION 1.40.– The sequence of r.v. defined on , with values in the set E, is called a Markov chain(or discrete-time Markov process) with a finite or countable state space, if the Markov property is satisfied.

A Markov chain is called nonhomogenous or homogenous(with respect to time) whether or not the common value of the two members of [1.6](i.e. the function p(n, i, j)) depends on n. This probability is called transition function(or probability)of the chain.

For more details on the study of discrete-time Markov processes with finite or countable state space, see [CHU 67, IOS 80, KEM 60, RES 92].

So, the Markovian modeling is adapted to physical phenomena or systems whose behavior is characterized by a certain memoryless property, in the sense specified in [1.6]. For real applications, it is very difficult often even impossible to know whether a physical system has a Markovian behavior or not; in fact, it is important to be able to justify this Markovian behavior (at least as a first approximation of the phenomenon) and thus to obtain a model useful for the study of the phenomenon.

Note that the Markovian modeling can also be used in the case in which a fixed number of states, not only the last one, determines the future evolution of the phenomenon. For instance, suppose that we take into account the last two visited states. Then, we can define a new process with n2 states, where the states are defined as couples of states of the initial process; this new process satisfies property [1.6] and the Markovian model is good enough, but with the obvious drawback of computational complexity.

PROPOSITION 1.41.– If the Markov property (1.6) is satisfied, then

[1.7]

for all and i0, i1, ..., in,j1, ...jm ∈ E.

REMARK 1.42.– The more general relation

[1.8]

can be proved for any A ∈ σ(Xk;k ≥ n + 1). The equalities between conditional probabilities have to be understood in the sense of almost surely . We will often write instead of

1.4.2. Transition function

Throughout this chapter, we will be concerned only with homogenous Markov chains and the transition function will be denoted by p(i, j). It satisfies the following properties:

[1.9]

[1.10]

A matrix that satisfies [1.9] and [1.10] is said to be stochastic.

[1.11]

The probability does not depend on n and will be denoted by p(m)(i, j).

From the following matrix equality

[1.12]

we obtain

[1.13]

for all . Equality [1.12](or [1.13]) is called the Chapman-Kolmogorov identity(or equality).

Using the eigenvalues of the matrix p, we obtain

and, for 1≤i≤m

EXAMPLE 1.45.– Storage model. A certain product is stocked in order to face a random demand. The stockpile can be replenished at times 0, 1, 2, … and the demand in the time interval (n, n + 1] is considered to be a discrete -valued r.v. ξn. The r.v. ξ0, ξ1, ξ2, ... are supposed to be i.i.d. and

The stocking strategy is the following: let m, M ∈ , be such that m < M; if, at an arbitrary time , the inventory level is less or equal to m, then the inventory is brought up to M. Whereas, if the inventory level is greater than m, no replenishment is undertaken.

If Xn denotes the stock level just before the possible supply at time n, we have

The same approach as in example 1.44 can be used in order to show that is a Markov chain and subsequently obtain its transition function.

1.4.3. Strong Markov property

Let be a Markov chain defined on , with values in E. Consider the filtration be a stopping time for the chain X(i.e. for the filtration and be the σ-algebra of events prior to τ. We want to obtain the Markov property (relation [1.6]) in case that the “present moment” is random.

PROPOSITION 1.46.– For all such that , we have

[1.14]

REMARK 1.47.– We can prove more general relations as follows: if B is an event subsequent to τ, i.e. B ∈ σ(Xτ+k, k ≥ 0), then

[1.15]

[1.16]

DEFINITION 1.48.– Relation [1.15] is called the strong Markov property.

PROPOSITION 1.49.– The sojourn time in a state j ∈ E is a geometric r.v. of parameter 1 − p(j, j) with respect to the probability for.

1.5. State classification

Note that relation i → j is transitive, i.e. if i → j and j → k then i → k.

DEFINITION 1.51.– A class of states is a subset C of E that satisfies one of the two following properties:

1)The set C contains only one state i ∈ E and relation i ↔ i is not verified.

2)For all i, j ∈ C we have i ↔ j and C is maximal with this property, i.e. it is not possible to increase C by another state which communicates with all the other states of C.

DEFINITION 1.53.– 1. A property concerning the states of E, such that the validity for a state i ∈ E implies the validity for all states from the class of i, is called a class property.

3. If a closed class contains only one state, then this state is called absorbing

4. If the state space E consists of only one closed class, then the chain is called irreducible.

5.A state i ∈ E is said to be essential if i → j yields j → i; otherwise i is called inessential.

PROPOSITION 1.54.– Let C be a closed class of period d and C0, C1, …, Cd−1be the cyclic subclasses.

1. If i ∈ Cr and p(n)(i,j)> 0, then j ∈ Cn+r.

2.If i ∈ Cr, we have

(The class subscripts are considered mod d).

We will denote by , the probabilities on σ(Xn; n ∈ ) defined by

and by i the corresponding expected values.

PROPOSITION 1.56.– A state i ∈ E is recurrent or transient, if the series is divergent, respectively convergent.

PROPOSITION 1.57.– Let (Xn, n ∈ )be a Markov chain with finite state space E. Then:

1) there exists at least a recurrent state;

2) a class is recurrent iff it is closed.

1.5.1. Stationary probability

[1.17]

Relation [1.17] can be written in matrix form

[1.18]

[1.19]

and

[1.20]

PROPOSITION 1.60.– We suppose that the transition matrix is such that the limits

[1.21]

exist for all i, j ∈ E and do not depend on i. Then, there are two possibilities:

DEFINITION 1.61.– A Markov chain is said to be ergodic if, for all i, j ∈ E, the limits limn→∞p(n)(i, j) exist, are positive, and do not depend on i.

PROPOSITION 1.62.– An irreducible, aperiodic, and positive recurrent Markov chain is ergodic.

PROPOSITION 1.63.– A finite Markov chain is ergodic if and only if

[1.22]

A Markov chain verifying[1.22]is called regular.

PROPOSITION 1.64.– A Markov chain with finite or countable state space E has a unique stationary probability if and only if the state space contains one and only one recurrent positive class.

COROLLARY 1.65.– A finite ergodic Markov chain (i.e. regular) has a unique stationary probability.

1.6. Continuous-time Markov processes

The concept of Markovian dependence in continuous time was introduced by A. N. Kolmogorov in 1931. The first important contributions are those of B. Pospisil, W. Feller, and W. Doeblin, and the standard references are [BLU 68, DYN 65, GIH 74].

1.6.1. Transition function

Let E be a finite or countable set and , be a matrix function with the properties:

[1.23]

where δij is the Kronecker symbol.

A family of r.v. with values in E is called a Markov process homogenous with respect to time, with state space E, if

[1.24]

for all 0 ≤ t0<t1<…<tn, t ≥ 0, i0, i1, …,in−1, i, j ∈ E, n ≤ 1. We will suppose that the sample paths t → X(t, ω)are right-continuous with left limits a.s. The matrix P(t), called the transition matrix function of the process, satisfies the Chapman-Kolmogorov equation

[1.25]

which can be written under matrix form

The functions pij(t) have some remarkable properties:

1) For all i, j ∈ E, the function Pij(t) is uniformly continuous on [0, ∞).

2) For all i,j ∈ E, the function pij(t) is either identically zero, or positive, on (0, ∞).

3) For all exists and it is finite.

PROPOSITION 1.66.– If E is finite, then there is no instantaneous state.

PROPOSITION 1.67.– The sample paths of the process are right continuous a.s. if and only if there is no instantaneous state.

1.6.2. Kolmogorov equations

[1.26]

If E is finite, then [1.26] becomes

[1.27]

Relation [1.27] is a necessary and sufficient condition such that pij(t) satisfy the differential equations

[1.28]

or, in matrix form,

Equations [1.28] are called Kolmogorov backward equations. In addition, if qj< ∞, j ∈ E, and the limit

is uniform with respect to i ≠ j, then we have

[1.29]

Equations [1.29] are called Kolmogorov forward equations.

[1.30]

Consequently, the transition intensity matrix Q uniquely determines the transition matrix function P(t).

The first jump time or the sojourn time in a state is defined by

Then is the distribution function of the sojourn time in state i.

PROPOSITION 1.68.– For i, j ∈ E, we have

[1.31]

and the r.v. T1 and XT1 are -independent.

The successive jump times of the process can be defined as follows:

The lifetime of the process is the r.v. , then the process is regular(non-explosive); in the opposite case, if , the process is called non-regular(explosive).

If Tn+1> Tn a.s. for all n ≥ 1, then (X(t),t ≥ 0) is said to be a jump process.

[1.32]

REMARK 1.70.– We have

[1.33]

PROPOSITION 1.72.– A necessary and sufficient condition for a Markov process (X(t),t ≥ 0)to be regular is a.s.

PROPOSITION 1.73.– (Kolmogorov integral equation)For i, j ∈ E, we have

[1.34]

– recurrent if ;

– transient if;

– positive recurrent if it is recurrent and ;

[1.35]

A Markov process (X(t),t> 0) is said to be ergodic if there exists a probability π on E such that, for all i, j ∈ E, we have

or, equivalently,

for all i ∈ E.

PROPOSITION 1.74.– For any state i of E, we have

PROPOSITION 1.75.– If the Markov process (X(t),t > 0)is irreducible (i.e. the chain (Yn, n ∈ )is so) and it has an invariant probability π, then for any positive and bounded function g on E, we have

1.7. Semi-Markov processes

A semi-Markov process is a natural generalization of a Markov process. Its future evolution depends only on the time elapsed from the last transition.

The semi-Markov processes that we will present are minimal semi-Markov processes associated with Markov renewal processes, with finite state spaces E. Consequently, we do not have to take into account instantaneous states and the sojourn times of a process form, almost surely on +, a dense set.

1.7.1. Markov renewal processes

Let the functions Qij, i, j ∈ E, defined on the real line, be non-decreasing, right continuous, and such that Qij(∞) ≤ 1; they will be called mass functions. Besides, if we have

Let us consider the Markov transition function P((i, s), {j} x[0,t]) defined on the measurable space by

Then [BLU 68, DYN 65, GIH74], there exists a Markov chain ((Jn,Tn),n ∈ ) with values in , such that the transition function is given by

[1.36]

[1.37]

Obviously,

where

DEFINITION 1.76.– The processes ((Jn,Tn), n ∈ ) and ((Jn,Xn),n ∈ ) are called Markov renewal process(MRP) and, respectively, J — X process.

The n-fold matrix Stieltjes convolution is defined by

and we have

[1.38]

1.7.2. Semi-Markov processes

We will suppose that

and define

DEFINITION 1.77.– The jump stochastic process (Zt, t ∈ +), where

[1.39]

is said to be a semi-Markov process associated with the MRP (Jn, Tn).

We only present some notions regarding semi-Markov processes here, for they will be detailed in Chapter 5.

The jump times are T0<T1<T2< · · · <Tn< … and the inter-jump times are X1, X2, ….

Obviously,

For any i, j ∈ E we define the distribution function Fij by

Note that Fij is the distribution function of the sojourn time in state i, knowing that the next visited state is j. These distribution functions are called conditional transition functions.

The transition functions of the semi-Markov process are defined by

[1.40]

We denote by Nj(t) the number of times the semi-Markov process visits state j during the time interval (0, t]. For i, j ∈ E we let

The function t → Ψij(t) is called the Markov renewal function. This function is the solution of the Markov renewal equation

[1.41]

The transition probabilities [1.40] satisfy the Markov renewal equation

[1.42]

1. In fact, the distribution (or law) of an r.v. is a probability on , i.e. on the Borel sets of .

2. Φ is the d.f. of N(0, 1).

Chapter 2

Simple Stochastic Models

This chapter presents stochastic models that, despite their simplicity, have been important for the development of the probability theory and of random modeling.

2.1. Urn models

An urn model (or scheme) is a system formed by urns that contain balls of different colors, to which we associate an experiment of successive ball drawings, with or without replacement in the urns, following some precise rules. These rules could consist in either putting in additional balls or taking out balls from some urns, or in changing the color of some balls at different stages of the experiment. The fundamental rule for computing the probability of a certain result of an experiment is that the random drawing from an urn with s balls is uniformly distributed, i.e. the probability of drawing any of the balls is 1/s.