Page 226 - DCAP601_SIMULATION_AND_MODELING

Simulation and Modelling

Notes t
ds
s
X  t  1 0  X ( ) , t  0,
t
Where X(t) = f(Y (t)). (With the discrete state space, we write both f(j) and f for the value of f at
j
argument j.)
A finite-state CTMC is characterized by its infinitesimal generator matrix Q  (Q ); Q is understood
ij ij
to be the derivative (from above) of the probability transition function
Y
t
P , i j ( )  P ( (s t  j | ( ) i )
s

Y

)
with respect to time t evaluated at t = 0. However, in applications the model is specified by
defining the infinitesimal generator Q. Then the probability transition function can be obtained
subsequently as the solution of the ordinary differential equations
P(t) = P(t)Q = QP(t) ;
which takes the form of the matrix exponential
k k
 Q t
P ( ) e Qt   .
t

k 0 k !
Key asymptotic quantities associated with a CTMC are the stationary probability vector  and
the fundamental matrix Z. (By convention, we let vectors be row vectors.) The stationary probability
vector  can be found by solving the system of equations
m
 Q  0 with    1.
i
i 0
The quantity we want to estimate is the expected value of the function f (represented as a row
vector) with respect to the stationary probability (row) vector , i.e.,
m
  f  T    i i , f
i 0
where T is the transpose.
We would not need to conduct a simulation to estimate  if indeed we can calculate it directly as
indicated above. As noted before, in intended applications of this planning approach, the actual
model of interest tends to be more complicated than a CTMC, so that we cannot calculate the
desired quantity  directly. We introduce a CTMC that is similar to the more complicated model
of interest, and use the CTMC analysis to get rough estimates of both  and the required
computational effort in order to estimate  by simulation. We will illustrate for queueing
models later.
To continue, the fundamental matrix Z describes the time-dependent deviations from the
stationary vector, in particular,


t
dt
, i j 
Z  [P , i j ( )   j ] .
0
Given the stationary probability vector, , the fundamental matrix Z can be found by first
forming the square matrix II, all of whose rows are the vector , and then calculating

1

Z  (II Q )  II ,
with the inverse always existing; again see Whitt (1992) and references therein. We now consider
how the desired asymptotic parameters can be expressed in terms of the stationary probability
vector  and the fundamental matrix Z, including ways that are especially effective for
computation.

220 LOVELY PROFESSIONAL UNIVERSITY