Transportation Distance between Probability Measures on the Infinite Regular Tree

.In the infinite regular tree \(Tq+1\) with \(q ∈ Z≥ 2\), we consider families \(\{μ_u^n\}\), indexed by vertices \(u\) and nonnegative integers ("discrete time steps") \(n\), of probability measures such that \(μ_u^n(v) = μ_{u}^n(v)\) if the distances \({d}(u,v)\) and \({d}(u,v)\) are equal. Let \(d\) be a positive integer, and let \(X\) and \(Y\) be two vertices in the tree which are at distance \(d\) apart. We compute a formula for the transportation distance \(W_1\! ( μ_X^n, μ_Y^n )\) in terms of generating functions. In the special case where \(μ_u^n = m_u^n\) are measures from simple random walks after \(n\) time steps, we establish the linear asymptotic formula \(W_1\! ( m_X^n, m_Y^n ) = An + B+o(1)\), as \(n → ∞\), and give the formulas for the coefficients \(A\) and \(B\) in closed forms. We also obtain linear asymptotic formulas when \(μ_u^n\) is the uniform distribution on the sphere or on the ball of radius \(n\) as \(n → ∞\). We show that these six coefficients (two from the simple random walk, two from the uniform distribution on the sphere, and two from the uniform distribution on the ball) are related by inequalities.Keywordstransportation distanceWasserstein distanceoptimal transportKantorovich problemasymptotic formulascoarse Ricci curvatureOllivier–Ricci curvaturerandom walks on graphsradially symmetric probability distributionsgenerating functionsgraph statisticsinfinite regular treeMSC codes05A1605A1505C1205C2149Q22