RANDOM-PROCESSES OF THE FORM XN+1=ANXN+BN (MOD P)

• 成果类型: Article
• 署名作者: HILDEBRAND, M
• 署名单位: University of Michigan System; University of Michigan; Harvard University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/aop/1176989264
• 发表日期: 1993
• 页码: 710-720
• 关键词: NUMBER

摘要

This paper considers random processes of the form X(n+1) = a(n)X(n) + b(n) (mod p), where X0 = 0 and the sequences a(n) and b(n) are independent with a(n) identically distributed for n = 0, 1, 2.... and b(n) identically distributed for n = 0, 1, 2,... . Chung, Diaconis and Graham studied such processes where a(n) = 2 always; this paper considers more general distributions for a(n) and b(n). The question is how long does it take these processes to get close to the uniform distribution? If an is a distribution on Z+ which does not vary with p and b(n) is a distribution on Z which also does not vary with p, an upper bound on this time is O((log p)2) with appropriate restrictions on p unless a(n) = 1 always, b(n) = 0 always or a(n) and b(n) can each take on only one value. This paper uses a recursive relation involving the discrete Fourier transform to find the bound. Under more restrictive conditions for a(n) and b(n), this paper finds that a generalization of the technique of Chung, Diaconis and Graham shows that O(log p log log p) steps suffice.