To illustrate the components of a stochastic process,
we use the example of a single automated teller machine
(ATM) located in foyer of a bank. The ATM performs
banking operations for arriving customers. Only
one person at a time can use the machine and that person
is said to be in service. Other customers
arriving when the machine is busy must wait in a single
queue; these persons are said to be in the queue.
Following the rule of first-come-first-served and
assuming that the average arrival rate is less than the
average service rate, a person in the queue will eventually
step up to the ATM, execute a series of transactions,
and then leave the system. The number of persons
in the system at any point in time is the sum of the number
in service and the number in the queue.
Time
Many situations are conveniently described by a sequence
of events that occur over time. For example, the
number of persons (in the queue or in service) in front
of the ATM depends on the particular sequence of arrivals
and departures.
Events occurring in continuous time
In the figure, time is a treated as a continuous parameter
but events occur at specific instances. We use t
to represent time and use subscripts to identify
the specific instances.
State
The state describes the attributes of a system at some
point in time. For the ATM, the state indicates
the number of persons in the system (either in service
or in the queue). It may be limited to a maximum
value determined by the physical size of the bank foyer
or it may be unlimited for practical purposes if a line
is allowed to form outside the building. The minimum
number is of course zero, occurring when there are no
customers in service. In this case, the machine
is said to be idle.
Depending on the situation, the state may be very complex
or very simple. To provide for this variety, we
use an m-component
vector,
to describe the state. The ATM example allows
a simple state definition with only one dimension.
Here
s
= (n)
where n is the
number in the system. To speak of the state at time
,
we attach the subscript i
to the state vector to get .
It is often convenient to assign a unique nonnegative
integer index to each possible value of the state vector.
We call this X
and require that for each s there is a unique
value of X.
For the ATM example, an obvious assignment is X = n.
For more complex state definitions there may be several
possible assignments describing different characteristics
of the system. X(t)
is the value of the variable at time t.
Because of the random nature of a stochastic process,
the future realization of X(t)
is usually not predictable with certainty. Rather
X(t) is
a random variable. To understand the behavior of
the system under study, it is necessary to describe the
statistical properties of this random variable.
The set of all possible states is called the state
space and is denoted by S. In
general, a state space may be either continuous or discrete
but here we limit our attention the discrete case only.
For the ATM example, the set of all nonnegative integers
can be used to describe the number of persons in the system
at any instance, so
S = {0, 1, 2,...}.
This is an infinite state space and assumes that there
is no limit to the number of persons that can be in the
system. If the physical dimensions of the bank foyer
restrict the number of customers to a maximum K, the state space is finite, and
S = {0, 1, 2,...,K}.
Activities and Events
The dynamic nature of a system is evidenced by its activities.
Each activity has some time interval between its initiation
and completion, called the duration. An activity
culminates in an event. In the ATM
example there are two activities, one associated with
service and the other with arrivals. The service activity
begins when a customer first appears in front of the ATM
and ends when all her banking transactions are completed
and she departs. This event is typically referred
to as a service completion. The duration
of the activity that leads to this event is the time
for service.
The arrival activity begins immediately after a customer
arrives and ends with the arrival of the next customer.
The event is an arrival and the duration of the
accompanying activity is the time between arrivals.
Symbolically, we use letters to designate activities
and events. Because each activity leads to a unique
event, we use the same letter for both the activity and
the subsequent event. For the current example, a
is used to represent the arrival activity as well as the
event of an arrival, and d to represent the service
activity as well as the event of service completion (and
departure of the customer).
The duration of each activity is a random variable governed
by a probability distribution. This is the probabilistic
element of the stochastic process. The time for
service, ,
and the time between arrivals, ,
may be described by their respective cumulative distribution
functions
and ..
Generally speaking, the set of possible activities, and
thus the set of possible events, depends on the state
of the system. For example, when there are no customers
in the system, the service activity is not active and
no departure can occur. If there is some upper limit
on the number of customers that can wait in the queue,
no arrival can occur when the queue is full. We
use the notation Y(s) to describe
the set of possible activities (events) for state s.
For the ATM example, we have
Y(0) = {a}; Y(n)
= {a, d} when 0 < n < K;
Y(K) = {d}.
The cardinality of Y(s) may be infinite
or finite, depending on the situation. In what follows,
the term calendar is used to describe Y(s).
The set of activities that may occur while in state s
determines the calendar for the state.
Given the current state s, one of the events in
Y(s) will occur next. This
next event and the time it takes place have important
effects on the state of the system. Let x be
the next event and
be the time that it occurs. When the activity durations
are random variables, x and
are random variables. By definition,
where x is the event for which the minimum is
obtained.
Transition
A transition is caused by an event and results in movement
from one state to another. Thus it always relates
to two states. For convenience we will say that
a transition describes the movement from the current
state to the next state. There are cases, however, in which the
current state is allowed to be the same as the next state.
A state-transition network is used to describe the components
of the stochastic model. In the diagram, each state
is represented by a node and the possible transitions
by directed arcs. Each arc originates at one state
and terminates at another. The event leading to
the transition is shown adjacent to the arc. The
figure depicts the network for the ATM example.
An arrival causes a transition to the next higher state,
and a departure causes a transition to the next lower
state.
State-transition network for ATM example
When the stochastic process is relatively
simple, the transitions can be represented graphically
as in the figure. For complex situations we use
a transition function.
This function gives the value of the next state in terms
of the current state and the next event. Let the
current state be s and the next event be
x. Let s'
be the next state determined by the transition function
T(s,x),
such that
s'
= T(s,x).
When the state vector has more than one component, the
transition function is multidimensional. It describes
how each component of the state vector changes when the
event occurs.
For the ATM example, the transition equation is
s'
= s + 1
if x = a and
s'
= s - 1
if x = d.
The Process
The state, the activity and event definitions, the probability
distributions for activity durations, and the state-transition
network are sufficient to describe a stochastic process.
In more formal terms, we have the following.
Definition 1: A stochastic process is a collection
of random variables {X(t)},
where t
is a time index that takes values from a given set T.
Both X(t)
and T may be continuous or discrete, giving rise to four different
categories of models. We consider here only finite discrete
state space ( X(t) is
finite and discrete). Both continuous and discrete time
models are considered.
A Markov process is a special case of a stochastic process
in which all the information concerning the model is entirely
determined by the current state. It is often said
to be memoryless because the future realization depends
only on the current state and in no way on the past.
Definition 2: Markovian property - Given that the
current state is known, the conditional probability of
the next state is independent of the states traversed
prior to the current state.
|