<< Chapter < Page Chapter >> Page >

Three companies, A size 12{A} {} , B size 12{B} {} , and C 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.

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

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

Since the long term market share does not depend on the initial market share, we can simply raise the transition market share to a large power and get the distribution.

T 20 = 13 / 55 3 / 11 27 / 55 size 12{T rSup { size 8{"20"} } = left [ matrix { "13"/"55" {} # 3/"11" {} # "27"/"55"{}} right ]} {}
Got questions? Get instant answers now!
Got questions? Get instant answers now!

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 T size 12{T} {} be a transition matrix for a regular Markov chain.
  1. As we take higher powers of T size 12{T} {} , T n size 12{T rSup { size 8{n} } } {} , as n becomes large, approaches a state of equilibrium.
  2. If M size 12{M} {} is any distribution vector, and E size 12{E} {} an equilibrium vector, then MT n = E size 12{ ital "MT" rSup { size 8{n} } =E} {} .
  3. Each row of the equilibrium matrix T n size 12{T rSup { size 8{n} } } {} is a unique equilibrium vector E size 12{E} {} such that ET = E size 12{ ital "ET"=E} {} .
  4. The equilibrium distribution vector E size 12{E} {} can be found by letting ET = 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.

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

The state S 2 size 12{S rSub { size 8{2} } } {} is an absorbing state, because the probability of moving from state S 2 size 12{S rSub { size 8{2} } } {} to state S 2 size 12{S rSub { size 8{2} } } {} is 1. Which is another way of saying that if you are in state S 2 size 12{S rSub { size 8{2} } } {} , you will remain in state S 2 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 , p ii size 12{p rSub { size 8{ ital "ii"} } } {} , is 1, then state S i 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.

Gambler's ruin problem

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 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.

The transition matrix is written below. Clearly the state 0 and state 5K size 12{5K} {} are the absorbing states. This makes sense because as soon as the gambler reaches 0, she is financially ruined and the game is over. Similarly, if the gambler reaches $5,000, she has promised herself to quit and, again, the game is over. The reader should note that p 00 = 1 size 12{p rSub { size 8{"00"} } =1} {} , and p 55 = 1 size 12{p rSub { size 8{"55"} } =1} {} .

Further observe that since the gambler bets only $1,000 at a time, she can raise or lower her money only by $1,000 at a time. In other words, if she has $2,000 now, after the next bet she can have $3,000 with a probability of . 40 size 12{ "." "40"} {} and $1,000 with a probability of . 60 size 12{ "." "60"} {} .

The matrix depicts the probability of winning a thousand dollars gambling per every thousand dollars won.

To determine the long term trend, we raise the matrix to higher powers until all the non- absorbing states are absorbed. This is the called the solution matrix .

The matrix depicts the probability of winning a thousand dollars gambling per every thousand dollars won.

The solution matrix is often written in the following form, where the non-absorbing states are written as rows on the side, and the absorbing states as columns on the top.

The matrix depicts the probability of winning either zero dollars or five thousand dollars.

The table lists the probabilities of getting absorbed in state 0 or state 5K starting from any of the four non-absorbing states. For example, if at any instance the gambler has $3,000, then her probability of financial ruin is 135/211.

Got questions? Get instant answers now!
Got questions? Get instant answers now!

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

In solving absorbing states, it is often convenient to rearrange the matrix so that the rows and columns corresponding to the absorbing states are listed first. This is called the Canonical form . The transition matrix of [link] in the canonical form is listed below.

The matrix depicts the probability of winning a thousand dollars gambling per every thousand dollars won.

The canonical form divides the transition matrix into four sub-matrices as listed below.

The matrix shows the absorbing and non-absorbing states of the previous matrix.

The matrix F = 1 n B 1 size 12{F= left (1 rSub { size 8{n} } - B right ) rSup { size 8{ - 1} } } {} is called the fundamental matrix for the absorbing Markov chain, where I n size 12{I rSub { size 8{n} } } {} is an identity matrix of the same size as B size 12{B} {} . The i size 12{i} {} , j th size 12{j - ital "th"} {} entry of this matrix tells us the average number of times the process is in the non-absorbing state j size 12{j} {} before absorption if it started in the non-absorbing state i size 12{i} {} . The matrix F size 12{F} {} for our problem is listed below.

This Fundamental matrix shows the average game played before absorption.

The Fundamental matrix F size 12{F} {} helps us determine the average number of games played before absorption.

According to the matrix, the entry 1.78 in the row 3, column 2 position says that the gambler will play the game 1.78 times before she goes from $3K to $2K. The entry 2.25 in row 3, column 3 says that if the gambler now has $3K, she will have $3K on the average 2.25 times before the game is over.

We now address the question of how many bets will she have to make before she is absorbed, if the gambler begins with $3K?

If we add the number of games the gambler plays in each non-absorbing state, we get the average number of games before absorption from that state. Therefore, if the gambler starts with $3K, the average number of Black Jack games she will play before absorption is

1 . 07 + 1 . 78 + 2 . 25 + . 90 = 6 . 0 size 12{1 "." "07"+1 "." "78"+2 "." "25"+ "." "90"=6 "." 0} {}

That is, we expect the gambler will either have $5,000 or nothing on the 7th bet.

Lastly, we find the solution matrix without raising the transition matrix to higher powers.

The matrix FA size 12{ ital "FA"} {} gives us the solution matrix.

FA = 1 . 54 . 90 . 47 . 19 1 . 35 2 . 25 1 . 18 . 47 1 . 07 1 . 78 2 . 25 . 90 . 64 1 . 07 1 . 35 1 . 54 . 6 0 0 0 0 0 0 . 4 = . 92 . 08 . 81 . 19 . 64 . 36 . 38 . 62 size 12{ ital "FA"= left [ matrix { 1 "." "54" {} # "." "90" {} # "." "47" {} # "." "19" {} ##1 "." "35" {} # 2 "." "25" {} # 1 "." "18" {} # "." "47" {} ## 1 "." "07" {} # 1 "." "78" {} # 2 "." "25" {} # "." "90" {} ##"." "64" {} # 1 "." "07" {} # 1 "." "35" {} # 1 "." "54"{} } right ]left [ matrix { "." 6 {} # 0 {} ##0 {} # 0 {} ## 0 {} # 0 {} ##0 {} # "." 4{} } right ]= left [ matrix { "." "92" {} # "." "08" {} ##"." "81" {} # "." "19" {} ## "." "64" {} # "." "36" {} ##"." "38" {} # "." "62"{} } right ]} {}

Which is the same as the following matrix we obtained by raising the transition matrix to higher powers.

Got questions? Get instant answers now!

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 i size 12{i} {} is an absorbing state if once the system reaches state i size 12{i} {} , it stays in that state; that is, p ii = 1 size 12{p rSub { size 8{ ital "ii"} } =1} {} .
  2. If a transition matrix T 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 i size 12{i} {} , j th size 12{j - ital "th"} {} entry of this matrix gives the probability of absorption in state j size 12{j} {} while starting in state i 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 size 12{T= left [ matrix { I rSub { size 8{n} } {} # 0 {} ##A {} # B{} } right ]} {}

      where I n 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 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. FA size 12{ ital "FA"} {} is the solution matrix, whose i size 12{i} {} , j th size 12{j - ital "th"} {} entry gives the probability of absorption in state j size 12{j} {} while starting in state i 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.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Applied finite mathematics. OpenStax CNX. Jul 16, 2011 Download for free at http://cnx.org/content/col10613/1.5
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Applied finite mathematics' conversation and receive update notifications?

Ask