Graphics Programs Reference

In-Depth Information

A state j is said to be transient if f
jj
< 1, i.e., if there is a positive probability

that the process never returns to state j after leaving it. A state j is said to

be recurrent if f
jj
= 1, i.e., if the process returns to state j in a finite time

with probability 1. A state i is said to be absorbing if q
ij
= 0 for all j
6
= i,

hence if q
ii
= 0. A subset A of the state space S is said to be closed if

X

X

q
ij
= 0

(A.34)

j∈A

i∈A

In this case p
ij
(t) = 0 for all i
∈
A, all j
∈
A, and all t > 0. The states in

A are thus not reachable from states in A.

A CTMC is said to be irreducible if no proper subset of S is closed, hence

if every state of S is reachable from any other state.

It can be shown that for all finite, irreducible, homogeneous CTMCs the lim-

iting probabilities exist, are independent of the initial distribution
{
η
j
(0),j
∈
S
}
,

and form the steady-state distribution, that can be computed by solving the

system of linear equations

X

q
ji
η
j
= 0
∀
i
∈
S

(A.35)

j∈S

together with the normalization condition

X

η
i
= 1

(A.36)

i∈S

In this case the states of the CTMC are ergodic, so that the chain itself is

said to be ergodic.

The mean recurrence time for a state j, M
j
, is defined as the average time

elapsing between two successive instants at which the process enters state

j. It can be shown that

M
j
=
−
1

η
j
q
jj

(A.37)

A.4.2

Matrix Formulation

Define the transition probability matrix P(t) as:

P(t) = [p
ij
(t)] , P(0) = I

(A.38)

and define the matrix

Q = [q
ij
] (A.39)

that is either called the infinitesimal generator of the transition probability

matrix P(t), or the transition rate matrix.

The matrix equation defining the steady-state distribution of an ergodic

CTMC together with
(A.36)
is

η Q = 0

(A.40)

where η is the vector

η =
{
η
1
,η
2
,
···}
(A.41)

Search WWH ::

Custom Search