Jacques J., Raimondo M. Semi-markov risk models for finance, insurance and reliability
Подождите немного. Документ загружается.
Renewal theory and Markov chains
57
7 ASYMPTOTIC BEHAVIOUR OF THE ()Nt-PROCESS
This section will yield two important results concerning the counting process
()
(), 0Nt t≥ associated with a recurrent renewal process characterized by the
d.f.
F
.
Proposition 7.1 (Strong law of large numbers) If
∞
<
m , then, almost surely:
() 1
lim .
t
Nt
tm
→∞
= (7.1)
Proposition 7.2 (Central limit theorem) If
2
σ
<
∞ , then for all y
∈
:
2
3
()
lim ( ) ,
t
t
Nt
m
Pyy
t
m
σ
→∞
⎛⎞
−
⎜⎟
≤=Φ
⎜⎟
⎜⎟
⎝⎠
(7.2)
where Φ represents the standard normal d.f..
Remark 7.1 From Proposition 7.2, we have the following approximation for
large t :
2
3
var( ( )) ~ ,
N
tt
m
σ
(7.3)
which simplifies the exact result (4.40).
8 DELAYED AND STATIONARY RENEWAL
PROCESSES
The notion of stationary renewal process is a particular case of a delayed
renewal process. A delayed renewal process is a renewal process with the
difference that the first r.v.
1
,
X
though still independent of the others, does not
have the same distribution.
More precisely, let
()
,1
n
Xn≥ be a sequence of non-negative independent
variables,
G being the d.f. of
1
X
and F the d.f. of all other r.v.
The corresponding sequence
(
)
,0
n
Tn≥
, where
0
0T
=
a.s., (8.1)
1
,
nn
TX X
=
++ (8.2)
is called a delayed renewal sequence or delayed renewal process.
Clearly the basic definition of the “classical” renewal processes can be extended
to the case of a delayed renewal process. For example if ( )
d
H
t represents the
58 Chapter 2
renewal function for a delayed renewal process, and if we pose the condition
1
,
X
x=
then we have:
()
1
0,,
|
1(), ,
d
x
t
HtX x
Ht x x t
>
⎧
==
⎨
+
−≤
⎩
(8.3)
where H represents the renewal function associated with the d.f.
.
F
Since, by
definition:
(
)
(
)
11
|()
d
H
tX ENtX
=
, (8.4)
we get:
(
)
(
)
(
)
1
() ,
d
ENt EH tX
=
(8.5)
[]
0
1()().
t
Ht x dGx=+ −
∫
(8.6)
Or:
() ().
d
H
Gt H Gt
=
+•
(8.7)
So, knowing renewal function
,H
we are just a convolution product away from
knowing
d
H
.
This notion of delayed renewal process is introduced because it has been
remarked that if one begins to observe a renewal process which has been running
for a long time, the first variable
1
X
observed has the d.f.
[]
0
1
() 1 () , 0.
x
Gx Fu du x
m
=− ≥
∫
(8.8)
If we consider a delayed renewal process with the d.f. defined by relation (8.8)
for
G the d.f. of
1
,
X
it called a stationary renewal process.
9 MARKOV CHAINS
This section presents briefly some fundamental results concerning the theory of
Markov chains with a finite number of states. These results will be used in the
following chapter. We will use the usual terminology introduced by Chung
(1960) and Parzen (1962).
9.1 Definitions
Let us consider an economic or physical system
S
with
m
possible states,
represented by the set I :
{
}
1, 2, ,Im
=
…
. (9.1)
Let the system
S
evolve randomly in discrete time
(
)
0, 1, 2, , , ,tn
=
……
and
let
n
J
be the r.v. representing the state of the system
S
at time
n
.
Renewal theory and Markov chains
59
Definition 9.1 The random sequence
(
)
,
n
Jn
∈
Ν
is a Markov chain iff for all
01
,,, :
n
j
jjI
∈
…
(
)
(
)
0011 11 11
|, ,, |
nn n n nnn n
PJ j J j J j J j PJ j J j
−− −−
=== === =…
(9.2)
(provided this probability has meaning).
Definition 9.2 A Markov chain
(
)
,0
n
Jn≥
is homogeneous iff the
probabilities (1.2) do not depend on
n
and is non-homogeneous in the other
cases.
For the moment, we will only consider the homogeneous case for which we
write:
(
)
1
|,
nn ij
PJ
j
Jip
−
=
==
(9.3)
and we introduce the matrix
P defined as:
[
]
ij
p
=P . (9.4)
The elements of the matrix
P have the following properties:
(i)
0,
ij
p ≥
for all , ,ij I∈ (9.5)
(ii)
1,
ij
jI
p
∈
=
∑
for all
.iI∈
(9.6)
A matrix
P satisfying these two conditions is called a Markov matrix or a
transition matrix.
To every transition matrix, we can associate a transition graph where vertices
represent states. There exists an arc between vertices i and j iff
0.
ij
p >
To fully define the evolution of a Markov chain, it is also necessary to fix an
initial distribution for state
0
J
, i.e. a vector
(
)
1
,, ,
m
pp
=
p …
(9.7)
such that:
0, ,
i
piI≥∈
(9.8)
1.
i
iI
p
∈
=
∑
(9.9)
For all
,
i
ip
represents the initial probability of starting from i :
(
)
0
.
i
pPJ i
=
=
(9.10)
For the rest of this chapter we will consider homogeneous Markov chains as
being characterized by the couple
(
)
,pP
.
If
n
J
i=
a.s., that is if the system starts with probability equal to 1 from state i ,
then the components of vector
p will be:
j
ij
p
δ
=
. (9.11)
We now introduce the transition probabilities of order
()n
ij
p
, defined as:
60 Chapter 2
(
)
()
|
n
ij n
p
PJ j J i
νν
+
=
==. (9.12)
From the Markov property (9.2), it is clear that conditioning with respect to
1
J
ν
+
,
we get
(2)
.
ij ik kj
k
p
pp=
∑
(9.13)
Using the following matrix notation:
[
]
(2) (2)
ij
p
=P , (9.14)
we find that relation (9.13) is equivalent to
(2) 2
=
PP
. (9.15)
Using induction, it is easy to prove that if
[
]
() ()nn
ij
p=P , (9.16)
then we obtain for all
1n ≥ :
()nn
=
PP
. (9.17)
Note that (9.17) implies that the transition probability matrix in
n steps is equal
to the nth power of the matrix
P.
For the marginal distributions related to
,
n
J
we define for iI
∈
and 0n ≥ :
(
)
() .
in
pn PJ i
=
=
(9.18)
These probabilities may be computed as follows:
()
() ,
n
ijji
j
p
npp iI
=
∈
∑
. (9.19)
If we write:
(0)
j
iji
p
δ
= or
(0)
=
PI
, (9.20)
then relation (9.19) is true for all
0n ≥ .
If:
(
)
1
() (), , (),
m
npnpn
=
p …
(9.21)
then relation (9.19) can be expressed, using matrix notation, as:
() .
n
n =ppP
(9.22)
Definition 9.3 A Markov matrix P is regular if there exists a positive integer
k
,
such that all the elements of the matrix
()k
P
are strictly positive.
From relation (9.17),
P is regular iff there exists an integer 0k > such that all the
elements of the kth power of
P are strictly positive.
Example 9.1 (i) If:
.5 .5
10
⎡
⎤
=
⎢
⎥
⎣
⎦
P
(9.23)
we have:
Renewal theory and Markov chains
61
2
.75 .25
.5 .5
⎡
⎤
=
⎢
⎥
⎣
⎦
P
(9.24)
so that
P is regular.
The transition graph associated to
P is given in Figure 9.1.
Figure 9.1
(ii) If:
10
.75 .25
⎡
⎤
=
⎢
⎥
⎣
⎦
P
, (9.25)
P is not regular, because for any integer k ,
()
12
0.
k
p
=
(9.26)
Figure 9.2
The transition graph in this case is depicted in
Figure 9.2.
The same is true for the matrix:
01
10
⎡
⎤
=
⎢
⎥
⎣
⎦
P
. (9.27)
(iii) Any matrix
P whose elements are all strictly positive is regular.
For example:
12
.7 .2 .1
33
.6 .2 .2
13
.4 .1 .5
44
⎡⎤
⎡
⎤
⎢⎥
⎢
⎥
⎢⎥
⎢
⎥
⎢⎥
⎢
⎥
⎣
⎦
⎣⎦
. (9.28)
62 Chapter 2
9.2. Markov Chain State Classification
Let
iI∈
, and let ( )di be the greatest common divisor of the set of integers
n
,
such that
()
0.
n
ii
p >
(9.29)
Definition 9.4 If () 1di > , the state i is said to be periodic with period ()di. If
() 1di = , then state i is aperiodic.
Clearly, if
0
ii
p >
, then i is aperiodic. However, the converse is not necessarily
true.
Remark 9.1 If P is regular, then all the states are aperiodic.
Definition 9.5 A Markov chain whose states are all aperiodic is called an
aperiodic Markov chain.
From now on, we will have only Markov chains of this type.
Definition 9.6 A state i is said to lead to state
j
(written
ij
) iff there exists a
positive integer
n such that
0.
n
ij
p > (9.30)
ij
C means that i does not lead to j.
Definition 9.7 States i and
j
are said to communicate iff
ij
and
j
i
, or if
j
i=
. We write
ij
.
Definition 9.8 A state
i
is said to be essential iff it communicates with every
state it leads to; otherwise it is called inessential.
The relation
defines an equivalence relation over the state space I resulting
in a partition of I . The equivalence class containing state i is represented by
()Ci .
Definition 9.9 A Markov chain is said to be irreducible iff there exists only one
equivalence class.
Clearly, if
P is regular, the Markov chain is both irreducible and aperiodic. Such
a Markov chain is said to be ergodic.
Renewal theory and Markov chains
63
It is easy to show that if the state i is essential (inessential) then all the elements
of the class ( )Ci are essential (inessential) (see Chung (1960)).
We can thus speak of essential and inessential classes.
Definition 9.10 A subset
E
of the state space I is said to be closed iff:
1
ij
jE
p
∈
=
∑
, for all
iE
∈
. (9.31)
It can be shown that every essential class is minimally closed. See Chung (1960).
Definition 9.11 For given states i and
j
, with
0
,
J
i
=
we can define the r.v.
ij
τ
called the first passage time to state j as follows:
if , 0 , ,
if , for all 0.
n
ij
nJj nJj
Jj
ν
ν
ν
τ
ν
≠
<< =
⎧
=
⎨
∞≠ >
⎩
(9.32)
ij
τ
is said to be the hitting time of the singleton
{
}
j
, starting from state i at time
0.
Supposing:
(
)
()
00
|,
n
ij ij
fP nJi n
τ
=== ∈ (9.33)
and
(
)
0
|,
ij ij
f
PJi
τ
=<∞= (9.34)
one can see that for
0n > :
()
()
0
,,0|,
n
ij n
f
PJ j J j nJ i
ν
ν
== ≠<<= (9.35)
1
,,
1
'
0
,
kk
ni j
n
S
k
p
αα
+
−
=
=
∑
∏
(9.36)
where the summation set
,,
'
ni j
S
is defined as:
()
{
}
,, 0 1 0
',,,:,,,,1,,1.
ni j n n k k
SijIjkn
α
ααα α α α
===∈≠=−……
(9.37)
We also have:
()
1
,
n
ij ij
n
f
f
∞
=
=
∑
(9.38)
(
)
0
1|.
ij ij
f
PJi
τ
−= =∞ = (9.39)
The elements
()n
ij
f
can readily be computed by induction, using the following
relations:
(1)
,
ij ij
p
f= (9.40)
1
() () ( ) ()
1
,2
n
nnn
ij ij jj ij
pfpfn
νν
ν
−
−
=
=+≥
∑
. (9.41)
Let:
64 Chapter 2
(
)
0
|,
ij ij
mE Ji
τ
== (9.42)
with the possibility of an infinite mean. The value of
ij
m
is given by:
()
()
1
1.
n
ij ij ij
n
mnf f
∞
=
=−∞−
∑
(*)
(9.43)
If
ij=
, then
ij
m
is called the first passage time mean or the mean recurrence
time of state i .
For every
j
, we define the sequence of successive return times to state
(
)
()
,
j
n
jr na≥ as follows:
()
0
0
j
r
=
, (9.44)
{
}
() ()
()
0, 1 1
sup , , , 0.
jj
j
nnn
k
rkkrJjrkn
ν
ν
−−
=
∈Ν > ≠ < < >
(9.45)
Using the Markov property and supposing
0
,
J
j
=
the sequence of return times to
state
j
is a renewal sequence with the r.v.
()
()
1
,1
j
j
nn
rr n
−
−
≥
(9.46)
distributed according to
j
j
τ
.
If
0
,,
J
ii j=≠
then
(
)
()
,0
j
n
rn≥ is a general renewal sequence. In this case:
()
1
,
j
ij
r
τ
= (9.47)
and
()
()
1
~, 1.
j
j
nn jj
rr n
τ
−
−
> (9.48)
This shows that a Markov chain contains many embedded renewal processes.
These processes are used to define the next classification of states.
Definition 9.12 A state i is said to be transient (recurrent) if the renewal
process associated with its successive return times to i is transient (recurrent).
A direct consequence of this definition is that:
transient 1,
ii
if
⇔
<
(9.49)
recurrent 1.
ii
if
⇔
=
(9.50)
A recurrent state
i
is said to be null (positive) if
(
)
ii ii
mm
=
∞<∞
. It can be
shown that if
ii
m <∞
, then we can only have positive recurrent states.
This classification leads to the decomposition theorem (see Chung (1960)).
(*)
Using the following conventions:
,, ,(0)aa a a∞+ =∞ ∈ ∞⋅ =∞ > , and in this particular case, 00
∞
⋅=.
Renewal theory and Markov chains
65
Proposition 9.1 (Decomposition theorem) The state space I of any Markov chain
can be decomposed into (1)rr≥ subsets
1
,,
r
CC…
forming a partition, such
that each subset
i
C
is one and only one of the following types:
(i) an essential recurrent positive closed set,
(ii) an inessential transient non-closed set.
Remark 9.2
(1) If an inessential class reduces to a singleton
{
}
i
, there are two possibilities:
a) There exists a positive integer N such that:
01
N
ii
p
<
<
. (9.51)
b) The
N in a) does not exist. In this case, the state i is said to be a non-return
state.
(2) If the singleton
{
}
i
forms an essential class, then
1
ii
p
=
(9.52)
and the state i is said to be an absorbing state.
(3) If
m =∞
, there may be two other types of class in the decomposition
theorems:
a) essential transient closed,
b) essential recurrent non-closed classes.
The literature on Markov chains gives the following necessary and sufficient
conditions for recurrence and transience.
Proposition 9.2
(i) State i is transient iff
()
1
.
n
ii
n
p
∞
=
<
∞
∑
(9.53)
In this case, for all
:kI∈
()
1
,
n
ki
n
p
∞
=
<
∞
∑
(9.54)
and in particular:
()
lim 0, .
n
ki
n
p
kI
→∞
=
∀∈
(9.55)
(ii) State i is recurrent iff
()
1
.
n
ii
n
p
∞
=
=
∞
∑
(9.56)
In this case:
()
1
,
n
ki
n
ki p
∞
=
⇒=∞
∑
(9.57)
and
66 Chapter 2
()
1
0.
n
ki
n
ki p
∞
=
⇒=
∑
C
(9.58)
9.3 Occupation Times
For any state
,
j
and for
0
n ∈
, we define the r.v.
()
j
Nn
as the number of times
the state
j
is occupied in the first
n
transitions:
{
}
{
}
() # 1, , : .
jk
Nn k n J
j
=
∈=…
(9.59)
By definition, the r.v.
()
j
Nn
is called the occupation time of state j in the first n
transitions.
The r.v.
() lim ()
jj
n
NNn
→∞
∞
=
(9.60)
is called the total occupation time of state j.
For any state
j
and
0
n ∈
let us define:
1if ,
()
0if .
n
j
n
J
j
Zn
J
j
=
⎧
=
⎨
≠
⎩
(9.61)
We may write:
1
() ().
n
jj
Nn Z
ν
ν
=
=
∑
(9.62)
We have from relation (9.34):
()
0
P()0| .
j
ij
N
Ji f∞> = = (9.63)
Let
ij
g
be the conditional probability of an infinite number of visits to the state
j
, starting with
0
J
i=
; that is:
(
)
0
() | .
ij j
g
PN J i=∞=∞= (9.64)
It can be shown that:
()
lim
n
ii ii
n
gf
→∞
=
, (9.65)
ij ij jj
gfg
=
⋅
, (9.66)
11
ii ii
g
fi=⇔ =⇔
is recurrent, (9.67)
01
ii ii
g
fi=⇔ <⇔
is transient. (9.68)
Results (9.67) and (9.68) can be interpreted as showing that the system
S
will
visit a recurrent state an infinite number of times, and that it will visit a transient
state a finite number of times.