Suppose that x_{t} could take on only integer values. A given value is called a state. As time proceeds, transitions are made from the jth state to the ith state according to a probability matrix p_{ij}. The system has no memory. The next state is probabilistically dependent on the current state but independent of the previous states. The classic example is of a frog in a lily pond. As time goes by, the frog jumps from one lily pad to another. He may be more likely to jump to a near one than to a far one. The state of the system is the number of the pad the frog currently occupies. The transitions are his jumps.
To begin with, one defines a state probability ,the probability that the system will occupy state i after k transitions if its state is known at k = 0. We also define the transition matrix P_{ij}. Then
(44) |
5-3
Figure 2 An example of a state-transition diagram. |
The diagram corresponds to the probability matrix
Since at each time a transition must occur, we have that the sum of the elements in a column must be unity. In other words, the row vector is an eigenvector of P with unit eigenvalue. Let us define the Z transform of the probability vector as(45) |
(46) |
(47) |
Finally, a word of caution must be added. Occasionally defective matrices arise (incomplete set of eigenvectors) and for these the Sylvester theorem does not apply. In such cases, the solutions turn out to contain not only terms like Z^{-t}_{j} but also terms like tZ^{-t} and t^{2} Z^{-t}. It is the same situation as that applying to ordinary differential equations with constant coefficients. Ordinarily, the solutions are of the form (r_{i})^{t} where r_{i} is the ith root of the indicial equation but the presence of repeated roots gives rise to solutions like tr^{t}_{i}.