Tan S.T. Finite Mathematics for the Managerial, Life, and Social Sciences

Подождите немного. Документ загружается.

25. G

ENETICS

In a certain species of roses, a plant with geno-

type (genetic makeup) AA has red flowers, a plant with

genotype Aa has pink flowers, and a plant with genotype

aa has white flowers, where A is the dominant gene and a

is the recessive gene for color. If a plant with one genotype

is crossed with another plant, then the color of the off-

spring’s flowers is determined by the genotype of the par-

ent plants. If a plant of each genotype is crossed with a

pink-flowered plant, then the transition matrix used to

determine the color of the offspring’s flowers is given by

Parent

Red Pink White

Red (AA)

Offspring Pink (Aa) or (aA)

White (aa)

If the offspring of each generation are crossed only with

pink-flowered plants, in the long run what percentage of

the plants will have red flowers? Pink flowers? White

flowers?

26. M

ARKET

HARE OF

UTO

ANUFACTURERS

In a study of the

domestic market share of the three major automobile man-

ufacturers A, B, and C in a certain country, it was found that

of the customers who bought a car manufactured by A, 75%

would again buy a car manufactured by A, 15% would buy

a car manufactured by B, and 10% would buy a car manu-

factured by C. Of the customers who bought a car manu-

factured by B, 90% would again buy a car manufactured by

B, whereas 5% each would buy cars manufactured by A and

C. Finally, of the customers who bought a car manufactured

by C, 85% would again buy a car manufactured by C, 5%

would buy a car manufactured by A, and 10% would buy a

car manufactured by B. Assuming that these sentiments

reflect the buying habits of customers in the future model

years, determine the market share that will be held by each

manufacturer in the long run.

In Exercises 27 and 28, determine whether the statement

is true or false. If it is true, explain why it is true. If it is

false, give an example to show why it is false.

27. A stochastic matrix T is a regular Markov chain if the pow-

ers of T approach a fixed matrix whose columns are all

equal.

28. To find the steady-state distribution vector X, we solve the

system

TX  X

 x



. . .

 x

 1

where T is the regular stochastic matrix associated with the

Markov process and

X 

冤



冥



29. Let T be a regular stochastic matrix. Show that the steady-

state distribution vector X may be found by solving the

vector equation TX  X together with the condition that the

sum of the elements of X is 1.

Hint: Take the initial distribution to be X, the steady-state distri-

bution vector. Then, when n is large, X ⬇ T

X. (Why?) Multiply

both sides of the last equation by T (on the left) and consider the

resulting equation when n is large.

502 9 MARKOV CHAINS AND THE THEORY OF GAMES

1. Let

X 

be the steady-state distribution vector associated with the

Markov process, where the numbers x and y are to be deter-

mined. The condition TX  X translates into the matrix

equation

which is equivalent to the system of linear equations

0.5x  0.8y  x

0.5x  0.2y  y

Each equation in the system is equivalent to the equation

0.5x  0.8y  0

.5 .8

.5 .2

d c

d c

Next, the condition that the sum of the elements of X is 1

gives

x  y  1

Thus, the simultaneous fulfillment of the two conditions

implies that x and y are the solutions of the system

0.5x  0.8y  0

x  y  1

Solving the first equation for x, we obtain

x  y

which, upon substitution into the second, yields

y  y  1

y 

9.2 Solutions to Self-Check Exercises

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 502

Therefore, x  and the required steady-state distribution

vector is

2. The transition matrix for the Markov process under con-

sideration is

T 

Now, let

X 

be the steady-state distribution vector associated with the

Markov process under consideration, where x, y, and z are

to be determined. The condition TX  X is

or, equivalently, the system of linear equations as follows:

.80 .05 .10

.05 .90 .15

.15 .05 .75

§ £

§ £

.80 .05 .10

.05 .90 .15

.15 .05 .75

0.80x  0.05y  0.10z  x

0.05x  0.90y  0.15z  y

0.15x  0.05y  0.75z  z

This system simplifies to

4x  y  2z  0

x  2y  3z  0

3x  y  5z  0

Since x  y  z  1 as well, we are required to solve the

system

4x  y  2z  0

x  2y  3z  0

3x  y  5z  0

x  y  z  1

Using the Gauss–Jordan elimination procedure, we find

x  y  z 

Therefore, in the long run, supermarkets A and C will each

have one-quarter of the customers, and supermarket B will

have half the customers.

9.2 REGULAR MARKOV CHAINS 503

USING

TECHNOLOGY

Finding the Long-Term Distribution Vector

The problem of finding the long-term distribution vector for a regular Markov chain

ultimately rests on the problem of solving a system of linear equations. As such, the

rref or equivalent function of a graphing utility proves indispensable, as the follow-

ing example shows.

EXAMPLE 1

Find the steady-state distribution vector for the regular Markov

chain whose transition matrix is

T 

Solution

Let

be the steady-state distribution vector, where x, y, and z are to be determined. The

condition TX  X translates into the matrix equation

.4 .2 .1

.3 .4 .5

.3 .4 .4

§ £

§ £

.4 .2 .1

.3 .4 .5

.3 .4 .4

(continued)

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 503

or, equivalently, the system of linear equations

0.4x  0.2y  0.1z  x

0.3x  0.4y  0.5z  y

0.3x  0.4y  0.4z  z

Since x  y  z  1, we are required to solve the system

0.6x  0.2y  0.1z  0

0.3x  0.6y  0.5z  0

0.3x  0.4y  0.6z  0

x  y  z  1

Entering this system into the graphing calculator as the augmented matrix

A 

and then using the rref function, we obtain the equivalent system (to two decimal

places)

Therefore, x ⬇ 0.20, y ⬇ 0.42, and z ⬇ 0.38, and so the required steady-state distri-

bution vector is approximately

.20

.42

.38

≥

100.20

010.42

001.38

0000

≥

.6 .2 .1 0

.3 .6 .5 0

.3 .4 .6 0

1111

504 9 MARKOV CHAINS AND THE THEORY OF GAMES

In Exercises 1 and 2, find the steady-state vector for the

matrix T.

T 

冤冥

.2 .2 .3 .2 .1

.1 .2 .1 .2 .1

.3 .4 .1 .3 .3

.2 .1 .2 .2 .2

.2 .1 .3 .1 .3

T 

冤冥

3. Verify that the steady-state vector for Example 4, page 499,

is (to two decimal places)

X  £

.47

.30

.23

.3 .2 .1 .3 .1

.2 .1 .2 .1 .2

.1 .2 .3 .2 .2

.1 .3 .2 .3 .2

.3 .2 .2 .1 .3

TECHNOLOGY EXERCISES

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 504

9.3 ABSORBING MARKOV CHAINS 505

9.3 Absorbing Markov Chains

Absorbing Markov Chains

In this section, we investigate the long-term trends of a certain class of Markov chains

that involve transition matrices that are not regular. In particular, we study Markov

chains in which the transition matrices, known as absorbing stochastic matrices, have

the special properties that we now describe.

Consider the stochastic matrix

associated with a Markov process. Interpreting it in the usual fashion, we see that after

one observation, the probability is 1 (a certainty) that an object previously in state 1

will remain in state 1. Similarly, we see that an object previously in state 2 must

remain in state 2. Next, we find that an object previously in state 3 has a probability

of .2 of going to state 1, a probability of .3 of going to state 2, a probability of .5 of

remaining in state 3, and no chance of going to state 4. Finally, an object previously

in state 4 must, after one observation, end up in state 2.

This stochastic matrix exhibits certain special characteristics. First, as observed

earlier, an object in state 1 or state 2 must stay in state 1 or state 2, respectively. Such

states are called absorbing states. In general, an absorbing state is one from which it

is impossible for an object to leave. To identify the absorbing states of a stochastic

matrix, we simply examine each column of the matrix. If column i has a 1 in the a

position (that is, on the main diagonal of the matrix) and zeros elsewhere in that col-

umn, then and only then is state i an absorbing state.

Second, observe that states 3 and 4, although not absorbing states, have the prop-

erty that an object in each of these states has a possibility of going to an absorbing

state. For example, an object currently in state 3 has a probability of .2 of ending up

in state 1, an absorbing state, and an object in state 4 must end up in state 2, also an

absorbing state, after one transition.

A Markov chain is said to be an absorbing Markov chain if the transition matrix

associated with the process is an absorbing stochastic matrix.

EXAMPLE 1

Determine whether the following matrices are absorbing stochastic

matrices.

a. b. ≥

1000

0100

00.5.4

00.5.6

¥≥

.70.10

01.50

.30.20

00.21

Absorbing Stochastic Matrix

An absorbing stochastic matrix has the following properties:

1. There is at least one absorbing state.

2. It is possible to go from each nonabsorbing state to an absorbing state in one

or more steps.

≥

10.20

01.31

00.50

00 00

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 505

506 9 MARKOV CHAINS AND THE THEORY OF GAMES

Solution

a. States 2 and 4 are both absorbing states. Furthermore, even though state 1 is not

an absorbing state, there is a possibility (with probability .3) that an object may

go from this state to state 3. State 3 itself is nonabsorbing, but an object in that

state has a probability of .5 of going to the absorbing state 2 and a probability of

.2 of going to the absorbing state 4. Thus, the given matrix is an absorbing sto-

chastic matrix.

b. States 1 and 2 are absorbing states. However, it is impossible for an object to go

from the nonabsorbing states 3 and 4 to either or both of the absorbing states.

Thus, the given matrix is not an absorbing stochastic matrix.

Given an absorbing stochastic matrix, it is always possible, by suitably reordering

the states if necessary, to rewrite it so that the absorbing states appear first. Then, the

resulting matrix can be partitioned into four submatrices,

Absorbing Nonabsorbing

where I is an identity matrix whose order is determined by the number of absorbing

states and O is a zero matrix. The submatrices R and S correspond to the nonabsorb-

ing states. As an example, the absorbing stochastic matrix of Example 1(a)

12 34 42 13

3 may be written as 1

upon reordering the states as indicated.

APPLIED EXAMPLE 2

Gambler’s Ruin John has decided to risk $2 in

the following game of chance. He places a $1 bet on each repeated play of

the game in which the probability of his winning $1 is .4, and he continues to

play until he has accumulated a total of $3 or he has lost all of his money. Write

the transition matrix for the related absorbing Markov chain.

Solution

There are four states in this Markov chain, which correspond to John

accumulating a total of $0, $1, $2, and $3. Since the first and last states listed are

absorbing states, we will list these states first, resulting in the transition matrix

Absorbing Nonabsorbing

$0 $3 $1 $2

which is constructed as follows: Since the state “$0” is an absorbing state, we see

that a

 1, a

 a

 0. Similarly, the state “$3” is an absorbing state,

so a

 1, and a

 a

 0. To construct the column corresponding to

the nonabsorbing state “$1,” we note that there is a probability of .6 (John loses)

in going from an accumulated amount of $1 to $0, so a

 .6; a

 a

 0

because it is not feasible to go from an accumulated amount of $1 to either an

accumulated amount of $3 or $1 in one transition (play). Finally, there is a proba-

≥

10.6 0

01 0.4

00 0.6

00.4 0

≥

10 0.2

01 0.5

00.7.1

00.3.2

¥≥

.70.10

01.50

.30.20

00.21

{

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 506

bility of .4 (John wins) in going from an accumulated amount of $1 to an accu-

mulated amount of $2, so a

 .4. The last column of the transition matrix is

constructed by reasoning in a similar manner.

The following question arises in connection with the last example: If John con-

tinues to play the game as originally planned, what is the probability that he will

depart from the game victorious—that is, leave with an accumulated amount of $3?

To answer this question, we have to look at the long-term trend of the relevant

Markov chain. Taking a cue from our work in the last section, we may compute the

powers of the transition matrix associated with the Markov chain. Just as in the case

of regular stochastic matrices, it turns out that the powers of an absorbing stochastic

matrix approach a steady-state matrix. However, instead of demonstrating this, we use

the following result, which we state without proof, for computing the steady-state

matrix:

APPLIED EXAMPLE 3

Gambler’s Ruin (continued) Refer to Exam-

ple 2. If John continues to play the game until either he has accumulated a

sum of $3 or he has lost all of his money, what is the probability that he will

accumulate $3?

Solution

The transition matrix associated with the Markov process is (see

Example 2)

A 

We need to find the steady-state matrix of A. In this case,

R  and S 

 R 

Using the formula in Section 2.6 for finding the inverse of a 2  2 matrix, we

find that (to two decimal places)

(I  R)

1

 c

1.32 .79

.53 1.32

d c

0.6

.4 0

d c

1 .6

.4 1

.6 0

0.4

0.6

.4 0

≥

10.6 0

01 0.4

00 0.6

00.4 0

Finding the Steady-State Matrix for an Absorbing Stochastic Matrix

Suppose an absorbing stochastic matrix A has been partitioned into submatrices

Then the steady-state matrix of A is given by

where the order of the identity matrix appearing in the expression (I  R)

1

chosen to have the same order as R.

9.3 ABSORBING MARKOV CHAINS 507

A  c

IS1I  R 2

1

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 507

508 9 MARKOV CHAINS AND THE THEORY OF GAMES

and so

S(I  R)

1



Therefore, the required steady-state matrix of A is given by

$0 $3 $1 $2

From this result we see that starting with $2, the probability is .53 that John will

leave the game with an accumulated amount of $3—that is, that he wins $1.

Our last example shows an application of Markov chains in the field of genetics.

APPLIED EXAMPLE 4

Genetics In a certain species of flowers, a

plant of genotype (genetic makeup) AA has red flowers, a plant of genotype

Aa has pink flowers, and a plant of genotype aa has white flowers, where A is the

dominant gene and a is the recessive gene for color. If a plant of one genotype is

crossed with another plant, then the color of the offspring’s flowers is determined

by the genotype of the parent plants. If the offspring are crossed successively

with plants of genotype AA only, show that in the long run all the flowers pro-

duced by the plants will be red.

Solution

First, let’s construct the transition matrix associated with the resulting

Markov chain. In crossing a plant of genotype AA with another of the same geno-

type AA, the offspring will inherit one dominant gene from each parent and thus

will have genotype AA. Therefore, the probabilities of the offspring being geno-

type AA, Aa, and aa are 1, 0, and 0, respectively.

Next, in crossing a plant of genotype AA with one of genotype Aa, the proba-

bility of the offspring having genotype AA (inheriting an A gene from the first

parent and an A from the second) is



; the probability of the offspring having

genotype Aa (inheriting an A gene from the first parent and an a gene from the

second parent) is



; finally, the probability of the offspring being of genotype aa

is 0 since this is clearly impossible.

A similar argument shows that when a plant of genotype AA is crossed with

one of genotype aa, the probabilities of the offspring having genotype AA, Aa,

and aa are 0, 1, and 0, respectively.

The required transition matrix is thus given by

Absorbing state

앗

AA Aa aa

T  Aa

Observe that the state AA is an absorbing state. Furthermore, it is possible to

go from each of the other two nonabsorbing states to the absorbing state AA.

Thus, the Markov chain is an absorbing Markov chain. To determine the long-

term effects of this experiment, let’s compute the steady-state matrix of T. Parti-

tioning T in the usual manner, we find

000

≥

1 0 .79 .47

0 1 .21 .53

0000

.6 0

0.4

d c

1.32 .79

.53 1.32

d c

.79 .47

.21 .53

c

IS1I  R 2

1

Explore & Discuss

Consider the stochastic matrix

A 

where a and b satisfy 0  a  1,

0  b  1, and 0  a  b  1.

1. Find the steady-state matrix.

2. What is the probability that

state 3 will be absorbed in

state 2?

10 a

01 b

001 a  b

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 508

9.3 ABSORBING MARKOV CHAINS 509

T 

R  and S 

Next, we compute

I  R 

and, using the formula for finding the inverse of a 2  2 matrix in Section 2.6,

(I  R)

1



Thus,

S(I  R)

1

[1 1]

Therefore, the steady-state matrix of T is given by

AA Aa aa



Interpreting the steady-state matrix of T, we see that the long-term result of cross-

ing the offspring with plants of genotype AA leads only to the absorbing state AA.

In other words, such a procedure will result in the production of plants that will

bear only red flowers, as we set out to demonstrate.

111

000

§c

IS1I  R 2

1

d c

d c

1

04c

000

9.3 Self-Check Exercises

1. Let

T 

a. Show that T is an absorbing stochastic matrix.

b. Rewrite T so that the absorbing states appear first, parti-

tion the resulting matrix, and identify the submatrices R

and S.

c. Compute the steady-state matrix of T.

2. There is a trend toward increased use of computer-aided

transcription (CAT) and electronic recording (ER) as alter-

natives to manual transcription (MT) of court proceedings

.2 0 0

.31.6

.50.4

by court stenographers in a certain state. Suppose the fol-

lowing stochastic matrix gives the transition matrix associ-

ated with the Markov process over the past decade:

CAT ER MT

CAT

T  ER

Determine the probability that a court now using electronic

recording or manual transcribing of its proceedings will

eventually change to CAT.

Solutions to Self-Check Exercises 9.3 can be found on

page 511.

1.3.2

0.6.3

0.1.5

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 509

510 9 MARKOV CHAINS AND THE THEORY OF GAMES

In Exercises 1–8, determine whether the matrix is an

absorbing stochastic matrix.

1. 2.

3. 4.

5. 6.

7. 8.

In Exercises 9–14, rewrite each absorbing stochastic

matrix so that the absorbing states appear first, partition

the resulting matrix, and identify the submatrices R and S.

9. 10.

11. 12.

13. 14.

In Exercises 15–24, compute the steady-state matrix of

each stochastic matrix.

15. 16.

17. 18. £

§£

1.2.3

0.4.2

0.4.5

.55 0

.45 1

≥

.100 0

.210.2

.301 0

.400.8

¥≥

.4 .2 0 0

.2 .3 0 0

0.310

.4 .2 0 1

.50.3

01.1

.50.6

§£

0.20

.5 .4 0

.5 .4 1

§c

.6 0

.4 1

≥

1000

0100

00.2.6

00.8.4

¥≥

10.3 0

01.2 0

00.1.5

00.4.5

≥

1000

¥£

100

0.7.2

0.3.8

§£

1.50

001

0.50

19. 20.

21. 22. ≥

10.2.1

01.4.2

00 0.4

00.4.3

¥≥

000

≥

¥≥

100

0001

9.3 Exercises

9.3 Concept Questions

1. What is an absorbing stochastic matrix?

2. Suppose the absorbing stochastic matrix A has been parti-

tioned into submatrices

Write the expression representing the steady-state matrix

of A.

23.

冤冥

24.

冤冥

25. G

ASOLINE

ONSUMPTION

As more and more old cars are

taken off the road and replaced by late models that use

unleaded fuel, the consumption of leaded gasoline will

continue to drop. Suppose the transition matrix

LUL

A 

describes this Markov process, where L denotes leaded

gasoline and UL denotes unleaded gasoline.

a. Show that A is an absorbing stochastic matrix and

rewrite it so that the absorbing state appears first. Parti-

tion the resulting matrix and identify the submatrices R

and S.

b. Compute the steady-state matrix of A and interpret your

results.

26. Diane has decided to play the following game of chance.

She places a $1 bet on each repeated play of the game in

which the probability of her winning $1 is .5. She has fur-

ther decided to continue playing the game until she has

either accumulated a total of $3 or has lost all her money.

What is the probability that Diane will eventually leave the

game a winner if she started with a capital of $1? Of $2?

27. Refer to Exercise 26. Suppose Diane has decided to stop

playing only after she has accumulated a sum of $4 or has

lost all her money. All other conditions being the same,

.80 0

.20 1

010

00000

100.2.1

010.1.2

001.3.1

000.2.2

000.2.4

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 510

what is the probability that Diane will leave the game a

winner if she started with a capital of $1? Of $2? Of $3?

28. V

IDEO

ECORDERS

Over the years, consumers are turning

more and more to newer and much improved video-

recording devices. The following transition matrix

describes the Markov chain associated with this process.

Here V stands for VHS recorders, D stands for DVD

recorders, and H stands for high definition video recorders.

VDH

A  D

a. Show that A is an absorbing stochastic matrix and

rewrite it so that the absorbing state appears first. Parti-

tion the resulting matrix and identify the submatrices R

and S.

b. Compute the steady-state matrix of A and interpret your

results.

29. E

DUCATION

ECORDS

The registrar of Computronics Insti-

tute has compiled the following statistics on the progress of

the school’s students in their 2-yr computer programming

course leading to an associate degree: Of beginning stu-

dents in a particular year, 75% successfully complete their

first year of study and move on to the second year, whereas

25% drop out of the program; of second-year students in a

particular year, 90% go on to graduate at the end of the

year, whereas 10% drop out of the program.

a. Construct the transition matrix associated with this

Markov process.

b. Compute the steady-state matrix.

c. Determine the probability that a beginning student

enrolled in the program will complete the course suc-

cessfully.

.10 0 0

.70 .60 0

.20 .40 1

30. E

DUCATION

ECORDS

The registrar of a law school has com-

piled the following statistics on the progress of the school’s

students working toward the LLB degree: Of the first-year

students in a particular year, 85% successfully complete

their course of studies and move on to the second year,

whereas 15% drop out of the program; of the second-

year students in a particular year, 92% go on to the third

year, whereas 8% drop out of the program; of the third-year

students in a particular year, 98% go on to graduate at the

end of the year, whereas 2% drop out of the program.

a. Construct the transition matrix associated with the

Markov process.

b. Find the steady-state matrix.

c. Determine the probability that a beginning law student

enrolled in the program will go on to graduate.

In Exercises 31 and 32, determine whether the statement

is true or false. If it is true, explain why it is true. If it is

false, give an example to show why it is false.

31. An absorbing stochastic matrix need not contain an absorb-

ing state.

32. In partitioning an absorbing matrix into subdivisions,

A 

the identity matrix I is chosen to have the same order as R.

33. G

ENETICS

Refer to Example 4. If the offspring are crossed

successively with plants of genotype aa only, show that in

the long run all the flowers produced by the plants will be

white.

9.3 ABSORBING MARKOV CHAINS 511

9.3 Solutions to Self-Check Exercises

1. a. State 2 is an absorbing state. States 1 and 3 are not

absorbing, but each has a possibility (with probability .3

and .6) that an object may go from these states to state

2. Therefore, the matrix T is an absorbing stochastic

matrix.

b. Denoting the states as indicated, we rewrite

123

in the form

231

1.6.3

0.4.5

00.2

.2 0 0

.3 1 .6

.5 0 .4

We see that

S  [.6 .3] and R 

c. We compute

I  R 

and, using the formula for finding the inverse of a 2  2

matrix in Section 2.6,

(I  R)

1



and so

S(I  R)

1

 [.6 .3]  [1 1]c

1.67 1.04

0 1.25

1.67 1.04

0 1.25

d c

.4 .5

0.2

d c

.6 .5

0.8

.4 .5

0.2

87533_09_ch9_p483-536 1/30/08 10:12 AM Page 511