@c This file has been automatically generated from markovchains.txi
@c by proc.m. Do not edit this file, all changes will be lost

@c -*- texinfo -*-

@c Copyright (C) 2008, 2009, 2010, 2011, 2012, 2014, 2018 Moreno Marzolla
@c
@c This file is part of the queueing package.
@c
@c The queueing package is free software; you can redistribute it
@c and/or modify it under the terms of the GNU General Public License
@c as published by the Free Software Foundation; either version 3 of
@c the License, or (at your option) any later version.
@c
@c The queueing package is distributed in the hope that it will be
@c useful, but WITHOUT ANY WARRANTY; without even the implied warranty
@c of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
@c GNU General Public License for more details.
@c
@c You should have received a copy of the GNU General Public License
@c along with the queueing package; see the file COPYING.  If not, see
@c <http://www.gnu.org/licenses/>.

@node Markov Chains
@chapter Markov Chains

@menu
* Discrete-Time Markov Chains::
* Continuous-Time Markov Chains::
@end menu

@node Discrete-Time Markov Chains
@section Discrete-Time Markov Chains

Let @math{X_0, X_1, @dots{}, X_n, @dots{} } be a sequence of random
variables defined over the discrete state space @math{1, 2,
@dots{}}. The sequence @math{X_0, X_1, @dots{}, X_n, @dots{}}  is a
@emph{stochastic process} with discrete time @math{0, 1, 2,
@dots{}}. A @emph{Markov chain} is a stochastic process @math{@{X_n,
n=0, 1, @dots{}@}} which satisfies the following Markov property:

@iftex
@tex
$$\eqalign{P\left(X_{n+1} = x_{n+1}\ |\ X_n = x_n, X_{n-1} = x_{n-1}, \ldots, X_0 = x_0 \right) \cr
& = P\left(X_{n+1} = x_{n+1}\ |\ X_n = x_n\right)}$$
@end tex
@end iftex
@ifnottex
@math{P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, @dots{}, X_0 = x_0) = P(X_{n+1} = x_{n+1} | X_n = x_n)}
@end ifnottex

@noindent which basically means that the probability that the system is in
a particular state at time @math{n+1} only depends on the state the
system was at time @math{n}.

The evolution of a Markov chain with finite state space @math{@{1,
@dots{}, N@}} can be fully described by a stochastic matrix @math{{\bf
P}(n) = [ P_{i,j}(n) ]} where @math{P_{i, j}(n) = P( X_{n+1} = j\
|\ X_n = i )}.  If the Markov chain is homogeneous (that is, the
transition probability matrix @math{{\bf P}(n)} is time-independent),
we can write @math{{\bf P} = [P_{i, j}]}, where @math{P_{i, j} = P(
X_{n+1} = j\ |\ X_n = i )} for all @math{n=0, 1, @dots{}}.

@cindex stochastic matrix

The transition probability matrix @math{\bf P} must be a
@emph{stochastic matrix}, meaning that it must satisfy the following
two properties:

@enumerate
@item @math{P_{i, j} @geq{} 0} for all @math{1 @leq{} i, j @leq{} N};
@item @math{\sum_{j=1}^N P_{i,j} = 1} for all @math{i}
@end enumerate

Property 1 requires that all probabilities are nonnegative; property 2
requires that the outgoing transition probabilities from any state
@math{i} sum to one.

@c
@anchor{doc-dtmcchkP}


@deftypefn {Function File} {[@var{r} @var{err}] =} dtmcchkP (@var{P})

@cindex Markov chain, discrete time
@cindex DTMC
@cindex discrete time Markov chain

Check whether @var{P} is a valid transition probability matrix.

If @var{P} is valid, @var{r} is the size (number of rows or columns)
of @var{P}. If @var{P} is not a transition probability matrix,
@var{r} is set to zero, and @var{err} to an appropriate error string.

@end deftypefn


A DTMC is @emph{irreducible} if every state can be reached with
non-zero probability starting from every other state.

@anchor{doc-dtmcisir}


@deftypefn {Function File} {[@var{r} @var{s}] =} dtmcisir (@var{P})

@cindex Markov chain, discrete time
@cindex discrete time Markov chain
@cindex DTMC
@cindex irreducible Markov chain

Check if @var{P} is irreducible, and identify Strongly Connected
Components (SCC) in the transition graph of the DTMC with transition
matrix @var{P}.

@strong{INPUTS}

@table @code

@item @var{P}(i,j)
transition probability from state @math{i} to state @math{j}.
@var{P} must be an @math{N \times N} stochastic matrix.

@end table

@strong{OUTPUTS}

@table @code

@item @var{r}
1 if @var{P} is irreducible (i.e., the state transition graph is
strongly connected), 0 otherwise (scalar)

@item @var{s}(i)
strongly connected component (SCC) that state @math{i} belongs to
(vector of length @math{N}). SCCs are numbered @math{1, 2, @dots{}}.
The number of SCCs is @code{max(s)}. If the graph is
strongly connected, then there is a single SCC and the predicate
@code{all(s == 1)} evaluates to true

@end table

@end deftypefn


@menu
* State occupancy probabilities (DTMC)::
* Birth-death process (DTMC)::
* Expected number of visits (DTMC)::
* Time-averaged expected sojourn times (DTMC)::
* Mean time to absorption (DTMC)::
* First passage times (DTMC)::
@end menu

@c
@c
@c
@node State occupancy probabilities (DTMC)
@subsection State occupancy probabilities

Given a discrete-time Markov chain with state space @math{@{1,
@dots{}, N@}}, we denote with @math{{\bf \pi}(n) = \left[\pi_1(n),
@dots{} \pi_N(n) \right]} the @emph{state occupancy probability
vector} at step @math{n = 0, 1, @dots{}}.  @math{\pi_i(n)}
is the probability that the system is in state @math{i} after @math{n}
transitions.

Given the transition probability matrix @math{\bf P} and the initial
state occupancy probability vector @math{{\bf \pi}(0) =
\left[\pi_1(0), @dots{}, \pi_N(0)\right]}, @math{{\bf \pi}(n)} can be
computed as:

@iftex
@tex
$${\bf \pi}(n) = {\bf \pi}(0) {\bf P}^n$$
@end tex
@end iftex
@ifnottex
@math{\pi(n) = \pi(0) P^n}
@end ifnottex

Under certain conditions, there exists a @emph{stationary state
occupancy probability} @math{{\bf \pi} = \lim_{n \rightarrow +\infty}
{\bf \pi}(n)}, which is independent from @math{{\bf \pi}(0)}. The
vector @math{\bf \pi} is the solution of the following linear system:

@iftex
@tex
$$
\left\{ \eqalign{
{\bf \pi P} & = {\bf \pi} \cr
{\bf \pi 1}^T & = 1
} \right.
$$
@end tex
@end iftex
@ifnottex
@example
@group
/
| \pi P   = \pi
| \pi 1^T = 1
\
@end group
@end example
@end ifnottex

@noindent where @math{\bf 1} is the row vector of ones, and @math{( \cdot )^T}
the transpose operator.

@c
@anchor{doc-dtmc}


@deftypefn {Function File} {@var{p} =} dtmc (@var{P})
@deftypefnx {Function File} {@var{p} =} dtmc (@var{P}, @var{n}, @var{p0})

@cindex Markov chain, discrete time
@cindex discrete time Markov chain
@cindex DTMC
@cindex Markov chain, stationary probabilities
@cindex Markov chain, transient probabilities

Compute stationary or transient state occupancy probabilities for a discrete-time Markov chain.

With a single argument, compute the stationary state occupancy
probabilities @code{@var{p}(1), @dots{}, @var{p}(N)} for a
discrete-time Markov chain with finite state space @math{@{1, @dots{},
N@}} and with @math{N \times N} transition matrix
@var{P}. With three arguments, compute the transient state occupancy
probabilities @code{@var{p}(1), @dots{}, @var{p}(N)} that the system is in
state @math{i} after @var{n} steps, given initial occupancy
probabilities @var{p0}(1), @dots{}, @var{p0}(N).

@strong{INPUTS}

@table @code

@item @var{P}(i,j)
transition probabilities from state @math{i} to state @math{j}.
@var{P} must be an @math{N \times N} irreducible stochastic matrix,
meaning that the sum of each row must be 1 (@math{\sum_{j=1}^N
P_{i, j} = 1}), and the rank of @var{P} must be @math{N}.

@item @var{n}
Number of transitions after which state occupancy probabilities are computed
(scalar, @math{n @geq{} 0})

@item @var{p0}(i)
probability that at step 0 the system is in state @math{i} (vector
of length @math{N}).

@end table

@strong{OUTPUTS}

@table @code

@item @var{p}(i)
If this function is called with a single argument, @code{@var{p}(i)}
is the steady-state probability that the system is in state @math{i}.
If this function is called with three arguments, @code{@var{p}(i)}
is the probability that the system is in state @math{i}
after @var{n} transitions, given the probabilities
@code{@var{p0}(i)} that the initial state is @math{i}.

@end table

@xseealso{ctmc}

@end deftypefn


@noindent @strong{EXAMPLE}

The following example is from @ref{GrSn97}. Let us consider a maze
with nine rooms, as shown in the following figure

@example
@group
+-----+-----+-----+
|     |     |     |
|  1     2     3  |
|     |     |     |
+-   -+-   -+-   -+
|     |     |     |
|  4     5     6  |
|     |     |     |
+-   -+-   -+-   -+
|     |     |     |
|  7     8     9  |
|     |     |     |
+-----+-----+-----+
@end group
@end example

A mouse is placed in one of the rooms and can wander around. At each
step, the mouse moves from the current room to a neighboring one with
equal probability. For example, if it is in room 1, it can move to
room 2 and 4 with probability @math{1/2}, respectively; if the mouse
is in room 8, it can move to either 7, 5 or 9 with probability
@math{1/3}.

The transition probabilities @math{P_{i, j}} from room @math{i} to
room @math{j} can be summarized in the following matrix:

@iftex
@tex
$$ {\bf P} = 
\pmatrix{ 0   & 1/2 & 0   & 1/2 & 0   & 0   & 0   & 0   & 0   \cr
          1/3 & 0   & 1/3 & 0   & 1/3 & 0   & 0   & 0   & 0   \cr
          0   & 1/2 & 0   & 0   & 0   & 1/2 & 0   & 0   & 0   \cr
          1/3 & 0   & 0   & 0   & 1/3 & 0   & 1/3 & 0   & 0   \cr
          0   & 1/4 & 0   & 1/4 & 0   & 1/4 & 0   & 1/4 & 0   \cr
          0   & 0   & 1/3 & 0   & 1/3 & 0   & 0   & 0   & 1/3 \cr
          0   & 0   & 0   & 1/2 & 0   & 0   & 0   & 1/2 & 0   \cr
          0   & 0   & 0   & 0   & 1/3 & 0   & 1/3 & 0   & 1/3 \cr
          0   & 0   & 0   & 0   & 0   & 1/2 & 0   & 1/2 & 0   }
$$
@end tex
@end iftex
@ifnottex
@example
@group
        / 0     1/2   0     1/2   0     0     0     0     0   \
        | 1/3   0     1/3   0     1/3   0     0     0     0   |
        | 0     1/2   0     0     0     1/2   0     0     0   |
        | 1/3   0     0     0     1/3   0     1/3   0     0   |
    P = | 0     1/4   0     1/4   0     1/4   0     1/4   0   |
        | 0     0     1/3   0     1/3   0     0     0     1/3 |
        | 0     0     0     1/2   0     0     0     1/2   0   |
        | 0     0     0     0     1/3   0     1/3   0     1/3 |
        \ 0     0     0     0     0     1/2   0     1/2   0   /
@end group
@end example
@end ifnottex

The stationary state occupancy probabilities can then be computed
with the following code:

@example
@group
@verbatim
 P = zeros(9,9);
 P(1,[2 4]    ) = 1/2;
 P(2,[1 5 3]  ) = 1/3;
 P(3,[2 6]    ) = 1/2;
 P(4,[1 5 7]  ) = 1/3;
 P(5,[2 4 6 8]) = 1/4;
 P(6,[3 5 9]  ) = 1/3;
 P(7,[4 8]    ) = 1/2;
 P(8,[7 5 9]  ) = 1/3;
 P(9,[6 8]    ) = 1/2;
 p = dtmc(P);
 disp(p)
@end verbatim
@end group
    @result{} 0.083333   0.125000   0.083333   0.125000   
       0.166667   0.125000   0.083333   0.125000   
       0.083333
@end example

@c
@node Birth-death process (DTMC)
@subsection Birth-death process

@anchor{doc-dtmcbd}


@deftypefn {Function File} {@var{P} =} dtmcbd (@var{b}, @var{d})

@cindex Markov chain, discrete time
@cindex DTMC
@cindex discrete time Markov chain
@cindex birth-death process, DTMC

Returns the transition probability matrix @math{P} for a discrete
birth-death process over state space @math{@{1, @dots{}, N@}}.
For each @math{i=1, @dots{}, (N-1)},
@code{@var{b}(i)} is the transition probability from state
@math{i} to @math{(i+1)}, and @code{@var{d}(i)} is the transition
probability from state @math{(i+1)} to @math{i}.

Matrix @math{\bf P} is defined as:

@tex
$$ \pmatrix{ (1-\lambda_1) & \lambda_1 & & & & \cr
             \mu_1 & (1 - \mu_1 - \lambda_2) & \lambda_2 & & \cr
             & \mu_2 & (1 - \mu_2 - \lambda_3) & \lambda_3 & & \cr
             \cr
             & & \ddots & \ddots & \ddots & & \cr
             \cr
             & & & \mu_{N-2} & (1 - \mu_{N-2}-\lambda_{N-1}) & \lambda_{N-1} \cr
             & & & & \mu_{N-1} & (1-\mu_{N-1}) }
$$
@end tex
@ifnottex
@example
@group
/                                                             \
| 1-b(1)     b(1)                                             |
|  d(1)  (1-d(1)-b(2))     b(2)                               |
|            d(2)      (1-d(2)-b(3))     b(3)                 |
|                                                             |
|                 ...           ...          ...              |
|                                                             |
|                         d(N-2)   (1-d(N-2)-b(N-1))  b(N-1)  |
|                                        d(N-1)      1-d(N-1) |
\                                                             /
@end group
@end example
@end ifnottex

@noindent where @math{\lambda_i} and @math{\mu_i} are the birth and
death probabilities, respectively.

@xseealso{ctmcbd}

@end deftypefn


@c
@node Expected number of visits (DTMC)
@subsection Expected Number of Visits

Given a @math{N} state discrete-time Markov chain with transition
matrix @math{\bf P} and an integer @math{n @geq{} 0}, we let
@math{L_i(n)} be the the expected number of visits to state @math{i}
during the first @math{n} transitions. The vector @math{{\bf L}(n) =
\left[ L_1(n), @dots{}, L_N(n) \right]} is defined as

@iftex
@tex
$$ {\bf L}(n) = \sum_{i=0}^n {\bf \pi}(i) = \sum_{i=0}^n {\bf \pi}(0) {\bf P}^i $$
@end tex
@end iftex
@ifnottex
@example
@group
         n            n
        ___          ___
       \            \           i
L(n) =  >   pi(i) =  >   pi(0) P
       /___         /___
        i=0          i=0
@end group
@end example
@end ifnottex

@noindent where @math{{\bf \pi}(i) = {\bf \pi}(0){\bf P}^i} is the state 
occupancy probability after @math{i} transitions, and @math{{\bf
\pi}(0) = \left[\pi_1(0), @dots{}, \pi_N(0) \right]} are the initial
state occupancy probabilities.

If @math{\bf P} is absorbing, i.e., the stochastic process eventually
enters a state with no outgoing transitions, then we can compute the
expected number of visits until absorption @math{\bf L}. To do so, we
first rearrange the states by rewriting @math{\bf P} as

@iftex
@tex
$$ {\bf P} = \pmatrix{ {\bf Q} & {\bf R} \cr
                       {\bf 0} & {\bf I} }$$
@end tex
@end iftex
@ifnottex
@example
@group
    / Q | R \
P = |---+---|
    \ 0 | I /
@end group
@end example
@end ifnottex

@noindent where the first @math{t} states are transient
and the last @math{r} states are absorbing (@math{t+r = N}). The
matrix @math{{\bf N} = ({\bf I} - {\bf Q})^{-1}} is called the
@emph{fundamental matrix}; @math{N_{i,j}} is the expected number of
times the process is in the @math{j}-th transient state assuming it
started in the @math{i}-th transient state. If we reshape @math{\bf N}
to the size of @math{\bf P} (filling missing entries with zeros), we
have that, for absorbing chains, @math{{\bf L} = {\bf \pi}(0){\bf N}}.

@anchor{doc-dtmcexps}


@deftypefn {Function File} {@var{L} =} dtmcexps (@var{P}, @var{n}, @var{p0})
@deftypefnx {Function File} {@var{L} =} dtmcexps (@var{P}, @var{p0})

@cindex expected sojourn times, DTMC
@cindex DTMC
@cindex discrete time Markov chain
@cindex Markov chain, discrete time

Compute the expected number of visits to each state during the first
@var{n} transitions, or until abrosption.

@strong{INPUTS}

@table @code

@item @var{P}(i,j)
@math{N \times N} transition matrix. @code{@var{P}(i,j)} is the
transition probability from state @math{i} to state @math{j}.

@item @var{n}
Number of steps during which the expected number of visits are
computed (@math{@var{n} @geq{} 0}). If @code{@var{n}=0}, returns
@var{p0}. If @code{@var{n} > 0}, returns the expected number of
visits after exactly @var{n} transitions.

@item @var{p0}(i)
Initial state occupancy probabilities; @code{@var{p0}(i)} is
the probability that the system is in state @math{i} at step 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{L}(i)
When called with two arguments, @code{@var{L}(i)} is the expected
number of visits to state @math{i} before absorption. When
called with three arguments, @code{@var{L}(i)} is the expected number
of visits to state @math{i} during the first @var{n} transitions.

@end table

@strong{REFERENCES}

@itemize
@item Grinstead, Charles M.; Snell, J. Laurie (July
1997). @cite{Introduction to Probability}, Ch. 11: Markov
Chains. American Mathematical Society. ISBN 978-0821807491.
@end itemize

@xseealso{ctmcexps}

@end deftypefn


@c
@node Time-averaged expected sojourn times (DTMC)
@subsection Time-averaged expected sojourn times

@anchor{doc-dtmctaexps}


@deftypefn {Function File} {@var{M} =} dtmctaexps (@var{P}, @var{n}, @var{p0})
@deftypefnx {Function File} {@var{M} =} dtmctaexps (@var{P}, @var{p0})

@cindex time-alveraged sojourn time, DTMC
@cindex discrete time Markov chain
@cindex Markov chain, discrete time
@cindex DTMC

Compute the @emph{time-averaged sojourn times} @code{@var{M}(i)},
defined as the fraction of time spent in state @math{i} during the
first @math{n} transitions (or until absorption), assuming that the
state occupancy probabilities at time 0 are @var{p0}.

@strong{INPUTS}

@table @code

@item @var{P}(i,j)
@math{N \times N} transition probability matrix.

@item @var{n}
Number of transitions during which the time-averaged expected sojourn times
are computed (scalar, @math{@var{n} @geq{} 0}). if @math{@var{n} = 0},
returns @var{p0}.

@item @var{p0}(i)
Initial state occupancy probabilities (vector of length @math{N}).

@end table

@strong{OUTPUTS}

@table @code

@item @var{M}(i)
If this function is called with three arguments, @code{@var{M}(i)} is
the expected fraction of steps @math{@{0, @dots{}, n@}} spent in
state @math{i}, assuming that the state occupancy probabilities at
time zero are @var{p0}. If this function is called with two
arguments, @code{@var{M}(i)} is the expected fraction of steps spent
in state @math{i} until absorption. @var{M} is a vector of length
@math{N}.

@end table

@xseealso{dtmcexps}

@end deftypefn


@c
@node Mean time to absorption (DTMC)
@subsection Mean Time to Absorption

The @emph{mean time to absorption} is defined as the average number of
transitions that are required to enter an absorbing state, starting
from a transient state or given initial state occupancy probabilities
@math{{\bf \pi}(0)}.

Let @math{t_i} be the expected number of transitions before being
absorbed in any absorbing state, starting from state @math{i}.  The
vector @math{{\bf t} = [t_1, @dots{}, t_N]} can be computed from the
fundamental matrix @math{\bf N} (@pxref{Expected number of visits
(DTMC)}) as

@iftex
@tex
$$ {\bf t} = {\bf N c} $$
@end tex
@end iftex
@ifnottex
@math{t = N c}
@end ifnottex

@noindent where @math{\bf c} is a column vector of 1's.

Let @math{{\bf B} = [ B_{i, j} ]} be a matrix where @math{B_{i, j}} is
the probability of being absorbed in state @math{j}, starting from
transient state @math{i}. Again, using matrices @math{\bf N} and
@math{\bf R} (@pxref{Expected number of visits (DTMC)}) we can write

@iftex
@tex
$$ {\bf B} = {\bf N R} $$
@end tex
@end iftex
@ifnottex
@math{B = N R}
@end ifnottex

@anchor{doc-dtmcmtta}


@deftypefn {Function File} {[@var{t} @var{N} @var{B}] =} dtmcmtta (@var{P})
@deftypefnx {Function File} {[@var{t} @var{N} @var{B}] =} dtmcmtta (@var{P}, @var{p0})

@cindex mean time to absorption, DTMC
@cindex absorption probabilities, DTMC
@cindex fundamental matrix
@cindex DTMC
@cindex discrete time Markov chain
@cindex Markov chain, discrete time

Compute the expected number of steps before absorption for a
DTMC with state space @math{@{1, @dots{}, N@}}
and transition probability matrix @var{P}.

@strong{INPUTS}

@table @code

@item @var{P}(i,j)
@math{N \times N} transition probability matrix.
@code{@var{P}(i,j)} is the transition probability from state
@math{i} to state @math{j}.

@item @var{p0}(i)
Initial state occupancy probabilities (vector of length @math{N}).

@end table

@strong{OUTPUTS}

@table @code

@item @var{t}
@itemx @var{t}(i)
When called with a single argument, @var{t} is a vector of length
@math{N} such that @code{@var{t}(i)} is the expected number of steps
before being absorbed in any absorbing state, starting from state
@math{i}; if @math{i} is absorbing, @code{@var{t}(i) = 0}. When
called with two arguments, @var{t} is a scalar, and represents the
expected number of steps before absorption, starting from the initial
state occupancy probability @var{p0}.

@item @var{N}(i)
@itemx @var{N}(i,j)
When called with a single argument, @var{N} is the @math{N \times N}
fundamental matrix for @var{P}. @code{@var{N}(i,j)} is the expected
number of visits to transient state @var{j} before absorption, if the
system started in transient state @var{i}. The initial state is counted
if @math{i = j}. When called with two arguments, @var{N} is a vector
of length @math{N} such that @code{@var{N}(j)} is the expected number
of visits to transient state @var{j} before absorption, given initial
state occupancy probability @var{P0}.

@item @var{B}(i)
@itemx @var{B}(i,j)
When called with a single argument, @var{B} is a @math{N \times N}
matrix where @code{@var{B}(i,j)} is the probability of being
absorbed in state @math{j}, starting from transient state @math{i};
if @math{j} is not absorbing, @code{@var{B}(i,j) = 0}; if @math{i}
is absorbing, @code{@var{B}(i,i) = 1} and @code{@var{B}(i,j) = 0}
for all @math{i \neq j}. When called with two arguments, @var{B} is
a vector of length @math{N} where @code{@var{B}(j)} is the
probability of being absorbed in state @var{j}, given initial state
occupancy probabilities @var{p0}.

@end table

@strong{REFERENCES}

@itemize
@item Grinstead, Charles M.; Snell, J. Laurie (July
1997). @cite{Introduction to Probability}, Ch. 11: Markov
Chains. American Mathematical Society. ISBN 978-0821807491.
@end itemize

@xseealso{ctmcmtta}

@end deftypefn


@c
@node First passage times (DTMC)
@subsection First Passage Times

The First Passage Time @math{M_{i, j}} is the average number of
transitions needed to enter state @math{j} for the first time,
starting from state @math{i}. Matrix @math{\bf M} satisfies the
property

@iftex
@tex
$$ M_{i, j} = 1 + \sum_{k \neq j} P_{i, k} M_{k, j}$$
@end tex
@end iftex
@ifnottex
@example
@group
           ___
          \
M_ij = 1 + >   P_ij * M_kj
          /___
          k!=j
@end group
@end example
@end ifnottex

To compute @math{{\bf M} = [ M_{i, j}]} a different formulation is
used.  Let @math{\bf W} be the @math{N \times N} matrix having each
row equal to the stationary state occupancy probability vector
@math{\bf \pi} for @math{\bf P}; let @math{\bf I} be the @math{N
\times N} identity matrix (i.e., the matrix of all ones). Define
@math{\bf Z} as follows:

@iftex
@tex
$$ {\bf Z} = \left( {\bf I} - {\bf P} + {\bf W} \right)^{-1} $$
@end tex
@end iftex
@ifnottex
@example
@group
               -1
Z = (I - P + W)
@end group
@end example
@end ifnottex

@noindent Then, we have that

@iftex
@tex
$$ M_{i, j} = {Z_{j, j} - Z_{i, j} \over \pi_j} $$
@end tex
@end iftex
@ifnottex
@example
@group
       Z_jj - Z_ij
M_ij = -----------
          \pi_j
@end group
@end example
@end ifnottex

According to the definition above, @math{M_{i,i} = 0}. We arbitrarily
set @math{M_{i,i}} to the @emph{mean recurrence time} @math{r_i} for
state @math{i}, that is the average number of transitions needed to
return to state @math{i} starting from it. @math{r_i} is:

@iftex
@tex
$$ r_i = {1 \over \pi_i} $$
@end tex
@end iftex
@ifnottex
@example
@group
        1
r_i = -----
      \pi_i
@end group
@end example
@end ifnottex

@anchor{doc-dtmcfpt}


@deftypefn {Function File} {@var{M} =} dtmcfpt (@var{P})

@cindex first passage times
@cindex mean recurrence times
@cindex discrete time Markov chain
@cindex Markov chain, discrete time
@cindex DTMC

Compute mean first passage times and mean recurrence times
for an irreducible discrete-time Markov chain over the state space
@math{@{1, @dots{}, N@}}.

@strong{INPUTS}

@table @code

@item @var{P}(i,j)
transition probability from state @math{i} to state @math{j}.
@var{P} must be an irreducible stochastic matrix, which means that
the sum of each row must be 1 (@math{\sum_{j=1}^N P_{i j} = 1}),
and the rank of @var{P} must be @math{N}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{M}(i,j)
For all @math{1 @leq{} i, j @leq{} N}, @math{i \neq j}, @code{@var{M}(i,j)} is
the average number of transitions before state @var{j} is entered
for the first time, starting from state @var{i}.
@code{@var{M}(i,i)} is the @emph{mean recurrence time} of state
@math{i}, and represents the average time needed to return to state
@var{i}.

@end table

@strong{REFERENCES}

@itemize
@item Grinstead, Charles M.; Snell, J. Laurie (July
1997). @cite{Introduction to Probability}, Ch. 11: Markov
Chains. American Mathematical Society. ISBN 978-0821807491.
@end itemize

@xseealso{ctmcfpt}

@end deftypefn


@c
@c
@c
@node Continuous-Time Markov Chains
@section Continuous-Time Markov Chains

A stochastic process @math{@{X(t), t @geq{} 0@}} is a continuous-time
Markov chain if, for all integers @math{n}, and for any sequence
@math{t_0, t_1 , @dots{}, t_n, t_{n+1}} such that @math{t_0 < t_1 <
@dots{} < t_n < t_{n+1}}, we have

@iftex
@tex
$$\eqalign{P(X(t_{n+1}) = x_{n+1}\ |\ X(t_n) = x_n, X(t_{n-1}) = x_{n-1}, \ldots, X(t_0) = x_0) \cr
&\hskip -8 em = P(X(t_{n+1}) = x_{n+1}\ |\ X(t_n) = x_n)}$$
@end tex
@end iftex
@ifnottex
@math{P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, ..., X_0 = x_0) = P(X_{n+1} = x_{n+1} | X_n = x_n)}
@end ifnottex

A continuous-time Markov chain is defined according to an
@emph{infinitesimal generator matrix} @math{{\bf Q} = [Q_{i,j}]},
where for each @math{i \neq j}, @math{Q_{i, j}} is the transition rate
from state @math{i} to state @math{j}. The matrix @math{\bf Q} must
satisfy the property that, for all @math{i}, @math{\sum_{j=1}^N Q_{i,
j} = 0}.

@anchor{doc-ctmcchkQ}


@deftypefn {Function File} {[@var{result} @var{err}] =} ctmcchkQ (@var{Q})

@cindex Markov chain, continuous time

If @var{Q} is a valid infinitesimal generator matrix, return
the size (number of rows or columns) of @var{Q}. If @var{Q} is not
an infinitesimal generator matrix, set @var{result} to zero, and
@var{err} to an appropriate error string.

@end deftypefn


Similarly to the DTMC case, a CTMC is @emph{irreducible} if every
state is eventually reachable from every other state in finite time.

@anchor{doc-ctmcisir}


@deftypefn {Function File} {[@var{r} @var{s}] =} ctmcisir (@var{P})

@cindex Markov chain, continuous time
@cindex continuous time Markov chain
@cindex CTMC
@cindex irreducible Markov chain

Check if @var{Q} is irreducible, and identify Strongly Connected
Components (SCC) in the transition graph of the DTMC with infinitesimal
generator matrix @var{Q}.

@strong{INPUTS}

@table @code

@item @var{Q}(i,j)
Infinitesimal generator matrix. @var{Q} is a @math{N \times N} square
matrix where @code{@var{Q}(i,j)} is the transition rate from state
@math{i} to state @math{j}, for @math{1 @leq{} i, j @leq{} N},
@math{i \neq j}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{r}
1 if @var{Q} is irreducible, 0 otherwise.

@item @var{s}(i)
strongly connected component (SCC) that state @math{i} belongs to.
SCCs are numbered @math{1, 2, @dots{}}. If the graph is strongly
connected, then there is a single SCC and the predicate @code{all(s == 1)}
evaluates to true.

@end table

@end deftypefn


@menu
* State occupancy probabilities (CTMC)::
* Birth-death process (CTMC)::
* Expected sojourn times (CTMC)::
* Time-averaged expected sojourn times (CTMC)::
* Mean time to absorption (CTMC)::
* First passage times (CTMC)::
@end menu

@node State occupancy probabilities (CTMC)
@subsection State occupancy probabilities

Similarly to the discrete case, we denote with @math{{\bf \pi}(t) =
\left[\pi_1(t), @dots{}, \pi_N(t) \right]} the @emph{state occupancy
probability vector} at time @math{t}. @math{\pi_i(t)} is the
probability that the system is in state @math{i} at time @math{t
@geq{} 0}.

Given the infinitesimal generator matrix @math{\bf Q} and initial
state occupancy probabilities @math{{\bf \pi}(0) = \left[\pi_1(0),
@dots{}, \pi_N(0)\right]}, the occupancy probabilities
@math{{\bf \pi}(t)} at time @math{t} can be computed as:

@iftex
@tex
$${\bf \pi}(t) = {\bf \pi}(0) \exp( {\bf Q} t )$$
@end tex
@end iftex
@ifnottex
@example
@group
\pi(t) = \pi(0) exp(Qt)
@end group
@end example
@end ifnottex

@noindent where @math{\exp( {\bf Q} t )} is the matrix exponential
of @math{{\bf Q} t}. Under certain conditions, there exists a
@emph{stationary state occupancy probability} @math{{\bf \pi} =
\lim_{t \rightarrow +\infty} {\bf \pi}(t)} that is independent from
@math{{\bf \pi}(0)}.  @math{\bf \pi} is the solution of the following
linear system:

@iftex
@tex
$$
\left\{ \eqalign{
{\bf \pi Q} & = {\bf 0} \cr
{\bf \pi 1}^T & = 1
} \right.
$$
@end tex
@end iftex
@ifnottex
@example
@group
/
| \pi Q   = 0
| \pi 1^T = 1
\
@end group
@end example
@end ifnottex

@anchor{doc-ctmc}


@deftypefn {Function File} {@var{p} =} ctmc (@var{Q})
@deftypefnx {Function File} {@var{p} =} ctmc (@var{Q}, @var{t}, @var{p0})

@cindex Markov chain, continuous time
@cindex continuous time Markov chain
@cindex Markov chain, state occupancy probabilities
@cindex stationary probabilities
@cindex CTMC

Compute stationary or transient state occupancy probabilities for a continuous-time Markov chain.

With a single argument, compute the stationary state occupancy
probabilities @math{@var{p}(1), @dots{}, @var{p}(N)} for a
continuous-time Markov chain with finite state space @math{@{1, @dots{},
N@}} and @math{N \times N} infinitesimal generator matrix @var{Q}.
With three arguments, compute the state occupancy probabilities
@math{@var{p}(1), @dots{}, @var{p}(N)} that the system is in state @math{i}
at time @var{t}, given initial state occupancy probabilities
@math{@var{p0}(1), @dots{}, @var{p0}(N)} at time 0.

@strong{INPUTS}

@table @code

@item @var{Q}(i,j)
Infinitesimal generator matrix. @var{Q} is a @math{N \times N} square
matrix where @code{@var{Q}(i,j)} is the transition rate from state
@math{i} to state @math{j}, for @math{1 @leq{} i \neq j @leq{} N}.
@var{Q} must satisfy the property that @math{\sum_{j=1}^N Q_{i, j} =
0}

@item @var{t}
Time at which to compute the transient probability (@math{t @geq{}
0}). If omitted, the function computes the steady state occupancy
probability vector.

@item @var{p0}(i)
probability that the system is in state @math{i} at time 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{p}(i)
If this function is invoked with a single argument, @code{@var{p}(i)}
is the steady-state probability that the system is in state @math{i},
@math{i = 1, @dots{}, N}. If this function is invoked with three
arguments, @code{@var{p}(i)} is the probability that the system is in
state @math{i} at time @var{t}, given the initial occupancy
probabilities @var{p0}(1), @dots{}, @var{p0}(N).

@end table

@xseealso{dtmc}

@end deftypefn


@noindent @strong{EXAMPLE}

Consider a two-state CTMC where all transition rates between states
are equal to 1. The stationary state occupancy probabilities can be
computed as follows:

@example
@group
@verbatim
 Q = [ -1  1; ...
        1 -1  ];
 q = ctmc(Q)
@end verbatim
    @result{} q = 0.50000   0.50000
@end group
@end example

@c
@c
@c
@node Birth-death process (CTMC)
@subsection Birth-Death Process

@anchor{doc-ctmcbd}


@deftypefn {Function File} {@var{Q} =} ctmcbd (@var{b}, @var{d})

@cindex Markov chain, continuous time
@cindex continuous time Markov chain
@cindex CTMC
@cindex birth-death process, CTMC

Returns the infinitesimal generator matrix @math{Q} for a
continuous birth-death process over the finite state space
@math{@{1, @dots{}, N@}}. For each @math{i=1, @dots{}, (N-1)},
@code{@var{b}(i)} is the transition rate from state @math{i} to
state @math{(i+1)}, and @code{@var{d}(i)} is the transition rate from state
@math{(i+1)} to state @math{i}.

Matrix @math{\bf Q} is therefore defined as:

@tex
$$ \pmatrix{ -\lambda_1 & \lambda_1 & & & & \cr
             \mu_1 & -(\mu_1 + \lambda_2) & \lambda_2 & & \cr
             & \mu_2 & -(\mu_2 + \lambda_3) & \lambda_3 & & \cr
             \cr
             & & \ddots & \ddots & \ddots & & \cr
             \cr
             & & & \mu_{N-2} & -(\mu_{N-2}+\lambda_{N-1}) & \lambda_{N-1} \cr
             & & & & \mu_{N-1} & -\mu_{N-1} }
$$
@end tex
@ifnottex

@example
@group
/                                                          \
| -b(1)     b(1)                                           |
|  d(1) -(d(1)+b(2))     b(2)                              |
|           d(2)     -(d(2)+b(3))        b(3)              |
|                                                          |
|                ...           ...          ...            |
|                                                          |
|                       d(N-2)    -(d(N-2)+b(N-1))  b(N-1) |
|                                       d(N-1)     -d(N-1) |
\                                                          /
@end group
@end example
@end ifnottex

@noindent where @math{\lambda_i} and @math{\mu_i} are the birth and
death rates, respectively.

@xseealso{dtmcbd}

@end deftypefn


@c
@c
@c
@node Expected sojourn times (CTMC)
@subsection Expected Sojourn Times

Given a @math{N} state continuous-time Markov Chain with infinitesimal
generator matrix @math{\bf Q}, we define the vector @math{{\bf L}(t) =
\left[L_1(t), @dots{}, L_N(t)\right]} such that @math{L_i(t)} is the
expected sojourn time in state @math{i} during the interval
@math{[0,t)}, assuming that the initial occupancy probabilities at time
0 were @math{{\bf \pi}(0)}. @math{{\bf L}(t)} can be expressed as the
solution of the following differential equation:

@iftex
@tex
$$ { d{\bf L}(t) \over dt} = {\bf L}(t){\bf Q} + {\bf \pi}(0), \qquad {\bf L}(0) = {\bf 0} $$
@end tex
@end iftex
@ifnottex
@example
@group
 dL
 --(t) = L(t) Q + pi(0),    L(0) = 0
 dt
@end group
@end example
@end ifnottex

Alternatively, @math{{\bf L}(t)} can also be expressed in integral
form as:

@iftex
@tex
$$ {\bf L}(t) = \int_0^t {\bf \pi}(u) du$$
@end tex
@end iftex
@ifnottex
@example
@group
       / t
L(t) = |   pi(u) du
       / 0
@end group
@end example
@end ifnottex

@noindent where @math{{\bf \pi}(t) = {\bf \pi}(0) \exp({\bf Q}t)} is
the state occupancy probability at time @math{t}; @math{\exp({\bf Q}t)}
is the matrix exponential of @math{{\bf Q}t}.

If there are absorbing states, we can define the vector of
@emph{expected sojourn times until absorption} @math{{\bf L}(\infty)},
where for each transient state @math{i}, @math{L_i(\infty)} is the
expected total time spent in state @math{i} until absorption, assuming
that the system started with given state occupancy probabilities
@math{{\bf \pi}(0)}. Let @math{\tau} be the set of transient (i.e.,
non absorbing) states; let @math{{\bf Q}_\tau} be the restriction of
@math{\bf Q} to the transient sub-states only. Similarly, let
@math{{\bf \pi}_\tau(0)} be the restriction of the initial state
occupancy probability vector @math{{\bf \pi}(0)} to transient states
@math{\tau}.

The expected time to absorption @math{{\bf L}_\tau(\infty)} is defined as
the solution of the following equation:

@iftex
@tex
$$ {\bf L}_\tau(\infty){\bf Q}_\tau = -{\bf \pi}_\tau(0) $$
@end tex
@end iftex
@ifnottex
@example
@group
L_T( inf ) Q_T = -pi_T(0)
@end group
@end example
@end ifnottex

@anchor{doc-ctmcexps}


@deftypefn {Function File} {@var{L} =} ctmcexps (@var{Q}, @var{t}, @var{p} )
@deftypefnx {Function File} {@var{L} =} ctmcexps (@var{Q}, @var{p})

@cindex Markov chain, continuous time
@cindex continuous time Markov chain
@cindex expected sojourn time, CTMC
@cindex CTMC

With three arguments, compute the expected times @code{@var{L}(i)}
spent in each state @math{i} during the time interval @math{[0,t]},
assuming that the initial occupancy vector is @var{p}. With two
arguments, compute the expected time @code{@var{L}(i)} spent in each
transient state @math{i} until absorption.

@strong{Note:} In its current implementation, this function
requires that an absorbing state is reachable from any
non-absorbing state of @math{Q}.

@strong{INPUTS}

@table @code

@item @var{Q}(i,j)
@math{N \times N} infinitesimal generator matrix. @code{@var{Q}(i,j)}
is the transition rate from state @math{i} to state @math{j},
@math{1 @leq{} i, j @leq{} N}, @math{i \neq j}.
The matrix @var{Q} must also satisfy the
condition @math{\sum_{j=1}^N Q_{i,j} = 0} for every @math{i=1, @dots{}, N}.

@item @var{t}
If given, compute the expected sojourn times in @math{[0,t]}

@item @var{p}(i)
Initial occupancy probability vector; @code{@var{p}(i)} is the
probability the system is in state @math{i} at time 0, @math{i = 1,
@dots{}, N}

@end table

@strong{OUTPUTS}

@table @code

@item @var{L}(i)
If this function is called with three arguments, @code{@var{L}(i)} is
the expected time spent in state @math{i} during the interval
@math{[0,t]}. If this function is called with two arguments
@code{@var{L}(i)} is the expected time spent in transient state
@math{i} until absorption; if state @math{i} is absorbing,
@code{@var{L}(i)} is zero.

@end table

@xseealso{dtmcexps}

@end deftypefn


@noindent @strong{EXAMPLE}

Let us consider a 4-states pure birth continuous process where the
transition rate from state @math{i} to state @math{(i+1)} is
@math{\lambda_i = i \lambda} (@math{i=1, 2, 3}), with @math{\lambda =
0.5}. The following code computes the expected sojourn time for each
state @math{i}, given initial occupancy probabilities @math{{\bf
\pi}_0=[1, 0, 0, 0]}.

@example
@group
@verbatim
 lambda = 0.5;
 N = 4;
 b = lambda*[1:N-1];
 d = zeros(size(b));
 Q = ctmcbd(b,d);
 t = linspace(0,10,100);
 p0 = zeros(1,N); p0(1)=1;
 L = zeros(length(t),N);
 for i=1:length(t)
   L(i,:) = ctmcexps(Q,t(i),p0);
 endfor
 plot( t, L(:,1), ";State 1;", "linewidth", 2, ...
       t, L(:,2), ";State 2;", "linewidth", 2, ...
       t, L(:,3), ";State 3;", "linewidth", 2, ...
       t, L(:,4), ";State 4;", "linewidth", 2 );
 legend("location","northwest"); legend("boxoff");
 xlabel("Time");
 ylabel("Expected sojourn time");
@end verbatim
@end group
@end example

@c
@c
@c
@node Time-averaged expected sojourn times (CTMC)
@subsection Time-Averaged Expected Sojourn Times

@anchor{doc-ctmctaexps}


@deftypefn {Function File} {@var{M} =} ctmctaexps (@var{Q}, @var{t}, @var{p0})
@deftypefnx {Function File} {@var{M} =} ctmctaexps (@var{Q}, @var{p0})

@cindex Markov chain, continuous time
@cindex time-alveraged sojourn time, CTMC
@cindex continuous time Markov chain
@cindex CTMC

Compute the @emph{time-averaged sojourn time} @code{@var{M}(i)},
defined as the fraction of the time interval @math{[0,t]} (or until
absorption) spent in state @math{i}, assuming that the state
occupancy probabilities at time 0 are @var{p}.

@strong{INPUTS}

@table @code

@item @var{Q}(i,j)
Infinitesimal generator matrix. @code{@var{Q}(i,j)} is the transition
rate from state @math{i} to state @math{j},
@math{1 @leq{} i,j @leq{} N}, @math{i \neq j}. The
matrix @var{Q} must also satisfy the condition @math{\sum_{j=1}^N Q_{i,j} = 0}

@item @var{t}
Time. If omitted, the results are computed until absorption.

@item @var{p0}(i)
initial state occupancy probabilities. @code{@var{p0}(i)} is the
probability that the system is in state @math{i} at time 0, @math{i
= 1, @dots{}, N}

@end table

@strong{OUTPUTS}

@table @code

@item @var{M}(i)
When called with three arguments, @code{@var{M}(i)} is the expected
fraction of the interval @math{[0,t]} spent in state @math{i}
assuming that the state occupancy probability at time zero is
@var{p}. When called with two arguments, @code{@var{M}(i)} is the
expected fraction of time until absorption spent in state @math{i};
in this case the mean time to absorption is @code{sum(@var{M})}.

@end table

@xseealso{ctmcexps}

@end deftypefn


@noindent @strong{EXAMPLE}

@example
@group
@verbatim
 lambda = 0.5;
 N = 4;
 birth = lambda*linspace(1,N-1,N-1);
 death = zeros(1,N-1);
 Q = diag(birth,1)+diag(death,-1);
 Q -= diag(sum(Q,2));
 t = linspace(1e-5,30,100);
 p = zeros(1,N); p(1)=1;
 M = zeros(length(t),N);
 for i=1:length(t)
   M(i,:) = ctmctaexps(Q,t(i),p);
 endfor
 clf;
 plot(t, M(:,1), ";State 1;", "linewidth", 2, ...
      t, M(:,2), ";State 2;", "linewidth", 2, ...
      t, M(:,3), ";State 3;", "linewidth", 2, ...
      t, M(:,4), ";State 4 (absorbing);", "linewidth", 2 );
 legend("location","east"); legend("boxoff");
 xlabel("Time");
 ylabel("Time-averaged Expected sojourn time");
@end verbatim
@end group
@end example

@c
@c
@c
@node Mean time to absorption (CTMC)
@subsection Mean Time to Absorption

@anchor{doc-ctmcmtta}


@deftypefn {Function File} {@var{t} =} ctmcmtta (@var{Q}, @var{p})

@cindex Markov chain, continuous time
@cindex continuous time Markov chain
@cindex CTMC
@cindex mean time to absorption, CTMC

Compute the Mean-Time to Absorption (MTTA) of the CTMC described by
the infinitesimal generator matrix @var{Q}, starting from initial
occupancy probabilities @var{p}. If there are no absorbing states, this
function fails with an error.

@strong{INPUTS}

@table @code

@item @var{Q}(i,j)
@math{N \times N} infinitesimal generator matrix. @code{@var{Q}(i,j)}
is the transition rate from state @math{i} to state @math{j}, @math{i
\neq j}. The matrix @var{Q} must satisfy the condition
@math{\sum_{j=1}^N Q_{i,j} = 0}

@item @var{p}(i)
probability that the system is in state @math{i}
at time 0, for each @math{i=1, @dots{}, N}

@end table

@strong{OUTPUTS}

@table @code

@item @var{t}
Mean time to absorption of the process represented by matrix @var{Q}.
If there are no absorbing states, this function fails.

@end table

@strong{REFERENCES}

@itemize
@item
G. Bolch, S. Greiner, H. de Meer and
K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and
Performance Evaluation with Computer Science Applications}, Wiley,
1998.
@end itemize

@xseealso{ctmcexps}

@end deftypefn


@noindent @strong{EXAMPLE}

Let us consider a simple model of redundant disk array. We assume that
the array is made of 5 independent disks and can tolerate up to 2 disk
failures without losing data. If three or more disks break, the array
is dead and unrecoverable. We want to estimate the
Mean-Time-To-Failure (MTTF) of the disk array.

We model this system as a 4 states continuous Markov chain with state
space @math{@{ 2, 3, 4, 5 @}}. In state @math{i} there are exactly
@math{i} active (i.e., non failed) disks; state @math{2} is
absorbing. Let @math{\mu} be the failure rate of a single disk. The
system starts in state @math{5} (all disks are operational). We use a
pure death process, where the death rate from state @math{i} to state
@math{(i-1)} is @math{\mu i}, for @math{i = 3, 4, 5}).

The MTTF of the disk array is the MTTA of the Markov Chain, and can be
computed as follows:

@example
@group
@verbatim
 mu = 0.01;
 death = [ 3 4 5 ] * mu;
 birth = 0*death;
 Q = ctmcbd(birth,death);
 t = ctmcmtta(Q,[0 0 0 1])
@end verbatim
    @result{} t = 78.333
@end group
@end example

@c
@c
@c
@node First passage times (CTMC)
@subsection First Passage Times

@anchor{doc-ctmcfpt}


@deftypefn {Function File} {@var{M} =} ctmcfpt (@var{Q})
@deftypefnx {Function File} {@var{m} =} ctmcfpt (@var{Q}, @var{i}, @var{j})

@cindex first passage times, CTMC
@cindex CTMC
@cindex continuous time Markov chain
@cindex Markov chain, continuous time

Compute mean first passage times for an irreducible continuous-time
Markov chain.

@strong{INPUTS}

@table @code

@item @var{Q}(i,j)
Infinitesimal generator matrix. @var{Q} is a @math{N \times N}
square matrix where @code{@var{Q}(i,j)} is the transition rate from
state @math{i} to state @math{j}, for @math{1 @leq{} i, j @leq{} N},
@math{i \neq j}. Transition rates must be nonnegative, and
@math{\sum_{j=1}^N Q_{i,j} = 0}

@item @var{i}
Initial state.

@item @var{j}
Destination state.

@end table

@strong{OUTPUTS}

@table @code

@item @var{M}(i,j)
average time before state
@var{j} is visited for the first time, starting from state @var{i}.
We let @code{@var{M}(i,i) = 0}.

@item m
@var{m} is the average time before state @var{j} is visited for the first
time, starting from state @var{i}.

@end table

@xseealso{ctmcmtta}

@end deftypefn