On random graph homomorphisms into Z

Given a bipartite connected finite graph G =(V, E) and a vertex upsilon(0) epsilon V, we consider a uniform probability measure on the set of graph ho momorphisms f: V --> Z satisfying f(upsilon(0)) = 0, This measure can be vi ewed as a G-indexed random walk on Z, generalizing both the usual time-inde xed random walk and tree-indexed random walk, Several general inequalities for the G-indexed random walk are derived, including an upper bound on fluc tuations implying that the distance d(f(u), f(upsilon)) between f(u) and f( upsilon) is stochastically dominated by the distance to O of a simple rando m walk on Z having run for d(u,upsilon) steps. Various special cases are st udied, For instance, when G is an n-level regular tree with all vertices on the last level wired to an additional single vertex. we show that the expe cted range of the walk is O(log n). This result can also be rephrased as a statement about conditional branching random walk. To prove it, a power-typ e Pascal triangle is introduced and exploited. (C) 2000 Academic Press.