0
$\begingroup$

My questions is about how jump proposals are made when using the Metropolis algorithm.
I understand that the motivation for using the metropolis algorithm is to deduce the most probable value of some parameters by sampling from the un-normalized target distribution. This is done by generating a random walk about the parameter space and evaluating the un-normalized target distribution at those random parameter values.
One of the requirements of the random walk is that parameters with larger density values should be sampled more, generally a normal distribution is used to achieve this.
At each time step the current parameters are evaluated and then a jump is proposed to another paramter value.
The equation i am given for how the next parameter value is selected is:
θ(proposed) = θ(current) + Δθ

How is Δθ derived? From what i have read it is randomly generated from the normal distribution, but if the point of the random walk is to meander around, the proposed jump can be to the right or left (if our parameter space is 1 dimensional) but since the normal distribution only outputs positive values, its co-domain is [0,infinity] how will our θ(proposed) ever move to the left if Δθ is always positive.

TLDR; Is Δθ = normal(randomly generated x), if not, what exact function is giving Δθ, the inverse normal?

$\endgroup$
  • 2
    $\begingroup$ Normal random variates can be negative. $\endgroup$ – Taylor Oct 27 '17 at 17:06
  • $\begingroup$ @Taylor are you implying we use a normal distribution shifted down? $\endgroup$ – Ricardo C Oct 27 '17 at 17:14
  • 3
    $\begingroup$ I am not sure what that means, but I don't think that I do. $\endgroup$ – Taylor Oct 27 '17 at 17:16
  • 1
    $\begingroup$ @RicardoC en.wikipedia.org/wiki/Normal_distribution Maybe you're thinking of the half-Normal? $\endgroup$ – Taylor Oct 27 '17 at 17:37
  • 2
    $\begingroup$ Are you perhaps talking about the domain&range of the probability density function of the normal distribution? $\endgroup$ – Juho Kokkala Oct 27 '17 at 18:42
6
$\begingroup$

The co-domain of the Normal density $N(0,\sigma^2)$ is $(0,1/\sqrt{2\pi\sigma^2})$, it has no impact on the outcome of the Metropolis algorithm, since the proposed value is a Normal realisation, not the value of the density at the current value. The proposed value does not use normal(x)=d-theta but directly x generated from the Normal density $N(0,\sigma^2)$, as in the following example.

When running a Metropolis algorithm based on a Normal N(0,1) random walk proposal, the current value is translated by a Normal N(0,1) realisation. Or repeated. For instance, if the target distribution is the $t(3,2,1)$ distribution, with density proportional to$$(1+(x-2)^2)^{-(3+1)/2}$$over $\mathbb{R}$, given the current value $x_t$, one proposes the new value $$y_t=x_t+z_t\qquad z_t\sim N(0,1)$$and accept this new value with probability$$\dfrac{(1+(y_t-2)^2)^{-2}}{(1+(x_t-2)^2)^{-2}}\wedge 1$$ So, for instance, if $x_t=-3.14$ I draw a normal realisation

> z <- rnrorm(1)
> z
[1] -0.07524364

and consider the new value $y_t$

> y <- x+z
> y
[1] -3.064756

This value $y_t$ is accepted with probability

> dt(y-2,df=3)/dt(x-2,df=3)
> [1] 1.054317

hence accepted since the ratio is larger than one. This means $x_{t+1}=y_t$. At the next round, I draw a normal realisation $z_{t+1}$

> z <- rnrorm(1)
> z
[1] -1.67524364

meaning the new proposed value is $y_{t+1}$

 > y <- x+z
 > y
 [1] -4.74

This value $y_{t+1}$ is accepted with probability

> dt(y-2,df=3)/dt(x-2,df=3)
> [1] 0.3500392

Which means that, if $u_{t+1}$ is such that

> u=runif(1)
> u
[1] 0.9250261

it will be rejected and $x_{t+2}=x_{t+1}$. And so on...

Warning: it is inexact to state that "the motivation for using the metropolis algorithm is to deduce the most probable value of some parameters by sampling from the un-normalized target distribution", as this is an optimisation target. The Metropolis algorithm aims at simulating from a target distribution, when the unnormalised version is the only thing available.

$\endgroup$
  • $\begingroup$ "The proposed value does not use normal(x)=d-theta but directly x" How is x generated, and how is it then related to the normal distribution? What specifically is rnorm(1) doing, is it sampling a random value from co-domain and return the domain value that gave it? $\endgroup$ – Ricardo C Oct 28 '17 at 18:02
  • 1
    $\begingroup$ If you do not understand the meaning of generating a random variate, it is unclear how you can benefit from advices on running a more advanced algorithm like the Metropolis-Hastings algorithm. $\endgroup$ – Xi'an Oct 29 '17 at 18:17
  • $\begingroup$ I was not aware of the difference between a random variable and random variate, i assumed you had made a typo or that the two words were synonymous. I am an undergraduate majoring in computer science and i have taken a course in probability and statistics.I take issue with your assumption that advice on the Metropolis Algorithm is useless to me because of my ignorance of variates. I am currently taking an experimental course on Bayesian data inference and I'm enjoying it very much, i believe i have a relatively good understanding of the algorithm, but i was unclear about this specific. $\endgroup$ – Ricardo C Oct 29 '17 at 20:10
  • 1
    $\begingroup$ @RicardoC Unfortunately you need to go back to the basics, I don't know if you're over thinking it or what but you are definitely confused on more than "just this specific". $\endgroup$ – Glen Nov 14 '17 at 17:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.