On the Wasserstein Distance Between $k$-Step Probability Measures on Finite Graphs

Abstract

We consider random walks $X,Y$ on a finite graph $G$ with respective lazinesses $\alpha ,\beta \in [0,1]$. Let ${\mu }_k$ and ${\nu }_k$ be the $k$-step transition probability measures of $X$ and $Y$. In this paper, we study the Wasserstein distance between ${\mu }_k$ and ${\nu }_k$ for general $k$. We consider the sequence formed by the Wasserstein distance at odd values of $k$ and the sequence formed by the Wasserstein distance at even values of $k$. We first establish that these sequences always converge, and then we characterize the possible values for the sequences to converge to. We further show that each of these sequences is either eventually constant or converges at an exponential rate. By analyzing the cases of different convergence values separately, we are able to partially characterize when the Wasserstein distance is constant for sufficiently large $k$.

31 pages, 0 figures