

Example
Problem


Computer
Repair 

A real estate office that relies on two aging computers
for word processing is experiencing high costs and great
inconvenience due to chronic machine failures. It has been
observed that when both computers are working in the morning,
there is a 30% chance that one will fail by evening and a
10% chance that both will fail. If it happens that only one
computer is working at the beginning of the day, there is
a 20% chance that it will fail by the close of business.
If neither is working in the morning, the office sends all
work to a typing service. In this case, of course, no machines
will fail during the day. Service orders are placed with
a local repair shop. The computers are picked up during the
day and returned the next morning in operating condition.
The oneday delay is experienced when either one or both
machines are under repair. 

Time 

For a DTMC, the system is observed
at discrete points in time that are indexed with the nonnegative
integers. Time t = 0 is the initial point of observation.
It is important to identify carefully the exact moment when the
system is to be observed in relation to the events described
by the problem statement. For the example, the system is to be
observed in the morning after any repaired computers are returned
and before any failures have occurred during the current day. 
State 

The state describes the situation
at a point in time. Because the states are required to be discrete
they can be identified with nonnegative integers 0, 1, 2, 3...
and so on. There may be a finite or an infinite number of states.
For this introductory discussion, it is easier to concentrate
on the finite case and use m  1 as the maximum state
index. The sequence of random variables
is the stochastic process that describes the state at time t.
Each can
take one of m values.
Depending on the situation, the state may be very complex
or very simple. We use a vdimensional vector of state
variables to define the state.
In constructing a model, it must be made clear what the onetoone
relationships are between the possible state vectors and the
nonnegative integers used to identify a state in a DTMC. We
call the state associated with index i, .
Depending on the context, i typically ranges from 0
to m  1 or from 1 to m. The state definition
must encompass all possible states; however, the system can
reside in only one state at any given time.
The computer repair example allows a simple state definition
with only one component, s = (n), where n is
the number of computers that have failed when the system is
observed in the morning. Note that the system is observed after
the repaired units are delivered but before any failures occur.
The list of possible states for the example appears in Table
1. The value of m is 3. In this case, the state index
is conveniently identical to the variable defining the state;
however, this relationship will not always be true. We assign
a cost of operating the system for one day that depends on
how many computers are failed. The cost is $50 per computer
failed. This cost is a function of the state.
Table 1. States for
the example 
Index 
s 
State definitions 
Cost 
0 

No computers have failed. The office starts the day with
both computers functioning properly. 
0 
1 

One computer has failed. The office
starts the day with one working computer and the other
in the shop until the next morning. 
50 
2 

Both computers have failed. All work
must be sent out for the day. 
100 

Events 

To understand the behavior of
a DTMC, it is necessary to identify the events that might occur
during a single time period and to describe their probabilities
of occurrence. Generally, the set of possible events and their
probabilities depend on the state s.
Given some current state at the beginning of a period and
one or more events occurring during the period, the system
will be in some new (next) state at the beginning of
the next period. This occurrence is called a transition. One
or more events may occur within the period, and by observing
them, we must identify the resulting new state at the beginning
of the next period.
For the computer example we list the current states in Table
2 together with the set of possible events that might occur
during the day. Given the current state and the problem description,
one must be able to determine the probability of every possible
transition for the upcoming period. We use colored bands to
distinguish the states. Note that each state has one or more
associated events and that the sum of the probabilities for
each state must equal 1. The cost column represents the repair
cost of the computers assummed to be $40 per computer repaired.
Table 2. Events, probabilities
and transitions 
Index 
s 
Events 
Probability 
Next state 
Cost 
0 

Neither computer fails. 
0.6 
(0) 
0 


One computer fails. 
0.3 
(1) 
40 


Both computers fail. 
0.1 
(2) 
80 
1 

The remaining computer does not fail and the other is
returned. 
0.8 
(0) 
0 


The remaining computer fails and the other is returned. 
0.2 
(1) 
40 
2 

Both computers have failed. No failures
can occur. 
1.0 
(0) 
0 

StateTransition Matrix 

The major properties of a DTMC
model can be described with the m x m statetransition
matrix P whose rows and columns are labeled 0 through m 
1. An element of the matrix, ,
is the probability that given the system is in state i at
some time t, the system will be in state j at
time t + 1. A requirement of a DTMC is that the transition
probability depends only on the current state i and
not on the particular path that the process takes to reach
state i.
The transition matrix for the computer example is easily constructed
from the data in Table 2. The state indices are shown to the
right and above the matrix.
Some general characteristics of the transition
matrix are as follows.
 The elements of a row must sum to 1. This follows from
the logical requirement that the states define every possible
condition for the system.
 All elements are between 0 and 1. This follows from the
definition of probability.

StateTransition Network 

The information in the transition
matrix can also be displayed in a directed network which has
a node for each state and an arc passing from state i to
state j if is
nonzero. The figure depicts the network for the computer repair
example. Transition probabilities are adjacent to the arcs.
A requirement is that the sum of all probabilities leaving
a node must be 1.

Complete Model 

A DTMC model requires
the specification of the following.
 The times when the system is to be observed.
 The discrete states in which the system may be found. The
list of states must be exhaustive. In addition, a onetoone
correspondence must be prescribed between the states and
the nonnegative integers.
 The statetransition matrix showing the transition probabilities
in one time interval. Transition probabilities must satisfy
the Markovian property, and every row must sum to one.
Although the model structure is easily stated
it is not always easy to realize. For example, one might propose
time and state definitions (parts (1) and (2) above) for which
the Markovian property is not satisfied. This may sometimes
be remedied by a more complex state definition.
Because a DTMC model is very general it can be
used to describe many interesting stochastic systems. In many
cases, however, the number of states required to adequately
define the model is very large. As with dynamic programming,
this "curse of dimensionality"
frequently arises when we try to identify all possible states
of the system. 


