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

Authors Sophia Benjamin, Arushi Mantri, Quinn Perian

Publication date 19 October 2021

Distance in graphs (05C12) Flows in graphs (05C21) Random walks on graphs (05C81) Optimal transportation (49Q22)

Abstract: We consider random walks

X, Y

on a finite graph

G

with respective lazinesses

. Let

m u_{k}

and

u_{k}

be the

k

-step transition probability measures of

X

and

Y

. In this paper, we study the Wasserstein distance between

m u_{k}

and

u_{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

.

This page was built for publication: On the Wasserstein Distance Between $k$-Step Probability Measures on Finite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380825)