RANDOM WALKS ON THE CIRCLE AND DIOPHANTINEAPPROXIMATION
Joint results with Bence Borda
Sums of independent random variables 1711Weak law of large numbers (J. Bernoulli 1711)
Central limit theorem (de Moivre 1733)
Strong law of large numbers (Borel 1909)
Law of the iterated logarithm (Khinchin 1924)

Sums of i.i.d. random variables mod 1
Sn = X1 + . . . + Xn,

Zn = {Sn}Motivation:
Benford’s law: leading digit of numbers in large databases is NOT uniformly
distributed: P ({1}) = log10 2 > 0.3”Typical” behavior of discrepancy of {nk α}1

{Sn} is random walk on circle =⇒ Markov chain(a) X1 absolutely continuous =⇒ exponential convergence to uniform distribution(b) X1 is lattice distributed with values kα, (k = 0, ±1, ±2, . . .), α irrational
Countable Markov chain =⇒ Convergence to uniform distribution is much slower
Random walks on finite groups

Kesten, Diaconis, Saloﬀ-Coste (1980-2000)

Card mixing: How many shuﬄes to uniformity?
Aldous (1983): Cutoﬀ at 32 log2 n steps
New York Times (January 9, 1990): In Shuﬄing Cards, 7 Is Winning Number
Random walk on circle:irrational

Moving forward or backward with angle ±α, α2Convergence speed depends on rational approximation properties of α
Sn = kα, |k| ≤ nAssume α = pq + O(q −100)

Sn = k pq + O(kq −100)

Schatte (1984-91)√Su (1998): If α is quadratic irrational (α = r + s t), thenC1n−1/2 ≤ sup |P (Sn < x) − x| ≤ C2n−1/2x√

Quadratic irrationals: bad rational approximation (worst case:5+12 )Nonrandom analogue: xn = {nα}, α irrational
Empirical measure1∑Fn(x) =I(0,x)(xk )nn

k=1

1 ∑DN (xk ) = supI[0,a)(xk ) − aN0≤a≤1
Ndiscrepancy

k=1The magnitude of DN ({kα}) depends on the continued fraction digits of α3Diophantine conditions in analysis
Poincaré (1890) Planetary motion∑m,n̸=0ei(mω1+nω2)tam,n.
mω1 + nω2Jupiter ω1 = 299.1”, Saturn ω2 = 12.5”, 2ω1 − 5ω2 ≈ 0.

Settled by Arnold (1963)
Siegel (1942) Stability of ﬁx point algorithms depends on rational approximation of α inz0 = e2πiαDiophantine type{}pA
sup c : α − < c+1 for inﬁnitely many p/qqqStrong typep
A< c+1qq
holds for inﬁnitely many p/q for large A and ﬁnitely many p/q for small A.
α−4Berry-Esseen type results
X1, X2, . . . i.i.d. integer valued nondegenerate random variables, α irrational, Sn =∆n = sup |P ({Snα} < x) − x|x

Theorem. If EX12 < ∞, Sn is unimodal and α is of strong type γ, then∆n = O(n−1/(2γ)),∆n = Ω(n−1/(2γ)).

γ = 1: badly approximable number α (bounded digits in continued fraction)
Theorem. Let 0 < β < 2 and assume
P (|X1| > t) ∼ ct−β andlim P (X1 ≥ x)/P (|X1| ≥ x) exists.

x→∞

If Sn is unimodal and α has strong type γ, then∆n = O(n−1/(βγ)),∆n = Ω(n−1/(βγ)).

Berry-Esseen problem for ordinary i.i.d. sums:()Sn
1−2/βsup P<x−G(x)=O(n)βn1/βx5∑n

k=1 Xk ,A random version of Schmidt’s lower boundFor any inﬁnite sequence (xk )

()

log N
DN (xk ) = ΩNand this bound is attained, e.g., for xk = {kα} with badly approximable α
Theorem. For any nondegenerate i.i.d. sequence (Xn) and any irrational α(√)
log log N
DN ({Sk α}) = Ωa.s.
N
This bound is attained if P (|X1| > x) ∼ 1/ log x
Critical behavior at γ = 2
Theorem. For smooth periodic f and γ < 2 we haveN∑dN −1/2f (Sk α) −→ N (0, σ 2)k=1

and this fails for γ > 2.
6

γ = 2:α − pq < qC3N∑

1{=1/2k∥kα∥
k=1O (log N ) if γ ≤ 2,()O N γ/2−1
if γ > 2

Some classical examples for critical phenomena:√∑Nk
Lacunary trigonometric series (Erdős 1962)
sin
nx,n≫
ek
k
k=1
∑1
Gaussian processes (Dobrushin, Major, Taqqu 1979) Nf(ξ)
r
∼kn
k=1n
Critical discrepancy behavior(i) If 1 ≤ γ ≤ 2, then(√

DN = O(ii) If γ > 2, thenlog log Nlog NN((DN = Olog log NN)(√,

DN = Ω)1/γ )(,7log log NN1
DN = ΩN 1/γ)
a.s.

)a.s.