     Random Walk Data Markov Chains Walk Model for DDP  Dynamic Programming Data - Random Walk: Markov Chains 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.  Operations Research Models and Methods
Internet
by Paul A. Jensen    