Stochastic process fundamentals - Modelling with Generalised Stochastic Petri Nets - page 265

sojourn time, the original curve (solid line in Fig. A.2) describes the prob-
ability density of the sojourn duration, at the instant when the state is
entered.
After t units of time have elapsed without a change of state, we know that
the sojourn time will not be less than t. The uncertainty about the sojourn
time duration at this point is thus described by the tail of the exponential
pdf at the right of the abscissa t (shaded area in Fig. A.2) . However, in order
to obtain a valid pdf, it is necessary to rescale the tail so that it integrates
to one. By so doing, we obtain the dashed line in Fig. A.2, that is identical
to the original curve, except for a translation to the right of t time units.
This translation reflects the fact that, after t time units have been spent in
the state, the sojourn time is made of a constant part (the time that already
elapsed, equal to t) and a variable part (the time that will be further spent
in the state, called the residual sojourn time), whose pdf is obtained by
translating the dashed line in Fig. A.2 to the left by t time units. The final
result is thus that the residual sojourn time in a state at any instant always
has the same pdf as the whole sojourn time.

A.3 Discrete-Time Markov Chains

By specializing the Markov property to the discrete-time, discrete-space case
we obtain the definition of a DTMC

DEFINITION
The stochastic sequence { X n ,n = 0, 1, 2, ···} is a DTMC provided that

P { X n+1 = x n+1 | X n = x n , X n−1 = x n−1 , ··· , X 0 = x 0 }
= P { X n+1 = x n+1 | X n = x n }

(A.8)

∀ n ∈ IN, and ∀ x k ∈ S.
The expression on the right-hand side of the above equation is the (one-
step) transition probability of the chain, and it denotes the probability that
the process goes from state x n to state x n+1 when the index parameter is
increased from n to n + 1. We use the following notation

p ij (n) = P { X n+1 = j | X n = i } (A.9)

Since we only consider homogeneous DTMCs, the above probabilities do not
depend on n, so that we may simplify the notation by dropping the variable
n, and thus denote transition probabilities as

p ij = P { X n+1 = j | X n = i } (A.10)

This quantity provides the probability of being in state j at the next step,
given that the present state is i. Note that summing the probabilities p ij
over all possible states j in the state space S the result is 1.