Graphics Programs Reference
In-Depth Information
The probability that the process is in state i at a given step n is denoted as
η
i
(n) = P
{
X
n
= i
}
(A.11)
and it can be evaluated from the knowledge of the transition probabilities
and of the initial PDF at time 0.
Moreover, in the case of DTMCs, the probabilistic behaviour of the pro-
cess is completely described by the initial distribution and by the one-step
transition probabilities.
A.3.1
Steady-State Distribution
An important problem that arises in the study of DTMCs concerns the
existence and the evaluation of the steady-state distribution.
In order to present the main results concerning the steady-state analysis of
DTMCs we must introduce several definitions concerning the chain and its
states.
Let
f
(n)
= P
{
first return in state j occurs n steps after leaving it
}
(A.12)
j
and
∞
X
f
(n)
= P
{
ever returning in state j
}
(A.13)
f
j
=
j
n=1
A state j is said to be transient if f
j
< 1, i.e., if there is a nonzero probability
of never returning to state j after leaving it. A state j is said to be recurrent
if f
j
= 1, i.e., if the process returns to state j with probability one after
leaving it.
Define the period of a state j, d
j
, as the greatest common divisor of all
positive integers n such that it is possible to reach state j from state j in
n steps. A recurrent state j is said to be periodic with period d
j
, if d
j
> 1,
and aperiodic if d
j
= 1.
A state j is said to be absorbing if p
jj
= 1. An absorbing state is recurrent.
For a recurrent state j define the mean recurrence time M
j
as
∞
X
n f
(n)
M
j
=
(A.14)
j
n=1
The mean recurrence time is the average number of steps needed to return
to state j for the first time after leaving it.
Recurrent states for which M
j
<
∞
are said to be recurrent nonnull. Re-
current states for which the mean recurrence time is infinite are said to be
recurrent null. In the case of finite DTMCs, recurrent states cannot be null.
Since we only consider the finite state space case, we shall use the term
recurrent implying recurrent nonnull.
Search WWH ::
Custom Search