MATS255 Computer Assignment

In this assignment you are required to simulate Markov chains using uniformly distributed pseudorandom numbers. Based on your observations, write a short report where you present your solutions to the problems below. Note that:

The report should be returned as a single pdf file named MATS255_ComputerAssignment_Surename1_Surename2.pdf and must contain:


Weather in Jyväskylä

Let us model the weather condition in Jyväskylä as a Markov chain with three states: sunny (1), cloudy (2), and rainy (3). Based on the morning's observations, it has been estimated that the current day will be

Denote by Xt the weather condition in Jyväskylä on day t, where day 0 refers to the current day.

Problem 1. Generate 100 samples of the current day's weather condition using the method described in Levin, Peres, Wilmer (2008, Sec B.3). You may program the method by yourself, or use the R program InitiationFunction.R Draw a histogram of your samples and compare your histogram with the precise distribution of the current day's weather.

Assume that, independently of the past days,

Problem 2. Write down the state space and the transition matrix of the Markov chain (Xt).

Problem 3. Simulate a 10-day sample path of the Markov chain (Xt) using the initiation function of Problem 1 and a random mapping presentation in Levin, Peres, Wilmer (2008, Prop. 1.5). Plot the sample path as a function of time. You may program the functions by yourself, or use the R programs InitiationFunction.R and UpdateFunction.R

Let us denote by Ci,t the number of time indices s < t such that Xs = i, and by Yi,t = Ci,t/t the occupancy ratio of state i during the time interval [0,t-1].

Problem 4. Simulate a 1000-day sample path of the Markov chain (Xt), and compute the occupancy ratios of the states for this sample path. Plot the occupancy ratios as functions of time. You may program the functions by yourself, or use the R program OccupancyRatios.R. What happens to the occupancy ratios when t tends large?

Problem 5. Compute the probability distribution mu1000 on day 1000 using matrix multiplication. Compare the result with the results of Problem 4.

Web page ranking

The World Wide Web can be modeled as a directed graph with k vertices, where vertices represent web pages and edges hyperlinks. A simplified version of Google's PageRank algorithm ranks the Web pages based on occupancy ratios of the following Markov chain:

Consider a directed graph G with four vertices and three edges, where vertex 1 has no outgoing edges, and all other vertices link to vertex 1.

Problem 6. Write down the transition matrix of the Markov chain corresponding to the graph G.

Problem 7. Simulate a 1000-step sample path of the Markov chain corresponding to the graph G, and compute the occupancy ratios of the states for this sample path. Plot the occupancy ratios as functions of time. What happens to the occupancy ratios when t tends to infinity?

Consider a directed graph G' constructed by adding a new vertex to G, making a link from the new vertex to vertex 1, and a link from vertex 1 to the new vertex.

Problem 8. Write down the transition matrix of the Markov chain corresponding to the graph G'.

Problem 9. Simulate a 1000-step sample path of the Markov chain corresponding to the graph G', and compute the occupancy ratios of the states for this sample path. Plot the occupancy ratios as functions of time. What happens to the occupancy ratios when t tends large?

Problem 10. Compare the long-run occupancy ratios of the vertices in graphs G and G'. How does adding the new vertex affect the occupancy ratios of the vertices in G?


2012-11-05 Lasse Leskelä