Markov Chain Monte Carlo: Metropolis-Hastings Algorithm for Distribution Simulation Coursework, Singapore

In this section, you are required to apply the Markov Chain Monte Carlo (MCMC) algorithm, specifically the Metropolis-Hastings algorithm. The goal is to generate random numbers for the probability distribution with the given probability density function:

f(x)=12exp⁡(−∣x∣),f(x) = \frac{1}{2} \exp(-|x|),f(x)=21​exp(−∣x∣),

where xxx takes values on the real line, and ∣x∣|x|∣x∣ represents the absolute value of xxx. More specifically, you are tasked with generating values x0,x1,…,xNx_0, x_1, \dots, x_Nx0​,x1​,…,xN​ and storing them using the following version of the Metropolis-Hastings algorithm, commonly known as the random walk Metropolis. The algorithm consists of the following steps:

Random Walk Metropolis Algorithm

1. Initialization: Set an initial value x0x_0x0​, a positive integer NNN, and a positive real number sss.
2. Iterative Procedure: For i=1,…,Ni = 1, \dots, Ni=1,…,N, repeat the following steps:
   • Generate a random number x∗x^*x∗ from the normal distribution with mean xi−1x_{i-1}xi−1​ and standard deviation sss.
   • Compute the ratio r(x∗,xi−1)=f(x∗)f(xi−1)r(x^*, x_{i-1}) = \frac{f(x^*)}{f(x_{i-1})}r(x∗,xi−1​)=f(xi−1​)f(x∗)​.
   • Draw a random number uuu from a uniform distribution between 0 and 1.
   • If u<r(x∗,xi−1)u < r(x^*, x_{i-1})u<r(x∗,xi−1​), set xi=x∗x_i = x^*xi​=x∗; otherwise, set xi=xi−1x_i = x_{i-1}xi​=xi−1​.

(a) Apply the Random Walk Metropolis Algorithm

Use N=10000N = 10000N=10000 and s=1s = 1s=1 to implement the random walk Metropolis algorithm. Use the generated samples (x1,…,xN)(x_1, \dots, x_N)(x1​,…,xN​) to create a histogram and a kernel density plot in the same figure. These will provide estimates of f(x)f(x)f(x). Additionally, overlay the graph of f(x)f(x)f(x) on the plot to visually assess the accuracy of these estimates. Report the sample mean and standard deviation of the generated samples, which are also known as the Monte Carlo estimates of the mean and standard deviation, respectively.

Practical Tip: To avoid numerical issues, it is recommended to use the equivalent criterion:

log⁡(u)<log⁡(r(x∗,xi−1))=log⁡(f(x∗))−log⁡(f(xi−1)),\log(u) < \log(r(x^*, x_{i-1})) = \log(f(x^*)) – \log(f(x_{i-1})),log(u)<log(r(x∗,xi−1​))=log(f(x∗))−log(f(xi−1​)),

instead of directly using u<r(x∗,xi−1)u < r(x^*, x_{i-1})u<r(x∗,xi−1​).

Note: This part assumes that the algorithm has already converged.

Convergence Diagnostics – RbR_bRb​ Value

One commonly used convergence diagnostic is the RbR_bRb​ value. To calculate the RbR_bRb​ value, follow the procedure below:

• Generate multiple chains of values x0,x1,…,xNx_0, x_1, \dots, x_Nx0​,x1​,…,xN​, potentially starting from different initial values x0x_0x0​. Denote each chain as (x0(j),x1(j),…,xN(j))(x^{(j)}_0, x^{(j)}_1, \dots, x^{(j)}_N)(x0(j)​,x1(j)​,…,xN(j)​) for j=1,2,…,Jj = 1, 2, \dots, Jj=1,2,…,J.
• For each chain jjj, calculate the sample mean MjM_jMj​:

Mj=1N∑i=1Nxi(j),M_j = \frac{1}{N} \sum_{i=1}^N x^{(j)}_i,Mj​=N1​i=1∑N​xi(j)​,

and the within-chain variance VjV_jVj​:

Vj=1N∑i=1N(xi(j)−Mj)2.V_j = \frac{1}{N} \sum_{i=1}^N (x^{(j)}_i – M_j)^2.Vj​=N1​i=1∑N​(xi(j)​−Mj​)2.

• Compute the overall within-chain variance WWW:

W=1J∑j=1JVj.W = \frac{1}{J} \sum_{j=1}^J V_j.W=J1​j=1∑J​Vj​.

• Calculate the overall sample mean MMM:

M=1J∑j=1JMj,M = \frac{1}{J} \sum_{j=1}^J M_j,M=J1​j=1∑J​Mj​,

and the between-chain variance BBB:

B=1J∑j=1J(Mj−M)2.B = \frac{1}{J} \sum_{j=1}^J (M_j – M)^2.B=J1​j=1∑J​(Mj​−M)2.

• Finally, compute the RbR_bRb​ value:

Rb=B+WW.R_b = \sqrt{\frac{B + W}{W}}.Rb​=WB+W​​.

Generally, values of RbR_bRb​ close to 1 indicate convergence, and a value of RbR_bRb​ below 1.05 is typically considered acceptable.

(b) Calculate RbR_bRb​ for Random Walk Metropolis

Calculate the RbR_bRb​ value for the random walk Metropolis algorithm with N=2000N = 2000N=2000, s=0.001s = 0.001s=0.001, and J=4J = 4J=4. With NNN and JJJ fixed, create a plot showing how the RbR_bRb​ values change over a grid of sss values in the range from 0.001 to 1.