History and Background In 1907, A. A. Markov began the study of chance processes for which the knowledge of each outcome is relevant only in predicting next outcome. This study has come to be known as the Markov chains and found in large number of areas like marketing, health services, finance, production and accounting. Assume we have set of states, S = {St, S2, S3, , Sk). The process starts in one of t states at time, T-0, and moves successively from one state to another at unit time intervals 2k S3 Time T = 0 T=1 S2 State S1 Sk state S to Each move is called a step. The probability Pi that the process moves from state S depends only on the state S, occupied before the step. In another words, the probability distribution of the state at time T+1 depends on the state at time T and does not depend on the states the chain passed through on the way. The probabilities Pj are called transition probabilities Suppose the entire cola industry produces only three colas [cola1, cola2, cola3]. Given that a person last purchased cola 1, there is a 90% chance that his/her next purchase will be cola!" Given that a person last purchased cola2, there is a 90% chance that his/her next purchase will be cola2. Also, given that a person last purchased cola3, there is a 90% chance that his/her next purchase will be cola3. Now we can define the initial probability distribution for this example. We represent this in a transition probability matrix: cola 1 cola 2 cola3 cola 1 0.9 0.05 0.05 cola 2 0.05 0.9 0.05 cola 3 0.05 0.05 0.9 In th Is example, each entry in the matrix Q must be non-negative and the entries in ach row purchase as e pers o mst sum to 1 (special case of Markov chains). We view each person's the a a Markov chain with the state at any given time being the type of cola on last purchased. So, how do we answer the question, if a person is History and Background In 1907, A. A. Markov began the study of chance processes for which the knowledge of each outcome is relevant only in predicting next outcome. This study has come to be known as the Markov chains and found in large number of areas like marketing, health services, finance, production and accounting. Assume we have set of states, S = {St, S2, S3, , Sk). The process starts in one of t states at time, T-0, and moves successively from one state to another at unit time intervals 2k S3 Time T = 0 T=1 S2 State S1 Sk state S to Each move is called a step. The probability Pi that the process moves from state S depends only on the state S, occupied before the step. In another words, the probability distribution of the state at time T+1 depends on the state at time T and does not depend on the states the chain passed through on the way. The probabilities Pj are called transition probabilities Suppose the entire cola industry produces only three colas [cola1, cola2, cola3]. Given that a person last purchased cola 1, there is a 90% chance that his/her next purchase will be cola!" Given that a person last purchased cola2, there is a 90% chance that his/her next purchase will be cola2. Also, given that a person last purchased cola3, there is a 90% chance that his/her next purchase will be cola3. Now we can define the initial probability distribution for this example. We represent this in a transition probability matrix: cola 1 cola 2 cola3 cola 1 0.9 0.05 0.05 cola 2 0.05 0.9 0.05 cola 3 0.05 0.05 0.9 In th Is example, each entry in the matrix Q must be non-negative and the entries in ach row purchase as e pers o mst sum to 1 (special case of Markov chains). We view each person's the a a Markov chain with the state at any given time being the type of cola on last purchased. So, how do we answer the question, if a person is