1
$\begingroup$

The following picture explains how the Random Walk Metropolis algorithm walk throughout time from $ t=1 $ to $ t=99 $.

At times $ t=1 $ and $ t=2 $, things are fine to understand, somehow, I am lost after time $ t=2 $. I don't think I understand how those histograms in the picture change over time after time $ t+1 $.

I thought that only two positions that are only one step further from the current position change but in the picture, the histogram of other positions changes, too. The calculation for the change of the histogram at time $ t=2 $ from time $ t=1 $ is explained. But I don't understand why histograms change the way as shown at time $ t=3 $. I'd be appreciated if you can show the way how the calculations are done up to $ t=3 $ or $ t=4 $.

The picture is from the book, "Doing Bayesian Data Analysis by John K, Kruschke" on page 150.

enter image description here

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What "random walk" algorithm exactly? You need to give us more details, so that the question is self-explainable. $\endgroup$
    – Tim
    Commented Dec 17, 2019 at 8:21
  • $\begingroup$ I have just changed the title of my question. It was not just the Random Walk algorithm, it is Random Walk Metropolis algorithm as printed in the book. I just cannot interpret the steps throughout different times. $\endgroup$
    – xabzakabecd
    Commented Dec 17, 2019 at 8:23

1 Answer 1

Reset to default
1
$\begingroup$

I just read the same book.:)

The main idea of this random walk is: At each timestep, 50% percent to right since the new value is larger and 50% times the fraction of values to left.

from t=1 to t=2:

flip a coin, $P(5)_2=0.5,P(3)_2=0.5*\frac{3}{4},P(4)_2=0.5*\frac{1}{4}$

Note that the denominator is current state value and the numerator is it's left's value.

from t=2 to t=3:

We have the population $P(5)_2=0.5,P(3)_2=\frac{3}{8},P(4)_2=\frac{1}{8}$

then move:

since we can only move to node 2 from node 3:

$P(2)_3=P(3)_2*0.5*\frac{2}{3}=\frac{3}{8}*0.5*\frac{2}{3}=\frac{1}{8}$

we can stay node 3 or move to node 3 from node 4:

$P(3)_3=P(3)_2*\frac{1}{3}*0.5+P(4)_2*\frac{3}{4}*0.5=\frac{3}{8}\times\frac{1}{3}*0.5+\frac{1}{8}\times\frac{3}{4}*0.5=\frac{7}{64}$

and so forth

Improve this answer
$\endgroup$
3
  • $\begingroup$ To move to node 2 from node 3 at time $ t=2 $, why is $ P(3)_2 $ is multiplied to calculate $ P(2)_3 $? and can I think of flipping a coin as generating(proposing) a number located within a range, for example, as one step to the left or to the right shown in the text book? $\endgroup$
    – xabzakabecd
    Commented Dec 17, 2019 at 9:41
  • 1
    $\begingroup$ Use Law of total probability here. $P(x_{3}=2) = P(x_{3}=2|x_{2}=3)*P(x_{2}=3)$. I'm not sure what you are asking about, what do you mean by range? It just a Bernoulli distribution. $\endgroup$
    – chzhrr
    Commented Dec 17, 2019 at 9:57
  • $\begingroup$ I was thinking about the normal distribution. I didn't recognize I was working on Bernoulli Distribution while I was typing my question. Thank you for the straight answer. I understand it now. $\endgroup$
    – xabzakabecd
    Commented Dec 17, 2019 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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