1) is considered, where (al denotes the A SEQUENCE znCl = lMx,I, x, (0, fractional part of the number a and M > 1 is a natural number. It is shown that when this sequence
is used as a pseudorandom sequence
in calculations
by the
MonteCarlo method, the central limit theorem holds for a fairly wide class
of the
functions integrated. In a number of papers (see, for example, 11, 21) the necessity for a theoretical justification of the algorithms for obtaining pseudorandom sequences has been mentioned. One important question which arises in this connection is the question of the appli~abili~ of the central limit theorem when estimating the remainder of the integration. In the present paper this question is discussed
in the case where a simple
Linear recurrence procedure is used to obtain the ~seudoraadom sequence.
Although
by [3, 41 the results presented below may be obtained with somewhat less rigid assumptions, a more elementary approach is used in this paper. It was then essential to use some of the results of IS] which are briefly formulated below (Theorem 1). We denote by D, a unit sdimensional
hypercube and assume that the
function f(x), X = (xx, *. . I xsf is Riemann integrable in the strict sense in D, We specify the natural large numbers M,, . . . , M,_, and associate with f, a function of a single variable, +$(x> = f(x, ~M~~~,~~~*~~~~,. . . , 84, f 0.Ms_pD* where (aj denotes the fractional
part of the number a,
fJ1
Below we denote by M the
least of the numbers M,, . . . , M,,r. As usual, we say that f(x) satisfies schitz eondition with exponent y (0 < y 6 1) and constant L > 0 in f), , if ____~.__,_
l____l“.
* Zh. u’jchisl, Mat. mat. Fiz.,
__.
12.4,
x_._~
~~77~~~2, 1972.
_....
.~._.
...
a Lip
_.
.I.‘
308
S. M. Ermakov
We formulate as a theorem the results of
If 4,(x) is Riemann integrable than some M,:
(2)
if this f(X) satisfies
[sI required
below.
in [O, 1) for all M1, . . . , M,_i if M is greater
the Lipschitz
condition (2), we have for M > M,
We note that the additional condition imposed by the requirement of the integrability of 4(x) is not too burdensome. It is satisfied in any case if f(X) is continuous in D,. We also require a number of fairly simple statements which will be formulated as lemmas.
Lemma1 For any integer k > 0 we have 4 (31
s
f(lM”lf,...,
;, if the integrals
{irP’+**z) )dx =
j&x, 0
dt,
= M, = . , . = Iv,* = Y, on the right and left sides exist.
The proof is by a method used repeatedly in [51. The interval (0, 1) is divided into iWkequal parts and the integral on the left side of (3) is correspondIn the jth term of the resulting sum the change ingly divided into Mk integrals. of variable Mkx = j + y is then made, and this leads to the required result. Lemma
2
Let f satisfy
in DS the Lipschitz
the function of hs variables
f”l(X,)
condition (2) and @ IL=xzi
. . . fm”(Xk) satisfies
i!(x) /* Then 8 in the ksdimensional
on pse~oraRdom
Note
a Lipschitz
unit cube D,,
tct mt +***+mkI. integers,
condition
with exponent
309
y and constant
(m, + . . . + mk) x
number and mi, 1~ a‘< k are nonnegative
Here k >, 1 is a natural
not simultaneously
sequences
zero.
The proof for k = 2 follows
from the equation
f”“,(X,‘) f”‘: (X,‘) ‘ f”l (X,“)fl%‘(XZ”) = = Pn*(X,‘) (fl,(X*‘)  f”l(X,“)) + f”‘ifX,“) (fmZ(X?‘\  f”‘z(X,“)). The general
case
is proved by induction.
Now let m,, . . . , mk be natural fying the condition ip+s
p1,
PfI ’
numbers
satis
. . . . k1.
(41
I f”‘,( (&f$x}, . . , {Jft,+A1,}) x . . . X p”k [{fkf~~~),. . . , {itl’~i”‘)) s 1)
Ixlml,*..,mJ= As before,
and i,, . . “, i, natural
numbers
the existence
of this integral
is assumed
for all M greater
~3.r
than some
M,.
The following
D.9
lim 13~[ml,. . ‘, tn.jJ = 31tm
(5)
holds
equation
for any function
also satisfies
I>!
G(m,
Proof.
f(X) Riemann
the Lipschitz
I
(6)
f”j(X)dX..
, . . +
J
f”“l (X)dX..
By Lemma
m#(ks
~~~X)~~.
in the strict
sense
in 0,.
If f
(2) in D, , we have for M > M, .
Jf”‘k(WdX I<
Da
Ds +
J Da
integrable
condition
[m,.. . . , m,$]
.

l)~“r+.,*“‘k*jC2Y.
1 we can put ZM[m,, . . . , m,] in the expression for i, = 0. 4(x) corresponding
After this it is easy to see that the i_ntegrand is a function to the function
of ks variables
f”l(X,)
. . . f”,(X,),
powers of the number M. By Theorem 1 this implies follows from Lemma 2 and Theorem 1. We also consider the sequence ca = x is some number of (0, 1) and f n+,  IM+
where M,, . . . , Mks_r are (5).
The inequality
& = Ed, c2, . . . of numbers
(6)
of (0, 1) such that
n = 0, 1, . +. , M 32, an integer.
(7)
310
S. M. Ermakov
By means
of the sequence
6 we form the sequence
Yo, Y,, . * * of points in D,
by the rule i=o,
vi = (‘is’ Ci***> * * * 9 Q+lfs_,), and investigate
the behaviour if,%I]=
(8)
of the remainder Nl
1
RN
I, *..,
+f=O
as a function
of the quantity
It is shown in
[sI that
co = x. if as c4 we choose
an absolutely
normal number,
we
have lim lim RN &, SO]= 0. iM+rn Nem It is known that a set of absolutely
normal numbers
has on (0, 1) a measure
equal
to 1. We also consider
the integrals 1
1~ =
s
NV [f, 4) p dx,
P = 1,2,. . . .
0
If
we
write
Ni
we have Rx If, .z] = +
c
Ff Yi)
i=*
and ,,=ivp~(~l(K+~” 0
f0
what follows it will be convenient to establish the relation between I, and the moments of some random variables and use some known facts of probability In
theory. Let a be a random variable
uniformly
and consider the corresponding sequences RN&, al obviously has moments identical is bounded,
the I, define F&)
=
a distribution
distributed
in (0, 1).
We put tD = a
(7) and (8). The random quantity with I,. On the other hand, since function
[email protected], al< yl= mes Ix: R,Ef, xl < yl.
f
Note on pseudorandomsequences unique (apart from a set of measure zero).
311
(Carleman’s condition 161, p. 212, is
easily verified.) We will also consider the sdimensional random quantity 5, uniformly distributed in D,, and the random variable v = I, = Np
(9)
CtJk
z
fyo. Since
PI mi!
i
. . , mk! s
m,+...+mpp it #
i2 #
O
. . . # ih,
on the assumption that f satisfies by Lemma 3 iim Zp _ NP Mro.
x
Jf*k(x)dx
Cd
c
=
Dr.
r =
1,.
k = 1,. . . . D..
. . , k,
all the constraints imposed above, we obtain
Vl,+...+??lk=p
...
f”l( yi,) . . . Ifmk( yi,) dx,
0
P! mi! . . . rnk! s
relax
x ...
D8
0
.($q.) p, i=O
Da
where the 17iare independent samples of the random variable Q. Therefore, re, as M + = every 1, is identical with the pth moment of the arithmetic mean of the independent samples of the random variable qr with zero mean and variance f2(X)dX
Oz. =
J
(If(X)q2~
DS
the nature of the convergence being determined by the central limit theorem subject to the condition that all the moments of the random variable r, exist (see, for example, [61, p. 229). For finite M and N the function FN(y) can obviously
be represented by two
terms FNW
=?&)
+GMW,
where pN (y) is the distribution function of the random variable G, (y) converges weakly to zero as M + 00. If f(x)
satisfies
pLp’
X 
iif?
the Lipschitz
< LOP‘p @s 
NJ Nl
c
,=O
condition (2), we have by (6) and (9)
1) My.
ni, and
S. M. Ermakov
312
Or, since L,< p, we have 1 f xpd GM(x) 1 < p$‘(ps  1)M’Y. This estimate enables us to judge the dependence of the moments of the function GM on the dimension of the domain of integration and the number M. The result may be formulated as the following theorem. Theorem 2 If f(X) is Riemann integrable in the proper sense in I), and for some M, for M > M, all the 4((x) are Riemann integrable in (0, I), we have
liinJly.lles { eo:~RNU,eol< I/}) =&ew(%) But if f(x)
satisfies
in DS the Lipschitz
condition (2), for fixed N and M > M,
This theorem implies that for every function f(X) satisfying for sufficiently inequality
du.
its conditions
great M and N, the measure of the set of those Q, for which the
(RNif, &Cdl < ;, is satisfied,
is 1  sfy, M, N), where
s(!/.M,N)=11(2/rc)
[ox,
(++6(M,iv)
Jr
s(n~,N)+O
If M and N are fixed S(M, N) = 6, an4 for two arbitrary distinct satisfying the conditions estimate (10) is satisfies
npu M,iVccxs. functions
f
of Theorem 2, the measure of those +, for which the simultaneously, will be at least 1  26. And generally,
if we denote by [al the integral part of the number a, the following corollary of Theorem 2 can be obtained.
For any [8 “1 distinct
functions satisfying
the conditions
eDcan be found such that the inequality (10) is satisfied
of Theorem 2, an
for each of them.
Therefore, these results may serve as a basis for the use of the sequences (7) as pseudorandom sequences and for the use of the inequality (1) to estimate the error in the MonteCarlo method. In this connection
the following remark may be made.
Note on pseudorcndomsequences Remark.
In the literature
313
on‘the study of the convergence
to zero of R,[f,
t,l
instead of the points Y,, points Fi formed by the rule
are often considered.
It is easy to see that in this case Lemma 3 cannot be used,
because condition (4) will not be satisfied.
Nevertheless
in this case an analogue
of the central limit theorem for sdependent random variables can be obtained. Therefore, convergence to the normal law holds in this case also, but the variance u7 will be different. In calculations by the MonteCarlo method pseudorandom sequences are often obtained by formula (7), with the essential difference in this case that the calculations are carried out with a fixed number of places. This question was discussed in IS]. Some additional remarks on this topic are made below. Let +, be some number of (0, I), which ensures for each function of the given set that (10) is satisfied, and that ep,e, . . . is the representation of co as a fraction to base M. It is obvious that the ith element of the sequence 6 will be of the form
In any case in practical
calculations
a finite number of places is used.
If M is so
great that the quantity 0.5M r can be neglected, it is for our purpose sufficient to put ti = eiM‘. If, as usual, we have for the representation of c0 a fixed number of binary digits, the approximation of t, must be such that each of some sufficiently large number of its first Mary ‘digits” the same as the corresponding Therefore,
must be at least approximately
“digit” of the exact E,.
the attempts at an empirical selection
not without justification, bound to be suitable
although each specific
for the integration
of the “best” cc and M are
pair E,, and M is not in general
of all the functions satisfying
the condi
tions of Theorem 2. In this paper, in order to obtain concrete tions satisfying
a Lipschitz
obviously be no difficulty
results,
we have considered
condition with exponent less than unity.
func
There would
in obtaining similar results for other classes
of func
tions, if we obtained for them an estimate of the quantity *
Is
v(t)dx
0
as a function of M.
J/w
1
JJs
Translated
by J. Berry
314
S. M. Ermakov REFERENCES
1,
FRANKLIN, 17, 2859,
2.
CHENTSOV,
J, N. ~e~rministic 1963. N. N.
Pseudorandom
Mat. mat. Fizz., 7, 3, 623843, 3.
simulation
of random processes.
numbers for modelling 1967.
Markov chains,
Cornput.,
Zh. uychisl.
LEONOV, V. P, Same Applications of Leading Seminvariants to the Theory of Stationery random Processes (Nekotorye primeneniya starshikh aeminv~iantov teorii statsionaruykh slnchainykh protsessov). ‘Nauka”, Moscow, 1964.
4.
IBRAGIMOV, I. A. Asymptotic distribution of the values Ser. matem., mekhan. i astron., 1, 1324, 1961.
5.
SOBOL’,
I. M.
An approach
Computing and Applied 100112, 6.
aunt.
Tashkent,
of some sums. Vestn.
to the evaluation of multiple integrals, in: Problems fVopr. vychisl. i prikl. matem.), Vol. 38,
~~kemat~cs
1970.
PROKHOROV, YU. V. and ROZANOV, YU. A. veroyatnostei). “Nanka”, Moscow, 1967.
Theory
of Probability
(Teoriya
k
LG’T.
of