An Affine Walk on the Hypercube

Let Z sup d sub 2 be the group of binary d-tuples. We study the process X sub n = AX sub (n-1) + epsilon sub n with X sub i epsilon Z sup d sub 2, A fixed in GL sub d(Zsub 2), and epsilon sub 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 sub n tends to the uniform distribution on Z sup d sub 2. 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.