Skip to content Skip to navigation Skip to collection information

Connexions

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

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.

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

Module by: Rupinder Sekhon. E-mail the author

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.

Chapter Overview

In this chapter, you will learn to:

  1. Write transition matrices for Markov Chain problems.
  2. Find the long term trend for a Regular Markov Chain.
  3. Solve and interpret Absorbing Markov Chains.

Markov Chains

We will now study stochastic processes, experiments in which the outcomes of events depend on the previous outcomes. Such a process or experiment is called a Markov Chain or Markov process. The process was first studied by a Russian mathematician named Andrei A. Markov in the early 1900s.

A small town is served by two telephone companies, Mama Bell and Papa Bell. Due to their aggressive sales tactics, each month 40% of Mama Bell customers switch to Papa Bell, that is, the other 60% stay with Mama Bell. On the other hand, 30% of the Papa Bell customers switch to Mama Bell. The above information can be expressed in a matrix which lists the probabilities of going from one state into another state. This matrix is called a transition matrix.

Figure 1
This matrix depict the flow of customers from mama bell to papa bell and vice versa.

The reader should observe that a transition matrix is always a square matrix because all possible states must have both rows and columns. All entries in a transition matrix are non-negative as they represent probabilities. Furthermore, since all possible outcomes are considered in the Markov process, the sum of the row entries is always 1.

Example 1

Problem 1

Professor Symons either walks to school, or he rides his bicycle. If he walks to school one day, then the next day, he will walk or cycle with equal probability. But if he bicycles one day, then the probability that he will walk the next day is 1/41/4 size 12{1/4} {}. Express this information in a transition matrix.

[ Show Solution ]

Example 2

Problem 1

In Example 1, if it is assumed that the first day is Monday, write a matrix that gives probabilities of a transition from Monday to Wednesday.

[ Show Solution ]

Example 3

Problem 1

The transition matrix for Example 1 is given below.

Figure 5
This matrix depicts the probability that Professor Symons will walk or bicycle to work on Monday or Tuesday.

Write the transition matrix from a) Monday to Thursday, b) Monday to Friday.

[ Show Solution ]

There are certain Markov chains that tend to stabilize in the long run, and they are the subject of Section 3. It so happens that the transition matrix we have used in all the above examples is just such a Markov chain. The next example deals with the long term trend or steady-state situation for that matrix.

Example 4

Problem 1

Suppose Professor Symons continues to walk and bicycle according to the transition matrix given in Example 1. In the long run, how often will he walk to school, and how often will he bicycle?

[ Show Solution ]

When this happens, we say that the system is in steady-state or state of equilibrium. In this situation, all row vectors are equal. If the original matrix is an nn size 12{n} {} by nn size 12{n} {} matrix, we get n vectors that are all the same. We call this vector a fixed probability vector or the equilibrium vector EE size 12{E} {}. In the above problem, the fixed probability vector EE size 12{E} {} is 1/32/31/32/3 size 12{ left [ matrix { 1/3 {} # 2/3{} } right ]} {}. Furthermore, if the equilibrium vector EE size 12{E} {} is multiplied by the original matrix TT size 12{T} {}, the result is the equilibrium vector EE size 12{E} {}. That is,

ET=EET=E size 12{ ital "ET"=E} {}
(9)

or,

1/32/31/21/21/43/4=1/32/31/32/31/21/21/43/4=1/32/3 size 12{ left [ matrix { 1/3 {} # 2/3{} } right ] left [ matrix { 1/2 {} # 1/2 {} ## 1/4 {} # 3/4{} } right ]= left [ matrix { 1/3 {} # 2/3{} } right ]} {}
(10)

Regular Markov Chains

At the end of Section 2, we took the transition matrix TT size 12{T} {} and started taking higher and higher powers of it. The matrix started to stabilize, and finally it reached its steady-state or state of equilibrium. When that happened, all the row vectors became the same, and we called one such row vector a fixed probability vector or an equilibrium vector EE size 12{E} {}. Furthermore, we discovered that ET=EET=E size 12{ ital "ET"=E} {}.

Section Overview

In this section, we wish to answer the following four questions.

  1. Does every Markov chain reach a state of equilibrium?
  2. Does the product of an equilibrium vector and its transition matrix always equal the equilibrium vector? That is, does ET=EET=E size 12{ ital "ET"=E} {}?
  3. Can the equilibrium vector EE size 12{E} {} be found without raising the matrix to higher powers?
  4. Does the long term market share distribution for a Markov chain depend on the initial market share?

Example 5

Problem 1

Does every Markov chain reach the state of equilibrium?

[ Show Solution ]

Example 6

Problem 1

Determine whether the following Markov chains are regular.

  1. A=10.3.7A=10.3.7 size 12{A= left [ matrix { 1 {} # 0 {} ## "." 3 {} # "." 7{} } right ]} {}

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

[ Show Solution ]

Example 7

Problem 1

Does the product of an equilibrium vector and its transition matrix always equal the equilibrium vector? That is, does ET=EET=E size 12{ ital "ET"=E} {}?

[ Show Solution ]

Example 8

Problem 1

Can the equilibrium vector EE size 12{E} {} be found without raising the transition matrix to large powers?

[ Show Solution ]

Example 9

Problem 1

Does the long term market share for a Markov chain depend on the initial market share?

[ Show Solution ]

Example 10

Problem 1

Three companies, AA size 12{A} {}, BB size 12{B} {}, and CC size 12{C} {}, compete against each other. The transition matrix T for people switching each month among them is given by the following transition matrix.

Figure 7
This matrix depict the flow of people between company A, B, and C.

If the initial market share for the companies AA size 12{A} {}, BB size 12{B} {}, and CC size 12{C} {} is .25.35.40.25.35.40 size 12{ left [ matrix { "." "25" {} # "." "35" {} # "." "40"{} } right ]} {} , what is the long term distribution?

[ Show Solution ]

We summarize as follows:

Regular Markov Chains

A Markov chain is said to be a Regular Markov chain if some power of it has only positive entries.
Let TT size 12{T} {} be a transition matrix for a regular Markov chain.

  1. As we take higher powers of TT size 12{T} {}, TnTn size 12{T rSup { size 8{n} } } {}, as n becomes large, approaches a state of equilibrium.
  2. If MM size 12{M} {} is any distribution vector, and EE size 12{E} {} an equilibrium vector, then MTn=EMTn=E size 12{ ital "MT" rSup { size 8{n} } =E} {}.
  3. Each row of the equilibrium matrix TnTn size 12{T rSup { size 8{n} } } {} is a unique equilibrium vector EE size 12{E} {} such that ET=EET=E size 12{ ital "ET"=E} {}.
  4. The equilibrium distribution vector EE size 12{E} {} can be found by letting ET=EET=E size 12{ ital "ET"=E} {}.

Absorbing Markov Chains

In this section, we will study a type of Markov chain in which when a certain state is reached, it is impossible to leave that state. Such states are called absorbing states, and a Markov Chain that has at least one such state is called an Absorbing Markov chain. Suppose you have the following transition matrix.

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

The state S2S2 size 12{S rSub { size 8{2} } } {} is an absorbing state, because the probability of moving from state S2S2 size 12{S rSub { size 8{2} } } {} to state S2S2 size 12{S rSub { size 8{2} } } {} is 1. Which is another way of saying that if you are in state S2S2 size 12{S rSub { size 8{2} } } {}, you will remain in state S2S2 size 12{S rSub { size 8{2} } } {}.

In fact, this is the way to identify an absorbing state. If the probability in row i and column i , piipii size 12{p rSub { size 8{ ital "ii"} } } {}, is 1, then state SiSi size 12{S rSub { size 8{i} } } {} is an absorbing state.

We begin with an application of absorbing Markov chains to the gambler's ruin problem.

Example 11: Gambler's Ruin Problem

Problem 1

A gambler has $3,000, and she decides to gamble $1,000 at a time at a Black Jack table in a casino in Las Vegas. She has told herself that she will continue playing until she goes broke or has $5,000. Her probability of winning at Black Jack is .40.40 size 12{ "." "40"} {}. Write the transition matrix, identify the absorbing states, find the solution matrix, and determine the probability that the gambler will be financially ruined at a stage when she has $2,000.

[ Show Solution ]

Example 12

Problem 1

Solve the Gambler's Ruin Problem of Example 11 without raising the matrix to higher powers, and determine the number of bets the gambler makes before the game is over.

[ Show Solution ]

We summarize as follows:

Absorbing Markov Chains

  1. A Markov chain is an absorbing Markov chain if it has at least one absorbing state. A state ii size 12{i} {} is an absorbing state if once the system reaches state ii size 12{i} {}, it stays in that state; that is, pii=1pii=1 size 12{p rSub { size 8{ ital "ii"} } =1} {}.
  2. If a transition matrix TT size 12{T} {} for an absorbing Markov chain is raised to higher powers, it reaches an absorbing state called the solution matrix and stays there. The ii size 12{i} {}, j−thj−th size 12{j - ital "th"} {} entry of this matrix gives the probability of absorption in state jj size 12{j} {} while starting in state ii size 12{i} {}.
  3. Alternately, the solution matrix can be found in the following manner.
    1. Express the transition matrix in the canonical form as below.
      T = I n 0 A B T = I n 0 A B size 12{T= left [ matrix { I rSub { size 8{n} } {} # 0 {} ## A {} # B{} } right ]} {}
      (29)

      where InIn size 12{I rSub { size 8{n} } } {} is an identity matrix, and 0 is a matrix of all zeros.
    2. The fundamental matrix F=I−B−1F=I−B−1 size 12{F= left (I - B right ) rSup { size 8{ - 1} } } {}. The fundamental matrix helps us find the number of games played before absorption.
    3. FAFA size 12{ ital "FA"} {} is the solution matrix, whose ii size 12{i} {}, j−thj−th size 12{j - ital "th"} {} entry gives the probability of absorption in state jj size 12{j} {} while starting in state ii size 12{i} {}.
  4. The sum of the entries of a row of the fundamental matrix gives us the expected number of steps before absorption for the non-absorbing state associated with that row.

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.