# Confused about how Random Walk Metropolis algorithm work?

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.

• What "random walk" algorithm exactly? You need to give us more details, so that the question is self-explainable. – Tim Dec 17 '19 at 8:21
• 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. – Changhee Kang Dec 17 '19 at 8:23

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

• 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? – Changhee Kang Dec 17 '19 at 9:41
• 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. – chzhrr Dec 17 '19 at 9:57
• 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. – Changhee Kang Dec 17 '19 at 10:34