We saw how Markov chains work in cases where we have a single random variable. However, in the case of graphical models, we have multiple variables, and each state of the Markov chain is an assignment to multiple variables. So in this case, it is convenient to decompose our transitioning model so that there is change only in a single variable in each transition. We can extend our drunk man example to understand this better. So now, consider that the man can now go ahead and back as well as left and right. To represent this case with our transitioning model, a pair of random variables will represent the X and Y positions for each state of the Markov chain.

In such cases, we define multiple transitioning models, and each such transitioning model is known as a kernel. Now, to construct the Markov chain from these sets of kernels, we can select a kernel with a probability . We could also simply cycle over each of the kernels. However, as we are using different...