Teoria Catene Di Markov

Preface

Markov chains are the simplest mathematical models for random phenomena evolving in time. Their simple structure makes it possible to say a great deal about their behaviour. At the same time, the class of Markov chains is rich enough to serve in many applications. This makes Markov chains the first and most important examples of random processes. Indeed, the whole of the mathematical study of random processes can be regarded as a generalization in one way or another of the theory of Markov chains.

This book is an account of the elementary theory of Markov chains, with applications. It was conceived as a text for advanced undergraduates or master’s level students and is developed from a course taught to undergraduates for several years. There are no strict prerequisites, but it is envisaged that the reader will have taken a course in elementary probability. In particular, measure theory is not a prerequisite.

The first half of the book is based on lecture notes for the undergraduate course. Illustrative examples introduce many of the key ideas. Careful proofs are given throughout. There is a selection of exercises, which forms the basis of classwork done by the students and which has been tested over several years. Chapter 1 deals with the theory of discrete-time Markov chains, and is the basis of all that follows. You must begin here. The material is quite straightforward and the ideas introduced permeate the whole book. The basic pattern of Chapter 1 is repeated in Chapter 3 for continuous-time chains, making it easy to follow the development by analogy. In between, Chapter 2 explains how to set up the theory of continuous-time chains, beginning with simple examples such as the Poisson process and chains with finite state space.

The second half of the book comprises three independent chapters intended to complement the first half. In some sections, the style is a little more demanding. Chapter 4 introduces, in the context of elementary Markov chains, some of the ideas crucial to the advanced study of Markov processes, such as martingales, potentials, electrical networks, and Brownian motion. Chapter 5 is devoted to applications, for example, to population growth, mathematical genetics, queues and networks of queues, Markov decision processes, and Monte Carlo simulation. Chapter 6 is an appendix to the main text, where we explain some of the basic notions of probability and measure used in the rest of the book and give careful proofs of the few points where measure theory is really needed.

The following paragraph is directed primarily at an instructor and assumes some familiarity with the subject. Overall, the book is more focused on the Markovian context than most other books dealing with the elementary theory of stochastic processes. I believe that this restriction in scope is desirable for the greater coherence and depth it allows. The treatment of discrete-time chains in Chapter 1 includes the calculation of transition probabilities, hitting probabilities, expected hitting times, and invariant distributions. Also treated are recurrence and transience, convergence to equilibrium, reversibility, and the ergodic theorem for long-run averages. All the results are proved, exploiting to the full the probabilistic viewpoint. For example, we use excursions and the strong Markov property to obtain conditions for recurrence and transience, and convergence to equilibrium is proved by the coupling method. In Chapters 2 and 3, we proceed via the jump chain/holding time construction to treat all right-continuous, minimal continuous-time chains, and establish analogues of all the main results obtained for discrete time. No conditions of uniformly bounded rates are needed. The student has the option to take Chapter 3 first, to study the properties of continuous-time chains before the technically more demanding construction. We have left measure theory in the background, but the proofs are intended to be rigorous, or very easily made rigorous, when considered in measure-theoretic terms. Some further details are given in Chapter 6.

It is a pleasure to acknowledge the work of colleagues from which I have benefitted in preparing this book. The course on which it is based has evolved over many years and under many hands – I inherited parts of it from Martin Barlow and Chris Rogers. In recent years it has been given by Doug Kennedy and Colin Sparrow. Richard Gibbens, Geoffrey Grimmett, Frank Kelly, and Gareth Roberts gave expert advice at various stages. Meena Lakshmanan, Violet Lo, and David Rose pointed out many typos and ambiguities. Brian Ripley and David Williams made constructive suggestions for improvement of an early version.

I am especially grateful to David Tranah at Cambridge University Press for his suggestion to write the book and for his continuing support, and to Sarah Shea-Simonds who typeset the whole book with efficiency, precision, and good humour.

Cambridge, 1996 James Norris

Introduction

This book is about a certain sort of random process. The characteristic property of this sort of process is that it retains no memory of where it has been in the past. This means that only the current state of the process can influence where it goes next. Such a process is called a Markov process. We shall be concerned exclusively with the case where the process can assume only a finite or countable set of states, when it is usual to refer to it as a Markov chain.

Examples of Markov chains abound, as you will see throughout the book. What makes them important is that not only do Markov chains model many phenomena of interest, but also the lack of memory property makes it possible to predict how a Markov chain may behave, and to compute probabilities and expected values which quantify that behaviour. In this book, we shall present general techniques for the analysis of Markov chains, together with many examples and applications. In this introduction, we shall discuss a few very simple examples and preview some of the questions which the general theory will answer.

We shall consider chains both in discrete time {0, 1, 2, ...} and continuous time [0, ∞). The letters n, m, k will always denote integers, whereas t and s will refer to real numbers. Thus we write (X_n)_n≥0 for a discrete-time process and (X_t)_t≥0 for a continuous-time process.

Markov chains are often best described by diagrams, of which we now give some simple examples:

• Discrete time: You move from state 1 to state 2 with probability 1. From state 3 you move either to 1 or to 2 with equal probability 1/2, and from 2 you jump to 3 with probability 1/3, otherwise stay at 2. We might have drawn a loop from 2 to itself with label 2/3. But since the total probability on jumping from 2 must equal 1, this does not convey any more information, and we prefer to leave the loops out.
• Continuous time: When in state 0 you wait for a random time with an exponential distribution of parameter λ, then jump to 1. Thus the density function of the waiting time T is given by f(t) = λe^-λt for t ≥ 0. We write T ∼ E(λ) for short.
• Continuous time (Poisson process): Here, when you get to 1 you do not stop but after another independent exponential time of parameter λ jump to 2, and so on. The resulting process is called the Poisson process of rate λ.
• Continuous time: In state 3 you take two independent exponential times T₁ ∼ E(2) and T₂ ∼ E(4); if T₁ is the smaller you go to 1 after time T₁, and if T₂ is the smaller you go to 2 after time T₂. The rules for states 1 and 2 are as given in examples (ii) and (iii).
• Discrete time: We use this example to anticipate some of the ideas discussed in detail in Chapter 1. The states may be partitioned into communicating classes, namely {0}, {1, 2, 3} and {4, 5, 6}. Two of these classes are closed, meaning that you cannot escape. The closed classes here are recurrent, meaning that you return again and again to every state. The class {1, 2, 3} is transient. The class {4, 5, 6} is periodic, but {0} is not.

We shall show how to establish the following facts by solving some simple linear equations. You might like to try from first principles.

• Starting from 0, the probability of hitting 6 is 1/4.
• Starting from 1, the probability of hitting 3 is 1.
• Starting from 1, it takes on average three steps to hit 3.
• Starting from 1, the long-run proportion of time spent in 2 is 3/8.

Let us write p⁽ⁿ⁾_ij for the probability starting from i of being in state j after n steps. Then we have:

• lim_n→∞ p⁽ⁿ⁾₀₁ = 9/32;
• p⁽ⁿ⁾₀₄ does not converge as n → ∞;
• lim_n→∞ (3n)p⁽ⁿ⁾₀₄ = 1/24.

Discrete-time Markov chains

This chapter is the foundation for all that follows. Discrete-time Markov chains are defined and their behaviour is investigated. For better orientation we now list the key theorems: these are Theorems 1.3.2 and 1.3.5 on hitting times, Theorem 1.4.2 on the strong Markov property, Theorem 1.5.3 characterizing recurrence and transience, Theorem 1.7.7 on invariant distributions and positive recurrence. Theorem 1.8.3 on convergence to equilibrium, Theorem 1.9.3 on reversibility, and Theorem 1.10.2 on long-run averages. Once you understand these you will understand the basic theory. Part of that understanding will come from familiarity with examples, so a large number are worked out in the text. Exercises at the end of each section are an important part of the exposition.

Definition and basic properties

Let I be a countable set. Each i ∈ I is called a state and I is called the state-space. We say that λ = (λ_i: i ∈ I) is a measure on I if 0 ≤ λ_i ≤ ∞ for all i ∈ I. If in addition the total mass Σ_i∈I λ_i equals 1, then we call λ a distribution. We work throughout with a probability space (Ω, F, P).

Recall that a random variable X with values in I is a function X: Ω → I. Suppose we set P(X = i) = λ_i = P({ω: X(ω) = i}). Then λ defines a distribution, the distribution of X. We think of X as modelling a random state which takes the value i with probability λ_i. There is a brief review of some basic facts about countable sets and probability spaces in Chapter 6.

We say that a matrix P = (p_ij: i, j ∈ I) is stochastic if every row (p_ij: j ∈ I) is a distribution. There is a one-to-one correspondence between stochastic matrices P and the sort of diagrams described in the Introduction. Here are two examples:

We shall now formalize the rules for a Markov chain by a definition in terms of the corresponding matrix P. We say that (X_n)_n≥0 is a Markov chain with initial distribution λ and transition matrix P if:

• (i) X₀ has distribution λ.
• (ii) For n ≥ 0, conditional on X_n = i, X_n+1 has distribution (p_ij: j ∈ I) and is independent of X₀, ..., X_n-1.

More explicitly, these conditions state that, for n ≥ 0 and i₁, ..., i_n+1 ∈ I:

• P(X₀ = i₁) = λ_i1;
• P(X_n+1 = i_n+1 | X₀ = i₁, ..., X_n = i_n) = p_inin+1.

We say that (X_n)_n≥0 is Markov (λ, P) for short. If (X_n)_0≤n≤N is a finite sequence of random variables satisfying (i) and (ii) for n = 0, ..., N-1, then we again say (X_n)_0≤n≤N is Markov (λ, P).

It is in terms of properties (i) and (ii) that most real-world examples are seen to be Markov chains. But mathematically, the following result appears to give a more comprehensive description, and it is the key to some later calculations.

Theorem 1.1.1. A discrete-time random process (X_n)_0≤n≤N is Markov (λ, P) if and only if for all i₁, ..., i_N ∈ I:

P(X₀ = i₁, X₁ = i₂, ..., X_N = i_N) = λ_i1p_i1i2p_i2i3...p_iN-1iN.

Proof. Suppose (X_n)_0≤n≤N is Markov (λ, P), then:

P(X₀ = i₁, ..., X_n = i_N) = P(X₀ = i₁)P(X₁ = i₂ | X₀ = i₁)...P(X_N = i_N | X₀ = i₁, ..., X_N-1 = i_N-1)

= λ_i1p_i1i2...p_iN-1iN.

On the other hand, if (1.1) holds for N, then by summing both sides over i_N ∈ I and using Σ_j∈I p_ij = 1, we see that (1.1) holds for N+1 and, by induction:

P(X₀ = i₁, ..., X_n = i_n) = λ_i1p_i1i2...p_in-1in for all n = 0, 1, ..., N.

In particular, P(X₀ = i₁) = λ_i1 and, for n = 0, 1, ..., N-1:

P(X_n+1 = i_n+1 | X₀ = i₁, ..., X_n = i_n) = p_inin+1.

So (X_n)_0≤n≤N is Markov (λ, P).

The next result reinforces the idea that Markov chains have no memory. We write δ_i = (δ_ij: j ∈ I) for the unit mass at i, where δ_ij = 1 if i = j, else 0.

Theorem 1.1.2 (Markov property). Let (X_n)_n≥0 be Markov (λ, P). Then, conditional on X_m = i, (X_m+n)_n≥0 is Markov (δ_i, P) and is independent of the random variables X₀, ..., X_m.

Proof. We have to show that for any event A determined by X₀, ..., X_m we have:

P({X_m+n = i_m+n} ∩ A | X_m = i) = δ_iimp_imim+1...p_im+n-1im+nP(A | X_m = i).

Then the result follows by Theorem 1.1.1. First, consider the case of elementary events {X₀ = i₀, ..., X_m+n = i_m+n}. In that case, we have to show:

P(X₀ = i₀, ..., X_m+n = i_m+n | X_m = i) = δ_iimp_imim+1...p_im+n-1im+nP(X₀ = i₀, ..., X_m = i_m).

This is true by Theorem 1.1.1. In general, any event A determined by X₀, ..., X_m may be written as a countable disjoint union of elementary events A_k:

A = ⋃_k=1^∞ A_k.

Then the desired identity for A follows by summing up the corresponding identities for A_k.

The remainder of this section addresses the following problem: what is the probability that after n steps our Markov chain is in a given state? First, we shall see how the problem reduces to calculating entries in the nth power of the transition matrix. Then we shall look at some examples where this may be done explicitly.

We regard distributions and measures λ as row vectors whose components are indexed by I, just as P is a matrix whose entries are indexed by I × I. When I is finite we will often label the states 1, 2, ..., N; then λ will be an N-vector and P an N × N-matrix. For these objects, matrix multiplication is a familiar operation. We extend matrix multiplication to the general case in the obvious way, defining a new measure λP and a new matrix P² by:

• (λP)_j = Σ_i∈I λ_ip_ij,
• (P²)_ij = Σ_k∈I p_ikp_kj.

We define Pⁿ similarly for any n. We agree that P⁰ is the identity matrix I, where I_ij = δ_ij. The context will make it clear when I refers to the state-space and when to the identity matrix. We write p⁽ⁿ⁾_ij = (Pⁿ)_ij for the (i, j) entry in Pⁿ.

In the case where λ_i > 0 we shall write P_i(A) for the conditional probability X₀ = i. By the Markov property at time m = 0, under P_i, (X_n)_n≥0 is Markov (δ_i, P). So the behaviour of (X_n)_n≥0 under P_λ does not depend on λ.

Theorem 1.1.3. Let (X_n)_n≥0 be Markov (λ, P). Then, for all n, m ≥ 0:

• (i) P(X_n = j) = (λPⁿ)_j;
• (ii) P(X_n+m = j | X_m = i) = p⁽ⁿ⁾_ij.

Proof. (i) By Theorem 1.1.1:

P(X_n = j) = Σ_{i1, ..., in-1 ∈ I} λ_i1p_i1i2...p_in-1j = (λPⁿ)_j.

(ii) By the Markov property, conditional on X_m = i, (X_m+n)_n≥0 is Markov (δ_i, P), so we just take λ = δ_i in (i).

In light of this theorem, we call p⁽ⁿ⁾_ij the n-step transition probability from i to j. The following examples give some methods for calculating p⁽ⁿ⁾_ij.

Example 1.1.4: The most general two-state chain has a transition matrix of the form:

and is represented by the following diagram:

α → 1 → 2 → β