home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15110 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  4.3 KB
  1. Xref: sparky sci.math:15110 sci.math.stat:2364
  2. Newsgroups: sci.math,sci.math.stat
  3. Path: sparky!uunet!mcsun!sun4nl!dutrun!donau!dutetvd.tudelft.nl!huub
  4. From: huub@dutetvd.tudelft.nl (Huub van Roosmalen)
  5. Subject: Decomposing Markov Models
  6. Message-ID: <1992Nov17.104641.29410@donau.et.tudelft.nl>
  7. Sender: news@donau.et.tudelft.nl (UseNet News System)
  8. Nntp-Posting-Host: dutetvd.et.tudelft.nl
  9. Organization: Delft University of Technology
  10. Date: Tue, 17 Nov 1992 10:46:41 GMT
  11. Lines: 90
  12.  
  13. Here is a problem ceoncerning Markov Models a friend of mine encountered 
  14. while doing her graduation thesis. Consider a finite state continuous 
  15. time inhomogenous Markov Model with states numbered from 0 to n. Each 
  16. state can be reached in one step from another state. Let the probability 
  17. that the model is in state x be Px. The model represents the total 
  18. activity of a number of videosources on a transmission channel.
  19.  
  20. In order to simulate this model in hardware, it is highly desirable
  21. to decompose the original model into n smaller models with only two 
  22. states and zero-state probability Sx. If the original model is in 
  23. state 0, then this implies that all smaller models are in state 0, 
  24. therefore S0*S1*..*Sn = P0. Similarly, if the original model is in 
  25. state n, then this implies that (1-S0)*(1-S1)*...*(1-Sn) = Pn. In 
  26. general, if the original model is in state x, the the probability 
  27. that this occurs equals the probability that x out of n small models 
  28. are in state 1. Thus, a system with states 0 through 7 is to be
  29. decomposed into 7 systems with two states.
  30.  
  31.                                    0-1
  32.                                    0-1
  33.                                    0-1
  34.           0-1-2-3-4-5-6-7  ->      0-1
  35.                                    0-1
  36.                                    0-1
  37.                                    0-1
  38.  
  39.  
  40. To perform the decomposition, we take a z-transform of the original
  41. model's state probability density. The roots of the polynomial of the
  42. z-transform correspond to the state probabilities of the decomposed 
  43. model. The reasoning behind this is that if we have the decomposed
  44. model, then the distribution of the sum of the states of the small
  45. models equals the convolution of their state distributions. In the
  46. z-domain this is equivalent to multiplication, so if we factorize the
  47. z transform of the original model, then the factors should each
  48. represent the z-transform of a small model.
  49.  
  50. A typical z-transform would be:
  51.  
  52.     3 + 31 z + 33 z^2 + 28 z^3 + 22 z^4 + 23 z^5 + 6 z^6 + z^7
  53.     ----------------------------------------------------------    (1)
  54.                                147
  55.  
  56. The relationship between the roots Zk and the probabilities of the 
  57. smaller models being in state 0 is:
  58.  
  59.            -Zk
  60.     Sk = --------                                                  (2)
  61.           1 - Zk
  62.  
  63.  
  64. The trouble begins when we calculate the roots: some of them turn out
  65. to be complex valued. Inserting these complex values into Equation 2
  66. leads to complex probabilities!
  67.  
  68. One observation we could make is that since the coefficients of the 
  69. polynomial are real, the complex zeros must be complex conjugated 
  70. values. We could try to settle for less by trying to decompose the
  71. original model into a set of models with two states for real zeros
  72. and three states for complex zeros. In this case the example with
  73. 7 states in the original model could, for one real zero and three
  74. complex pairs, be decomposed as:
  75.  
  76.                                   0-1
  77.                                   0-1-2
  78.           0-1-2-3-4-5-6-7  ->     0-1-2
  79.                                   0-1-2
  80.  
  81. The results are slightly better, but we still end up with negative 
  82. values for the probability that a small three-state model is in state 1
  83. and the probabilities for states 0 and 2 of the small models are real
  84. and positive and add up to 1.
  85.  
  86. I have several questions on this:
  87.  
  88. - Is it possible at all to perform a decomposition of the model in 
  89.   this way?
  90.  
  91. - If so, How should I interpret (transform?) the complex or negative 
  92.   values  resulting from this model? Taking the modulus or just the
  93.   real or imaginary parts of the results does not seem to work
  94.  
  95. - Are there any references available to literature treating complex
  96.   or negative probabilities? All pointers are welcome
  97.  
  98. Huub van Roosmalen
  99. huub@dutetvd.et.tudelft.nl
  100. Faculty of Electrical Engineering
  101. Delft University Of Technology
  102. The Netherlands
  103.