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 by email in pdf format by Wed 16 Nov 2011 10:00.
• The assignment is graded at the scale 0–3.
• The maximum length of the report is 4 pages, including figures but excluding code.
• The text must be written in full sentences. A plain list of answers is not sufficient.
• The assignment can be done and returned alone or in pairs.
• The report can be written in Finnish or English.
• You are free to use any numerical software or programming language.

• Student name and id.
• Course name and id.
• Short description of the assignment.
• Answers to given problems and a description of the solution methods.
• A separate attachment which contains your code.

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

• sunny with probability 0.1, cloudy with probability 0.8, and rainy with probability 0.1.

Problem 1. Generate 100 samples of the current day's weather condition using the initiation function described in Häggström (2002) p.19. You may program the initiation function 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,

• after a sunny day, the next day will be sunny with probability 0.5, cloudy with probability 0.4, and rainy with probability 0.1;
• after a cloudy day, the next day will be sunny with probability 0.2, cloudy with probability 0.6, and rainy with probability 0.2;
• after a rainy day, the next day will be sunny with probability 0.1, cloudy with probability 0.6, and rainy with probability 0.3.

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

Problem 3. Simulate a 10-day sample path of the Markov chain (X_n) using the initiation and update functions described in Häggström (2002) p.19. 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 C_i,n the number of time indices m < n such that X_m = i, and by Y_i,n = C_i,n/n the occupancy ratio of state i during the time interval [0,n-1].

Problem 4. Simulate a 1000-day sample path of the Markov chain (X_n), 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 n tends large?

Problem 5. Compute the probability distribution mu₁₀₀₀ 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:

• The chain starts at a uniformly randomly chosen vertex.
• At any time instant, the next vertex is obtained by following an edge which is chosen uniformly randomly among all outgoing edges from the current vertex.
• If the current vertex has no outgoing edges, the next vertex is chosen uniformly randomly among all vertices.

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 n tends large?

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 n 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?