Optimal control for diffusions on graphs

DOI10.1137/17M1125923MaRDI QIDQ4562316zbMATH OpenOpenAlexWikidataFDO

Authors Laura Florescu, Yuval Peres, Miklós Z. Rácz

Publication date 19 December 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.09892

zbMATH Keywords

combinatorial optimizationcontrolled diffusionoptimal controloptimal transportpotential theory

Mathematics Subject Classification ID

Trees (05C05) Random walks on graphs (05C81) Probabilistic potential theory (60J45) Combinatorial optimization (90C27)

Abstract: Starting from a unit mass on a vertex of a graph, we investigate the minimum number of "emph{controlled diffusion}" steps needed to transport a constant mass $p$ outside of the ball of radius $n$. In a step of a controlled diffusion process we may select any vertex with positive mass and topple its mass equally to its neighbors. Our initial motivation comes from the maximum overhang question in one dimension, but the more general case arises from optimal mass transport problems. On $mathbb{Z}^d$ we show that $Theta(n^{d+2})$ steps are necessary and sufficient to transport the mass. We also give sharp bounds on the comb graph and $d$-ary trees. Furthermore, we consider graphs where simple random walk has positive speed and entropy and which satisfy Shannon's theorem, and show that the minimum number of controlled diffusion steps is $exp(ncdoth/ell(1+o(1)))$, where $h$ is the Avez asymptotic entropy and $ell$ is the speed of random walk. As examples, we give precise results on Galton-Watson trees and the product of trees $mathbb{T}_{d}imesmathbb{T}_k$.

Recommendations

• Optimal mass transport on metric graphs
• Lazy random walks and optimal transport on graphs
• Optimal control of diffusions
• A problem of control of Markovian processes on a graph
• Optimal control for absolutely continuous stochastic processes and the mass transportation problem

Cites work

• Asymptotic entropy and Green speed for random walks on countable groups
• Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measure
• Heat kernel asymptotics on the lamplighter group
• scientific article; zbMATH DE number 3875656 (Why is no real title available?)
• scientific article; zbMATH DE number 2233864 (Why is no real title available?)
• Intersections of random walks.
• Maximum overhang
• Potential kernel for two-dimensional random walk
• Probability on trees and networks
• Random walks on discrete groups: Boundary and entropy
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• Tree-indexed random walks on groups and first passage percolation

Cited in

(2)

• A problem of control of Markovian processes on a graph
• Optimal control of a fractional diffusion Sturm-Liouville problem on a star graph

This page was built for publication: Optimal control for diffusions on graphs

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