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

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

22. C

OMMUTER

RENDS

Within a large metropolitan area, 20%

of the commuters currently use the public transportation

system, whereas the remaining 80% commute via automo-

bile. The city has recently revitalized and expanded its

public transportation system. It is expected that 6 mo from

now 30% of those who are now commuting to work via

automobile will switch to public transportation, and 70%

will continue to commute via automobile. At the same

time, it is expected that 20% of those now using public

transportation will commute via automobile and 80% will

continue to use public transportation.

a. Construct the transition matrix for the Markov chain

that describes the change in the mode of transportation

used by these commuters.

b. Find the initial distribution vector for this Markov

chain.

c. What percentage of the commuters are expected to use

public transportation 6 mo from now?

23. U

RBAN

–S

UBURBAN

OPULATION

LOW

Refer to Example 4.

If the initial probability distribution is



City

Suburb

what will be the population distribution of the city after 1

yr? After 2 yr?

24. Refer to Example 6. If the initial distribution vector for the

location of the taxis is

Zone I

 Zone II

Zone III

what will be the distribution after all of them have made

one pickup and discharge?

25. M

ARKET

HARE

At a certain university, three bookstores—

the University Bookstore, the Campus Bookstore, and the

Book Mart—currently serve the university community.

From a survey conducted at the beginning of the fall quar-

ter, it was found that the University Bookstore and the

Campus Bookstore each had 40% of the market, whereas

the Book Mart had 20% of the market. Each quarter the

University Bookstore retains 80% of its customers but

loses 10% to the Campus Bookstore and 10% to the Book

Mart. The Campus Bookstore retains 75% of its customers

but loses 10% to the University Bookstore and 15% to the

Book Mart. The Book Mart retains 90% of its customers

but loses 5% to the University Bookstore and 5% to the

Campus Bookstore. If these trends continue, what percent-

age of the market will each store have at the beginning of

the second quarter? The third quarter?

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 their current market shares were 60%, 30%, and 10%,

respectively. Furthermore, it was found that of the cus-

tomers who bought a car manufactured by A, 75% would

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

.80

.20

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

tured by C. Of the customers who bought a car manufac-

tured 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 manufac-

tured 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 senti-

ments reflect the buying habits of customers in the future,

determine the market share that will be held by each man-

ufacturer after the next two model years.

27. C

OLLEGE

AJORS

Records compiled by the Admissions

Office at a state university indicating the percentage of stu-

dents who change their major each year are shown in the

following transition matrix. Of the freshmen now at the

university, 30% have chosen their major field in Business,

30% in the Humanities, 20% in Education, and 20% in the

Natural Sciences and other fields. Assuming that this trend

continues, find the percentage of these students that will be

majoring in each of the given areas in their senior year.

Hint: Find T

Nat. Sc.

and

Bus. Hum. Educ. others

Business

Humanities

Education

Nat. Sci. and others

28. H

OMEOWNERS

’ C

HOICE OF

NERGY

A study conducted by

the Urban Energy Commission in a large metropolitan area

indicates the probabilities that homeowners within the area

will use certain heating fuels or solar energy during the

next 10 yr as the major source of heat for their homes. The

transition matrix representing the transition probabilities

from one state to another is

Elec. Gas Oil Solar

Electricity

Natural gas

Fuel oil

Solar energy

Among homeowners within the area, 20% currently use

electricity, 35% use natural gas, 40% use oil, and 5% use

solar energy as the major source of heat for their homes.

What is the expected distribution of the homeowners who

will be using each type of heating fuel or solar energy

within the next decade?

In Exercises 29 and 30, 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.

29. A Markov chain is a process in which the outcomes at any

stage of the experiment depend on the outcomes of the pre-

ceding stages.

30. The sum of the entries in each column of a transition

matrix must not exceed 1.

≥

.70000

.15 .90 .20 .05

.05 .02 .75 0

.10 .08 .05 .95

≥

.80 .10 .20 .10

.10 .70 .10 .05

.05 .10 .60 .05

.05 .10 .10 .80

492 9 MARKOV CHAINS AND THE THEORY OF GAMES

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

1. The required transition matrix is

T 

2. a. The initial distribution vector is



b. The vector representing the market share of each super-

market after 1 yr is

 TX

 £

.80 .05 .10

.05 .90 .15

.15 .05 .75

§ £

§ £

.365

.335

.300

.80 .05 .10

.05 .90 .15

.15 .05 .75

That is, after 1 yr supermarket A will command a 36.5%

market share, supermarket B will have a 33.5% share, and

supermarket C will have a 30% market share.

The vector representing the market share of the super-

markets after 2 yr is

 TX



That is, 2 yr later the market shares of supermarkets A,

B, and C will be 33.88%, 36.48%, and 29.65%, respec-

tively.

.80 .05 .10

.05 .90 .15

.15 .05 .75

§ £

.365

.335

.300

§⬇ £

.33875

.36475

.29650

9.1 MARKOV CHAINS 493

9.1 Solutions to Self-Check Exercises

USING

TECHNOLOGY

Finding Distribution Vectors

Since the computation of the probability distribution of a system after a certain num-

ber of observations involves matrix multiplication, a graphing utility may be used to

facilitate the work.

EXAMPLE 1

Consider the problem posed in Example 6, page 488, where

T  and X



Verify that



as obtained in that example.

Solution

First, we enter the matrix X

as the matrix A and the matrix T as the

matrix B. Then, performing the indicated multiplication, we find that

B^2*A 

That is,

 T



as was to be shown.

.4965

.3000

.2035

.4965

.3000

.2035

.4965

.3000

.2035

.80

.15

.05

§£

.6 .4 .3

.3 .3 .3

.1 .3 .4

(continued)

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

494 9 MARKOV CHAINS AND THE THEORY OF GAMES

In Exercises 1–2, find X

(the probability distribution of

the system after five observations) for the distribution

vector X

and the transition matrix T.

1. X



冤冥

, 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

3. Refer to Exercise 26 on page 492. Using the same data,

determine the market share that will be held by each man-

ufacturer five model years after the study began.

4. Refer to Exercise 25 on page 492. Using the same data,

determine the expected market share that each store will

have at the beginning of the fourth quarter.

Steady-State Distribution Vectors

In the last section, we derived a formula for computing the likelihood that a physical

system will be in any one of the possible states associated with each stage of a Markov

process describing the system. In this section we use this formula to help us investi-

gate the long-term trends of certain Markov processes.

APPLIED EXAMPLE 1

Educational Status of Women A survey con-

ducted by the National Commission on the Educational Status of Women

reveals that 70% of the daughters of women who have completed 2 or more years

of college have also completed 2 or more years of college, whereas 20% of the

daughters of women who have had less than 2 years of college have completed

2 or more years of college. If this trend continues, determine, in the long run, the

percentage of women in the population who will have completed at least 2 years

of college given that currently only 20% of the women have completed at least

2 years of college.

Solution

This problem may be viewed as a Markov process with two possible

states: “completed 2 or more years of college” (state 1) and “completed less than

2 years of college” (state 2). The transition matrix associated with this Markov

chain is given by

T 

The initial distribution vector is given by



To study the long-term trend pertaining to this particular aspect of the educa-

tional status of women, let’s compute X

, X

, . . . , the distribution vectors associ-

.7 .2

.3 .8

TECHNOLOGY EXERCISES

9.2 Regular Markov Chains

2. X



冤冥

, T 

冤冥

.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

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

9.2 REGULAR MARKOV CHAINS 495

ated with the Markov process under consideration. These vectors give the per-

centage of women with 2 or more years of college and that of women with less

than 2 years of college after one generation, after two generations, and so on.

With the aid of Formula (1), Section 9.1, we find (to four decimal places)

After one generation X

 TX



After two generations X

 TX



After three generations X

 TX



Proceeding further, we obtain the following sequence of vectors:



⬇

After ten generations X

⬇

From the results of these computations, we see that as m increases, the proba-

bility distribution vector X

approaches the probability distribution vector

Such a vector is called the limiting, or steady-state, distribution vector for the

system. We interpret these results in the following way: Initially, 20% of the

women in the population have completed 2 or more years of college, whereas

80% have completed less than 2 years of college. After one generation, the for-

mer has increased to 30% of the population, and the latter has dropped to 70% of

the population. The trend continues, and eventually, 40% of all women in future

generations will have completed 2 or more years of college, whereas 60% will

have completed less than 2 years of college.

To explain the foregoing result, let’s analyze Formula (1), Section 9.1, more

closely. Now, the initial distribution vector X

is a constant; that is, it remains fixed

throughout our computation of X

, X

, . . . . It appears reasonable, therefore, to con-

jecture that this phenomenon is a result of the behavior of the powers, T

, of the tran-

sition matrix T. Pursuing this line of investigation, we compute



 c

.7 .2

.3 .8

d c

.55 .3

.45 .7

d c

.475 .35

.525 .65

.7 .2

.3 .8

d c

.7 .2

.3 .8

d c

.55 .3

.45 .7

.3998

.6002

.3996

.6004

.3992

.6008

.3984

.6016

.3969

.6031

.3938

.6062

.3875

.6125

.7 .2

.3 .8

.35

.65

d c

.375

.625

.7 .2

.3 .8

d c

.35

.65

.7 .2

.3 .8

d c

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

Proceeding further, we obtain the following sequence of matrices:

 T

⬇

⬇ T

⬇

⬇ T

⬇

⬇ T

⬇

These results show that the powers T

of the transition matrix T tend toward a

fixed matrix as m gets larger and larger. In this case, the “limiting matrix” is the matrix

L  or

Such a matrix is called the steady-state matrix for the system. Thus, as suspected, the

long-term behavior of a Markov process such as the one in this example depends on

the behavior of the limiting matrix of the powers of the transition matrix—the steady-

state matrix for the system. In view of this, the long-term (steady-state) distribution

vector for this problem may be found by computing the product



which agrees with the result obtained earlier.

Next, since the transition matrix T in this situation seems to have a stabilizing

effect over the long term, we are led to wonder whether the steady state would be

reached regardless of the initial state of the system. To answer this question, suppose

the initial distribution vector is



Then, as before, the steady-state distribution vector is given by



Thus, the steady state is reached regardless of the initial state of the system!

Regular Markov Chains

The transition matrix T of Example 1 has several important properties, which we

emphasized in the foregoing discussion. First, the sequence T, T

, T

, . . . approaches

a steady-state matrix in which the columns of the limiting matrix are all equal and all

entries are positive. A matrix T having this property is called a regular Markov chain.

Regular Markov Chain

A stochastic matrix T is a regular Markov chain if the sequence

T, T

, T

, . . .

approaches a steady-state matrix in which the columns of the limiting matrix are

all equal and all the entries are positive.

.40 .40

.60 .60

d c

1  p

d c

.40

.60

1  p

.40 .40

.60 .60

d c

d c

.40

.60

.40 .40

.60 .60

.4003 .3998

.5997 .6002

.4006 .3996

.5994 .6004

.4012 .3992

.5988 .6008

.4023 .3984

.5977 .6016

.4047 .3969

.5953 .6031

.4094 .3938

.5906 .6062

.4188 .3875

.5813 .6125

.4375 .375

.5625 .625

496 9 MARKOV CHAINS AND THE THEORY OF GAMES

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

It can be shown that a stochastic matrix T is regular if and only if some power of

T has entries that are all positive. Second, as in the case of Example 1, a Markov chain

with a regular transition matrix has a steady-state distribution vector whose column is

identical to a column in the steady-state matrix; thus, this steady-state distribution vec-

tor is always reached regardless of the initial distribution vector.

We will return to computations involving regular Markov chains, but for

the moment let’s see how one may determine whether a given matrix is indeed

regular.

EXAMPLE 2

Determine which of the following matrices are regular.

a. b. c.

Solution

a. Since all the entries of the matrix are positive, the given matrix is regular. Note

that this is the transition matrix of Example 1.

b. In this case, one of the entries of the given matrix is equal to zero. Let’s

compute

앖

All entries are positive.

Since the second power of the matrix has entries that are all positive, we con-

clude that the given matrix is in fact regular.

c. Denote the given matrix by A. Then,

A 



Observe that A

 A. It therefore follows that A

 A

, A

 A, and so on. In

other words, any power of A must coincide with either A or A

. Since not all

entries of A and A

are positive, the same is true of any power of A. We conclude

accordingly that the given matrix is not regular.

We now return to the study of regular Markov chains. In Example 1, we found the

steady-state distribution vector associated with a regular Markov chain by studying

the limiting behavior of a sequence of distribution vectors. Alternatively, as pointed

out in the subsequent discussion, the steady-state distribution vector may also be

obtained by first determining the steady-state matrix associated with the regular

Markov chain.

Fortunately, there is a relatively simple procedure for finding the steady-state dis-

tribution vector associated with a regular Markov process. It does not involve the

d c

d c

d c

d c

.4 1

.6 0

 c

.4 1

.6 0

d c

.4 1

.6 0

d c

.76 .4

.24 .6

.4 .1

.6 0

.7 .2

.3 .8

9.2 REGULAR MARKOV CHAINS 497

———

씮

———

씮

Explore & Discuss

Find the set of all 2  2 stochas-

tic matrices with elements that

are either 0 or 1.

Not all entries are positive.

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

rather tedious computations required to obtain the sequences in Example 1. The pro-

cedure follows.

A justification of the foregoing procedure is given in Exercise 29.

EXAMPLE 3

Find the steady-state distribution vector for the regular Markov

chain whose transition matrix is

T  See Example 1.

Solution

Let

X 

be the steady-state distribution vector associated with the Markov process, where the

numbers x and y are to be determined. The condition TX  X translates into the

matrix equation

or, equivalently, the system of linear equations

0.7x  0.2y  x

0.3x  0.8y  y

But each of the equations that make up this system of equations is equivalent to the

single equation

0.3x  0.2y  0

0.7



 0.2

 0

0.3

 0.8



 0

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.3x  0.2y  0

x  y  1

Solving the first equation for x, we obtain

x  y

.7 .2

.3 .8

d c

d c

.7 .2

.3 .8

Finding the Steady-State Distribution Vector

Let T be a regular stochastic matrix. Then 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 the vector X be equal

to 1.

498 9 MARKOV CHAINS AND THE THEORY OF GAMES

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

which, upon substitution into the second, yields

y  y  1

y 

Thus, x  , and the required steady-state distribution vector is given by

X 

which agrees with the result obtained earlier.

APPLIED EXAMPLE 4

Taxicab Movement In Example 6, Section

9.1, we showed that the transition matrix that described the movement of

taxis from zone to zone was given by the regular stochastic matrix

T 

Use this information to determine the long-term distribution of the taxis in the

three zones.

Solution

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

translates into the matrix equation

or, equivalently, the system of linear equations

0.6x  0.4y  0.3z  x

0.3x  0.3y  0.3z  y

0.1x  0.3y  0.4z  z

The system simplifies into

4x  4y  3z  0

3x  7y  3z  0

x  3y  6z  0

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

x  y  z  1

4x  4y  3z  0

3x  7y  3z  0

x  3y  6z  0

.6 .4 .3

.3 .3 .3

.1 .3 .4

§ £

§ £

.6 .4 .3

.3 .3 .3

.1 .3 .4

9.2 REGULAR MARKOV CHAINS 499

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

500 9 MARKOV CHAINS AND THE THEORY OF GAMES

Using the Gauss–Jordan elimination procedure of Chapter 2, we find that

x  y  z 

or x ⬇ 0.47, y  0.30, and z ⬇ 0.23. Thus, in the long run, approximately 47% of

the taxis will be in zone I, 30% in zone II, and 23% in zone III.

9.2 Exercises

9.2 Self-Check Exercises

9.2 Concept Questions

1. Find the steady-state distribution vector for the regular

Markov chain whose transition matrix is

T 

2. Three supermarkets serve a certain section of a city. Dur-

ing the year, supermarket A is expected to retain 80% of its

customers, lose 5% of its customers to supermarket B, and

lose 15% to supermarket C. Supermarket B is expected to

.5 .8

.5 .2

retain 90% of its customers and lose 5% to each of super-

market A and supermarket C. Supermarket C is expected to

retain 75% of its customers, lose 10% to supermarket A,

and lose 15% to supermarket B. If these trends continue,

what will be the market share of each supermarket in the

long run?

Solutions to Self-Check Exercises 9.2 can be found on

page 502.

1. Explain (a) a steady-state distribution vector, (b) a steady-

state matrix, and (c) a regular Markov chain.

2. How do you find the steady-state distribution vector given

a regular stochastic matrix T associated with a Markov

process?

In Exercises 1–8, determine which of the matrices are

regular.

1. 2.

3. 4.

5. 6.

7. 8.

In Exercises 9–16, find the steady-state vector for the

transition matrix.

9. 10.

11. 12. c

.9 1

.1 0

.5 .2

.5 .8

100

§£

.7 .2 .3

.3 .8 .3

00.4

1.3.1

0.4.8

0.3.1

§£

1.8

0.2

0.3

1.7

13. 14.

15. 16.

17. P

SYCHOLOGY

XPERIMENTS

A psychologist conducts an

experiment in which a mouse is placed in a

T-maze, where

it has a choice at the

T-junction of turning left and receiv-

ing a reward (cheese) or turning right and receiving a mild

shock. At the end of each trial a record is kept of the

mouse’s response. It is observed that the mouse is as likely

to turn left (state 1) as right (state 2) during the first trial.

In subsequent trials, however, the observation is made that

if the mouse had turned left in the previous trial, then the

probability that it will turn left in the next trial is .8,

whereas the probability that it will turn right is .2. If the

mouse had turned right in the previous trial, then the prob-

ability that it will turn right in the next trial is .1, whereas

the probability that it will turn left is .9. In the long run,

what percentage of the time will the mouse turn left at the

T-junction?

.1 .2 .3

.8 .6 .4

§£

.2 0 .3

0.6.4

.8 .4 .3

.6 .3 0

.4 .4 .6

0.3.4

§£

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

18. C

OMMUTER

RENDS

Within a large metropolitan area, 20%

of the commuters currently use the public transportation

system, whereas the remaining 80% commute via automo-

bile. The city has recently revitalized and expanded its pub-

lic transportation system. It is expected that 6 mo from now

30% of those who are now commuting to work via auto-

mobile will switch to public transportation, and 70% will

continue to commute via automobile. At the same time, it is

expected that 20% of those now using public transportation

will commute via automobile, and 80% will continue to use

public transportation. In the long run, what percentage of

the commuters will be using public transportation?

19. O

AND

-I

NCOME

AMILIES

From data compiled over

a 10-yr period by Manpower, Inc., in a statewide study of

married couples in which at least one spouse was working,

the following transition matrix was constructed. It gives

the transitional probabilities for one and two wage earners

among married couples.

Current State

1 Wage 2 Wage

Earner Earners

Next State

1 Wage Earner .72 .12

2 Wage Earners .28 .88

At the present time, 48% of the married couples (in which

at least one spouse is working) have one wage earner, and

52% have two wage earners. Assuming that this trend con-

tinues, what will be the distribution of one- and two-wage

earner families among married couples in this area 10 yr

from now? Over the long run?

20. P

ROFESSIONAL

OMEN

From data compiled over a 5-yr

period by Women’s Daily in a study of the number of

women in the professions, the following transition matrix

was constructed. It gives the transitional probabilities for

the number of men and women in the professions.

Current State

Men Women

Men .95 .04

Next State

Women .05 .96

As of the beginning of 1986, 52.9% of professional jobs

were held by men. If this trend continues, what percentage

of professional jobs will be held by women in the long run?

21. B

UYING

RENDS OF

OME

UYERS

From data collected over

the past decade by the Association of Realtors of a certain

city, the following transition matrix was obtained. The

matrix describes the buying pattern of home buyers who

buy single-family homes (S) or condominiums (C ).

Current State

S .85 .35

Next State

C .15 .65

9.2 REGULAR MARKOV CHAINS 501

Currently, 80% of the homeowners live in single-family

homes, whereas 20% live in condominiums. If this trend

continues, what percentage of homeowners in this city will

own single-family homes and condominiums 2 decades

from now? In the long run?

22. H

OMEOWNERS

’ C

HOICE OF

NERGY

A study conducted by

the Urban Energy Commission in a large metropolitan area

indicates the probabilities that homeowners within the area

will use certain heating fuels or solar energy during the

next 10 yr as the major source of heat for their homes. The

following transition matrix represents the transition proba-

bilities from one state to another:

Elec. Gas Oil Solar

Electricity

Natural gas

Fuel oil

Solar energy

Among the homeowners within the area, 20% currently use

electricity, 35% use natural gas, 40% use oil, and 5% use

solar energy as their major source of heat for their homes.

In the long run, what percentage of homeowners within the

area will be using solar energy as their major source of

heating fuel?

23. N

ETWORK

EWS

IEWERSHIP

A television poll was con-

ducted among regular viewers of the national news in a

certain region where the three national networks share the

same time slot for the evening news. Results of the poll

indicate that 30% of the viewers watch the ABC evening

news, 40% watch the CBS evening news, and 30% watch

the NBC evening news. Furthermore, it was found that of

those viewers who watched the ABC evening news during

1 wk, 80% would again watch the ABC evening news dur-

ing the next week, 10% would watch the CBS news, and

10% would watch the NBC news. Of those viewers who

watched the CBS evening news during 1 wk, 85% would

again watch the CBS evening news during the next week,

10% would watch the ABC news, and 5% would watch the

NBC news. Of those viewers who watched the NBC

evening news during 1 wk, 85% would again watch the

NBC news during the next week, 10% would watch ABC,

and 5% would watch CBS.

a. What share of the audience consisting of regular view-

ers of the national news will each network command

after 2 wk?

b. In the long run, what share of the audience will each

network command?

24. N

ETWORK

EWS

IEWERSHIP

Refer to Exercise 23. If the

initial distribution vector is

ABC

 CBS

NBC

what share of the audience will each network command in

the long run?

.40

.20

≥

.70 0 .10 0

.15 .90 .10 .05

.05 .02 .75 .05

.10 .08 .05 .90

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