Shortest spanning trees and a counterexample for random walks in random environments (Q2497160): Difference between revisions

Random walks in random environment (RWRE) are considered. RWRE is the Markov chain \(X_n\), \(n=1,2,3,\dots,\) with state space \(\mathbb Z^d\), such that \(X_0=z\), and whose transition probabilities \(P^z_\omega\) satisfy \(P^z_\omega(X_{n+1}=x+e\mid X_n=x)=\omega(x,x+e)\) for \(x,e \in \mathbb Z^d\) with \(| e| =1\). Here \(| \cdot| \) denotes the 1-norm \(| \cdot| _1\), so \(x\) and \(x+e\) are always nearest neighbors on the lattice \(\mathbb Z^d\). An environment is called stationary if \(\omega(x,x+e)\) is stationary with respect to transitions of \(\mathbb Z^d\). It is called uniformly elliptic if \(P(w(x,x+e)>\kappa>0)=1\) for all \(x,e \in \mathbb Z^d\) with \(| e| =1\). The polynomially mixing property restricts the mutual dependence of probabilities \(\omega(x,\cdot)\), \(\omega(x+s,\cdot)\) as \(s \to \infty\). The 0-1 law conjecture for RWRE states that if \(\omega(x,\cdot)\), \(x \in \mathbb Z^d\) are i.i.d. and \(\omega\) is uniformly elliptic then \( E[P^0_\omega (\lim_{n \to \infty} X_n \cdot l = + \infty)] \in \{0,1\}\) where \(E\) is the mathematical expectation, \(l\) is a fixed vector in \(R^d\), \(l \neq 0\). A counterexample is constructed to the 0-1 law conjecture in \(d \geq 3\) for a stationary, polynomially mixing and uniformly elliptic RWRE. The technique is based on constructing forests that span \(\mathbb Z^d\), \(d \geq 2\), that are stationary and directed and whose trees are infinite, but for which the subtrees attached to each vertex are as short as possible. For \(d \geq 3\), two independent copies of such forests, pointing in opposite directions, can be pruned so as to become disjoint.