Scribd
Upload
116 views

Homework 3 Markov Chain Random Walk

This document contains 7 questions about Markov chains and random walks. Question 1 involves defining the transition matrix for a Markov chain modeling balls moving between two urns and computing its limiting distribution. Question 2 defines a Markov chain for a student progressing through medical school. Question 3 asks about the steady-state probability a professor gets wet given the daily probability of rain and umbrella availability. Question 4 defines a Markov chain for a mathematician traveling between coffee shops. Questions 5-7 involve additional Markov chain and random walk simulations and analyses.

Uploaded by

faraz hassan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
116 views

Homework 3 Markov Chain Random Walk

This document contains 7 questions about Markov chains and random walks. Question 1 involves defining the transition matrix for a Markov chain modeling balls moving between two urns and computing its limiting distribution. Question 2 defines a Markov chain for a student progressing through medical school. Question 3 asks about the steady-state probability a professor gets wet given the daily probability of rain and umbrella availability. Question 4 defines a Markov chain for a mathematician traveling between coffee shops. Questions 5-7 involve additional Markov chain and random walk simulations and analyses.

Uploaded by

faraz hassan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

F11MT Modelling and Tools

Homework 3: Markov Chains and Random Walks


1. The following is a special case of a model, called the Ehrenfest model, that has been used to
explain diffusion of gases. We have two urns that, between them, contain four balls. At each
step, one of the four balls is chosen at random and moved from the urn that it is in into the
other urn. We choose as possible states of the process the number of balls in the first urn.

(a) Define the transition matrix P of a Markov chain modelling this process.
(b) Show that this Markov chain is ergodic but not regular.
(c) Explain why the limit
I + P + P2 + ··· + Pn
lim
n→∞ n+1
exists and compute it.
3 marks

2. Assume that for a student going to a three-year medical school, in each year we have a probability
q = 0.2 of flunking out, a probability r = 0.1 of having to repeat the year, and a probability
p = 0.7 of moving on to the next year (in the third year, moving on means graduating). This
process can be modelled by a Markov chain with states 1, 2, 3, G and F, where F stands for
flunking out, G for graduating, and 1, 2, and 3 represent the first, second and third years of
study, respectively.

(a) Determine the transition matrix of this Markov chain.


(b) Show that this Markov chain is an absorbing Markov chain.
(c) Write the transition matrix in canonical form.
(d) Define the fundamental matrix M for this Markov chain.
2 marks

3. An absent-minded professor has two umbrellas, used when commuting from home to work and
back. If it rains and an umbrella is available, the professor takes it. If an umbrella is not
available, the professor gets wet. If it does not rain the professor does not take the umbrella. It
rains on a given commute with probability p, independently for all days. What is the steady-
state probability that the professor will get wet on a given day? Will the process converge to
the steady-state? Explain / justify your answer.
2 marks

4. A mathematician travels between four coffee shops located as shown in Figure 1 below. Assume
she chooses among the paths departing from a coffee shop by treating each path as equally likely.
We can model the mathematician’s journey as a Markov chain. Take as a suitable state space
S = {1, 2, 3, 4} corresponding to the coffee shops as indicated in Figure 1.

(a) Write the transition matrix P for this Markov chain. Is this Markov chain regular, ergodic
or absorbing. Explain / justify your answer.
(b) Considering xTn = xTn−1 P = x0 P n , does the limit of xn , as n → ∞, exist for any x0 ? Does
the limit of P n , as n → ∞, exist? Explain / justify your answer. If yes determine the
matrix obtained in the limit.
3 marks

1
3

1 2

Figure 1: A mathematician travels between four coffee shops located as shown.

5. Consider the Markov chain with transition matrix


 
2/3 1/3 0 0
 1/10 9/10 0 0 
P =  1/10
.
0 9/10 0 
1/10 0 0 9/10

Find a stationary distribution for the stochastic matrix P . Is this Markov chain regular? Explain
/ justify your answer.
1 marks

6. A spider in a bath tub goes up with a probability of p = 0.51 and down with a probability 1 − p.
Denote by n ∈ N the position of the spider (height along the tub). Consider that the spider
starts at position n = n0 and escapes if n = s, for some n0 , s ∈ N, and drowns if n = 0.

ˆ Write down the relationship for the probability the spider escapes.
ˆ If n0 = 6 and s = 12 what is the probability the spider escapes?
ˆ Use Python to simulate the spider’s fate.

4 marks

7. (a) Write a Python code to simulate M steps of a random walk on the real line starting from
zero with probability of moving left or right equal to 1/2 and with ∆x = 0.1 and ∆t = 0.1.

ˆ Simulate 1000 different random walks and plot them in time.


ˆ For 1000 samples plot a histogram of the position of the particles after 100 steps (i.e. at
t = 10).

(b) Consider different probabilities q = 1/3 for moving to the left and 1 − q = 2/3 for moving to
the right.

ˆ Simulate 1000 different random walks and plot them in time.


ˆ For 1000 samples plot a histogram of the position of the particles after 100 steps (i.e. at
t = 10).
ˆ Derive the corresponding continuous diffusion-convection equation, following the same ideas
as in Section 3.4.2 of the lecture notes.

(c) Explain the difference between the two situations considered here.
5 marks

You might also like