AN AFFINE WALK ON THE HYPERCUBE

Let Z2d be the group of binary d-tuples. We study the process X(n) = AX(n-1) + epsilon(n) with X(i) is-an-element-of Z2d, A fixed in GL(d)(Z2) and epsilon(n) a random vector of disturbance terms. This models algorithms in the presence of a "bad bit". For a class of situations we show that the distribution of X(n) tends to the uniform distribution on Z2d. We determine sharp rates of convergence and demonstrate the existence of cutoff phenomena. The analysis depends on understanding codes made from the binomial coefficients (mod 2). It leads to a novel type of oscillating behavior for the location of the cutoff and for the error terms.