4.13 Transition Matrices & Markov Chains

In a robotics lab a robot is programmed to move randomly between three different locations, ,  and , according to a fixed set of probabilities.  At each ‘step’ of the robot’s movement about the lab, the robot will either remain where it is or else move to another location according to the probabilities in the following transition state diagram:

Write down the transition matrix for this system of probabilities.

Given that the robot begins at location , find the probabilities that the robot will be at locations ,  or  three steps later.

By considering the matrices  and , determine the long-term probabilities of the robot being found at locations   or .  State whether or not these probabilities depend on the robot’s starting position.

Two social media influencers, Mememe and EegoTiss, are in a constant struggle to steal each other’s followers.  No one who follows Mememe will ever follow EegoTiss at the same time, and no one who follows EegoTiss will ever follow Mememe at the same time.  Each week, however, 15% of the people who follow Mememe switch to following EegoTiss and 20% of the people who follow EegoTiss switch to following Mememe.  It may be assumed that there are no other gains or losses of followers by the two influencers.

Write down a transition matrix  representing the movement of followers between the two influencers in a particular week.

Initially Mememe and EegoTiss each have 7000 followers.

(i)

Write down the initial state vector  for the system.

(ii)

Find the product .

Find the number of followers that Mememe and EegoTiss will each have in the long term.

Find the total number of followers per week in the long term who will change from following one influencer to following the other.

In a videogame three mighty wizards – Eugenes (), Ischyros () and Skleros () – are attempting to create armies of magical followers. They do this by magically changing members of the other armies into members of their own armies.  This happens in the following ways:

• Eugenes’ army is made up of unicorns. During each turn of the game he quietly turns 40% of Ischyros’ myrmidons and 40% of Skleros’ orcs into unicorns.

• Ischyros’ army is made up of myrmidons. During each turn of the game he powerfully turns 20% of Eugenes’ unicorns and 50% of Skleros’ orcs into myrmidons.

• Skleros’ army is made up of orcs. During each turn of the game he wickedly turns 20% of Eugenes’ unicorns and 50% of Ischyros’ myrmidons into orcs.

There is no other way for the numbers of creatures in each of the wizard’s armies to increase or decrease.

Write down a transition matrix  representing the changes in the wizards’ armies from turn to turn.

At the start of a particular game Eugenes has 10 unicorns, Ischyros has 80 myrmidons, and Skleros has 350 orcs.

Find the number of creatures in each wizard’s army after one turn.

Find the number of creatures that each wizard can expect to have in his army if the game continues for a large number of turns.

The marketing department of ShedHead brand shampoo (“It makes you look like you woke up in a garden shed!”) is attempting to predict the percentage of potential customers who will purchase its product month by month in the future.

One marketing researcher believes that the probability of a potential customer buying ShedHead shampoo one month depends on what shampoo they bought the previous month, as well as what shampoo they bought the month before that.

Explain why a Markov chain cannot be used to represent month by month sales for this marketing researcher’s model.

Another marketing researcher believes that what shampoo a potential customer purchases one month depends only on what shampoo the customer purchased the previous month. Her research shows that if a customer buys ShedHead shampoo one month then there is a 93% chance they will buy it again the following month, while if a customer does not buy ShedHead shampoo one month then there is only a 5% chance that they will buy it the following month.

Write down a transition matrix  representing customer behaviour according to this researcher’s model.

Currently 20% of potential customers buy ShedHead shampoo.

Find the probability that a randomly selected potential customer

A delivery company operates a fleet of lorries serving three major cities, ,  and Past experience shows that if a lorry starts a week in city  there is a 70% chance that it will still be in city  at the start of the following week; otherwise there is a 20% chance that it will be in city  and a 10% chance that it will be in city . If a lorry starts a week in city  there is an 80% chance that it will still be in city  at the start of the following week; otherwise it is equally likely to be in city  or city . If a lorry starts a week in city  there is a 90% chance that it will still be in city  at the start of the following week; otherwise it will be in city , with no chance of it being in city .

Write down a transition matrix  representing the movement of the company’s lorries from week to week according to the above information.

By solving the system of linear equations represented by

determine a steady state vector   corresponding to matrix .

The company is about to replace its entire fleet of lorries with a fleet of 280 brand new lorries.

Suggest how the company should initially distribute the new lorries between cities ,  and . Be sure to justify your answer.

In the town of Manh, all the residents belong to either one or the other of the town’s two fitness clubs – Giang’s House of Fitness (G) or Thu’s Wonder Gym (T). Each year 30% of the members of switch to  and 25% of the members of  switch to . Any other losses or gains of members by the two fitness clubs may be ignored.

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

Find the eigenvalues and corresponding eigenvectors of .

Hence write down matrices  and  such that .

Initially there are 2500 members of  and 800 members of .

Using the matrix power formula, show that the numbers of members of  and  after  years will be  and , respectively.

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

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