A Compression Algorithm for Probability Transition Matrices.
This paper describes a compression algorithm for probability transition matrices.  The compressed matrix is itself a probability transition matrix. In general the compression is not error free, but the error appears to be small even for high levels of compression.
Introduction
. Many discrete systems can be described by a Markov chain
model in which each state of the Markov model is some discrete state of the dynamical
system. If there are N states, then the Markov chain model is defined by an N \Theta N
matrix Q called the "1-step probability transition matrix," where Q(i; j) is the probability
of going from state i to state j in one step. The n-step behavior is described
by the nth power of Q, Q n . For many systems, the number of states is enormous and
there is a computational advantage in reducing N .
Previous methods for reducing the number of states (referred to as compression,
aggregation, or lumping methods) have focused on techniques that provide good estimations
of the steady-state behavior of the Markov model. The focus of this paper,
however, is on transient behavior, and the goal is to produce an algorithm for compressing
Q matrices in a way that yields good estimates of the transient behavior of
the Markov model. The algorithm described in this paper compresses a Q matrix into
a smaller Q matrix with less states. In general, the compression will not be without
error, so the goal is to provide an algorithm that compresses the original Q matrix
without significant error. Although computing a compressed matrix might take some
time, the savings resulting from using this compressed matrix in all subsequent computations
can more than offset the compression time.
The organization of this paper is as follows. Section 2 introduces the compression
algorithm, which compresses pairs of states by taking a weighted average of the row
entries for those two states, followed by summing the two columns associated with
those two states. Section 2 also introduces the important concepts of row and column
equivalence, which are important for identifying pairs of states that can be compressed
with no error. Section 3 provides mathematical justification for taking the weighted
average of row entries and shows that the weights are simply column sums of probability
mass. Section 4 proves that pairs of states that are row or column equivalent
lead to perfect compression. Section 5 introduces an analysis of error and uses this
to define a metric for row and column similarity which can be used to find pairs of
states that yield almost perfect compression. Later sections illustrate the utility of
the compression algorithm through experiments.
2. The Compression Algorithm at a High Level. The entries in the Q
probability that the system will tran-
This work was supported by ARPA Order # D106/03.
y AI Center - Code 5514, Naval Research Laboratory, 4555 Overlook Avenue, Washington DC,
20375. Phone: 202-767-9006, FAX: 202-767-3172 (spears@aic.nrl.navy.mil).
W. M. SPEARS
sition to state j in one step, given that it currently is in state i. 1 Now suppose that
states i and j have been chosen for compression. The new compressed state is referred
to as state fi - jg. Compressing states i and j together means that the combined
state represents being in either state i or state j. Since this is a disjunctive situation,
the probability of transition from state k into the compressed state is simply the sum
Stated another way, part of the compression algorithm is to
sum columns of probability numbers.
However, in general, transitions from a compressed state are more complicated to
compute. Clearly, the probability of transitioning from the compressed state to some
other state p fi-jg;k must lie somewhere between p i;k and p j;k , depending on how much
time is spent in states i and j. Thus a weighted average of row entries appears to
be called for, where the weights reflect the amount of time spent in states i and j.
Precisely how to do this weighted average is investigated in Section 3.
The algorithm for compressing two states i and j together is as follows: 2
(a) Compute a weighted average of the ith and jth rows.
Place the results in rows i and j.
(b) Sum the ith and jth columns.
Place the results in column i. Remove row j and column j.
The compression algorithm has two steps. It takes as input a matrix Q u (an uncompressed
averages the row entries, producing an intermediate
row-averaged matrix Q r . Step (b) sums column entries to produce the final compressed
matrix Q c . Step (a) is the sole source of error, since in general it is difficult
to estimate the amount of time spent in states i and j.
Now that the compression algorithm has been outlined, it is important to define
what is meant by "perfect" compression. As mentioned before, analysis of n-step
transition probabilities (i.e., transient behavior of the Markov chain) can be realized
by computing Q n . For large Q matrices this is computationally expensive. It would be
less expensive to compress Q and to then raise it to the nth power. If the compression
algorithm has worked well then the nth power of the compressed matrix Q c should
be (nearly) identical to compressing the nth power of the uncompressed matrix Q u .
In other words, perfect compression has occurred if (Q n
c .
It turns out that there are two situations under which perfect compression can
be obtained. The first situation is referred to as "row equivalence", in which the two
states i and j have identical rows (i.e., 8k p In this case the weighted
averaging can not produce any error, since the weights will be irrelevant. The second
situation is referred to as "column equivalence", in which state i has column entries
that are a real multiple q of the column entries for state j (i.e., 8k p
intuition here is that when this situation occurs, the ratio of time spent in state i to
state j is precisely q. The details of this can be found in Section 4.
However, for arbitrary matrices, compressing an arbitrarily chosen pair of states
will not necessarily lead to good results. Thus, the goal is to identify pairs of states i
and j upon which the above compression algorithm will work well. It turns out that
pairs of states that are row or column similar are good candidates for compression.
The justification for these measures will be provided in Section 5.
1 The notation p (n)
denotes the entries of the n-step probability transition matrix Q n .
2 The algorithm is written this way because it makes it amenable to mathematical analysis.
COMPRESSING PROBABILITY TRANSITION MATRICES 3
At a high level, of course, this simple compression algorithm must be repeated
for many pairs of states, if one wants to dramatically reduce the size of a Q matrix.
The high level compression algorithm is simply:
Compress()
Repeat as long as possible
(i) Find the pair of states i and j most similar to each other.
3. The Compression Algorithm in More Detail. In the previous section
the compression algorithm was described in two steps. Step (a) is where error can
occur and care must be taken to mathematically justify the weighted averaging of
rows. This can be done by attempting to force (Q 2
to be as similar as possible
to
c (later sections will generalize this to higher powers). This is mathematically
difficult, but fortunately it suffices to force Q 2
u to be as similar as possible to Q
which is much simpler and focuses on the row-averaged matrix Q r explicitly. The
intuition behind this is that if compression is done correctly, passage through the new
compressed state should affect the 2-step transition probabilities as little as possible. 3
This will be shown with a 4 \Theta 4 Q matrix, and then generalized to an arbitrary N \Theta N
matrix. The result will be the weighted row averaging procedure outlined earlier. This
particular presentation has been motivated by a concern for comprehension and hence
is not completely formal. A completely formal presentation is in the Appendix.
3.1. Weighted Averaging with a 4 \Theta 4 Matrix. Consider a general uncompressed
4 \Theta 4 matrix Q u for a Markov chain model of 4 states, as well as the general
intermediate matrix
The notation r i;j j Q r (i; j) is used to prevent confusion with the p i;j in Q u .
Without loss of generality the goal will be to compress the 3rd and 4th states (rows
and columns) of this matrix. Since the 3rd and 4th states are being compressed, rows
1 and 2 of Q r must be the same as Q u (i.e., averaging rows 3 and 4 will not affect
rows 1 and 2). Denoting f3 - 4g to be the compressed state, the intermediate matrix
is:
The r f3-4g;k represent the weighted average of rows 3 and 4 of Q u . Recall that
step (a) of Compress-states(3,4) will place that average in both rows 3 and 4, which
is why rows 3 and 4 of Q r are the same. The trick now is to determine what r f3-4g;1 ,
r f3-4g;2 , r f3-4g;3 , and r f3-4g;4 should be in order to produce a reasonable compression.
This is done by considering
3 More formally, it can be shown that if Q 2
c for row or column
equivalent situations. See Section 4.
4 W. M. SPEARS
a (2)
1;1 a (2)
1;2 a (2)
1;3 a (2)
a (2)
2;1 a (2)
2;2 a (2)
2;3 a (2)
a (2)
3;1 a (2)
3;2 a (2)
3;3 a (2)
a (2)
4;1 a (2)
4;2 a (2)
4;3 a (2)
The notation a (2)
i;j is used to prevent confusion with the p (2)
i;j in Q 2
u . Since the goal
is to have
it is necessary to have p (2)
i;j be as similar as possible to a (2)
i;j .
The p (2)
i;j values can be computed using p i;j values, while the a (2)
i;j values require the
unknowns r f3-4g;1 , r f3-4g;2 , r f3-4g;3 , and r f3-4g;4 .
For example, p (2)
1;1 can be computed by multiplying Q u by itself:
However, a (2)
1;1 is computed by multiplying Q u and
a (2)
In the ideal situation we would like both of these to be equal. This implies that:
But we can write another formula for r f3-4g;1 by considering p (2)
2;1 and a (2)
a (2)
Again, we would like both of these to be equal. This implies that:
Similarly, consideration of p (2)
3;1 and a (2)
3;1 yields:
while consideration of p (2)
4;1 and a (2)
4;1 yields:
What has happened here is that the four elements in the first column of Q
lead to four expressions for r f3-4g;1 . In general, all four expressions for r f3-4g;1 can
not hold simultaneously (although we will investigate conditions under which they will
hold later). The best estimate is to take a weighted average of the four expressions
for r f3-4g;1 (this is related to the concept of "averaging" probabilities - see Appendix
for more details). This yields:
COMPRESSING PROBABILITY TRANSITION MATRICES 5
Note how the final expression for r f3-4g;1 is a weighted average of the row entries
p 3;1 and p 4;1 , where the weights are column sums for columns 3 and 4. In general the
elements of Q in the kth column will constrain r f3-4g;k :
Once again, note how the expression for r f3-4g;k is a weighted average of the row
entries p 3;k and p 4;k , where the weights are column sums for columns 3 and 4.
3.2. Weighted Averaging with an N \Theta N Matrix. The previous results for
a 4 \Theta 4 matrix can be extended to an N \Theta N matrix. Without loss of generality
compress states . Then the N elements of column k yield N expressions
for each r fN \Gamma1-Ng;k . The best estimate is (see Appendix for details):
Note again how the weights are column sums for columns Generalizing
this to compressing two arbitrary states i and j yields:
l p l;i )p i;k
l p l;j )p j;k
l
l p l;j
are the sums of the probability mass in columns i and j of Q u .
Equation 3.1 indicates how to compute the r fi-jg;k entries in Q r . Note how they
are computed using the weighted average of the row entries in rows i and j. The
weights are simply the column sums. This justifies the row averaging component of
the compression algorithm described in the previous section. Intuitively stated, the
column mass for columns i and j provide good estimates of the relative amount of time
spent in states i and j. The estimates are used as weights to average the transitions
from i to state k and from j to k, producing the probability of transition from the
combined state fi - jg to k.
3.3. Mathematical Restatement of the Compression Algorithm. Now
that the weighted averaging of rows i and j has been explained, it is only necessary
to sum columns i and j in order to complete the compression algorithm. The whole
algorithm can be expressed simply as follows. Assume that two states have been
chosen for compression. Let S denote the set of all N states, and let the non-empty
sets such that one S i contains the two chosen states, while
each other S i is composed of exactly one state. Let m i denote the column mass of
state i. Then the compressed matrix Q c is:
6 W. M. SPEARS
j2Sy
This corresponds to taking a weighted average of the two rows corresponding to
the two chosen states, while summing the two corresponding columns. The other
entries in the Q matrix remain unchanged. Consider an example in which states 2
and 3 are compressed. In that case S is described by:
Applying this to the following column equivalent matrix Q u produces perfect
results
c
In summary, this section has justified the use of column mass as weights in the row
averaging portion of the compression algorithm. The whole compression algorithm
is stated succinctly as a mathematical function, which can compress any arbitrary
pair of states. However, as stated earlier, compression of arbitrary pairs of states
need not lead to good compression. The goal, then, is to identify such states. This
is investigated in the next section, and relies upon the concepts of row and column
equivalence.
4. Special Cases in Which Compression is Perfect. If compression is working
well, then the compressed version of Q n
u should be (nearly) identical to Q n
c . As
suggested in Section 2, there are two situations under which perfect compression will
occur. The first situation is when two states are row equivalent. The intuition here
is that the row average of two identical rows will not involve any error, and thus
the compression will be perfect. The second situation is when two states are column
equivalent. The intuition for this situation is that if the column c i is equal to qc j , then
the ratio of time spent in state i to state j is exactly q. Under these circumstances
the weighted row average will also produce no error.
This section will prove that (Q n
c when the two states being compressed
are either row equivalent or column equivalent. This will hold for any n and for any
Q u matrix of size N \Theta N . The method of proof will be to treat the compression
algorithm as a linear transformation f , and then to show that f(Q n
where f(Q u
COMPRESSING PROBABILITY TRANSITION MATRICES 7
4.1. Row Equivalence and the Compression Algorithm. This subsection
will prove that when two states are row equivalent, compression of those states can be
described by a linear transformation (matrix multiplication). The compression algorithm
compresses an N \Theta N matrix Q u to an . However,
for the sake of mathematical convenience all of the matrix transformations will be with
N \Theta N matrices. Without loss of generality it is assumed that states are
being compressed. When it comes time to expressing the final compression, the Nth
row and column will simply be ignored, producing the
matrix. The "ffl" notation is used to denote entries that are not important for the
derivation.
Assume that states are row equivalent. Thus 8k pN
Using Equation 3.1 to compute the row averages yields:
and the compressed matrix should have the form:
Theorem 4.1. If states N and are row equivalent then Q
and
can be expressed as follows:
This is precisely what Q c should be. Thus the compression of two row equivalent
states can be expressed simply as TQ u T . The first T performs row averaging (which
is trivial) and the second T performs column summing. The reader will also note that
some elements of T do not appear to be important for the derivation that Q
This is true, however, the purpose of these elements is to ensure that I , since
this fact will also be used to help prove that (Q n
8 W. M. SPEARS
4.2. Column Equivalence and the Compression Algorithm. This subsection
will prove that when two states are column equivalent, compression of those
states can be described by a linear transformation. Assume without loss of generality
that states are column equivalent. Thus 8k
Using Equation 3.1 to compute the row averages yields:
and the compressed matrix should have the form:
qpN \Gamma1;1 +pN;1
Theorem 4.2. If states N and are column equivalent then Q
Y =4 I 0
I 0q
can be expressed as follows:
qpN \Gamma1;1 +pN;1
This is precisely what Q c should be. Thus the compression of two column equivalent
states can be expressed simply as XQ u Y . X performs row averaging and Y
performs column summing. The reader will note that some elements of X and Y are
not important for the derivation that Q could be used instead of
Y ). This is true, however, the purpose of these elements is to ensure that Y
since this fact will be used to help prove that (Q n
c at the end of this section.
COMPRESSING PROBABILITY TRANSITION MATRICES 9
4.3. Some Necessary Lemmas. Before proving that (Q n
c for row or
column equivalent states, it is necessary to prove some simple lemmas. The idea is to
show that if Q u is row or column equivalent, so is Q n
u . This will allow the previous
linear transformations to be applied to Q n
u as well as Q u .
Let square matrices A and B be defined as matrices of row and column vectors
respectively:
A =6 4
a
a 1
Then the matrix product AB can be represented using dot product notation:
Lemma 4.3. Row equivalence is invariant under post-multiplication.
Proof: Suppose states i and j of A are row equivalent (a
. So, states i and j in AB must be row equivalent.
Lemma 4.4. Column equivalence is invariant under pre-multiplication.
Proof: Suppose states i and j of B are column equivalent (b
states i and j in AB must be column equivalent.
Lemma 4.5. Row and column equivalence are invariant under raising to a power.
Proof: . Thus, if states i and j are row equivalent in Q, they are
row equivalent in Q n by Lemma 4.3. Similarly, Q states i and j
are column equivalent in Q, they are column equivalent in Q n by Lemma 4.4.
Lemma 4.5 indicates that the previous linear transformations can be applied to
u to produce (Q n
when two states in Q u are row or column equivalent.
4.4. Theorems for Perfect Compression. Given the previous theorems concerning
the linear transformations and Lemma 4.5, it is now possible to state and
prove the theorems for perfect compression. The Q matrix can be considered to be
Q u in these theorems.
Theorem 4.6. If Q is row equivalent, then Q
r implies (Q n
r ,
and
c
Proof: If Q is row equivalent, then so is Q n by Lemma 4.5. If Q
r
then
r , and (Q n
c .
Theorem 4.7. If Q is column equivalent, then Q
r implies (Q n
r ,
and
c
Proof: If Q is column equivalent, then so is Q n by Lemma 4.5. If Q
r then (Q n
r , and (Q n
c .
These two theorems illustrate the validity of trying to force Q 2
u to be as similar
as possible to Q u Q r in Section 3.
Theorem 4.8. If Q is row equivalent, then (Q n
c .
Proof: If Q is row equivalent, then so is Q n by Lemma 4.5. Then (Q
c .
Theorem 4.9. If Q is column equivalent, then (Q n
c .
Proof: If Q is column equivalent, then so is Q n by Lemma 4.5. Then (Q
c .
These theorems hold for all n and for all row or column equivalent N \Theta N Q
matrices, and highlight the importance of row and column equivalence. If two states
are row or column equivalent, then compression of those two states is perfect (i.e.,
5. Error Analysis and a Similarity Metric. The previous sections have explained
how to merge pairs of states and have explained that row or column equivalent
pairs will yield perfect compression. Of course, it is highly unlikely that pairs of states
will be found that are perfectly row equivalent or column equivalent. The goal then
is to find a similarity metric that measures the row and column similarity (i.e., how
close pairs of states are to being row or column equivalent). If the metric is formed
correctly, those pairs of states that are more similar should yield less error when
compressed. This section will derive an expression for error and then use this as a
similarity metric for pairs of states.
We will use Q
u to estimate error. As mentioned before, it is desirable to
have the entries in those two matrices be as similar as possible. Consider compressing
two states i and j. Then the entries in Q 2
are:
The entries in Q are:
a (2)
Then the error associated with the (x; y)th element of Q is:
Using Equation 3.1 for r fi-jg;k (and substituting y for
Now denote ff i;j . This is a measure of the row similarity for rows
and j at column y (and will be explained further below). Then:
This simplifies to:
Denote fi i;j
COMPRESSING PROBABILITY TRANSITION MATRICES 11
Now fi i;j (x) can be considered to be a measure of column similarity for columns
and j at row x (this will be shown more explicitly further down). Since only the
magnitude of the error is important, and not the sign, the absolute value of the error
should be considered:
jError i;j (x;
Recall that Error i;j (x; y) is the error associated with the (x; y)th element of
states i and j are compressed. The total error of the whole matrix is:
x
y
jError i;j (x;
x
y
But this can be simplified to:
x
y
jff i;j (y)j
To understand this equation consider the situation where states i and j are row
equivalent. Then 8y This indicates that 8y ff i;j
Thus there is no error associated with compressing row equivalent states i and j, as
has been shown in earlier sections.
Consider the situation where states i and j are column equivalent. Then 8x
qp x;j and m . It is trivial to show that 8x fi i;j and as a consequence
there is no error associated with compressing column equivalent
states i and j, as has been shown in earlier sections.
Given this, a natural similarity metric is the expression for error:
x
y
jff i;j (y)j
If the similarity is close to zero then error is close to zero, and pairs of states can
be judged as to the amount of error that will ensue if they are compressed. 4 The
compression algorithm can now be written as follows:
Compress()
Repeat as long as possible
(i) Find pair of states i and j such that Similarity i;j ! ffl.
The role of ffl is as a threshold. Pairs of states that are more similar than this
threshold can be compressed. By raising ffl one can compress more states, but with a
commensurate increase in error.
The paper thus far has fully outlined the compression algorithm for pairs of states,
and identified situations under which compression is perfect - namely, when the pairs
of states are row or column equivalent. By performing an error analysis, a natural
measure of similarity was derived, in which pairs of states that are row or column
similar yield small amounts of error in the compression algorithm. The following
section outlines some experiments showing the degree of compression that can be
achieved in practice.
4 It is useful to think of this as a "Dissimilarity" metric.
6. Some Experiments. In order to evaluate the practicality of the compression
algorithm, it was tested on some Markov chains derived from the field of genetic
algorithms (GAs). In a GA a population of individuals evolves generation by generation
via Darwinian selection and perturbation operators such as recombination and
mutation. Each individual in the population can be considered to be a point in a
search space (see [8] for an overview of GAs).
Each different population of the GA is a state in the Markov chain, and p i;j
is the probability that the GA will evolve from one population i to another j, in
one generation (time step). The number of states grows extremely fast as the size
of the population increases and as the size of individuals increase. The details of
the mapping of GAs to Markov chains can be found in [6]. Their use in examining
transient behavior can be found in [2]. 5
6.1. Accuracy Experiments. The first set of experiments examine the accuracy
of the compressed Markov chains by using both Q n
c to compute the
probability distribution p (n) over the states at time n. To answer such questions, Q n
must be combined with a set of initial conditions concerning the GA at generation 0.
Thus, the a priori probability of the GA being in state i at time 0 is p (0)
. 6 Given
this, the probability that the GA will be in a particular state j at time n is:
It is also possible to compute probabilities over a set of states. Define a predicate
red J and the set J of states that make P red J true. Then the probability that the
GA will be in one of the states of J at time n is:
In this paper, J represents the set of all states which contain at least one copy
of the optimum (i.e., the set of all populations which have at least one individual
with the optimum function value). The Markov model is used to compute p (n)
J , the
probability of having at least one copy of the optimum in the population at time n.
The compression algorithm can thus be evaluated by using both Q n
truth) and Q n
c (the estimate) to compute p (n)
J for different values of n. The closer the
estimate is to ground truth, the better the compression algorithm is working.
Since the goal is to compute probabilities involving states containing the optimum
(the J set), J states should not be compressed with non-J states. Consequently, the
compression algorithm is run separately for both sets of states. The algorithm is:
Repeat until no new compressed states are created
(a) For each state i in the J set of the current compressed model
(i) Find the most similar state j in the J set.
(ii) If Similarity i;j ! ffl, Compress-states(i,j).
(b) For each state i in the non-J set of the current compressed model
(i) Find the most similar state j in the non-J set.
(ii) If Similarity i;j ! ffl, Compress-states(i,j).
5 For the GA, Q has no zero entries and is thus ergodic.
6 If states i and j have been compressed then p (0)
fi-jg
COMPRESSING PROBABILITY TRANSITION MATRICES 13
(n
Search Space 1
(n
Search Space 2
(n
Search Space 3
(n
Search Space 4
Fig. 6.1. p (n)
J where ffl is 0.0 and 0.15 for 455. The bold curves represent the exact values,
while the non-bold curves represent the values computed from the compressed matrix.
In theory this compression algorithm could result in a two state model involving
just J and non-J . In practice this would require large values of ffl and unacceptable
error in p (n)
J computations.
Four different search spaces were chosen for the GA. This particular set of four
search spaces was chosen because experience has shown that it is hard to get a single
compression algorithm to perform well on all. Also, in order to see how well the
compression algorithm scales to larger Markov chains, four population sizes were
chosen for the GA (10, 12, 14, and 16). These four choices of population size produced
Markov chains of 286, 455, 680, and 969 states, respectively. Thus, the compression
algorithm was tested on sixteen different Markov chains. 7
Naturally, the setting of ffl is crucial to the success of the experiments. Experiments
indicated that a value of 0.15 yielded good compression with minimal error, for all
sixteen Markov chains. The results for are shown in Figure 6.1. The
results for the other experiments are omitted for the sake of brevity, but they are
almost identical. The values p (n)
J are computed for n ranging from 2 to 100, for both
the compressed and uncompressed Markov chains, and graphed as curves. The bold
curves represent the exact p (n)
J values, while the non-bold curves represent the values
computed from the compressed matrix.
The figures clearly indicate that the compressed matrix is yielding negligible error.
To see how the amount of compression is affected by the size of the Markov chain,
consider Table 6.1, which gives the percentage of states removed for each of the sixteen
chains. What is interesting is that, for these particular search spaces, the amount of
compression is increasing as N increases (while still yielding negligible error). For
80% of the states have been removed, yielding Q c matrices roughly
3% the size (in terms of memory requirements) of the original Q u matrix. It is also
interesting to note that different search spaces are consistently compressed to different
7 See [2] for a definition of these search spaces.
14 W. M. SPEARS

Table
The percentage of states removed when
Search Space 1 85% 88% 90% 92%
Search Space 2 71% 76% 81% 84%
Search Space 3 65% 73% 79% 82%
Search Space 4 64% 73% 79% 82%
degrees. For example, the third and fourth search spaces are consistently compressed
less than the first search space. Further investigation into the nature of these search
spaces may help characterize when arbitrary Markov chains are hard/easy to compress
with this algorithm.
6.2. Timing Experiments. It is now necessary to examine the computational
cost of the compression algorithm. Our prior work, [2] and [9], focused heavily on
the insights gained by actually examining Q n
u , which involved computations on the
order of N 3 (to multiply Q u repeatedly). Thus, the primary motivation for producing
the compression algorithm was to gain the same insights more efficiently by dramatically
reducing N . Since the second search space is quite representative in terms of
the performance of the compression algorithm, we draw our timing results from the
experiments with that particular search space. Table 6.2 gives the amount of CPU
time (in minutes) needed to compute Q n
u as n ranges from 2 to 100. Table 6.3 gives
the amount of time needed to compress Q u to Q c as well as the time needed to compute
c as n ranges from 2 to 100. 8 Clearly, the compression algorithm achieves
enormous savings in time when it is actually necessary to compute powers of Q u .

Table
The time (in minutes) to compute Q n
Computation Time 27 125 447 1289

Table
The time (in minutes) to compress Qu and to compute Q n
c for
Compression Time 0.2 0.9 3.0 9.5
Computation Time 2.4 7.6 17.9 38.1
Another common use of Q n
u is to compute the probability distribution p (n) over
the states at time n (as we did in the previous subsection). If the prior distribution
p (0) is known in advance, however, this is more efficiently done by multiplying p (0) by
repeatedly (i.e., this is repeated n times to produce p (n) ). The computation is of
instead of N 3 .

Table

6.4 and Table 6.5 give the amount of time needed to compute p (n) (from
Q u and Q c respectively). Despite the obvious benefits of computing p (n) from Q c ,
the compression algorithm is not advantageous in this case since the time needed
timing results are on a Sun Sparc 20. The code is written in C and is available from the
author.
COMPRESSING PROBABILITY TRANSITION MATRICES 15

Table
The time (in minutes) to compute p (n) for
Computation Time 0.1 0.3 0.7 1.4

Table
The time (in minutes) to compress Qu and to compute p (n) for
Compression Time 0.2 0.9 3.0 9.5
Computation Time 0.02 0.02 0.03
to compress Q u exceeds the time to produce p (n) from Q u . However, there are still
occasions when compressing Q u and then using Q c to compute p (n) will in fact be
more efficient. The first is when it is necessary to compute p (n) for a large number of
different prior distributions (recall that Q c does not depend on the prior information
and hence need not be recomputed). The second occasion is when it is necessary
to compute p (n) for large n (e.g., [10] indicates that times on the order of 10 8 are
sometimes required). In both of these situations the cost of the compression algorithm
is amortized. Finally, compression is also advantageous when the prior distribution is
not known in advance. 9
In summary, the compression algorithm is most advantageous when it is necessary
to actually examine the powers of Q u directly. For computing probability
distributions over the states, the compression algorithm will be advantageous if the
prior distribution is initially unknown, if a large number of prior distributions will be
considered, or if the transient behavior over a long period of time is required.
7. Related Work. The goal of this paper has been to provide a technique for
compressing (or aggregating) discrete-time Markov chains (DTMCs) in a way that
yields good estimates of the transient behavior of the Markov model. This section
summarizes the work that is most closely related.
There is a considerable body of literature concerning the approximation of transient
behavior in Markov chains. Techniques include the computation of matrix expo-
nentials, the use of ordinary differential equations, and Krylov subspace methods [10].
However, all of these techniques are for continuous-time Markov chains (CTMCs),
which use an infinitesimal generator matrix instead of a probability transition matrix.
It is possible to discretize a CTMC to obtain a DTMC such that the stationary probability
vector of the CTMC is identical to that of the DTMC. However, [10] notes
that the transient solutions of DTMCs are not the same as those of the corresponding
CTMCs, indicating that these techniques will be problematic for computing the
transient behavior of DTMCs.
There is also considerable work in aggregation of DTMCs. Almost all theoretical
analyses of aggregation (e.g., "block aggregation" [5]) utilize the same functional form:
where A and B are matrices that determine the partitioning and the aggregation of
the states [3] [4]. This functional form must satisfy two axioms: "linearity" and "state
9 It is also important to emphasize that it is very likely that the compression algorithm can be
extensively optimized, producing much better timing results.
W. M. SPEARS
partitioning". Linearity implies that A and B do not depend explicitly on the entries
in Q u . State partitioning implies that the "aggregated" transition probabilities should
depend only upon the probabilities associated with the aggregated states (e.g., the
aggregation of states i and j should only depend on p i;i , p i;j , p j;i , and p j;j ).
Neither axiom is true for compression of column equivalent states in this paper.
This is reflected in the fact that in general I . Instead, in this paper
I for both row and column equivalence, yielding desirable properties with
respect to the powers of Q u . The current results indicate that the relevance of both
axioms should be re-examined.
The aggregation technique most closely related to the work in this paper is described
by [10], [11] and [12]. This aggregation technique partitions the set of states
Denoting the steady state probability of state i as
j2Sy
If compression is performed in this manner, the steady state behavior of the compressed
system is the same as the original system. The aggregated matrix can be
computed via the method of "stochastic complementation" or via "iterative aggre-
gation/ disaggregation" methods. The former will work on arbitrary matrices but
is generally computationally expensive. The latter is most efficient for "nearly completely
see [1]). However, the emphasis is always
on steady-state behavior, and not on transient behavior. This difference in emphasis
can been seen by noting the difference in the choice of weights - the focus in this
paper has been on column mass instead of steady state values.
In a sense the compression algorithm presented in this paper is a generalization of
steady state aggregation. The steady state matrix is column equivalent for every pair
of states, and the column masses, when renormalized, are the same as the steady state
probabilities. Thus the compression algorithm is a generalization of the aggregation
formula to transient behavior. 10 This leads to the intriguing hypothesis that this
new compression algorithm will be more accurate when describing transient behavior,
and less accurate for describing steady state behavior. Preliminary results appear to
confirm this hypothesis.
8. Summary and Discussion. This paper has introduced a novel compression
algorithm for probability transition matrices. The output from the algorithm is a
smaller probability transition matrix with less states. The algorithm is designed to
aggregate arbitrary (not necessarily NCD) probability transition matrices of DTMCs
in order to obtain accurate estimations of transient behavior. Thus it appears to fill
the gap between existing transient techniques (which focus on CTMCs) and existing
aggregation techniques for DTMCs (which focus on steady-state behavior).
There are a number of potential avenues for further expansion of this research.
The first possibility is to compress more than two states at once. Multiple-state
compression may yield better results, by allowing for a more accurate estimation of
error. Another avenue is to derive estimates of how error propagates to higher powers
of Q c . The current similarity metric is not necessarily a good indicator of the error at
Note that Lemma 4.5 implies that if b
COMPRESSING PROBABILITY TRANSITION MATRICES 17
higher powers of Q c , although empirically the results are quite good. However, both
of these avenues greatly increase the computational complexity of the algorithm.
The comparison with the related work indicates that this new compression algorithm
can be considered to be a generalization of the more traditional aggregation
formulas. This indicates yet a third avenue for research. If in fact column mass turns
out to yield better weights for the weighted average during transient behavior, then
it may be possible to smoothly interpolate between column mass and steady state
probabilities as the transient behavior approaches steady state. Of course, this pre-supposes
the existence of the steady state distribution, but efficient algorithms do
exist to compute these distributions.
The current algorithm also quite deliberately ignores the roles of the priors p (0)
in order to have as general an algorithm as possible. However, if priors are known,
then it may be possible to use this information to improve the weighted averaging
procedure (see Appendix), thus once again reducing the error in some situations.
Finally, the amount of compression that can be achieved with negligible error is
a useful indicator of whether the system is being modeled at the correct level of gran-
ularity. If the probability transition matrix is hard to compress, then the system is
probably modeled at a reasonable level of granularity. However, ease of compression
indicates that the system is being modeled in too much detail. In these cases monitoring
the states that are chosen for compression by the similarity metric can yield
important information about the characteristics of the system. This approach could
be used to characterize systems that are defined by a probability transition matrix
but are still not well understood at a higher level.

Acknowledgements

. I thank Diana Gordon for pointing out that a method
for evaluating the compression algorithm was to show that (Q n
c . Diana
also pointed out sections that needed mathematical refinement. I also thank the
anonymous reviewers for their very constructive comments.



--R


Using Markov chains to analyze GAFOs.
Aggregation of Markov processes: axiomatization.
Linear aggregation of input-output models

Modelling genetic algorithms with Markov chains.
A survey of methods for computing large sparse matrix exponentials arising in Markov chains.
An overview of evolutionary computation.
Analyzing GAs using Markov models with semantically ordered and lumped states.
Introduction to the numerical solution of Markov chains.
Numerical experiments with iteration and aggregation for Markov chains.
Modeling simple genetic algorithms.
--TR
lumping;transient behavior;probability transition matrix;aggregation;compression