Transition Matrices & Markov Chains (DP IB Maths: AI HL)

It is known that in the legendary frozen town of Kholod the weather displays the following patterns: 

• If it snows on one day then there is a probability of 0.8 that it will snow on the following day 

• If it does not snow on one day then there is a probability of 0.6 that it will also not snow on the following day 

Represent this information as 

(i)     a transition state diagram 

(ii)    a transition matrix.

Let  be the transition matrix found in part (a)(ii).

By first finding an appropriate power of the matrix , find the probability that it will snow on Friday, given that it did not snow on the preceding Tuesday.

Bartolomé is a professional probabilist who has devised a way to save money on lodging.  He has decided he can spend each day working in cafés in one of three cities A,B, and C.  Then each night he will sleep on an overnight train travelling between the cities (or in some cases returning by morning to the same city from which it left).  Due to his fondness for probability, Bartolomé has determined to allow his movement between the cities each night to be subject to the probabilities in the following transition state diagram:

Write down the transition matrix for this system of probabilities.

One Friday, Bartolomé spends the day in the same city where he spent the preceding Monday.  Determine the probabilities of this having happened for each of the cities.

Find the long-term probabilities of Bartolomé spending a given day in cities  or .

Two bands from Wem, WeDaBoyz and Grrl Pow-R, are the megastars of the new W-Pop scene.  At any one time, no fan of WeDaBoyz will ever also be a fan of Grrl Pow-R, and no fan of Grrl Pow-R will ever also be a fan of WeDaBoyz.  Each week, however, 17% of WeDaBoyz’s fans switch to become fans of Grrl Pow-R, and 13% of Grrl Pow-R’s fans switch to become fans of WeDaBoyz.  It may be assumed that there are no other gains or losses of fans by the two bands.

Write down a transition matrix  representing the movement of fans between the two bands in a particular week.

Initially WeDaBoyz has 4000 fans and Grrl Pow-R has 2300 fans.

Write down the initial state vector  for the system.

Determine the number of fans that WeDaBoyz and Grrl Pow-R will each have after four weeks.

Find

On a mystery cruise, each passenger is assigned to one of three groups – suspects, investigators or red herrings.  At a special ‘reveal’ event each night, passengers are reassigned roles according to the following scheme: 

• Due to additional revealed information about the fictional crime, half the suspects become red herrings while one twentieth of them become investigators 

• Due to revealed events from their fictional pasts, one third of the investigators become suspects and one tenth become red herrings 

• Due to revealed disambiguations, all of the red herrings become either suspects or investigators, with five becoming suspects for each two that become investigators 

There is no other way for the numbers of passengers in each of the three roles to increase or decrease.  Initially there are 2100 suspects, 15 investigators, and 885 red herrings. 

Write down a transition matrix  and an initial state vector  representing the movement of passengers between the three roles from night to night.

Determine the number of nightly reveals will it take until the number of investigators exceeds 650.

If the cruise continued for an indefinite period of time, find

The marketing department of BreadHead brand shampoo (“It makes you look like you have breadcrumbs in your hair!”) is attempting to predict the percentage of potential customers who will purchase its product month by month in the future. 

The lead marketing researcher reports that, according to his research, there is only a 3% chance that a potential customer who buys BreadHead shampoo one month will buy it again the following month.  On the other hand, due to product placement deals with a number of popular social media influencers, there is a 99% chance that a potential customer who does not buy BreadHead shampoo one month will buy it the following month. 

Explain what assumption the marketing researcher would need to make in order to use a Markov chain to predict month by month sales according to his research.

The researcher decides to model the situation using a Markov chain.  It is known that currently 5% of potential customers buy BreadHead shampoo. 

Find the probability that a randomly selected potential customer 

(i)     will purchase BreadHead shampoo next month, 

(ii)    will purchase BreadHead shampoo in the long term.

Criticise the model, in particular the researcher’s decision to use a Markov chain.

An electric car hire company offers one-day hires from three hire centres located in a large city – one at the Airport (A), one at the Breakdancing Museum (B), and one in the City Centre (C).  Past experience shows that 82% of cars hired at A are returned to A; otherwise they are twice as likely to be returned to C as they are to B.   Only 12% of cars hired at B are returned to B, with 48% being returned to A and the rest returned to C.  Of cars hired at C, 64% are returned to C, with equal numbers of the remainder returned to A and B. 

By solving a system of linear equations represented by , for an appropriately defined matrix , determine a steady state vector  corresponding to .

After a one-week shutdown for maintenance, the company is about to redistribute its entire fleet of 725 cars between its three locations. 

In the town of Petersham, all the residents belong to either one or the other of the town’s two curling clubs – the Slippery Sliders (S) or the Wild Sweepers (W).  Competition between the clubs is fierce, and members tend to be quite loyal.  Still, each year 2% of the members of S switch to W and 3% of the members of W switch to S.  Any other losses or gains of members by the two curling clubs may be ignored.

Write down a transition matrix  representing the movement of members between the two clubs in a particular year.

Diagonalise the matrix by writing it in the form  for appropriate matrices  and .

Initially there are 574 members of  and 621 members of W.

Show that the numbers of members of S and W after n years will be     and  , respectively.

Hence write down the number of members that each of the curling clubs can expect to have in the long term.

Blythe is a chess player whose results in games during tournaments are strongly affected by the result of the immediately preceding game: 

• If he wins a game, his increased confidence means that the probabilities for him winning, drawing or losing the next game are 0.38, 0.35 and 0.27 respectively. 

• If he draws a game, his feeling of calm means that the probabilities for him winning, drawing or losing the next game are 0.24, 0.57 and 0.19 respectively. 

• If he loses a game, his desire for retribution means that the probabilities for him winning, drawing or losing the next game are 0.47, 0 and 0.53 respectively. 

Represent this information as 

(i)     a transition state diagram 

(ii)    a transition matrix

Blythe is playing in a five-day tournament, and he will be playing one game on each of the five days.  His game on the last day of the tournament is against his arch-rival Rob Skodur.  Blythe does not care how he does in the rest of the tournament, as long as he wins against Rob Skodur on the final day. 

Determine the result Blythe should seek in his first game of the tournament, to maximise his chances of winning against Rob Skodur on the final day.  Be sure to justify your answer.

Paul is a pizza fanatic, and he has his dinner every night in one of three pizza restaurants – the Athol House of Pizza (A), Lenny and John’s Pizzeria (L), or Original Pizza II (O).  Depending on where he has eaten on one night, his choice of restaurant the following night is determined according to the probabilities in the following transition state diagram:

Write down the transition matrix  for this system of probabilities.

Determine the probabilities that, in the long term, 

All members of the Pwll y Felin Mathematics Society are fans of either quaternions or of octonions as being their favourite normed division algebra.  At any one time, no quaternions fan will ever also be a fan of octonions, and no octonions fan will ever also be a fan of quaternions.  Each week, however, due to ongoing mathematical discoveries, 3.5% of the quaternion fans switch to become octonion fans, and 1.75% of the octonion fans switch to become quaternion fans. It may be assumed that there are no other changes in the numbers of fans of each of the two normed division algebras. 

Initially there are 45240 members of the society, and they are evenly split between fans of quaternions and fans of octonions. 

Use a matrix method to determine the number of fans that each normed division algebra will have after six weeks.

Determine the number of society members in the long term who will not change which normed division algebra they are a fan of from any given week to the next.

The hero Odysseus has landed on the island of Aiaia. The island is ruled by the sorceress Circe who has turned all 600 of Odysseus’ followers into beasts.  However the goddess Athena has come to help Odysseus, and with her help and his own herbal medicine skills Odysseus hopes to be able to turn his followers back into men and leave the island.  Each month on the island: 

• Athena turns 15% of the beasts back into men, and turns another 55% of the beasts into half-beasts that will be easier for Odysseus to cure with his herbs 

• Odysseus uses his herbs to turn 3% of the beasts and 60% of the half-beasts back to men 

• Circe uses her spells to turn 17% of the men and 20% of the half-beasts back into beasts 

There is no other way for Odysseus’ followers to change between forms, and at any one time each of the followers will be either a ‘man’ or a ‘half-beast’ or a ‘beast’. 

Write down a transition matrix  and an initial state vector representing the transformations of Odysseus’ followers from month to month.

Show that Odysseus can never get all of his followers turned back into men at the same time.

Odysseus decides that he will have to leave the island once no more than 130 of his followers are in beast form.  Although he will have to leave the beasts behind, he will be able to take all the rest of his followers and cure the half-beasts during the journey home. 

Find (i) the whole number of months it will be before Odysseus can leave Aiaia, and (ii) the respective numbers of half-beasts and of men he will have with him on the journey home.

Determine the long-term fate of Odysseus’ followers if Odysseus did not have Athena’s help, but all other factors remained the same.

The marketing department of DeadHead brand shampoo (“It makes you look like you’re stuck in a time warp from 1967!”) is attempting to predict the percentage of potential customers who will purchase its product month by month in the future. 

The lead marketing researcher claims that most of the potential customers for DeadHead shampoo have very short memories, and will not remember what shampoo they have used or how well it has worked for more than a month. 

Explain why the lead researcher’s claim, if it were true, would support the use of a Markov chain to model DeadHead shampoo’s month-on-month market share of potential customers.

Suggest a counter-claim that, if it were true, would suggest that a Markov chain is not a suitable method for modelling DeadHead’s month-on-month market share.

Currently 13% of potential customers buy DeadHead shampoo.  Research suggests that there is a 98% chance that a potential customer who buys DeadHead shampoo one month will buy it again the following month.  On the other hand, there is only a 5% chance that a potential customer who does not buy DeadHead shampoo one month will switch to buying DeadHead shampoo the following month. 

Assuming that a Markov chain may be used to model the situation, find the probability that a randomly selected potential customer 

(i)     will purchase DeadHead shampoo two months from now 

(ii)    will purchase DeadHead shampoo in the long term.

A canoe hire company offers one-day canoe rentals from its three locations in towns on the Millers River – one in Athol (A), one in Orange (O), and one in Millers Falls (M).  Past experience shows that two-fifths of canoes hired at A are returned to A; otherwise they are half as likely to be returned to O as they are to M.   Only 4% of canoes hired at O are returned to O, with seven of the remainder being returned to M for each one that is returned to A.  Of canoes hired at M, 80% are returned to M, with two fifths of the remainder returned to O and the rest returned to A. 

By solving an appropriate system of linear equations, determine a steady state vector for the number of canoes at each of the three locations.

The hire company owns a total of 468 hire canoes.  The owner of the company would like to minimise the number of road trips that need to be made to shuttle canoes between the three locations.

Suggest how the owner might distribute the canoes between locations A, O and M in order to minimise the number of road trips. Be sure to justify your answer.

Athol lies upstream of Orange, which in turn lies upstream of Millers Falls. 

Given this additional information, explain why the answer to part (b) might not be the best way for the business to distribute its hire canoes between the three locations.

In the town of Sodden Chipsbury, all the residents support either one or the other of the town’s two lawn bowling teams – the Barnstorming Boulists (B) or the Jackanapes (J).  Feelings run high, and supporters of rival teams will sometimes even refuse to chat about the weather with each other.  Yet supporters are also fickle, and each year 9% of the supporters of B switch to supporting J and 7% of the supporters of J switch to supporting B.  Any other losses or gains of supporters by the two teams may be ignored. 

Initially there are 2824 supporters of B and 2232 supporters of J. 

Use a matrix method to show that the numbers of supporters of B and J after n years will be    and    respectively.

Hence determine the number of years it will be until the Jackanapes have more supporters than the Barnstorming Boulists.

Write down the number of supporters each team will have in the long term, being sure to justify your answer