Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » Applied Finite Mathematics » Markov Chains: Homework

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • College Open Textbooks display tagshide tags

    This collection is included inLens: Community College Open Textbook Collaborative
    By: CC Open Textbook Collaborative

    Comments:

    "Reviewer's Comments: 'I recommend this book for undergraduates. The content is especially useful for those in finance, probability statistics, and linear programming. The course material is […]"

    Click the "College Open Textbooks" link to see all content they endorse.

    Click the tag icon tag icon to display tags associated with this content.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "Applied Finite Mathematics covers topics including linear equations, matrices, linear programming, the mathematics of finance, sets and counting, probability, Markov chains, and game theory."

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • CompInf display tagshide tags

    This module is included inLens: Lee Mond's Lens
    By: Lee Mondshein

    Click the "CompInf" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
Download
x

Download collection as:

  • PDF
  • EPUB (what's this?)

    What is an EPUB file?

    EPUB is an electronic book format that can be read on a variety of mobile devices.

    Downloading to a reading device

    For detailed instructions on how to download this content's EPUB to your specific device, click the "(what's this?)" link.

  • More downloads ...

Download module as:

  • PDF
  • EPUB (what's this?)

    What is an EPUB file?

    EPUB is an electronic book format that can be read on a variety of mobile devices.

    Downloading to a reading device

    For detailed instructions on how to download this content's EPUB to your specific device, click the "(what's this?)" link.

  • More downloads ...
Reuse / Edit
x

Collection:

Module:

Add to a lens
x

Add collection to:

Add module to:

Add to Favorites
x

Add collection to:

Add module to:

 

Markov Chains: Homework

Module by: UniqU, LLC. E-mail the author

Based on: Applied Finite Mathematics: Chapter 09 by Rupinder Sekhon

Summary: This chapter covers principles of Markov Chains. After completing this chapter students should be able to: write transition matrices for Markov Chain problems; find the long term trend for a Regular Markov Chain; Solve and interpret Absorbing Markov Chains.

MARKOV CHAINS

Exercise 1

Is the matrix given below a transition matrix for a Markov chain? Explain.

  1. .2.3.5.3−.2.9.3.3.5.2.3.5.3−.2.9.3.3.5 size 12{ left [ matrix { "." 2 {} # "." 3 {} # "." 5 {} ## "." 3 {} # - "." 2 {} # "." 9 {} ## "." 3 {} # "." 3 {} # "." 5{} } right ]} {}

  2. .3.3.4.3.4.4000.3.3.4.3.4.4000 size 12{ left [ matrix { "." 3 {} # "." 3 {} # "." 4 {} ## "." 3 {} # "." 4 {} # "." 4 {} ## 0 {} # 0 {} # 0{} } right ]} {}

[ Show Solution ]

Exercise 2

A survey of American car buyers indicates that if a person buys a Ford, there is a 60% chance that their next purchase will be a Ford, while owners of a GM will buy a GM again with a probability of .80. The buying habits of these consumers are represented in the transition matrix below.

Figure 1
This matrix depicts the buying habits of GM and Ford customers.

Find the following probabilities:

  1. The probability that a present owner of a Ford will buy a GM as his next car.

  2. The probability that a present owner of a GM will buy a GM as his next car.

  3. The probability that a present owner of a Ford will buy a GM as his third car.

  4. The probability that a present owner of a GM will buy a GM as his fourth car.

Exercise 3

Professor Hay has breakfast at Hogee's every morning. He either orders an Egg Scramble, or a Tofu Scramble. He never orders Eggs on two consecutive days, but if he does order Tofu one day, then the next day he can order Tofu or Eggs with equal probability.

  1. Write a transition matrix for this problem.

  2. If Professor Hay has Tofu on the first day, what is the probability he will have Tofu on the second day?

  3. If Professor Hay has Eggs on the first day, what is the probability he will have Tofu on the third day?

  4. If Professor Hay has Eggs on the first day, what is the probability he will have Tofu on the fourth day?

[ Show Solution ]

Exercise 4

A professional tennis player always hits cross-court or down the line. In order to give himself a tactical edge, he never hits down the line two consecutive times, but if he hits cross-court on one shot, on the next shot he can hit cross-court with .75 probability and down the line with .25 probability.

  1. Write a transition matrix for this problem.

  2. If the player hit the first shot cross-court, what is the probability that he will hit the third shot down the line?

Exercise 5

The transition matrix for switching political parties in an election year is given below, where Democrats, Republicans, and Independents are denoted by the letters DD size 12{D} {}, RR size 12{R} {}, and II size 12{I} {}, respectively.

Figure 2
This matrix shows the tendencies of Democrat, Republicans, and Independents to switch sides during an election year.

  1. Find the probability of a Democrat voting Republican.

  2. Find the probability of a Democrat voting Republican in the second election.

  3. Find the probability of a Republican voting Independent in the second election.

  4. Find the probability of a Democrat voting Independent in the third election.

[ Show Solution ]

REGULAR MARKOV CHAINS

Exercise 6

Determine whether the following matrices are regular Markov chains.

  1. 10.5.510.5.5 size 12{ left [ matrix { 1 {} # 0 {} ## "." 5 {} # "." 5{} } right ]} {}

  2. .6.401.6.401 size 12{ left [ matrix { "." 6 {} # "." 4 {} ## 0 {} # 1{} } right ]} {}

  3. .60.4.2.4.4000.60.4.2.4.4000 size 12{ left [ matrix { "." 6 {} # 0 {} # "." 4 {} ## "." 2 {} # "." 4 {} # "." 4 {} ## 0 {} # 0 {} # 0{} } right ]} {}

  4. .2.4.4.6.40.3.2.5.2.4.4.6.40.3.2.5 size 12{ left [ matrix { "." 2 {} # "." 4 {} # "." 4 {} ## "." 6 {} # "." 4 {} # 0 {} ## "." 3 {} # "." 2 {} # "." 5{} } right ]} {}

[ Show Solution ]

Exercise 7

Company I and Company II compete against each other, and the transition matrix for people switching from Company I to Company II is given below.

Figure 3
This matrix shows the tendency of customers to switch between Company I and Company II.

Find the following.

  1. If the initial market share is 40% for Company I and 60% for Company II, what will the market share be after 3 steps?

  2. If this trend continues, what is the long range expectation for the market?

Exercise 8

Suppose the transition matrix for the tennis player in Exercise 4 is as follows, where CC size 12{C} {} denotes the cross-court shots and DD size 12{D} {} denotes down-the-line shots.

Figure 4
This matrix depicts the tendency of a tennis player to make cross-court shots and down-the-line shots.

Find the following.

  1. If the player hit the first shot cross-court, what is the probability he will hit the fourth shot cross-court?

  2. Determine the long term shot distribution.

[ Show Solution ]

Exercise 9

Professor Hay never orders eggs two days in a row, but if he orders tofu one day, then there is an equal probability that he will order tofu or eggs the next day.

Find the following:

  1. If Professor Hay had eggs on Monday, what is the probability that he will have tofu on Friday?

  2. Find the long term distribution for breakfast choices for Professor Hay.

Exercise 10

Many Russians have experienced a sharp decline in their living standards due to President Yeltsin's reforms. As a result, in the parliamentary elections held in December 1995, Communists and Nationalists made significant gains, and a new pattern in switching political parties emerged. The transition matrix for such a change is given below, where Communists, Nationalists, and Reformists are denoted by the letters CC size 12{C} {}, NN size 12{N} {}, and RR size 12{R} {}, respectively.

Figure 5
This matrix depicts the tendencies for the different political parties to take power.

Find the following.

  1. If in this election Communists received 25% of the votes, Nationalists 30%, and Reformists the rest 45%, what will the distribution be in the next election?

  2. What will the distribution be in the third election?

  3. What will the distribution be in the fourth election?

  4. Determine the long term distribution.

[ Show Solution ]

ABSORBING MARKOV CHAINS

Exercise 11

Given the following absorbing Markov chain.

Figure 6
This matrix depicts the probability of moving from one sate to the other.

Find the following:

  1. Identify the absorbing states.

  2. Write the solution matrix.

  3. Starting from state 4, what is the probability of eventual absorption in state 1?

  4. Starting from state 2, what is the probability of eventual absorption in state 3?

[ Show Solution ]

Exercise 12

Two tennis players, Andre and Vijay each with two dollars in their pocket, decide to bet each other $1, for every game they play. They continue playing until one of them is broke.

Do the following:

  1. Write the transition matrix for Andre.

  2. Identify the absorbing states.

  3. Write the solution matrix.

  4. At a given stage if Andre has $1, what is the chance that he will eventually lose it all?

Exercise 13

Repeat Exercise 12, if the chance of winning for Andre is .4 and for Vijay .6.

  1. Write the transition matrix for Andre.

  2. Write the solution matrix.

  3. If Andre has $3, what is the probability that he will eventually be ruined?

  4. If Vijay has $1, what is the probability that he will eventually triumph?

[ Show Solution ]

Exercise 14

Repeat Exercise 12, if initially Andre has $3 and Vijay has $2.

  1. Write the transition matrix.

  2. Identify the absorbing states.

  3. Write the solution matrix.

  4. If Andre has $4, what is the probability that he will eventually be ruined?

Exercise 15

The non-tenured professors at a community college are regularly evaluated. After an evaluation they are classified as good, bad, or improvable. The "improvable" are given a set of recommendations and are re-evaluated the following semester. At the next evaluation, 60% of the improvable turn out to be good, 20% bad, and 20% improvable. These percentages never change and the process continues.

  1. Write the transition matrix.

  2. Identify the absorbing states.

  3. Write the solution matrix.

  4. What is the probability that a professor who is improvable will eventually become good?

[ Show Solution ]

Exercise 16

A rat is placed in the maze shown below, and it moves from room to room randomly. From any room, the rat will choose a door to the next room with equal probabilities. Once it reaches room 1, it finds food and never leaves that room. And when it reaches room 5, it is trapped and cannot leave that room. What is the probability the rat will end up in room 5 if it was initially placed in room 3?

Figure 11
This figure shows the layout of the rooms that the rat can navigate through.

Exercise 17

In Exercise 16, what is the probability the rat will end up in room 1 if it was initially placed in room 2?

[ Show Solution ]

CHAPTER REVIEW

Exercise 18

Is the matrix given below a transition matrix for a Markov chain? Explain.

  1. .1.4.5.5−.3.8.3.4.3.1.4.5.5−.3.8.3.4.3 size 12{ left [ matrix { "." 1 {} # "." 4 {} # "." 5 {} ## "." 5 {} # - "." 3 {} # "." 8 {} ## "." 3 {} # "." 4 {} # "." 3{} } right ]} {}

  2. .2.6.2000.3.4.5.2.6.2000.3.4.5 size 12{ left [ matrix { "." 2 {} # "." 6 {} # "." 2 {} ## 0 {} # 0 {} # 0 {} ## "." 3 {} # "." 4 {} # "." 5{} } right ]} {}

[ Show Solution ]

Exercise 19

A survey of computer buyers indicates that if a person buys an Apple computer, there is an 80% chance that their next purchase will be an Apple, while owners of an IBM will buy an IBM again with a probability of .70. The buying habits of these consumers are represented in the transition matrix below.

Figure 12
This matrix shows the probable buying habits of consumers from Apple to IBM.

Find the following probabilities:

  1. The probability that a present owner of an Apple will buy an IBM as his next computer.

  2. The probability that a present owner of an Apple will buy an IBM as his third computer.

  3. The probability that a present owner of an IBM will buy an IBM as his fourth computer.

[ Show Solution ]

Exercise 20

Professor Trayer either teaches Finite Math or Statistics each quarter. She never teaches Finite Math two consecutive quarters, but if she teaches Statistics one quarter, then the next quarter she will teach Statistics with a 1/31/3 size 12{1/3} {} probability.

  1. Write a transition matrix for this problem.

  2. If Professor Trayer teaches Finite Math in the Fall quarter, what is the probability that she will teach Statistics in the Winter quarter.

  3. If Professor Trayer teaches Finite Math in the Fall quarter, what is the probability that she will teach Statistics in the Spring quarter.

[ Show Solution ]

Exercise 21

The transition matrix for switching academic majors each quarter by students at a university is given below, where Science, Business, and Liberal Arts majors are denoted by the letters SS size 12{S} {}, BB size 12{B} {}, and AA size 12{A} {}, respectively.

Figure 13
This matrix shows the probability for students to switch between these three majors.

  1. Find the probability of a science major switching to a business major during their first quarter.

  2. Find the probability of a business major switching to a Liberal Arts major during their second quarter.

  3. Find the probability of a science major switching to a Liberal Arts major during their third quarter.

[ Show Solution ]

Exercise 22

Determine whether the following matrices are regular Markov chains.

  1. 10.3.710.3.7 size 12{ left [ matrix { 1 {} # 0 {} ## "." 3 {} # "." 7{} } right ]} {}
  2. .2.4.4.6.40.3.2.5.2.4.4.6.40.3.2.5 size 12{ left [ matrix { "." 2 {} # "." 4 {} # "." 4 {} ## "." 6 {} # "." 4 {} # 0 {} ## "." 3 {} # "." 2 {} # "." 5{} } right ]} {}
[ Show Solution ]

Exercise 23

John Elway, the football quarterback for the Denver Broncos, calls his own plays. At every play he has to decide to either pass the ball or hand it off. The transition matrix for his plays is given in the following table, where PP size 12{P} {} represents a pass and HH size 12{H} {} a handoff.

Figure 14
This matrix shows the probability that of the next play being a pass or a hand off.

Find the following.

  1. If John Elway threw a pass on the first play, what is the probability that he will handoff on the third play?

  2. Determine the long term play distribution.

[ Show Solution ]

Exercise 24

Company I, Company II, and Company III compete against each other, and the transition matrix for people switching from company to company each year is given below.

Figure 15
This matrix shows the probability that customers will switch between the three companies.

Find the following.

  1. If the initial market share is 20% for Company I, 30% for Company II and 50% for Company III, what will the market share be after the next year?

  2. If this trend continues, what is the long range expectation for the market?

[ Show Solution ]

Exercise 25

Given the following absorbing Markov chain.

Figure 16
This matrix depicts the probability of moving from one sate to the other.

  1. Identify the absorbing states.

  2. Write the solution matrix.

  3. Starting from state 4, what is the probability of eventual absorption in state 1?

  4. Starting from state 3, what is the probability of eventual absorption in state 2?

[ Show Solution ]

Exercise 26

A rat is placed in the maze shown below, and it moves from room to room randomly. From any room, the rat will choose a door to the next room with equal probabilities. Once it reaches room 1, it finds food and never leaves that room. And when it reaches room 6, it is trapped and cannot leave that room. What is the probability that the rat will end up in room 1 if it was initially placed in room 3?

Figure 18
This figure shows the layout of the rooms that the rat can navigate through.

[ Show Solution ]

Exercise 27

In Exercise 26, what is the probability that the rat will end up in room 6 if it was initially in room 2?

[ Show Solution ]

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Reuse / Edit:

Reuse or edit collection (?)

Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.

| Reuse or edit module (?)

Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.