Probability Models Fall 2020 Semester
Homework 6:
Instructions
• Write your full name, “Homework 6”, and the date at the top of the first page.
• Show all work, including each step of your solution, to earn maximal partial credit.
• Each question has multiple parts. Write legibly and neatly. Box your final answers.
• Use Genius Scan or a similar application to convert your solutions to .pdf format.
• Submit a single .pdf file to Gradescope under the assignment “Homework 6”.
• If you have any questions, email me or come to office hours (WF 11:00am-12:00pm)
• You are encouraged to work together (on Piazza) but must write up your own solutions.
Assignment (4 Problems: 20 + 30 + 20 + 30 = 100 points total.)
Q Problem 1 Consider the simple graph Γ = (V, E) with 5 vertices and 4 edges below
and let {Xn}∞n=0 be the simple random walk on Γ as defined in HW5.
• 1.1 [10 points] Find an equilibrium distribution of this Markov chain.
• 1.2 [10 points] Is this Markov chain reversible?
Q Problem 2 In L14, we considered the experiment of selecting 1 of 4 indistinguishable molecules in two urns A and B uniformly at random, taking the chosen molecule out of its urn, and placing it in the opposite urn. We saw that the resulting stochastic process is a Markov chain in X = {0, 1, 2, 3, 4} with 1-step transition matrix
0 1 0 0 0
/4 0 3/4 0 0
P = 0 1/2 0 1/2 0 .
0 0 3/4 0 1/4
0 0 0 1 0
• 2.1 [15 points] Is this Markov chain reversible?
• 2.2 [15 points] If initially all 4 molecules are in urn A, what is the probability that there are infinitely-many instances in which all 4 molecules are back in urn A?
Q Problem 3 Consider the simple graph Γ = (V, E) with 2 vertices and 1 edge above and consider the probability distribution µ on V = {a, b} given by
µ→ = [µa µb] = [0.3 0.7].
• 3.1 [10 points] For this µ, find the 1-step transition matrix P of the Hastings-Metropolis Markov chain Xn ∞n=0 on X = V = a, b assuming that the proposal chain Q is the simple random walk on Γ. Hint: to check your work, see if µ above satisfies the full balance equations µ→ = µ→ P or detailed balance equations µiPij = µjPji for your P.
• 3.2 [10 points] Assume X0 = a. What is the time n = 5 marginal distribution of the Hastings-Metropolis chain? Specifically, what are P (X5 = a) and P (X5 = b)?
Q Problem 4 Consider the Markov chain on X = {a, b, c} with 1-step transition matrix
Q = 0.1 0 0.9
0.9 0.1 0
• 4.1 [10 points] Is this Markov chain reversible?
• 4.2 [10 points] Consider the uniform distribution µ on {a, b, c} given by
µ→ = [µa µb µc] = [ 1 1 1 ].
Construct the 1-step transition matrix P for the Hastings-Metropolis Markov chain
{Xn}∞n=0 on X = {a, b, c} assuming that the proposal chain is Q above.
• 4.3 [10 points] Is your Hastings-Metropolis chain in Problem 4.2 reversible?
Q Bonus [X points] Is the simple random walk on the graph below reversible?
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
