Equitable Partitions and Random Walks

In the random walk on a finitary graph, we define the probability that a walker at vertex $v$ transitions to vertex $u$ as being proportional to the weight of the edge $e_{uv}$. This leads to the definition of the related walk matrix,  
\[
W := MD^{-1},
\]  
where $D$ is the diagonal matrix of vertex degrees. This matrix $W$ is stochastic, meaning that $W\mathbf{1} = \mathbf{1}$, and governs the probability distribution after $t$ steps, given by $W^t u$, where $u$ is the initial probability distribution. 

If the graph is unweighted, undirected, and simple, the associated matrix $W$ is similar to the normalized Laplacian, a matrix that encodes many important spectral properties of the graph and is widely studied \cite{chung1997spectral}.

In graphs with regularities, often arising from symmetries but not limited to them, we can partition the graph into cells such that the probability of transitioning from $v$ to $u$ in $t$ steps depends only on the cells containing $v$ and $u$. When this occurs, we say that the partition is an \emph{equitable partition} of $M$.

The study of equitable partitions has also appeared in other graph-theoretical contexts. Notably, it arises in two distinct polynomial-time algorithms used as necessary conditions for the graph isomorphism problem. The Weisfeiler--Leman algorithm \cite{weisfeiler1968reduction} and fractional isomorphism \cite{scheinerman2013fractional} both involve restrictions of the graph isomorphism problem and determine whether two graphs share a common equitable partition.

We can introduce three types of quotients based on equitable partitions. In our work \cite{eu}, we studied and extended new conditions under which two graphs can have a common quotient of one of these types.

Another important concept is that of a \emph{pseudo-equitable partition}, a generalization of equitable partitions that is particularly useful in the framework of quantum walks. Notably, it serves as a tool for constructing graphs with Perfect State Transfer (PST) \cite{PST_graph_limbo}. In \cite{eu}, we provided new characterizations of pseudo-equitable partitions and established conditions under which two graphs can share a common quotient.

The concept of pseudo-equitable partitions also arises naturally in the context of random walks, where edge weights can be interpreted as an initial probability distribution. All the theorems mentioned above can be applied to the study of random walks.