RIESZ-RAIKOV SUMS AND IRRATIONAL ROTATIONS
Katusi FUKUYAMA (Kobe)
Abstract. In this note, we will consider on an eﬀectiveness of quasi Monte-Carlo
method. We will prove some central limit theorem for Riesz-Raikov sums, and by usingthat we will explain why the quasi Monte-Carlo method is not no more eﬀective in casewhen the integrand is complicated functions. This partly solves the Sugita’s conjecture.
We will also give a new proof of a previous result.

§1. Monte-Carlo and quasi Monte-Carlo method
In this note, we study some topics related to random numbers and numerical integrations. Among various methods of numerical integration, we here treat
Monte-Carlo method and quasi Monte-Carlo method. Let us first explain these two
methods, especially in one-dimensional case.
Suppose that a Riemann integrable function f on unit interval [ 0, 1 ] is given.
∫1
The purpose is to evaluate the integral 0 f (x) dx numerically. If we can prepare[ 0, 1 ]-valued uniform i.i.d. {ξn }, we have the following law of the large numbers:
1 ∑f (ξn ) −→
N n=1
N

∫ 1
f (x) dx a.s.,

(1.1)

0

The Monte-Carlo method evaluates the integral by using this theorem. More precisely, by using [ 0, 1 ]-valued uniform random numbers {ξ˜n }, we have an approxi∑Nf (ξ˜n ) for large enough N .
mate value of the integral by calculating (1/N )n=1

It is important for practical purpose to ask how to prepare random numbers
and how large we should take N . As to the first question, it seems that we still
don’t have complete answer. The question seems to be too diﬃcult and we do notstudy further here. We only mention that the statement (1.1) contains the phrase‘almost surely’and there definitely exists a non-trivial exceptional set, so that evenin the case when we have i.i.d., it is not easy to pick up correct ω which ensures theconvergence.
On the other hand, we have a good answer to the second question. By precise
version of the law of large numbers or the law of iterated logarithm, we have thefollowing estimate of errors:
1 ∑f (ξn ) −
N n=1
N

∫ 1
0

(
)
f (x) dx = O N ε−1/2

a.s. for all

ε > 0,(1.2)

in which ε can not be 0.
By the way, to escape from the above ambiguity of exceptional ω, the following
quasi Monte-Carlo method seems to be eﬀective. Let α be an irrational numberand ω0 be an arbitrary real number. Then, by Weyl’s theorem, we have1 ∑f (ω0 + nα) −→
N n=1
N

∫ 1
f (x) dx,

(1.3)

0

where f is extended over R periodically. The first advantage of the quasi MonteCarlo method is that there is no ambiguity in the statement, and the second is thefollowing estimate of errors: If α is an algebraic irrational number, we have1 ∑f (ω0 + nα) −
N n=1
N

∫ 1

(
)
f (x) dx = O N ε−1

for all ε > 0.

(1.4)

0

By these results, the quasi Monte-Carlo method seems to be much eﬀective
than the Monte-Carlo method, but it is not generally correct.
For example, to integrate a function on high dimensional space, the quasi
Monte-Carlo method is not eﬀective. An extensive treatment on this phenomenon
is recently given by Sugita & Takanobu [16].
And when the integrand f is irregular in some sense, the quasi Monte-Carlo
method is not eﬀective, either. In this paper, we give some treatment on thisphenomenon. The story goes back to the results given by Sugita [14].
2. Sugita’s results and its refinements
Let Sm be a one-dimensional simple random walk. Sugita [14] considers thefollowing scheme to evaluate the probability P (Sm = a) numerically.
()
Prepare the Lebesgue probability space Ω := [ 0, 1), P (dω) := dω andRademacher functions ri . Recall that ri is a function on R with period 1 definedby ri (ω) := r1 (2i−1 ω) and r1 (ω) := 1[ 0,1/2) (ω) − 1[ 1/2,1) (ω) (ω ∈ Ω).
∑m
By putting Sm := i=1 ri , a simple random walk {Sm } is defined on this space.
∫1
Since P (Sm = a) is given by the integral 0 1{Sm =a} (ω)dω on this space, by virtueof the quasi-Monte Carlo method, it holds that
1 ∑P (Sm = a) = lim
1{Sm =a} (ω0 + nα).
N →∞ N
n=1
N

(2.1)

for all ω0 ∈ Ω and α ̸∈ Q. When α is an algebraic irrational, the theoretical rate ofconvergence in (2.1) is of O(N ε−1 ), but Sugita [14] reports that this rate cannot be
observed in numerical experiments and only the rate O(N ε−1/2 ) is observed whenm is large. He claims that the quasi Monte-Carlo method is not eﬀective in thisscheme. He explains this phenomenon by his conjecture that the sequence Sm (ω),
Sm (ω + α), Sm (ω + 2α), . . . is nearly independent when m is large. His result is asfollows:{√(m)
Theorem A. The correlation Rα (n) of stationary sequence X(m)= Sm (ω)/ m,α}√√
Sm (ω + α)/ m, Sm (ω + 2α)/ m, . . . decays when m → 0 and its order is ofO(m−1/2+ε ) for every n, ε > 0, and for almost every α.
As a refinement of this theorem, we have the following results (Cf. [5].):
Theorem 1. (1) For almost every α, the stationary sequence X(m)converges toαGaussian i.i.d. as m → ∞, in sense of convergence of every finite dimensional
distributions.
√√(m)(2) For almost every α and every n, lim supm→∞ m/log log m Rα (n) = 2/3.
(3) Hausdorﬀ dimension of the set of α for which (1) does not hold is 1.
By (1) and (2), we can say that Sugita’s conjecture is correct for almost every
α, and that Theorem A gives almost best possible result, but by (3) we conclude
that the exceptional set for this phenomenon is also large.
There is, however, other interpretation of this result apart from the conjecture.
There is some possibility that random numbers can be generated by X(m)for largeαm. For the purpose of practical use, we must be serious about the exceptional setof α. We need some test to distinguish good α and bad one. In the next section,
we give results for every α and try to give some answer to this demand.
By the way, we would like to mention that, by using similar but more simple
scheme, Sugita [15] gives eﬀective random number generator.
3. Riesz-Raikov sums and irrational rotation
To study limit behavior of X(m)for every α, the following treatment as RieszαRaikov sums is appropriate. Let us first begin with the introduction of this notion.
Let θ > 1, α ∈ R, and g be a function on R with period 1 satisfying∫ 1∫ 1
g(t) dt = 0

0

and

2

g(t) dt < ∞.

0<
0

(3.1)

Let us put

1 ∑(ω) := √g(θk−1 ω).
m
m

X

(m)

k=1

The sum in the right hand side is called Riesz-Raikov sum. If we put θ := 2 and√g := r1 , we have g(θk−1 ω) = rk (ω) and X (m) = Sm / m and thereby we can regard
the Riesz-Raikov sum as an extension of simple random walk {Sm }.
As before, we have the next central limit theorem for Riesz-Raikov sums. (seeBerkes [1], [2] and Fukuyama [6].)Theorem B. Let θ > 1 and g satisfy (3.1) and∞∑s2k+1 − s2k 2 < ∞,

(3.2)

k=0

where ∥ · ∥2 denotes L2 [ 0, 1 ]-norm and si denotes i-th subsum of the Fourier seriesof g. Then for any measurable Ω ⊂ [ 0, 1) with |Ω| > 0,D

X (m) −→ N (0, v)()
holds on Ω, dω/|Ω| , where the limiting variance v = vg,θ is given as follows: In
case
θr ∈
/Q

(r ∈ N)(3.3)

is satisfied, v = ∥g∥22 ; Otherwise, by using p and q given byθr =pwhere r = min{ n ∈ N | θn ∈ Q }, p, q ∈ N and gcd(p, q) = 1,q

we havev = ∥g∥22 + 2

∞ ∫ 1
∑
k=1

(3.4)

g(pk t)g(q k t) dt < ∞.

0

As before, we operate irrational rotation to X (m) and define X(m)α , i.e.,{ (m) }X(m):= Xα;nαn∈Z(m)where Xα;n(ω) := X (m) (ω + nα) .

Next theorem characterizes the possible limit distribution of X(m)as m → ∞.
α
There is no restriction or ambiguity on α.

Theorem 2. Suppose that (3.1) and (3.2) are satisfied. Then for all Ω ⊂ [ 0, 1)()
with |Ω| > 0, θ > 1 and α ∈ R, on probability space Ω, dω/|Ω| , the sequenceZ{X(m)α }m∈N is relatively compact in the sense of convergence in distribution on R ,and all the possible limit is stationary Gaussian sequence, i.e., for any subsequenceof {X(m)α }m∈N there exists a subsequence which converges to a stationary gaussiansequence. This subsequence can be taken independently of Ω and g, and the limit
distribution does not depend on Ω.
By this theorem, we see that only stationary gaussian distribution can appear
as the limit distribution.
The next theorem gives a relation between convergence of the correlation andconvergence in law. It means that, by calculating the correlation numerically, we
can test whether α is good one or not. It has a practical significance.
Theorem 3. Let us assume (3.1) and (3.2). Let {mj }j∈N be a subsequence of Nand Ω ⊂ [ 0, 1) satisfy |Ω| > 0. For any n and l ∈ Z, the convergence of correlation()(mj ) (mj )lim E Xα;nXα;l= rn l(3.5)
j→∞holds if and only if X(mj ) converges as j → ∞ to the stationary gaussian sequencewith mean vector 0 and correlation matrix {rn l }n,l∈Z .
As before, the limit of X(m) is gaussian i.i.d. for almost all α. The next theorem
state this result.
Theorem 4. Let us assume (3.1) and (3.2). For almost all α with respect to theLebesgue measure, the sequence X(m)converges in distribution to gaussian i.i.d.
αThe exceptional set of α can be taken to be independent of Ω and g.
Let us next consider about the fluctuation of the correlation. From now on we
only consider the case when θ > 1 is an integer.
Theorem 5. Let Ω = [ 0, 1), θ > 1 be an integer and g satisfies (3.1), v = vg,θ > 0and∞∑k s2k+1 − s2k 2 < ∞.
(3.6)
k=0

(
)
Then the correlation on Ω, dω obeys√()
m(mj ) (mj )lim sup
E Xα;nXα;l=βlog log m
m→∞

a.e.

α

for some positive constant β.
Unlike as it appears, proof of β > 0 is more diﬃcult rather than the law of theiterated logarithm itself.
The next result claim that the exceptional set of α is not small with respect tothe Hausdorﬀ dimension.
Theorem 6. Let θ > 1 be an integer and g satisfies (3.1), v = vg,θ > 0 and∞∑

2kγ s2k+1 − s2k 2 < ∞for some

γ>0

(3.7)

k=0

The set of α for which the limit distribution of X(m)is dependent has Hausdorﬀ
αdimension 1.
By the way, the regularity conditions (3.2), (3.6) and (3.7) are derived fromsome smoothness conditions on g. We now note these implications. Let us define
the L2 -modulus of continuity ω2 (δ) of function g by
(∫ 1
)1/2
2
ω2 (δ) := supg(t + h) − g(t) dt
.
|h|≤δ

0

The condition (3.2), (3.6) or (3.7) are derived from∫ 1
∫ 1
ω2 (y)
ω2 (y) log 1/ydy < ∞,
dy < ∞ or
y
y
0
0

∫ 1
0

ω2 (y)
dy < ∞,
y 1−γ

(3.8)

respectively. (Cf. Zygmund [18], (3.3) of pp. 241).
Obviously Hölder continuous functions and functions of bounded variation satisfy these conditions.
Proofs of all results stated in this section can be found in [7].
4. Rademacher functions
In this section, we restrict ourself to the case of Rademacher functions, and givea sketch of proofs of our result putting g = r1 .
The next lemma plays an key.
Lemma 1. For any sequence {αi } of real numbers, the sequence {ri′ (ω) := ri (ω +αi )} is an i.i.d. on (Ω, P ).
Here we will give new proof. It is enough to prove()
1
P r1′ = ε1 , . . . , rn′ = εn = n , where ε1 , . . . , εn ∈ {−1, +1}.
2

(4.1)

(
)
Let us put Ψ(ω) := r1′ (ω), . . . , rn′ (ω) . (4.1) reduces to Ψ−1 (ε1 , . . . , εn ) = 1/2n . It
is clear that ri′ (ω + 1/2i ) = −ri′ (ω) holds, and thereby ri′ (ω + j/2i ) = (−1)j ri′ (ω)
holds. If we take j = 1, . . . , 2n − 1 arbitrary, we can write j = (2j ′ + 1)2m . Hence
we have
(
)
′
′
′
rn−m
(ω + j/2n ) = rn−m
ω + (2j ′ + 1)/2n−m = −rn−m(ω).
Thus we have Ψ(ω +j/2n ) ̸= Ψ(ω), and we can collude that Ψ(ω +j/2n ) (j = 0, . . . ,2n − 1) are diﬀerent from each other, and thereby Ψ(ω + j/2n ) (j = 0, . . . , 2n − 1)takes all values in {−1, +1}n .
It implies that Ψ−1 (ε1 , . . . , εn ) + j/2n (j = 0, . . . , 2n − 1) do not intersect
each other and the union of these coincides with Ω. Thus we can conclude thatΨ−1 (ε1 , . . . , εn ) has measure 1/2n .
(m)

To prove (1) of Theorem 1, it is enough to prove that the law of a1 X1;α + · · · +(m)ak Xk;α converges to the standard normal law for any a1 , . . . , ak with a21 +· · ·+a2k =1.
To prove this, we use the next theorem due to McLeish [11].
Theorem B. Let { ζm,j ; 1 ≤ j ≤ km } be a triangular array of random variables
(
)
√
∏
∑
and put Lm := j≤km 1 + −1tζm,j . The law of j≤km ζm,j converges to thestandard normal distribution as m → ∞, provided that the following four conditions
are satisfied for all t ∈ R:
(1) ELm → 1 as m → ∞;(2) The sequence {Lm }m∈N is uniformly integrable;∑
2(3)
j≤km ζm,j → 1 in probability as m → ∞;(4) maxj≤km |ζm,j | → 0 in probability as m → ∞.
( √ ) ∑kPutting ζm,i (ω) := 1/ m
j=1 aj ri (ω + jα), we apply this theorem. As tocondition (1), by Lemma 1, we have ELm = 1. (2) and (4) are easily verified. (3)is derived from the following:
1 ∑limri (ω + pα)ri (ω + qα) = 0,
m→∞ m
i=1
m

a.s.

It is easily proved that the above formula holds for almost all (ω, α). By applying
Fubini’s theorem, we complete the proof.
For the proof of the rest of the result, see [5].

References∑[1] Berkes, I., On the asymptotic behavior off (nk x), Main theorems, Z. Wahr. verw. Geb., 34(1976) 319–345∑[2] Berkes, I., On the asymptotic behavior off (nk x), Applications, Z. Wahr. verw. Geb., 34(1976) 347–365[3] Billingsley, P., Ergodic theory and information. Wiley, New York, 1967
[4] Erdős, P. & Taylor, S. J., On the set of points of convergence of a lacunary trigonometricseries and the equidistribution properties of related sequences, Proc. London Math. Soc. (3),
7 (1957) 598–615[5] Fukuyama, K., The central limit theorem for Rademacher system, Proc. Japan Acad. Ser. A,
70 (1994) 253–256[6] Fukuyama, K., The central limit theorem for Riesz-Raikov sums, Prob. Theory Related Fields,
100 (1994) 57–75[7] Fukuyama, K., Riesz-Raikov sums and Weyl transform, Monte Carlo Methods and Appl., 2(1996) 271–293[8] Hawkes, J., Probabilistic behaviour of some lacunary series, Z. Wahr. verw. Geb. 53 (1980)
21–33[9] Heyde, C. & Scott, J., Invariance principles for the law of the iterated logarithm for martingales
and process with stationary increments, Ann. Prob., 1 (1973) 428–436[10] Kupier, L. & Niederreiter, H., Uniform distribution of sequences, Wiley, New York, 1974.
[11] McLeish, D. L., Dependent central limit theorem and invariance principles, Annals of Prob. 2(1974) 620–628[12] Salem, R. & Zygmund, A., On lacunary trigonometric series I, Proc. Nat. Acad. Sci. U. S. A.,
33 (1947) 333–338[13] Salem, R. & Zygmund, A., On lacunary trigonometric series II, Proc. Nat. Acad. Sci. U. S. A.,
34 (1948) 54–62[14] Sugita, H., A private communication, (1993)[15] Sugita, H., Pseudo-random number generator by means of irrational rotation, Monte Carlo
methods and Appl., 1 (1995) 35-57[16] Sugita, H. & Takanobu, S., Limit theorem for symmetric statistics with respect to Weyl transformation: Disappearance of dependency, preprint∑[17] Takahashi, S., On the distribution of values of the typef (q k t), Tôhoku Math. J., 14 (1962)
233–243[18] Zygmund, A., Trigonometric series I, Cambridge university press, Cambridge, 1959

Katusi FUKUYAMA Department of Mathematics, Kobe University, Rokko, Kobe,
657 Japan
E-mail: fukuyama@math.s.kobe-u.ac.jp