On random graph homomorphisms into $\mathbb Z$

The study of Lipschitz functions on graphs and metric spaces is rather advanced. Uniform measure on graph homomorphisms into $\mathbb Z$ provides a model for looking at typical Lipschitz functions. Given a bipartite connected finite graph $G=(V,E)$ and a vertex $v_0\in V$, we consider uniform probability measure on the set of graph homomorphisms $f: \, V \rightarrow \mathbb Z$ satisfying $f(v_0)=0$. This measure can be viewed as a $G$-indexed random walk on ${\bf Z}$, generalizing both the usual time-indexed random walk and tree-indexed random walk. We will present several general inequalities for $G$-indexed random walks, including an upper bound on fluctuations implying that the distance $d(f(u),f(v))$ between $f(u)$ and $f(v)$, is stochastically dominated by the distance to $0$ of a simple random walk on $\mathbb Z$ having run for $d(u,v)$ steps. We will also discuss various special cases, some conjectures and algorithmic aspects of these models.