Which random walks are cyclic?

Details Which random walks are cyclic? Which random walks are cyclic?

2011-07-26

arxiv.org/abs/1107.5336v2

Mathematics

Probability

Statement of Theorem 2.16 changed, 35 pages, 5 figures, to appear on ALEA

Scientific paper

A cyclic random walk is a random walk whose transition probabilities/rates can be written as a superposition of the empirical measures of a family of finite cycles. This identifies a convex set of models. We discuss the problem of characterization of cyclic random walks in some special cases showing that it is related to several remarkable and classical results. In particular we introduce the notion of balanced measure and show that a translation invariant random walk on $\mathbb Z^d$ is cyclic if and only if its transition probability is balanced. The characterization of the extremal elements is obtained using the Carath\'{e}odory's Theorem of convex analysis. We then show that a random walk on a finite set is cyclic if and only if at every vertex the outgoing flux of the transition graph is equal to the ingoing flux. The extremal elements are characterized by the Birkhoff-Von-Neumann Theorem. Finally we consider the discrete torus and discuss when the cyclic decomposition can be done using only homotopically trivial cycles or elementary cycles associated to edges and two dimensional faces. While in one dimension this is equivalent to require some geometric properties of a discrete vector field associated to the transition rates, in two dimension this is not the case. In particular we give a simple characterization of the polyhedron of the rates admitting a cyclic decomposition with elementary cycles. The proof is based on a discrete Hodge decomposition, elementary homological algebra and the Helly's Theorem of convex analysis. Finally we discuss a natural discretization procedure of smooth divergence free continuous vector fields and an application to random walks in random environments.

Affiliated with

Also associated with

No associations

Rating

Which random walks are cyclic? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Which random walks are cyclic?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Which random walks are cyclic? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-112372