AN AFFINE WALK ON THE HYPERCUBE

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:41

Article

DIACONIS, P ; GRAHAM, R

关键词: MARKOV CHAIN;    UNIFORM DISTRIBUTION;    CUTOFF PHENOMENA;    FOURIER ANALYSIS;    CODE;   

DOI  :  10.1016/0377-0427(92)90251-R

来源: Elsevier

【 摘 要 】

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.

【 授权许可】

Free