Markov Chains
A Markov chain is a process, invented by the Russian mathematician Andrei Markov (1856-1922), used for predicting future outcomes or "states" of a system based upon the current state of the system. More formally, a Markov chain is a probabilistic dynamical system consisting of a finite number of states in which the probability that the system will be in a given state at time n depends only upon the state of the system at time n-1. The states of the system form the "chain." The movement of the system from one state to the next is called a transition. Every Markov chain has a "transition matrix" which contains the probabilities involved in moving from one state to the next. Also associated with each Markov chain is an initial state vector giving the state of the system at time 0. Beginning with the initial state vector, succeeding states of the Markov chain may be computed by a recursive process. If X0 is the initial state vector, Xn the state vector at time n, and T the transition matrix, then the recursion formula Xn=Xn-1T for n=1,2,3_, computes the state vectors for each successive state of the system.
As an example of how the above schema can be put into practice, suppose that the probability that an automated assembly line works correctly is 0.9 if it worked correctly the last time it was used, but only 0.7 if it did not work correctly the last time it was used. Also, suppose that statistical records indicate that the assembly line has worked correctly 80% of the time in the past. We want to predict the long term probabilities that the system works correctly or incorrectly. Our initial state vector would then be [0.8 0.2] where the first entry indicates the probability that the system is currently working correctly and the second entry is the probability that it is not working correctly. The transition matrix for this Markov chain would be a 2 by 2 matrix whose first row is [0.9 0.1], indicating the probabilities that the assembly line will work correctly (0.9) or not work correctly (0.1) given that it did work correctly the last time it was used; and whose second row is [0.7 0.3], indicating the probabilities of working and not working given that it worked the last time it was used.
So we are starting at state 0 which is [0.8 0.2]. To find state 1 of the system, we simply multiply [0.8 0.2] by the transition matrix, which gives [0.86 0.14]. This is interpreted to mean that the probability that the assembly line will work correctly at state 1 is 0.86. To find the probabilities for state 2 we multiply the new state vector [0.86 0.14] by the transition matrix, which gives [0.872 0.128]. Thus at state 2, the probability that the line will work correctly is 0.872. Now we simply continue this recursive procedure of multiplying each new state vector by the transition matrix to obtain the probabilities at the next state and we notice something interesting happening. Here are the state vectors for states 2 through 5: [0.8744 0.1256], [0.87488 0.12512], [0.874976 0.125024], and [0.8749952 0.1250048]. If we continue this process, we notice that at each new state of the system the state vector gets ever closer to [0.875 0.125]. In fact, after 13 iterations of this process, the calculator rounds off to [0.875 0.125] and, from that point on, each new iteration gives [0.875 0.125]. We interpret this to mean that, in the long run, we can expect our assembly line to work correctly 87.5% of the time. The vector [0.875 0.125] is called a "steady state" vector or an "equilibrium" vector for this Markov chain. A Markov chain which has an equilibrium vector is said to be regular.
Although Markov chains have been around since 1907, their use in applications was limited until the advent of fast digital computers with sufficient power to handle the often high dimensional matrices needed to model large systems. Currently Markov chains are used to predict future trends in business, economics, sociology, transportation, marketing, engineering, and the physical and biological sciences.
This is the complete article, containing 689 words
(approx. 2 pages at 300 words per page).
