So sánh và kiểm định độ phân kỳ của các dãy và tập điểm tựa-ngẫu-nhiên một chiều

N(J,X).
Co´ theˆ’ coi doˆ. phaˆn ky` sao D
∗
N nhu
. sai phaˆn tuyeˆ.t doˆ´i lo´
.n nhaˆ´t giu˜.a xa´c suaˆ´t de`ˆu lieˆn tu. c
va` xa´c suaˆ´t de`ˆu ro`.i ra.c treˆn taˆ´t ca’ ca´c h`ınh laˆ. p phu
.o.ng con cu’a Is co´ chu´.a goˆ´c toa. doˆ. .
Giu˜.a DN va` D
∗
N co´ ca´c heˆ. thu´
.c:
D∗N(X) 6 DN(X) 6 2s.D∗N(X).
Nhu. vaˆ.y vo´
.i s coˆ´ di.nh, ca’ hai da. i lu
.o.. ng na`y co´ cu`ng doˆ. lo´
.n. Trong tru.`o.ng ho.. p moˆ. t chie`ˆu
(s = 1), Niederreiter chu´.ng minh du.o.. c ra`˘ng
D∗N > 1/2N, DN > 1/N
SO SA´NH VA` KIEˆ’M DI.NH DOˆ. PHAˆN KY` CU
’A CA´C DA˜Y 253
va` ca’ hai da.t du
.o.. c cu
.
. c tieˆ’u khi xk = (2k − 1)/2N . Daˆy la` trung dieˆ’m cu’a ca´c doa.n
[(k − 1)/N, k/N ], va` du.o.. c go. i la` taˆ.p ca´c trung dieˆ’m hoa˘. c da˜y trung dieˆ’m. Chu´ y´ ra`˘ng taˆ.p
na`y khoˆng pha’ i la` N dieˆ’m da`ˆu tieˆn cu’a moˆ. t da˜y voˆ ha.n, v`ı chu´ng khoˆng co`n gia´ tri. tu
.o.ng
u´.ng vo´.i ca´c taˆ. p dieˆ’m (N + 1), (N + 2)... pha`ˆn tu.’ . Thoˆng thu.`o.ng ca´c da˜y du.o.. c coi la` co´ doˆ.
phaˆn ky` thaˆ´p neˆ´u D∗N co´ doˆ. lo´
.n baˆ.c O((logN)s/N). Soˆ´ ha.ng logarit co´ theˆ’ bi. hu´t va`o moˆ. t
luy˜ thu`.a na`o do´ cu’a N , daˆ˜n deˆ´n caˆ.n O(1/N1−) vo´.i mo. i  > 0.
Di.nh ly´ 1. Da˜y voˆ ha. n X = {xk, 0 6 k 6 N} phaˆn boˆ´ de`ˆu trong [0, 1)s neˆ´u
limDN ({xk, 0 6 k 6 N}) = 0, N →∞
hoa˘. c tu
.o.ng du.o.ng nhu. theˆ´
limD∗N({xk, 0 6 k 6 N}) = 0, N →∞.
2.2. Ca´c u.´o.c lu.o.. ng ve`ˆ doˆ. phaˆn ky` va` toˆ´c doˆ. hoˆ. i tu.
Da˜y ngaˆ˜u nhieˆn thu.. c D
∗
N = O(
√
log logN
N
) (theo luaˆ. t logarit la˘. p).
Da˜y tu.. a ngaˆ˜u nhieˆn (doˆ. da`i voˆ ha.n) D
∗
N = O((logN)
s/N).
Taˆ.p dieˆ’m tu
.
. a ngaˆ˜u nhieˆn (doˆ. da`i hu˜
.u ha.n) D
∗
N = O((logN)
s−1/N).
Na˘m 1954 nha` toa´n ho.c K. F. Roth da˜ xa´c di.nh du
.o.. c caˆ. n du
.´o.i cho N dieˆ’m trong khoˆng
gian s chie`ˆu
D∗N > O((logN)(s−1)/2/N).
Trong ba´o ca´o nghieˆn cu´.u thu.. c nghieˆ.m doˆ. phaˆn ky` cu’a ca´c da˜y tu
.
. a-ngaˆ˜u-nhieˆn nhie`ˆu
chie`ˆu ([3]) L. Finschi nhaˆ.n xe´t ra˘`ng doˆ´i vo´
.i moˆ˜i da˜y co´ doˆ. phaˆn ky` thaˆ´p x1, x2, ... trong khoˆng
gian s chie`ˆu, toˆ`n ta. i ha`˘ng soˆ´ Cs sao cho
D∗N(x1, ..., xN) 6 Cs.(lnN)s/N +O((lnN)s−1/N)
va` da˜ t´ınh du.o.. c ca´c gia´ tri. Cs doˆ´i vo´
.i moˆ. t soˆ´ da˜y vo´
.i ca´c chie`ˆu kha´c nhau.
2.3. Doˆ. phaˆn ky` trong tru
.`o.ng ho.. p moˆ. t chie`ˆu
Trong tru.`o.ng ho.. p moˆ. t chie`ˆu, doˆ. phaˆn ky` cu’a da˜y soˆ´ x0, x1, ..., xN−1 du.o.. c di.nh ngh˜ıa nhu.
sau
D(x0, x1, ..., xN−1) = D = sup
06x61
|SN(x)/N − x|,
trong do´ SN(x) la` soˆ´ dieˆ’m thuoˆ. c khoa’ng [0, x).
Neˆ´u xi da˜ du
.o.. c sa˘´p x1 6 x2 6 ... 6 xN th`ı heˆ. thu´.c treˆn daˆy du.o.. c ru´t go.n tha`nh coˆng
thu´.c Niederreiter (xem [10])
D = 1/2 + max
16i6N
|i− 1
2
−N.xi|.
Coˆng thu´.c na`y cho ta thaˆ´y cu.. c tieˆ’u cu’a D la` 1/2 va` da. t du
.o.. c khi xi = (i− 1/2)/N trong
do´ i = 1, 2, ..., N (xem [10]). Trong tru.`o.ng ho.. p N coˆ´ di.nh, da˜y soˆ´ na`y la` toˆ´i u.u theo tieˆu
chuaˆ’n cu’a doˆ. phaˆn ky`. Nhu
.ng khi chuyeˆ’n tu`. N sang (N + 1) th`ı taˆ´t ca’ mo. i dieˆ’m de`ˆu pha’ i
thay doˆ’i. Vı´ du. da˜y soˆ´ toˆ´i u
.u vo´.i N = 3 la` (1/6, 3/6 va` 5/6), vo´.i N = 4 la. i la` (1/8, 3/8,
254 VU˜ HOA`I CHU.O.NG, NGUYE˜ˆN COˆNG DIE`ˆU
5/8, 7/8). Nhu. vaˆ.y khoˆng theˆ’ xaˆy du
.
. ng du
.o.. c moˆ. t da˜y voˆ ha.n ca´c dieˆ’m xi sao cho doa.n
x0, x1, x2, ..., xk (k = 2...N) na`o cu˜ng phaˆn boˆ´ de`ˆu toˆ´i u.u.
2.4. Caˆ.n Koksma-Hlawka
Doˆ. phaˆn ky` khoˆng chı’ la` doˆ. do quan tro.ng cu’a phaˆn boˆ´ de`ˆu ma` co`n do´ng vai tro` ch´ınh
trong vieˆ.c gio´
.i ha.n sai soˆ´ cu’a xaˆ´p xı’ t´ıch phaˆn. Keˆ´t qua’ then choˆ´t trong hu
.´o.ng na`y la` baˆ´t
da˘’ ng thu´.c Koksma-Hlawka do Jurjen Koksma coˆng boˆ´ na˘m 1942 cho tru.`o.ng ho.. p moˆ. t chie`ˆu
va` du.o.. c Edmun Hlawka toˆ’ng qua´t hoa´ va`o na˘m 1961 ([5]). Theo do´ sai soˆ´ t´ıch phaˆn du
.o.. c
gio´.i ha.n bo
.’ i t´ıch cu’a hai da. i lu
.o.. ng: moˆ. t da. i lu
.o.. ng chı’ phu. thuoˆ. c va`o ha`m du
.´o.i daˆ´u t´ıch phaˆn
f (qua doˆ. do bieˆ´n phaˆn toa`n pha`ˆn), da. i lu
.o.. ng kia chı’ phu. thuoˆ.c va`o taˆ. p dieˆ’m du`ng deˆ´n (qua
D∗N , tu´
.c la` doˆ. leˆ. ch so vo´
.i phaˆn boˆ´ de`ˆu).
Du.´o.i daˆy la` moˆ´i quan heˆ. giu˜
.a ca´c da˜y tu.. a-ngaˆ˜u-nhieˆn va` phe´p t´ıch phaˆn tu
.
. a Monte-
Carlo.
T´ıch phaˆn s chie`ˆu I(f) =
∫
Is
f(x)dx du.o.. c xaˆ´p xı’ ba`˘ng Q(f) = (1/N)
N∑
k=1
f(xk), trong do´
xk la` da˜y tu.. a ngaˆ˜u nhieˆn s chie`ˆu vo´
.i doˆ. phaˆn ky` sao D
∗
N .
Neˆ´u f(x) co´ bieˆ´n phaˆn toa`n pha`ˆn bi. cha˘.n V (f) treˆn [0,1] th`ı
|Q(f)− I(f)| 6 V (f).D∗N .
Da´ng tieˆ´c ra`˘ng trong thu.. c teˆ´ raˆ´t kho´ u
.´o.c lu.o.. ng sai soˆ´ tu`
. baˆ´t da˘’ ng thu´.c na`y, va` daˆy ch´ınh
la` vaˆ´n de`ˆ nan gia’ i cu’a phu.o.ng pha´p tu.. a-Monte-Carlo (QMC).
3. MOˆ. T SO´ˆ DA˜Y TU
.
. A NGA˜ˆU NHIEˆN – DA˜Y CO´ DOˆ. PHAˆN KY` THA´ˆP
Trong toa´n ho.c, da˜y co´ doˆ. phaˆn ky` thaˆ´p la` da˜y ma` vo´
.i mo. i N , da˜y con (x1, x2, ..., xN) ha`ˆu
nhu. phaˆn boˆ´ de`ˆu va` da˜y (x1, x2, ..., xN, xN+1) cu˜ng ha`ˆu nhu. phaˆn boˆ´ de`ˆu. Pha’ i xaˆy du.. ng
taˆ. p N pha`ˆn tu
.’ (x1, x2, ..., xN) sao cho khi xaˆy du.. ng taˆ. p (N + 1) pha`ˆn tu.’ th`ı khoˆng ca`ˆn t´ınh
la. i N pha`ˆn tu
.’ tru.´o.c.
3.1. Ca´c da˜y soˆ´ van der Corput
Daˆy la` da˜y soˆ´ phaˆn boˆ´ de`ˆu trong khoa’ng (0,1) va` du.o.. c nghieˆn cu´
.u kha´ ky˜ trong l˜ınh vu.. c
ly´ thuyeˆ´t soˆ´, do nha` toa´n ho.c Ha` Lan Johannes Gualtherus van der Corput (1890-1975) de`ˆ
xuaˆ´t va`o na˘m 1935. Da˜y soˆ´ na`y laˆ´p da`ˆy doa.n [0,1) moˆ. t ca´ch die`ˆu hoa` vo´
.i doˆ. phaˆn ky` nho’
ma˘. c du` no´ khoˆng bieˆ´n thieˆn moˆ. t ca´ch ngaˆ˜u nhieˆn. Cu`ng vo´
.i su.. pha´t trieˆ’n cu’a ma´y t´ınh,
ngu.`o.i ta da`ˆn da`ˆn thaˆ´y du.o.. c kha’ na˘ng u´
.ng du. ng cu’a da˜y soˆ´ na`y trong t´ınh toa´n soˆ´ tri. no´i
chung va` trong phu.o.ng pha´p (tu.. a)-Monte-Carlo no´i rieˆng.
3.1.1. Di.nh ngh˜ıa co
. ba’n
Go. i p(k) la` soˆ´ van der Corput thu´. k. Neˆ´u trong heˆ. nhi. phaˆn k = e1e2...em−1em trong do´
ei la` chu˜
. soˆ´ nhi. phaˆn (tu´
.c la` chı’ nhaˆ.n hai gia´ tri. 0 va` 1) th`ı
p(k) = 0...em.em−1...e2e1.
Vı´ du. , k la`ˆn lu
.o.. t la` 7 soˆ´ tu
.
. nhieˆn da`ˆu tieˆn, k = 1, 2, 3, 4, 5, 6, 7.
Da.ng nhi. phaˆn cu’a chu´ng la` 1, 10, 11, 100, 101, 110, 111.
Ca´c soˆ´ van der Corput tu.o.ng u´.ng la`
+ da.ng nhi. phaˆn: 0,1; 0,01; 0,11; 0,001; 0,101; 0,011; 0,111
SO SA´NH VA` KIEˆ’M DI.NH DOˆ. PHAˆN KY` CU
’A CA´C DA˜Y 255
+ da.ng thaˆ. p phaˆn: 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8.
3.1.2. Toˆ’ng qua´t
Laˆ´y moˆ. t soˆ´ nguyeˆn toˆ´ p > 1 la`m co. soˆ´. Mo. i soˆ´ nguyeˆn du.o.ng k de`ˆu co´ phe´p bieˆ’u die˜ˆn
duy nhaˆ´t theo co. soˆ´ p,
k =
∑
j>0
aj(k).pj
trong do´ aj ∈ Fp = {0, 1, 2, ..., p− 1} va` aj(k) = 0 khi j kha´ lo´.n, tu´.c la` toˆ’ng no´i treˆn hu˜.u
ha.n.
Ha`m ngu.o.. c goˆ´c (radical inverse function) se˜ a´nh xa. moˆ˜i gia´ tri. k va`o moˆ. t dieˆ’m trong [0,1)
ba`˘ng ca´ch da’o ngu.o.. c ca´c heˆ. soˆ´ aj(k) va` ta.o neˆn phaˆn soˆ´ 0, a0a1a2... (trong heˆ. deˆ´m co. soˆ´ p).
Ch´ınh xa´c ho.n
ψp(k) =
∑
j>0
aj(k).p−j−1, k > 0.
Da˜y van der Corput co. soˆ´ p ch´ınh la` da˜y X = {ϕp(0) = 0, ϕp(1), ϕp(2), ϕp(3), ...}.
Vı´ du. , t`ım ϕ7(1205) tu´.c la` soˆ´ ha.ng van der Corput co. soˆ´ 7 tu.o.ng u´.ng vo´.i soˆ´ 1205.
Tru.´o.c tieˆn ta khai trieˆ’n theo co. soˆ´ 7:
1205 = 3.73 + 3.72+ 4.71 + 1.70,
tu`. daˆy chuyeˆ’n tu`. heˆ. deˆ´m thaˆ.p phaˆn sang heˆ. deˆ´m thaˆ´t phaˆn
1205(10) = 3341(7).
Sau do´ pha’n chieˆ´u ca´c heˆ. soˆ´ qua daˆ´u pha’y, 3341(7)→ 0, 1433(7). Va` thu du.o.. c keˆ´t qua’
0.1433(7) = 1/7 + 4/72 + 3/73 + 3/74 = 563/2401(10).
Ngu.`o.i ta da˜ chu´.ng minh du.o.. c ra`˘ng taˆ´t ca’ ca´c da˜y van der Corput la` da˜y co´ doˆ. phaˆn ky`
thaˆ´p. Ch´ınh xa´c ho.n, D∗N cu’a N pha`ˆn tu
.’ da`ˆu tieˆn cu’a da˜y co´ doˆ. lo´
.n O(logN/N) vo´.i moˆ. t
ha`˘ng soˆ´ aˆ’n phu. thuoˆ.c va`o co
. soˆ´ p.
Co. soˆ´ p ca`ng lo´.n th`ı soˆ´ dieˆ’m ca`ˆn thieˆ´t deˆ’ da.t du
.o.. c phaˆn boˆ´ de`ˆu ca`ng lo´
.n. Da˜y van der
Corput chu´.a nhu˜.ng chu ky` co´ doˆ. da`i p vo´
.i ca´c soˆ´ ta˘ng do.n dieˆ.u (trong moˆ˜i chu ky`).
3.2. Da˜y Richtmyer {k.α(p)}
Cho α = (α1, α2, ..., αs) la` taˆ. p ca´c soˆ´ voˆ tı’ va` 1, α1, α2, ..., αs doˆ.c laˆ. p tuyeˆ´n t´ınh. Da˜y
{k.α(p)} du.o.. c cho du.´o.i da.ng
Xk = ({k.α1}, {k.α2}, ..., {k.αs}), k > 0
trong do´ {x} bieˆ’u thi. pha`ˆn thaˆ.p phaˆn cu’a soˆ´ x.
M. Mascagni ([7]) go. i daˆy la` doˆ.ng lu
.
. c ho.c ergodic (ergodic dynamics).
Ngu.`o.i ta thu.`o.ng cho.n αi la` ca˘n cu’a ca´c soˆ´ nguyeˆn toˆ´ ([1, 5]). Trong ba`i na`y chu´ng toˆi
cho.n thu
.’ nghieˆ.m αi la` ca´c ha˘`ng soˆ´ toa´n ho.c voˆ ty’ quen bieˆ´t nhu
. pi, Au (ty’ leˆ. va`ng), e, C
(ha`˘ng soˆ´ Euler-Mascheroni), G (ha`˘ng soˆ´ Catalan) va` ca´c ha`m ln(p), sin(p), cos(p), arctan(p).
3.3. Da˜y soˆ´ V
Co´ hai loa. i tieˆu chuaˆ’n ve`ˆ phaˆn phoˆ´i de`ˆu cu’a moˆ. t da˜y soˆ´
+ Loa. i 1 du
.
. a treˆn doˆ. kha´c bieˆ.t cu’a ca´c ha`m phaˆn phoˆ´i maˆ˜u va` ly´ thuyeˆ´t. Deˆ’ kieˆ’m di.nh tieˆu
chuaˆ’n loa. i na`y, thu
.`o.ng du`ng nhaˆ´t la` ba phe´p thu.’ χ2, Kolmogorov va` ω2. Doˆ´i vo´.i ca´c da˜y
tu.. a-ngaˆ˜u-nhieˆn co`n theˆm doˆ. phaˆn ky`.
256 VU˜ HOA`I CHU.O.NG, NGUYE˜ˆN COˆNG DIE`ˆU
+ Loa. i 2 du
.
. a treˆn ca´c gia´ tri. cu’a moment maˆ˜u va` ly´ thuyeˆ´t.
Da˜y soˆ´ V (xem [11]) la` da˜y tu.. a-ngaˆ˜u-nhieˆn du
.
. a treˆn ca´c da˘’ ng thu´
.c giu˜.a moment maˆ˜u va`
moment ly´ thuyeˆ´t. Khi ca`ˆn ta. o ra N dieˆ’m phaˆn boˆ´ de`ˆu th`ı ta´ch N tha`nh toˆ’ng cu’a h soˆ´ ha.ng
N = K1 +K2 + ...+Kh sao cho ca´c Ki kha´c nhau.
Moˆ˜i da˜y soˆ´ V co´ K dieˆ’m du.o.. c ta.o ra theo ca´c coˆng thu´
.c do.n gia’n. Treˆn doa.n (0,1) ca´c
dieˆ’m ca´ch de`ˆu nhau moˆ. t khoa’ng u, dieˆ’m da`ˆu (x1) ca´ch dieˆ’m 0 va` dieˆ’m cuoˆ´i (xk) ca´ch dieˆ’m
1 moˆ.t khoa’ng T
x1 = T, x2 = T + u, x3 = T + 2u, ..., xK = T + (K − 1).u
trong do´, T = (1−
√
K − 1
K + 1
)/2 va` u = (1− 2T )/(K − 1) = 1/√(K − 1)(K + 1).
Thuaˆ. t toa´n treˆn daˆy du
.
. a treˆn ca´c gia´ tri. cu’a moment (tieˆu chuaˆ’n phaˆn boˆ´ de`ˆu loa. i 2),
nhu.ng ca´c da˜y soˆ´ V du.o.. c ta. o ra cu˜ng da´p u´
.ng da`ˆy du’ ca’ ca´c tieˆu chuaˆ’n phaˆn boˆ´ de`ˆu loa. i 1
(ve`ˆ doˆ. phaˆn ky` cu’a ca´c ha`m phaˆn phoˆ´i). Qua taˆ´t ca’ ca´c phe´p thu
.’ ca´c da˜y tu.. a-ngaˆ˜u-nhieˆn V
na`y de`ˆu vu.o.. t troˆ. i so vo´
.i ca´c da˜y soˆ´ ngaˆ˜u nhieˆn va` gia’ -ngaˆ˜u-nhieˆn (xem [9]). Keˆ´t qua’ so sa´nh
da˜y V vo´.i ca´c da˜y tu.. a-ngaˆ˜u-nhieˆn kha´c se˜ du
.o.. c tr`ınh ba`y trong pha`ˆn sau.
4. CA´C NGHIEˆN CU´
.
U THU
.
. C NGHIEˆ.M SO SA´NH
4.1. Moˆ ta’ va` ky´ hieˆ.u ca´c da˜y soˆ´ du
.o.. c kha’o sa´t
Ca´c da˜y soˆ´ va` taˆ. p dieˆ’m vo´
.i N = 2459(N la` soˆ´ nguyeˆn toˆ´), du.o.. c ta. o tha`nh theo ca´c Mu. c
3.1, 3.2 va` 3.3 treˆn daˆy vo´.i ca´c co. soˆ´ kha´c nhau, va` du.o.. c ky´ hieˆ.u trong ngoa˘. c do
.n tu`. (1) deˆ´n
(100). Doˆ. phaˆn ky` D*, tieˆu ch´ı quan tro.ng nhaˆ´t doˆ´i vo´
.i ca´c da˜y va` taˆ. p dieˆ’m tu
.
. a-ngaˆ˜u-nhieˆn,
se˜ la` tieˆu chuaˆ’n so sa´nh.
4.1.1. Ca´c da˜y soˆ´ van der Corput
(1) - (15): ca´c da˜y soˆ´ van der Corput vo´.i co. soˆ´ la` 15 soˆ´ nguyeˆn toˆ´ da`ˆu tieˆn
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}.
4.1.2. Ca´c da˜y Richtmyer {k.α(p)}
Trong ca´c da˜y (16) - (90) du.´o.i daˆy, p ky´ hieˆ.u 15 soˆ´ nguyeˆn toˆ´ da`ˆu tieˆn.
(16) - (30): ca´c da˜y soˆ´ {k.α} vo´.i α = √p
(31) - (45): ca´c da˜y soˆ´ {k.α} vo´.i α = ln(p)
(46) - (60): ca´c da˜y soˆ´ {k.α} vo´.i α = sin(p)
(61) - (75): ca´c da˜y soˆ´ {k.α} vo´.i α = cos(p)
(76) - (90): ca´c da˜y soˆ´ {k.α} vo´.i α = arctan(p).
Ca´c da˜y (91) - (95) du.. a va`o 5 ha˘`ng soˆ´ toa´n ho.c quen thuoˆ. c laˆ´y gia´ tri. tu`
. [12]. Chu.o.ng
tr`ınh t´ınh toa´n vo´.i 24 soˆ´ le’ , du.´o.i daˆy chı’ ghi 12 soˆ´ le’ da`ˆu tieˆn.
(91): da˜y soˆ´ {k.α} vo´.i α = pi = 3, 141592654358...
(92): da˜y soˆ´ {k.α} vo´.i α = ty’ leˆ. va`ng = Au = (
√
5 + 1)/2 = 1, 618033988749...
(93): da˜y soˆ´ {k.α} vo´.i α = e = 2, 718281828459...
(94): da˜y soˆ´ {k.α} vo´.i α = ha`˘ng soˆ´ Euler-Mascheroni,
C = lim(− lnk + 1+ 1/2 + 1/3 + 1/4 + ...+ 1/k) = 0, 577215664901...
(95): da˜y soˆ´ {k.α} vo´.i α = ha`˘ng soˆ´ Catalan G,
G = 1− 1/32 − 1/52 − 1/72... = 0, 915965594177...
SO SA´NH VA` KIEˆ’M DI.NH DOˆ. PHAˆN KY` CU
’A CA´C DA˜Y 257
4.1.3. Ca´c da˜y soˆ´ gia’ ngaˆ˜u nhieˆn R
(96) - (97): hai da˜y soˆ´ gia’ -ngaˆ˜u-nhieˆn Ri do ma´y t´ınh ta.o ra ba`˘ng ha`m Random cu’a Turbo
Pascal. Nha˘`m ta˘ng t´ınh ngaˆ˜u nhieˆn, ta da˘. t thu’ tu. c Randomize o
.’ da`ˆu chu.o.ng tr`ınh deˆ’ kho.’ i
doˆ.ng boˆ. ta.o soˆ´ vo´
.i moˆ. t gia´ tri. ngaˆ˜u nhieˆn.
4.1.4. Ca´c taˆ. p dieˆ’m ca´ch de`ˆu
(98): taˆ.p dieˆ’m V
(99): taˆ.p dieˆ’m (k − 1)/N
(100): taˆ. p ca´c trung dieˆ’m (k − 0, 5)/N.
Ba taˆ.p dieˆ’m ca´ch de`ˆu (98), (99), (100) treˆn daˆy de`ˆu do 21 doa.n ho
.
. p tha`nh sao cho soˆ´
pha`ˆn tu.’ la`ˆn lu.o.. t la` N = 128, 311, 424, 602, 808, 888, 903, 925, 1130, 1205, 1212, 1410, 1603,
1911, 1964, 2003, 2009, 2104, 2307,2404, 2459, co´ ngh˜ıa la`
k1 = 128, k2 = 311− 128 = 183, k3 = 424− 311 = 113, · · · , k21 = 2459− 2404 = 55.
4.2. Keˆ´t qua’ so sa´nh thu.. c nghieˆ.m
Trong 2 ba’ng du.´o.i daˆy ca´c da˜y va` taˆ. p dieˆ’m ma` ba`i ba´o de`ˆ xuaˆ´t du
.o.. c ghi ba`˘ng chu˜
. daˆ.m.
Vieˆ.c so sa´nh du
.o.. c tieˆ´n ha`nh giu˜
.a ca´c nho´m (cu`ng moˆ. t da.ng) va` giu˜
.a ca´c da˜y vo´.i nhau.
4.2.1. So sa´nh ca´c nho´m
Ba’ng 1 ghi doˆ. phaˆn ky` trung b`ınh cu’a ca´c nho´m, xeˆ´p theo thu´
. tu.. ta˘ng da`ˆn. Du´
.ng da`ˆu
la` ca´c da˜y Richtmyer nguyeˆn thu’y vo´.i α(p) =
√
p. Die`ˆu do´ gia’ i th´ıch v`ı sao da˜y na`y du.o.. c
mo. i ngu
.`o.i thu`.a nhaˆ.n. Du´
.ng thu´. hai la` ca´c taˆ.p dieˆ’m ca´ch de`ˆu, trong do´ co´ da˜y V do ta´c gia’
de`ˆ xuaˆ´t ([11]) va` da˜y (k − 1/2)/N du.o.. c du.a va`o thu.’ nghieˆ.m la`ˆn da`ˆu. Tieˆ´p theo do´, 2 nho´m
α (ha`˘ng soˆ´ voˆ ty’ ) va` {k. arctan(p)} du´.ng treˆn ca’ nho´m van der Corput quen thuoˆ.c. Co`n
ca´c nho´m {k. ln(p)} va` {k. cos(p)} tuy co´ ke´m ho.n nhu.ng vaˆ˜n o.’ treˆn nho´m gia’ -ngaˆ˜u-nhieˆn
R. Ca´c da˜y {k. sin(p)} du´.ng cuoˆ´i cu`ng vo´.i doˆ. phaˆn ky` trung b`ınh qua´ lo´.n cho neˆn nho´m
na`y khoˆng chaˆ´p nhaˆ.n du
.o.. c. Tuy vaˆ.y, du
.´o.i daˆy se˜ thaˆ´y, vo´.i moˆ. t va`i gia´ tri. p cu. theˆ’, da˜y
{k. sin(p)} vaˆ˜n co´ theˆ’ la` da˜y tu.. a-ngaˆ˜u-nhieˆn.
Ba’ng 1. Doˆ. phaˆn ky` trung b`ınh theo nho´m
Thu´. D∗ da˜y soˆ´ da˜y Nho´m
tu.. trung b`ınh trong nho´m
1 3,19723 (16) - (30) 15 da˜y Richtmyer {k.√p}
2 5,21334 (98) - (100) 3 taˆ.p dieˆ’m (k − 1)/N, (k− 0, 5)/N, V
3 6,92485 (91) - (95) 5 da˜y Richtmyer ca’ i bieˆn theo ha˘`ng soˆ´
{k.pi}{k.Au}{k.e}, {k.C}, {k.G},
4 7,83201 (76) - (90) 15 da˜y {k. arctan(p)}
5 9,05301 (1) - (15) 15 da˜y van der Corput
6 10,76932 (31) - (45) 15 da˜y {k. ln(p)}
7 10,79202 (61) - (75) 15 da˜y {k. cos(p)}
8 33,04532 (96) - (97) 2 da˜y gia’ ngaˆ˜u nhieˆn R
9 96,35071 (46) - (60) 15 da˜y {k. sin(p)}
4.2.2. So sa´nh ca´c da˜y va` taˆ. p dieˆ’m
Doˆ. phaˆn ky` trung b`ınh (ba’ng 2) du
.o.. c t´ınh theo ca´c gia´ tri. D
∗ cu’a da˜y co´ doˆ. da`i ta˘ng da`ˆn:
N = 128, 311, 424, 602, 808, 888, 903, 925, 1130, 1205, 1212, 1410, 1603, 1911, 1964, 2003,
258 VU˜ HOA`I CHU.O.NG, NGUYE˜ˆN COˆNG DIE`ˆU
2009, 2104, 2307,2404, 2459.
Trong 10 da˜y du´.ng da`ˆu co´ to´.i 7 da˜y do chu´ng toˆi de`ˆ xuaˆ´t. Da˘. c bieˆ.t da˜y {k.Au}, laˆ´y ty’ leˆ.
va`ng la`m co. soˆ´, co´ doˆ. phaˆn ky` trung b`ınh nho’ nhaˆ´t. Trong 10 da˜y cuoˆ´i ba’ng cu˜ng co´ 8 da˜y
do chu´ng toˆi thu.’ nghieˆ.m. Die`ˆu do´ chu´
.ng to’ ca´c da.ng ca’ i bieˆn chı’ du
.o.. c chaˆ´p nhaˆ. n vo´
.i nhu˜.ng
gia´ tri. p nhaˆ´t di.nh. Trong hai toˆ´p daˆ˜n da`ˆu va` cuoˆ´i na`y khoˆng co´ ca´c taˆ. p dieˆ’m ca´ch de`ˆu va`
ca´c da˜y van der Corput.
Ca´c da˜y {k. ln(p)}, {k. sin(p)}{k. arctan(p)} xuaˆ´t hieˆ.n o.’ ca’ toˆ´p treˆn va` toˆ´p du.´o.i, tu`y
thuoˆ.c va`o ca´c gia´ tri. p kha´c nhau.
Ba’ng 2. Mu.`o.i da˜y co´ doˆ. phaˆn ky` D
∗ trung b`ınh nho’ nhaˆ´t, lo´.n nhaˆ´t
va` thu´. tu.. cu’a chu´ng ta. i 3 gia´ tri. N
Thu´. tu.. D
∗
tr.b.(i) Da˜y Da.ng Thu´
. tu.. ta. i 3 gia´ tri. N
chung N = 311 N = 1205 N = 2459
1. 1,91236 (92) {k.Au} 6. 7. 9.
2. 2,08522 (16) {k.√2} 19. 14. 7.
3. 2,31358 (90) {k. arctan47} 4. 8. 14.
4. 2,31592 (85) {k. arctan29} 15. 9. 10.
5. 2,42076 (17) {k.√3} 26. 11. 11.
6. 2,43589 (36) {k. ln13} 16. 26. 12.
7. 2,45736 (89) {k. arctan43} 29. 23. 20.
8. 2,46239 (40) {k. ln29} 20. 21. 23.
9. 2,48654 (57) {k. sin37} 12. 15. 30.
10. 2,50865 (18) {k.√5} 18. 6. 22.
... ... ... ... ... ... ...
91. 15,50845 (68) {k. cos 19} 96. 91. 81.
92. 23,36515 (75) {k. cos 47} 97. 93. 85.
93. 26,16343 (73) {k. cos 41} 73. 94. 91.
94. 32,97025 (96) R1 78. 97. 95.
95. 33,12040 (97) R2 95. 90. 97.
96. 36,50603 (76) {k. arctan2} 86. 96. 98.
97. 39,16400 (65) {k. cos 11} 99. 98. 93.
98. 44,71712 (37) {k. ln17} 98. 95. 96.
99. 65,70675 (38) {k. ln19} 94. 99. 99.
100. 1343,98573 (50) {k. sin11} 100. 100. 100.
4.2.3. Keˆ´t luaˆ. n
Ca´c t´ınh toa´n kieˆ’m di.nh cho ta moˆ. t ca´i nh`ın bao qua´t ve`ˆ y´ ngh˜ıa thu
.
. c teˆ´ cu’a ca´c da˜y
tu.. a-ngaˆ˜u-nhieˆn. Cha˘’ ng ha.n nhu
. ve`ˆ co. so.’ ly´ thuyeˆ´t, da˜y van der Corput de.p ho
.n ha˘’ n da˜y
Richtmyer. Nhu.ng kha’ na˘ng u´.ng du. ng th`ı hoa`n toa`n ngu
.o.. c la. i.
Ca´c da.ng ca’ i bieˆn do chu´ng toˆi thu
.’ nghieˆ.m chu
.a dem la. i moˆ. t da.ng mo´
.i toˆ’ng qua´t cho ca´c
da˜y tu.. a-ngaˆ˜u-nhieˆn, nhu
.ng da˜ du.a ra du.o.. c moˆ. t soˆ´ da˜y mo´
.i (7 da˜y in daˆ.m trong pha`ˆn da`ˆu
Ba’ng 2) co´ doˆ. phaˆn ky` thaˆ´p ho
.n so vo´.i ca´c taˆ. p dieˆ’m ca´ch de`ˆu va` ca´c da˜y van der Corput.
Co´ theˆ’ su.’ du. ng hu˜
.u hieˆ.u ca´c da˜y na`y deˆ’ ta˘ng toˆ´c doˆ. hoˆ. i tu. trong ca´c t´ınh toa´n theo so
. doˆ`
tu.. a-Monte-Carlo. Ma˘. t kha´c co´ theˆ’ keˆ´t ho
.
. p ca´c da˜y na`y vo´
.i ca´c da˜y thuoˆ. c da.ng kha´c deˆ’ ta. o
ra ca´c da˜y tu.. a-ngaˆ˜u-nhieˆn nhie`ˆu chie`ˆu co´ tu
.o.ng quan yeˆ´u giu˜.a ca´c tha`nh pha`ˆn.
SO SA´NH VA` KIEˆ’M DI.NH DOˆ. PHAˆN KY` CU
’A CA´C DA˜Y 259
TA`I LIEˆ. U THAM KHA
’ O
[1] I. Dupain, T.V. So´s, On the discrepancy of {n.α} sequences, Topics in Classical Number
Theory Vol. 1, North-Holland (1981) 355–387.
[2] S.R. Finch, Discrepancy and Uniformly, Cambridge Univer. Press, 2004.
[3] L. Finschi, Quasi-Monte Carlo: An empirical study on low-discrepancy sequences, Tech-
nical Report, Institute For Operations Research (IFOR), ETH, Zurich 1996.
[4] Frey Tama´s - Szelezsa´n Ja´nos, Sza´mı´ta´stechnika, Akade´miai Kiado´, Budapest 1973.
[5] P. Glasserman, Monte Carlo Methods in Financial Engineering, Springer-Verlag, New
York, 2000.
[6] Hua Loo Keng - Wang Yuan, Applications of Number Theory to Numerical Analysis,
Springer-Verlag, Berlin-Heidelberg and Science Press, Beijing, 1981.
[7] M. Mascagni, “Quasi-Monte Carlo Methods: Where Randomness and Determinism col-
lide”,  ∼mascagni
[8] W. J. Morokoff, R.E. Caflisch, Quasi-random sequences and their discrepancies, SIAM
Journal on Scientific Computing 15 (1994) 1251–1279.
[9] Nguye˜ˆn Va˘n Hu`ng, Bu`i Va˘n Thanh, Nghieˆn cu´.u thu.. c nghieˆ.m t´ınh phaˆn boˆ´ de`ˆu cu’a ca´c
da˜y soˆ´ ngaˆ˜u nhieˆn, gia’ ngaˆ˜u nhieˆn va` tu.. a ngaˆ˜u nhieˆn, Ta.p ch´ı Tin ho. c va` Die`ˆu khieˆ’n
ho. c 22 (1) (2006) 53–62.
[10] I.M. Sobol, Ca´c dieˆ’m laˆ´p da`ˆy khoˆ´i laˆ. p phu
.o.ng nhie`ˆu chie`ˆu, Nha` xuaˆ´t ba’n Znanie,
Moskva, 1985. (tieˆ´ng Nga).
[11] Vu˜ Hoa`i Chu.o.ng, Moˆ. t thuaˆ. t toa´n do
.n gia’n ta. o da˜y soˆ´ tu
.
. a ngaˆ˜u nhieˆn, Ta. p ch´ı Khoa
ho. c va` Coˆng ngheˆ. 40 (soˆ´ DB) (2002) 94–99.
[12] WolframMathWorld, Constants, 
Nhaˆ. n ba`i nga`y 12 - 12 - 2006