 |
The data form for
the grid walk problem is shown below. This section cosiders
a model where the walker moves about the grid randomly with
the direction chosen governed by a probability distribution.
This is often called the random walk problem and we will use
this the term random walk on this page.
The structure allows
many alternative assumptions that can easily be accommodated
by the model structure. In the current example we describe
a random walk in two dimensions over a grid with maximum length
of 4 in both directions. The balk costs, move costs and move
probabilities for steps in the four directions are specified
in columns F through G. A Build
Table option
is available when the move costs are probabilities depend on
the current state. This
is a Discrete Time Markov Chain (DTMC) model.
The random walk takes place on the grid illustrated below.
In the example the grid points range from 0 to 3 in each of
two directions. The size of the grid depends on
the corresponding data in column E. We call one direction the
N/S direction and the other the W/E direction. There is a wall
at 0 and another at 3 in both directions. A state is described
its location on the grid (N/S, W/E). The yellow state indicated
below is at (2, 1)
A walker wanders around on the grid points randomly, and
walls constrain the walker. With the walker at some grid point,
he can move in any of four directions not constrained by a
wall. There is a fixed probability of traveling
in any direction and also a cost. When the walker tries to
move in the direction constrained by a wall, a balk cost is
expended, but the walker does not move. |
Build Model |
| |
Once the data is entered,
click the Build Model button to call the DP Models add-in.
The DP Data add-in calls
the DP Models add-in to construct the model on a new
worksheet. Problem parameters and control buttons are at the
upper-left corner. |
| |
|
| |
The model worksheet holds
descriptions of the states of the model and the events that cause
transitions from one state to another. There are no actions associated
with the DTMC model. The transitions are described by eight transition
blocks. |
States and Events |
| |
The Markov Chain model
requires only the State and Event elements.
The VBA code of the DP Data add-in specifies
the number of state variables and event variables to include
in the model. For this case there are two state variables,
one for each dimension. The state vector is the range
F14:G14. The single event variable identifies the moves with
the indices 1, 2, 3, and 4 representing the directions
N, S, W, and E.
Red outlines identify most of the cells that are filled by
the DP Data add-in. Some of the titles
are not outlined in red to make the figure more readable. .
For example the range F18:G19 holds formulas linking the cell
contents to the corresponding values on the data worksheet. M21
and M22 hold the cost and probability given for the events. |
| |
|
| |
The summary area in
columns O through R indicates whether the State is
feasible and whether the event leads to a feasible transition.
The current state is position (2, 1) and the current event
is to move South. The summary indicates that this state is
feasible and that the event leads to a state that is also feasible.
The number in Q20 indicates the transition block defining the
transition. |
Enumeration |
| |
|
The state definition appears
at the left. The state indicates the coordinates of the
current state. Clicking the List Elements button
at the top of the page enumerates all the elements of the
model. The state enumeration is accomplished by changing
the index value in E14 through all integer values from
0 to 15. The program does this automatically Sixteen states
are discovered and listed on the model lists worksheet.
Details concerning the states are shown below.
|
|
| |
 |
The event definition has only one component
indicating the move. There are four moves. The event
probability and cost cells hold formulas that link to the
data worksheet.
|
|
Transitions |
| |
The remainder of
the model describes transitions. With the system in
some state, the occurrence of an event may cause the state
to change. This portion of the model indicates the state/event
combinations that might occur with the associated costs and
probabilities. Also the model indicates the new state reached
when the event occurs. Starting in row 28 the model identifies
two sets of transitions, those that indicate a balk and those
that result in a move. The order of the transitions is important
since if more than one of the transitions is feasible, the
top one is chosen.
There are four balk transitions with two shown below. Each
transition block is associated with a balk for a certain boundary.
For example, the first transition is only possible when the
current point is at the north boundary. The lower and upper
bounds in cells F36 and F37 are both 0 indicating that this
block is only relevant at the north boundary. The balk occurs
only when the movement is toward the north as indicated by
the lower and upper bounds in L36 and L37. Since the current
state is (2, 1) and the movement is south, these logical requirements
are not met. This is indicated by the FALSE in Q34.
In like manner the conditions for block 2 will be feasible
only when the point is on the south boundary and the movement
is south. For the current state none of the balk transition
blocks are feasible. |
|
| |
The remainder of the
transitions describe the four moves.
The first two are below. We focus on transition block 6 because
it is feasible for the current state and event. Transition
block 6 is only relevant when the move value is 2, or south.
In that case the new state is shown in row 91. It is found
by adding 1 to the first state variable. The new state is (3,
1). It's cost, probability and index are in column Q. |
| |
|
| |
The
enumeration process combines all feasible states with all feasible
events. For those combinations that have a feasible transition,
the transition characteristics are listed in the transition list.
The first 28 transitions are below. The balk transitions are
indicated by the high costs. A balk transition does not result
in a state change, but there is a cost. There are 64 transitions
with nonzero probability. |
| |
|
Call Solver |
| |
The DTMC model admits
both the Markov Analysis and DP Solver methods. Here
we have clicked the Transfer to DP
Solver button.
The DP Solver add-in constructs the appropriate
Excel worksheet and the DP Models add-in inserts the
data defined by the model. The probability transition matrix
model for the example is shown below. |
|
| |
The economic transition
matrix is also constructed. The balk costs are on the diagonal
and the move costs are off the diagonal. |
|
| |
The figure below shows
the steady-state solution obtained with the DP
Solver
add-in The green column labeled Last Probabilities shows
the steady-state probabilities. The yellow column labeled State
Value shows the steady-state NPW values. The quantity
in M11 is the expected step value for the solution. |
|
Continuous Time Markov Chain |
| |
|
The data form for the CTMC
is similar to the DTMC except that column H contains rates
rather than probabilities. The model worksheet is built
by clicking the Build Model button. The model
is linked by formulas to the data worksheet, so the model
can be adjusted by simply changing the data. The titles
in column D describe the data items.
The model is the same as the model for the
DTMC except that rates are used for the event instead of
probabilities.
From the model worksheet we choose the Markov
Analysis method for solution.
|
|
| |
Clicking the Make Model button
on the top of the data worksheet, calls the DP Models add-in
to construct the model worksheet. The model is the same as
the DTMC except that rates rather than probabilities are used
for the event. No direct interaction with this model is necessary
to solve the walk problem. All the data is on the data worksheet.
Clicking the Transfer to Markov Analysis button
on the model worksheet creates a CTMC matrix model. |
|
| |
The transition costs appear in the
economic matrix. |
|
| |
The steady-state solution is shown
below. The expected transition times are equal for all states,
because all states have the same transition rates. |
|
The Approximating DTMC |
|
|
The data on the left corresponds to an approximation of
the CTMC solved above with a time step of 0.01 hours. The
probabilities are computed as the move rates multiplied by
the time step. The discount rate has also been adjusted for
the time step. The probabilities do not add to 1 because
the add-in assumes that all unspecified probabilities are
included with non-move probability.
Clicking the Build Model button creates the model
worksheet and clicking the Transfer to Markov Analysis button
on that worksheet constructs the matrix model.
The solution of this DTMC is shown below. The two solutions
are quite similar. The average cost rate for the CTMC is approximately
100 times more than the average cost for the DTMC, because the
period for the DTMC is 0.01 hours. |
 |
| |
|
Summary |
| |
This page has demonstrated
the two Markov Chain models for the random walk. The DP
Data add-in constructs a table holding the data.
By clicking the Build Model button
on the data worksheet, the DP Models add-in constructs
the model worksheet and fills it with the constants and
formulas that implement the model. By clicking the Transfer
to DP Solver button,
the DP Solver add-in creates the solution worksheet
and transfers the information from the list worksheet. All three
add-ins must be installed for all the steps to work.
The Markov Analysis add-in solves the CTMC. |
| |
|
