From: huub@dutetvd.tudelft.nl (Huub van Roosmalen)
Subject: Decomposing Markov Models
Organization: Delft University of Technology
Date: Tue, 17 Nov 1992 10:46:41 GMT

Here is a problem ceoncerning Markov Models a friend of mine encountered 
while doing her graduation thesis. Consider a finite state continuous 
time inhomogenous Markov Model with states numbered from 0 to n. Each 
state can be reached in one step from another state. Let the probability 
that the model is in state x be Px. The model represents the total 
activity of a number of videosources on a transmission channel.

In order to simulate this model in hardware, it is highly desirable
to decompose the original model into n smaller models with only two 
states and zero-state probability Sx. If the original model is in 
state 0, then this implies that all smaller models are in state 0, 
therefore S0*S1*..*Sn = P0. Similarly, if the original model is in 
state n, then this implies that (1-S0)*(1-S1)*...*(1-Sn) = Pn. In 
general, if the original model is in state x, the the probability 
that this occurs equals the probability that x out of n small models 
are in state 1. Thus, a system with states 0 through 7 is to be
decomposed into 7 systems with two states.

                                   0-1
                                   0-1
                                   0-1
          0-1-2-3-4-5-6-7  ->      0-1
                                   0-1
                                   0-1
                                   0-1


To perform the decomposition, we take a z-transform of the original
model's state probability density. The roots of the polynomial of the
z-transform correspond to the state probabilities of the decomposed 
model. The reasoning behind this is that if we have the decomposed
model, then the distribution of the sum of the states of the small
models equals the convolution of their state distributions. In the
z-domain this is equivalent to multiplication, so if we factorize the
z transform of the original model, then the factors should each
represent the z-transform of a small model.

A typical z-transform would be:

    3 + 31 z + 33 z^2 + 28 z^3 + 22 z^4 + 23 z^5 + 6 z^6 + z^7
    ----------------------------------------------------------    (1)
                               147

The relationship between the roots Zk and the probabilities of the 
smaller models being in state 0 is:

           -Zk
    Sk = --------                                                  (2)
          1 - Zk


The trouble begins when we calculate the roots: some of them turn out
to be complex valued. Inserting these complex values into Equation 2
leads to complex probabilities!

One observation we could make is that since the coefficients of the 
polynomial are real, the complex zeros must be complex conjugated 
values. We could try to settle for less by trying to decompose the
original model into a set of models with two states for real zeros
and three states for complex zeros. In this case the example with
7 states in the original model could, for one real zero and three
complex pairs, be decomposed as:
 
                                  0-1
                                  0-1-2
          0-1-2-3-4-5-6-7  ->     0-1-2
                                  0-1-2

The results are slightly better, but we still end up with negative 
values for the probability that a small three-state model is in state 1
and the probabilities for states 0 and 2 of the small models are real
and positive and add up to 1.

I have several questions on this:

- Is it possible at all to perform a decomposition of the model in 
  this way?

- If so, How should I interpret (transform?) the complex or negative 
  values  resulting from this model? Taking the modulus or just the
  real or imaginary parts of the results does not seem to work
 
- Are there any references available to literature treating complex
  or negative probabilities? All pointers are welcome

Huub van Roosmalen
huub@dutetvd.et.tudelft.nl
Faculty of Electrical Engineering
Delft University Of Technology
The Netherlands
Newsgroups: sci.math