Birth-Death Data Birth-Death Model Finite Queue Random Walk
 Dynamic Programming Data - Random Walk Model

The data form for the random walk problem is shown below. 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 E/W direction. There is a wall at 0 and another at 3 in both directions.

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. The example shows the walker as the yellow circle located at grid point (1, 2). 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 nine 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, 4 and 5 representing the directions N, S, W, E and Null, respectively. With the Null event state does not change.

Red outlines identify most of the cells that are filled by the DP Data add-in. Some of the titles that are filled 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 (1,2) 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. 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 five moves, including the null move. 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 cost and probability. 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 (1, 2) 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 moves. There are five of these including the null move. 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 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 (2, 2). 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.

Summary

This page has demonstrated the DTMC model 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 it is filled 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.

Operations Research Models and Methods
Internet
by Paul A. Jensen