I expected the direction of the step to be based on importance sampling but here it says it's random.
Apparently the importance sampling kicks in with "transition probability"...but what transition is that referring to?
@ak-47: Yes, the step direction is random. The key is that you're taking a small random step, i.e., maybe just a pixel or two away from where you last were (rather than a random sample over the whole image). The "transition" is exactly the small step you take between your old pixel location and your new one. So you check: was the function larger before or after I took that little step? If it's larger, I prefer to stay here; otherwise, I prefer to go back. However, I don't stay or go with 100% probability; as described on the slide I compute the ratio "after/before," flip an (unbiased) coin, and check if it's less than the ratio to make my decision.