
There are 3 programs in this directory:

 (1) Finite State Automata Simulation (fsa)
 (2) Semi-Markov Model Simulation (markov)
 (3) Pulse Process Simulation (pulse)

(2) MARKOV

This will provide you with link and state statistics given a semi-Markov
model. The input to MARKOV is a file formatted as follows:

#states time-for-simulation-run
adjacency matrix
label-for-state-1
label-for-state-2
...


Consider a simple cycle composed of 5 states. This is a Markov
implementation of the dining philosophers. We will simulate
a set of dining philosophers (numbered 1 through 5) by letting
philosopher 1 and 3 eat simultaneously, and then 2 and 4, and so on.
We will let each eating action (the time associated with a state)
be 3 minutes. A state, then, is specified as a pair (such as (1,3)).
We will specify each arc to be 1 minute. The arc represents a 
probabilistic change in state. Probabilities are shown in the 
following 5 state Markov process. We can see, for instance, that
philosophers 2 and 4 (the second state) have a greater chance of
eating again (probability = 0.4) right after their 3 minute eating
activity.

 

      0.1                       0.4                          0.1
      ---                       ---                          ---
      \ |                       \ |                          \ |
       \v  0.9          (2,4)    \v     0.6             (3,5) \v
 (1,3)  o ----------------------> o -------------------------> o
         ^                                                     |
          \                                                    | 0.9
           <----------- o <----------------- o <---------------
            0.8   (5,2) ^\        0.8  (4,1) ^\
                        | \                  | \
                        ---                  ---
                        0.2                  0.2

To try out this simulation do:

%make markov
%markov < dpm.dat

You can use Markov models to simulate a wide variety of probabilistic
phenomena that does not involve explicit queuing. Consider testing
the performance of an algorithm by encoding its flowchart as a Markov
model:

(NOTE: This flowchart is found in MacDougall "Simulating Computer Systems",
MIT Press, 1987, Page 28)


                               +----+
                               \    /
                                \  /
                                 \/
                                  |
                                  |
                                  v                          
                            +-----------+
                            |           |
                            |     1     |<--------------------------
                            +-----------+                           | 
                                  |                                 |
                                  v                                 |
                                  /\                                |
      +----------+              /    \                              |
  --->|          |   0.2      /        \                            |
 |    |    3     |<---------/      2     \                          |
 |    +----------+          \            /                          |
 |         |                  \        /                            |
 |         |                    \    /                              |
 |         |                      \/                                |
 |0.25     |                       | 0.8                            |
 |         v                       v                                |
 |         /\                     /\                                |
 |       /    \                 /    \                              |
 |     /        \             /        \  0.45   +-----------+      |
  -- /      4     \         /      5     \------>|           |      |
     \            /         \            /       |     6     |      |
       \        /             \        /         +-----------+      |
         \    /                 \    /                 |            |
           \/                     \/                   |            |
            | 0.75                 | 0.55              |            |
            |                      v                   |            |
             --------------------> O <-----------------             |
                                   |                                |
                                   |                                |
                                   v                                |
                             +-----------+                          |
                             |           |                          |
                             |     7     |                          |
                             +-----------+                          |
                                   |                                |
                                   v                                |
                                  /\                                |
                                /    \                              |
                              /        \   0.30                     |
                            /            \--------------------------+          
                            \      8     /
                              \        /
                                \    /
                                  \/
                                  | 0.70
                                  |
                                 /\
                                /  \
                               /    \
                                ----
                      


For the flowchart simulation, do:

%markov < flowchart.dat


SUGGESTED READING:

"Systems Analysis Using Simulation and Markov Models" by John Clymer,
Prentice Hall, 1990.

"Discrete Mathematical Models" by Fred S. Roberts, Prentice Hall, 1976.


