7144CEM Principles of Data Science

7144CEM Assignment Help

Principles of Data Science Assignment help

Task 1. Markov Chains
Example: Flowers. Consider a particular variety of flower which can take one of three colours: red, white and pink. Suppose after each year, 40% of red flowers remain red but 60% of red flowers mutate to pink. For pink flowers, 30% mutate to red, 50% remain as pink, and 20% mutate to white. For white flowers, 90% remain as white and 10% mutate to pink. We can capture these probabilities in a transition matrix 𝑃 where the columns correspond to red, pink and white flowers in the current year and the rows correspond to red, pink and white flowers in the next year. 𝑃=[0.40.300.60.50.100.20.9]

If a certain garden initially has 80 of this variety of red flowers and 20 of this variety of white flowers then after one year: 𝑃[80020]=[325018]

so we would expect to see 32 red, 50 pink and 18 white flowers in the garden. If we look at the garden after 5 years: 𝑃𝑃𝑃𝑃𝑃[80020]=𝑃5[80020]=[20.8837.0842.04]

so we would expect to see approximately 21 red, 37 pink and 42 white flowers in the garden. This is an example of a system called a “Markov chain”. The next state of the system depends only on its present state and does not depend on the earlier history of the system.

Assessment: Mice in a maze. Consider the closed maze shown below containing seven rooms (labelled 0 to 6) with doorways connecting the rooms. A number of mice are placed in the maze and the mice then move randomly from room to room. Each time step, a mouse either stays in the same room (with probability 0.6) or leaves the room it is in by choosing at random (equally likely) one of the doors out of the room.
(1) Construct a 7×7 transition matrix 𝑃 (as a numpy array) to model the mice moving around the maze as a Markov chain.
(2) Suppose that 50 mice are placed in Room 0 and 90 mice are placed in Room 1. All other rooms are initially empty. Use numpy to calculate how many mice we would expect to see in each room at the end of each time step for each of the next 30 time steps. Use Python to plot your results on a line graph showing one line for each room, together with a legend. Briefly comment on what you observe. You might find numpy.linalg.matrix_power() helpful.
(3) Use numpy to find the eigenvectors of the transition matrix 𝑃 from part (1), and explain how one of these eigenvectors is related to the number of mice we would expect to see in each room in the “long-run steady state”. Also, for each room 𝑗, find the expected number of time steps for a particular mouse initially located in room 𝑗 to first return to room 𝑗. Hint: if 𝑝𝑗 is the probability that the particular mouse is in room 𝑗 in the “long-run steady state” then the expected first return time is given by 1/𝑝𝑗.
(4) Suppose the mouse population is in the “long run steady state” from part (3) when a large piece of poisoned cheese is placed in Room 6 so that any mouse that enters that room instantly dies.

(a) Modify the transition matrix 𝑃 from part (1) and estimate the number of time steps until 80% of the mice have died.

(b) The expected number of time steps needed for a mouse starting from room 𝑖 to reach room 𝑘 for the first time can be calculated using matrix operations and is denoted 𝜇𝑖𝑘. For a particular destination room 𝑘, let 𝑁 be the transition matrix 𝑃 from part (4)(a) but with row 𝑘 and column 𝑘 both deleted, and let 𝐼 be the 6×6 identity matrix. The sum of each column of the matrix (𝐼−𝑁)−1 gives the values 𝜇𝑖𝑘. Use this method to find the expected number of time steps needed for a mouse to die, for each of the possible rooms in the maze that the mouse could start from. Briefly comment on what you observe.