

ATM
Example




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 firstcomefirstserved 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 mcomponent
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 statetransition 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.
Statetransition 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 statetransition 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. 


