A lower bound for the Chung-Diaconis-Graham random process
| dc.creator | Hildebrand, Martin | |
| dc.date | 2008-01-20 | |
| dc.date | 2008-05-30 | |
| dc.date.accessioned | 2026-07-07T09:41:28Z | |
| dc.date.available | 2026-07-07T09:41:28Z | |
| dc.description | Chung, Diaconis, and Graham considered random processes of the form X_{n+1}=a_n X_n+b_n (mod p) where p is odd, X_0=0, a_n=2 always, and b_n are i.i.d. for n=0,1,2,... . In this paper, we show that if P(b_n=-1)=P{b_n=0)=P(b_n=1)=1/3, then there exists a constant c>1 such that c log_2 p steps are not enough to make X_n get close to uniformly distributed on the integers mod p. | |
| dc.description | 10 pages; this version makes a small change on p. 6 | |
| dc.identifier | https://arxiv.org/abs/0801.3094 | |
| dc.identifier | http://arxiv.org/abs/0801.3094 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/161837 | |
| dc.subject | Probability | |
| dc.subject | 60C05 (Primary); 60B15 (Secondary) | |
| dc.title | A lower bound for the Chung-Diaconis-Graham random process | |
| dc.type | text |