

\documentstyle[12pt]{article}


\def\x1_to_n{x_{1}, x_{2}, x_{3}, \ldots, x_{n}}
\def\then{\rightarrow}
\def\lthen{\Rightarrow}
\def\iff{\leftrightarrow}
\def\liff{\Leftrightarrow}
\def\lor{\vee}
\def\land{\wedge}
\def\inter{\cap}
\def\union{\cup}
\def\gap{\hspace{5em}}
\def\sgap{\hspace{2em}}
\def\tgap{\vspace{2ex}}
\def\compl{\sim\!}
\def\ar{\rangle}
\def\al{\langle}
\def\xy{\mbox{$\langle x,y\rangle $}}

\newcommand{\limp}[1]{\mbox{$\lthen$\makebox[0pt][r]{\raisebox{-1.2ex}{\tiny $#1$\ }}}}
\newcommand{\blimp}[2]{\mbox{$\lthen$\makebox[0pt][r]{\raisebox{-1.2ex}{\tiny $#1$\ }}\makebox[0pt
][r]{\raisebox{1.3ex}{\scriptsize $#2$\ }}}}

\newcommand{\ass}{\noindent {\bf Assignment(s)}\par\noindent}

\newcommand{\question}{\par \noindent}

\begin{document}


{\LARGE \bf Program for Markov Chain Analysis}

\section{Generalities}

The program ``ctmarkov'' is a menu-driven program to calculate transient and
equilibrium solutions for Markov chains. The program can deal with both
discrete-time and continuous-time Markov chains. The input is either from
file or from the terminal. It is also possible to save the transition matrix
onto a file. The transient and equilibrium solutions cannot be
saved on file. They can, however, be recovered by using script as described
below. The details of the program are now discussed. We will use two
examples. The first examples involves a discrete-time Markov chain with the
transition matrix

\begin{tabular}{rrr}
0.2 & 0.4 & 0.4\\
0.5 & 0.1 & 0.4\\
0.4 & 0.5 & 0.1\\
\end{tabular}

\noindent
The transition matrix of the second example is

\begin{tabular}{rrr}
-4 & 2 & 2\\
1 & -5 & 4\\
0 & 4 & -4\\
\end{tabular}

For both cases, transient and equilibrium solutions will be obtained.
To use the program, the only thing you need to do is to type ``ctmarkov''
on a line for itself in a window.

\section{The Input Menu}

At the beginning of the program, the transition matrix must be entered.
There are several ways to do this. The selection is done by means of a menu,
namely the input menu.  This menu comes up immediately after typing
ctmarkov. The input menu can also be selected from the main menu as will be
shown later.  Here is a copy of the start of a typical session.
(The string ``sk4898'' is a prompt of the operating system, and it gives the
name of the computer you are using. Other computers have other prompts.)
\begin{verbatim}
sk4898 [8]>ctmarkov

Solution for Markov chains

Input Menu
Available Options
0. Go to main menu
1. Read entire matrix from file
2. Read entire matrix from terminal
3. Read individual entries from terminal
4. Update matrix
5. Print matrix on terminal
Enter 0, 1, 2, 3, 4, or 5
\end{verbatim}

Since we do not have a file yet, we read the transition matrix from the
terminal. To do this, we type a 2 to select option ``Read entire matrix
from terminal''.  The matrix of the first example is now entered.
The program now asks for the number of states, which is 3. After that,
the entries of the transition matrix are requested, according to the
following session transcript.
For clarity, we repeat the line which prompts for the desired option.
\begin{verbatim}
Enter 0, 1, 2, 3, 4, or 5 2

Number of states? 3
matrix(1,1) = 0.2
matrix(1,2) = 0.4
matrix(1,3) = 0.4

matrix(2,1) = 0.5
matrix(2,2) = 0.1
matrix(2,3) = 0.4

matrix(3,1) = 0.4
matrix(3,2) = 0.5
matrix(3,3) = 0.1
\end{verbatim}
After the matrix has thus been entered, the input menu cames up again.
Of particular importance are menu items 4 and 5. Menu item 4 allows you
to change individual entries of your matrix. This is, for instance
useful for correcting errors. Suppose, for instance, that you entered
0.5 rather than 0.4 for matrix(1,2). In this case, you can select option
4, ``Update matrix'', and enter the correct value. The dialog is as follows
\begin{verbatim}
Available Options
0. Go to main menu
1. Read entire matrix from file
2. Read entire matrix from terminal
3. Read individual entries from terminal
4. Update matrix
5. Print matrix on terminal
Enter 0, 1, 2, 3, 4, or 5 4
Give entries. End with zero.
Give row and column 1 2
matrix(  1,  2) = 0.4
Give row and column 0
\end{verbatim}
Note that option 4 prompts for individual entries. If you made several errors,
you can thus change more than one entry. First, you have to give the row and
the column of the entry, which is 1 and 2, respectively. After that, the new
value of the entry must be given, which is 0.4. Once all changes are done, one
must type a zero in place of the row to return to the input menu.

Sometimes, matrices are sparse, and in this case, it is economical
to enter only the entries which are different from zero, of which there
are only few.  To do this, one chooses option 3
``Read individual entries from terminal''. This option works exactly like
option 4, except that the matrix is set to zero initially.

At some stage, you may not be sure what the entries of the matrix are. No
problem. You can always use option 5 of the input menu and the matrix appears
in your window.
Finally, there may be a file which contains the transition matrix, and in
this case, you can read the file by using option 4. This is of interest
because the program has a save facility to save the transition matrix
for later use. We return to this point.

\section{The Main Menu}

After all data has been entered, the calculations can begin. 
To select the proper options, we have to go to the main menu.
This is done by typing the option 0 ``Go to main menu'' while in the
input menu. The result of option 0 is as follws.
\begin{verbatim}
Main Menu
Available Options
0. Quit
1. Input or update matrix
2. Find equilibrium vector
3. Discrete time transient solution
4. Continuous time transient solution
5. Save matrix
Enter 0, 1, 2, 3, 4, or 5 
\end{verbatim}
Suppose that we want to find the transient probabilities.
We choose option 3, ``Discrete time transient solution''. Of course, we
have to give the initial probabilities, and the time up to which transient
solutions are to be calculated. This is done in the following way.
\begin{verbatim}
Enter 0, 1, 2, 3, 4, or 5 3

Initial Probabilities
prob(  1) = 1
prob(  2) = 0
prob(  3) = 0

Give time of last transient probability 4
\end{verbatim}
In the first of these lines, we select option 3. In line 4, 5 and 6, we
enter the initial probabilities. They are, respectively, 1, 0 and 0, indicating
that the system starts in state 1. The last line, finally, indicates that
we want to find the transient probabilities for times  1, 2, 3 and 4. The
system reponds with the transient probabilities as desired.
\beg��e���������l����܁��z|�|����t
.20000    0.40000    0.40000  

Transient Probabilities for time   2
  0.40000    0.32000    0.28000  

Transient Probabilities for time   3
  0.35200    0.33200    0.31600  

Transient Probabilities for time   4
  0.36280    0.33200    0.30520  

Options at this point
0. Go to main menu
1. Start over
2. New Time
0, 1 or 2? 
\end{verbatim}
As one can see, a menu comes up after the output of the transient probabilities.
Option 1 lets you start with new initial probabilities, and option 2 allows
us to increase your time form, say 4 to 7. You may want to experiment with
these options. Here, we return to the main menu to calculate the steady-state
probabilities. Hence, we choose option 0, and once we are in the main menu,
we choose option 2. In detail, one has
\begin{verbatim}
Main Menu
Available Options
0. Quit
1. Input or udate matrix
2. Find equilibrium vector
3. Discrete time transient solution
4. Continuous time transient solution
5. Save matrix
Enter 0, 1, 2, 3, 4, or 5 2

Equilibrium Probabilities

  0.36095 
  0.33136 
  0.30769 
\end{verbatim}
At this stage, we have all the results we wanted to have for the discrete-time
Markov chain, and we can now enter the continuous-time Markov chain. However,
before we do this, in may be wise to save the transition matrix for later use.
This is done by using option 5 ``Save matrix''. To do this, we have to
provide a filename under which the file can be referenced. Suppose we want
to save the matrix under the name ``ex1''.
This is done as follows
\begin{verbatim}
Enter 0, 1, 2, 3, 4, or 5  5

Give filename ex1
\end{verbatim}
After the file is saved, the system returns to the main menu. We choose
option 1, which brings us to the input menu. We now read the matrix
of our second example, which is

\begin{tabular}{rrr}
-4 & 2 & 2\\
1 & -5  & 4\\
0 & 4 & -4\\
\end{tabular}

Since this is done the same way as in the discrete case, we skip this step.
Actually, in the case of the continuous-time Markov chain, one can enter any value
into the diagonal: the procedures used in the case of continuous-time Markov
chains simply ignore these elements.
After entering the matrix, the system returns to the main menu. We now choose
option 4 ``Continuous time transient solution''. We start in state 1, and
calculate
first the probabilities for time 2, then for time 3. The details are as follows
\begin{verbatim}
Enter 0, 1, 2, 3, 4, or 5 4

Initial Probabilities
prob(  1) = 1
prob(  2) = 0
prob(  3) = 0

For which time do you want a solution? 2.0

Probabilities for time   2.00
  0.10539   0.42100   0.47361 

Options at this point
0. Go to main menu
1. Start over
2. New Time
0, 1 or 2? 2

For which time do you want a solution? 3

Probabilities for time   3.00
  0.10526   0.42105   0.47368 
\end{verbatim}
We seem to be close to the equilibrium. We check this by calculating the
equilibrium probabilities, which are obtained by returning to the main menu
and choosing option 2. One finds
\begin{verbatim}
Equilibrium Probabilities

  0.10526 
  0.42105 
  0.47368 
\end{verbatim}
After this, our task is complete.

\section{Some Useful Unix Commands}

The ACL-lab runs under Unix, a very well known operating system. Unix has
a great variety of commands which may prove useful. A small subset of
commands is listed below. Further details of these commands can be found
by typing ``man'', followed by the command name.
\begin{tabbing}
Command\ \ \ \ \ \ \ \= Use\\
\\
ls \> Lists all files in directory\\
cp file1 file2 \> renames file1 to become file2\\
cp file1 file2 \> copies file1 into file2\\
script \> records of all action on terminal in the file typescript\\
exit \> In script: finishes recording\\
\> Otherwise: closes window.\\
more filename \> Lists file, one window at a time.\\
\> To get next window, press spacebar.\\
lpr filename \> prints file on lineprinter\\
\end{tabbing}
A typical session would be as follows, except that you do not have sk4898,
but the name of the computer you are woring on
\begin{verbatim}
sk4898 [2]> script
Script started, file is typescript.
sk4898 [5] ctmarkov

your work, ....

sk4898 [2]> exit
sk4898 [3]> Script done, file is typescript
sk4898 [6]> mv typescript myfile
sk4898 [7]> lpr myfile
\end{verbatim}
It is also possible to print the file typescript if you prefer to do this.
The disadvantage, of course, is that the next time you use script, the
old content of typescript is overwritten and consequently lost.

\ass
\question
1. In a queue with Poisson arrivals and exponential service times, nobody
joins if the number in the system is 2 or more. The arrival rate is 10 per
hour, and the service rate is 6 per hour. Formulate the problem as a Markov
chain, and use ctmarkov to find the the probabilities of having $i$ elements
in the system after one hour, where $i=0,1,2$. Use these probabilities
to find the average number in the system after one hour. Also, find the
equilibrium probabilities, and the average number in the system in equilibrium.
How close is the system to equilibrium after one hour?

\question
2. Solve the problem of question 1, except that arrivals ar now Erlang 2.
