The electric network approach to the study of Markov Chains

Abstract

Markov chains are used to describe random processes in discrete time, which have the property of being memoryless. This report covers Markov chains on a finite space that are homogeneous in time and mainly follows the structure of ''Markov Chains and Mixing Times''. Markov chains exhibit a strong connection with electric networks. We exploit such a connection and apply the laws of physics to answer several probabilistic questions about random walks, which are certain types of Markov chains. This connection is then called the electric network approach and is built on translating the random walk into an electric network by relating the transition probability to the so-called conductance. The electric network approach provides problem simplification tools, such as the Series/Parallel Law, and powerful inequalities, such as the Nash-Williams inequality. These tools are based on physics and are often more intuitive than their probabilistic counterpart. We simulate a two-dimensional random walk that starts at the center of a square and ''escapes'' if it reaches the perimeter of the square before returning to the center. We then compare this escape probability to an upper bound, which results from using the Nash-Williams inequality. The sharpness of the upper bound depends on the choice of edge-cutsets. We find that choosing edge-cutsets with a minimal amount of edges gives a sharper upper bound, than choosing edge-cutsets that contain all the edges of the square. The relation between the upper bound and the escape probability seems to be independent of the size of the square. Furthermore, we provide proofs that are not explicit in ''Markov Chains and Mixing Times'' and ''Reversible Markov Chains and Random Walks on Graphs'' and add to the contents of ''Markov Chains and Mixing Times'' by studying random walks from a graph theory perspective.