Markov Chains question involving transition probabilities Pl

Markov Chains question involving transition probabilities. Please help!

A hard drive in a data center lasts k periods before failing with probability for be the remaining life of the hard drive in service at the end of period t Thus, will be the total operating lifetime of the next hard drive installed.

Solution

Markov Chains

Most of our study of probability has dealt with independent trials processes. These processes are the basis of classical probability theory and much of statistics. We have discussed two of the principal theorems for these processes: the Law of Large Numbers and the Central Limit Theorem. We have seen that when a sequence of chance experiments forms an independent trials process, the possible outcomes for each experiment are the same and occur with the same probability. Further, knowledge of the outcomes of the previous experiments does not influence our predictions for the outcomes of the next experiment. The distribution for the outcomes of a single experiment is sufficient to construct a tree and a tree measure for a sequence of n experiments, and we can answer any probability question about these experiments by using this tree measure. Modern probability theory studies chance processes for which the knowledge of previous outcomes influences predictions for future experiments. In principle, when we observe a sequence of chance experiments, all of the past outcomes could influence our predictions for the next experiment. For example, this should be the case in predicting a student’s grades on a sequence of exams in a course. But to allow this much generality would make it very difficult to prove general results. In 1907, A. A. Markov began the study of an important new type of chance process. In this process, the outcome of a given experiment can affect the outcome of the next experiment. This type of process is called a Markov chain.

Specifying a Markov Chain We describe a Markov chain as follows: We have a set of states, S = {s1, s2,...,sr}. The process starts in one of these states and moves successively from one state to another. Each move is called a step. If the chain is currently in state si, then it moves to state sj at the next step with a probability denoted by pij , and this probability does not depend upon which states the chain was in before the current state.

. The probabilities pij are called transition probabilities. The process can remain in the state it is in, and this occurs with probability pii. An initial probability distribution, defined on S, specifies the starting state. Usually this is done by specifying a particular state as the starting state. R. A. Howard1 provides us with a picturesque description of a Markov chain as a frog jumping on a set of lily pads. The frog starts on one of the pads and then jumps from lily pad to lily pad with the appropriate transition probabilities.

Example 11.1 According to Kemeny, Snell, and Thompson, the Land of Oz is blessed by many things, but not by good weather. They never have two nice days in a row. If they have a nice day, they are just as likely to have snow as rain the next day. If they have snow or rain, they have an even chance of having the same the next day. If there is change from snow or rain, only half of the time is this a change to a nice day. With this information we form a Markov chain as follows. We take as states the kinds of weather R, N, and S. From the above information we determine the transition probabilities. These are most conveniently represented in a square array as

P =

Transition Matrix

The entries in the first row of the matrix P in Example 11.1 represent the probabilities for the various kinds of weather following a rainy day. Similarly, the entries in the second and third rows represent the probabilities for the various kinds of weather following nice and snowy days, respectively. Such a square array is called the matrix of transition probabilities, or the transition matrix . We consider the question of determining the probability that, given the chain is in state i today, it will be in state j two days from now. We denote this probability by p (2) ij . In Example 11.1, we see that if it is rainy today then the event that it is snowy two days from now is the disjoint union of the following three events: 1) it is rainy tomorrow and snowy two days from now, 2) it is nice tomorrow and snowy two days from now, and 3) it is snowy tomorrow and snowy two days from now. The probability of the first of these events is the product of the conditional probability that it is rainy tomorrow, given that it is rainy today, and the conditional probability that it is snowy two days from now, given that it is rainy tomorrow. Using the transition matrix P, we can write this product as p11p13. The other two events also have probabilities that can be written as products of entries of P. Thus, we have

p (2) 13 = p11p13 + p12p23 + p13p33

This equation should remind the reader of a dot product of two vectors; we are dotting the first row of P with the third column of P. This is just what is done in obtaining the 1, 3-entry of the product of P with itself. In general, if a Markov chain has r states, then

p (2) ij = Xr k=1 pikpkj

The following general theorem is easy to prove by using the above observation and induction

Where do Markov chains come from

At each time we apply some new ‘randomness’ to determine the next step, in a way that is a function only of the current state. We might take U1, U2, . . . as some i.i.d. random variables taking values in a set E and a function F : I × E I. Take i I. Set X0 = i and define recursively Xn+1 = F(Xn, Un+1), n 0. Then (Xn)n0 is Markov(i , P) where pij = P(F(i, U) = j).

How can we simulate them

Use a computer to simulate U1, U2, . . . as i.i.d. U[0, 1]. Define F(U, i) = J by the rules

U [0, pi1) = J = 1 U hPj1 k=1 pik, Pj k=1 pik , j 2 = J = j.

The n-step transition matrix

Let A be an event. A convenient notation is Pi(A) = P(A | X0 = i). For example

Pi(X1 = j) = pij .

Given the initial distribution , let us treat it as a row vector. Then

P(X1 = j) = X iI iPi(X1 = j) = X iI ipij

Similarly,

Pi(X2 = j) = X k Pi(X1 = k, X2 = j) = X k pikpkj = (P 2 )ij

P(X2 = j) = X i,k iPi(X1 = k, X2 = j) = X i,k ipikpkj = (P2 )j .

Application to Markov Chains

Suppose there is a physical or mathematical system that has n possible states and at any one time, the system is in one and only one of its n states. As well, assume that at a given observation period, say k ^th   period, the probability of the system being in a particular state depends only on its status at the k-1st period. Such a system is called Markov Chain or Markov process. Let us clarify this definition with the following example.

Example Suppose a car rental agency has three locations in Ottawa: Downtown location (labeled A), East end location (labeled B) and a West end location (labeled C). The agency has a group of deliverydrivers to serve all three locations. The agency\'s statistician has determined the following:

1.      Of the calls to the Downtown location, 30% are delivered in Downtown area, 30% are delivered in the East end, and 40% are delivered in the West end

2.      Of the calls to the East end location, 40% are delivered in Downtown area, 40% are delivered in the East end, and 20% are delivered in the West end

3.      Of the calls to the West end location, 50% are delivered in Downtown area, 30% are delivered in the East end, and 20% are delivered in the West end.

After making a delivery, a driver goes to the nearest location to make the next delivery. This way, the location of a specific driver is determined only by his or her previous location.

We model this problem with the following matrix:

T=

T is called the transition matrix of the above system. In our example, a state is the location of a particular driver in the system at a particular time. The entry s_ji in the above matrix represents the probability of transition from the state corresponding to i to the state corresponding to j. (e.g. the state corresponding to 2 is B)

To make matters simple, let\'s assume that it takes each delivery person the same amount of time (say 15 minutes) to make a delivery, and then to get to their next location. According to the statistician\'s data, after 15 minutes, of the drivers that began in A, 30% will again be in A, 30% will be in B, and 40% will be in C. Since all drivers are in one of those three locations after their delivery, each column sums to 1. Because we are dealing with probabilities, each entry must be between 0 and 1, inclusive. The most important fact that lets us model this situation as a Markov chain is that the next location for delivery depends only on the current location, not previous history. It is also true that our matrix of probabilities does not change during the time we are observing

	R	N	S
R	1/2	1/4	1/4
N	1/2	0	1/2
S	1/4	1/4	1/2