I am studying Markov chain as a beginner. When I read some documents, I often find a sentence as follows.
"For an undirected graph, many finite irreducible Markov chains can be generated."
But, it is difficult for me to imagine some examples for the sentence. Could you please give a simple example that explains the sentence above?
Thanks!
Take a connected graph and think of a simple random walk on it. This means that at any given vertex, you go to a neighbouring one with equal probability. This is also called the drunkard's walk, since it is like a drunk person stumbling randomly at each time. Thus you can create the probability transition matrix and think of it as Markov chain since at any given moment, how you move is not affected by past movements. Since the graph is connected, you can reach any given point so it is also irreducible.