(ver )

Transcription

1 2007 ver )

2 Wikipedia) 940 von Neumann) Ulam) Wikipedia)) Blum) : ) 2 i

3 3 3. P NP ) C A ii

4 i i.id = = iii

5 L m RWS i.i.d C random sampler.c random sampler.h m90.c drws.c m90random: DRWS: DRWS: iv

6 N := {, 2,...}, Z := {..., 2,, 0,, 2,...}, R := B x) := B Pr := ) E[X] := X ) Var[X] := X. Ω, F, P) Ω = {0, } L L N), F = 2 Ω, P = P L = Ω, S : {0, } L R ω {0, } L S ω Sω) ) ) S S.2.) S S B A := { ω {0, } L ; Sω) B } P L A) S P L A) 2 S L L.2.2 L = 2 26 ) ω {0, } L ω {0, } L L 2 a b a b a b a b

7 L = MB 3 ) ω {0, } L.3) P L A) S P L A) ω S ω {0, } L S {0, } L ) S ω {0, }- {0, }- g : {0, } n {0, } L n < L {0, }- ω {0, } n ω {0, } n n ) ω gω ) {0, } L S Sgω )) g Sgω )) S P n gω ) A) g P n gω ) A) g S g A.4.2) S ω A ) S S ω A.5.2) 4.2).2 3 4, 94, ,000 2

8 .2. Monte-Carlo method) ) r 32 3 r 0r r r /32 : r ) r 0r /32 ) r 4 X X S S X 2 PrX < c) = /0000 X c {X i } i= X S := min i X i PrS < c) = ) e 4 = S c

9 = 28 7 p 2 7 N 7 S N N S N /N p : 3 N = 2 9 = 524, 288 S 2 9/2 9 [ S9 ] [ S9 ] p p) E = p, V = /4 = Chebyshev s inequality) S 2 9 Pr 2 p ) ) = = 32, ) S 2 9/2 9 p 3 ) = 2 26 = 67, 08, 864 S 9 3 S 2 9 Ω = {0, } 226, 2 Ω, P 2 26 = ) : X : {0, } 27 {0, } Xξ,..., ξ 2 7) := max n n+6 ξ k, ξ,..., ξ 2 7) {0, } 27, k=n ξ,..., ξ 2 7) 7 X = X = 0 S 2 9 : {0, } 226 Z ω = ω,..., ω 2 26) {0, } S 2 9ω) := Xω 2 7 k )+,..., ω 2 7 k) S 2 9 ω A 0 { } A 0 := ω {0, } 226 ; S 2 9ω) p k= ) P 2 26A 0 ) / ω {0, } 226 ω A 0 ω A 0 /32 4 2)

10 ω {0, } 226 {0, } 226 P 2 26A 0 ) ω {0, } = 67, 08, 864 8MB, ) {0, } ω {0, } = l- 2 l l l = 2 l+ ) {0, } = ω {0, } ω {0, } /52 {0, } 226 5/ {0, }- {0, }- {0, }- 6 L {0, } L.4 4 P 2 26A 0 ) /32 P 2 26 ω {0, } 226 ω {0, } 226 P 2 26A 0 ) /32 ω ) IT {0, }- 7 [8] 5

11 .4. 4 S 2 9ω) ω {0, } 226 n < L g : {0, } n {0, } L pseudo-random generator) g ω {0, } n seed) 8 gω ) {0, } L pseudo-random number) 9 ω {0, } n gω ) n N ω g 5 4 g : {0, } 28 {0, } 226 g ω {0, } 28 ω 2 8 = ) S 2 9gω )) ω {0, } g ω {0, } 28 S 2 9gω ) )) P 2 8 p ) 3) g ω S 2 9gω )) S ) 2 g : {0, } n {0, } L n < L A {0, } L secure) P L ω A) P n gω ) A) randomize) 0 x y x y 6

12 5 g : {0, } 28 {0, } 226 2) A 0 ω {0, } 28 Sgω )) S S g g A g A g : {0, } n {0, } L A g := g{0, } n ) {0, } L P L ω A g ) 2 n L P n gω ) A g ) = g A g A.4.3 g : {0, } n {0, } L n < L A {0, } L ω {0, } L ω A A {0, } L 2 2L 2 L.3 A 2 L L = 2 26 A {0, } A ω A ω A A computationally secure cryptographically secure)) ) ) 3.) 5 g S 2 9ω) S 2 9gω )) S 2 9 c, c 2 Z Ac, c 2 ) := {ω ; c S 2 9ω) c 2 } ω Ac, c 2 ) 7

13 p ) S 2 9ω) P 2 26 p 2 9 S 2 9gω ) )) 2 8 P 2 8 p ).5 Monte-Carlo integration) 3.5. i.id.- 3 : X m {0, } m X E[X] X N {X n } N n= S N S N Nm X N ω) := Xω n ), ω n {0, } m, ω = ω,..., ω N ) {0, } Nm, N S N ω) := X n ω). n= S N /N X P Nm P m ) E[S N /N] = E[X]) Var[S N /N] = Var[X]/N S N /N X i.i.d.- 2 S N P Nm N E[X] ) δ Var[X] Nδ 2 3 A := { ω {0, } Nm ; S N ω) N } E[X] δ ω {0, } Nm ω A ω A 2 {X n } N n= i.i.d. ) 3 E[X] Var[X] Var[X] 3 X ) 8 4)

14 .5.2 {0, } m 4 [4] Lecture 5, cf. [0]) N 2 m 5 g : {0, } 2m {0, } Nm : ω ω P 2m P Nm E[S N gω ))] = E[S N ω)] = NE[X]), Var[S N gω ))] = Var[S N ω)] = NVar[X]).. g : GF2 m ) 2 m 2 φ : GF2 m ) {0, } m ψ : GF2 m ) {, 2, 3,..., 2 m } {0, } m {, 2, 3,..., 2 m } GF2 m ) ω := x, α) GF2 m ) GF2 m ) {0, } 2m Z n ω ) := x + nα, n GF2 m ) {, 2, 3,..., 2 m } g : {0, } 2m {0, } Nm gω ) := Z ω ), Z 2 ω ),..., Z N ω )) GF2 m ) N {0, } Nm ω GF2 m ) 2 {0, } 2m P 2m Z n ω ) {0, } m E[S N gω ))] = E[S N ω)]. {Z n ω )} 2m n= a, b GF2m ) {0, } m n < n 2 m P 2m Z n ω ) = a, Z n ω ) = b) = P 2m x + nα = a, x + n α = b ) x, α) GF2 m ) x + nα = a x + n α = b x 0, α 0 ) GF2 m ) GF2 m ) P 2m Z n ω ) = a, Z n ω ) = b) = P 2m {x 0, α 0 )}) = 2 2m = P 2m Z n ω ) = a)p 2m Z n ω ) = b) 4 [0] {0, } m {0, } m 2 m ) N < 2 m 9

15 N Var[S N gω ))] = E XZn ω )) E[X] ) 2 = = N n= n= n = N E [ XZ n ω )) E[X] ) XZ n ω )) E[X] )] N E [ XZn ω )) E[X] ) ] 2 n= +2 E [ XZ n ω )) E[X] ) XZ n ω )) E[X] )] n<n N = NVar[X]. g g S N gω ))/N E[X] 4) A P 2m gω S N gω ) )) ) A ) = P 2m E[X] N δ Var[X] Nδ 2 S N ω) g A g g : {0, } 28 {0, } P 2 8 S 2 9gω ) )) p cf.3)) ω {0, } 28 = {0, } 256 2m ω {0, } 2m g : {0, } n {0, } 2m n 2m ω {0, } 2m g g : {0, } n {0, } 2m {0, } Nm A 2 2 X PrX < c) = /0000 X, X 2,..., X X S := i= {Xi <c} ) E[S] = 4, Var[S] = 40000Var[ {Xi <c}] = < 4. PrS ) Pr S 4 < 4) = 3 4. min i X i 3/4 c 0

16 3 g m GF2 m ) ) ω {0, } n ω g ω = x, α) = 0, 0) GF2 m ) GF2 m ) Z n ω ) 0 GF2 m ) S 5 ω {0, }- g ω Sgω )) ω {0, } L {0, }- 4 JIS[8] p.7 ) ) ω ω

17 .6.2 [8] :. ) 2. ω g gω ) 3. g. A 2. P n gω ) A) 3. P L ω A) g A

18 2 {0, }- {0, }- 0 ) {0, }- {0, }- {0, }- C Pascal... ) = Martin- Löf) = 7) partial recursive function [, 27]) 6. ) zero : N 0 N, zero ) := 0 suc : N N, sucx) := x + p n i : N n N, p n i x,..., x n ) := x i, i =,..., n. 2. ) g : N m N g : N n N f : N n N, f x,..., x n ) := gg x,..., x n ),..., g m x,..., x n )) 3. ) g : N n N h : N n+2 N f : N n+ N, f x,..., x n, 0) := gx,..., x n ) f x,..., x n, y + ) := hx,..., x n, y, f x,..., x n, y)) 6 N n N m - g : N n N m 3

19 4. ) g : N n N =,..., m 5. ) p : N n+ N min g : N n + +n m N m, g := g,..., g m ) µ y px,..., x n, y)) := min{y N px,..., x n, y) = } 6. 5 N m N n ) 4 primitive recursive function) {y N px,..., x n, y) = } µ y px,..., x n, y)) recursive function) 2 ) l N B : N N l N A : N l N e A N Be A, x) = Ax), x N l. 2 B enumerating function) e A A Gödel number) [, 27]) A universal Turing machine [] ) {0, }- 2 e A Be, x) e e x 5 2 B : N N N 2 hx) := Bx, x) + e h N hx) = Be h, x) x = e h Be h, e h ) + = he h ) = Be h, e h ) ) 7 7 4

20 {0, } := n N {0}{0, } n {0, } {0, }- 0 {0, }- 2. p {0, } p {0, } n n Lp) N {0} p ) 3. {0, } canonical order) N : x, y {0, } x y {0, }- x y 2 5 ) A : {0, } {0, } {0, } N N N A A x {0, } y {0, } min = 8 K A y x) := min{lp) p {0, }, Ap, x) = y } 5 A A p A p x y K A y x) A x y p K A A 3 A 0 : {0, } {0, } {0, } A : {0, } {0, } {0, } c A0 A N : K A0 y x) K A y x) + c A0 A, x, y {0, }. A 0 universal algorithm asymptotically optimal algoruthm)). e, p {0, } ē p {0, } : e = e,..., e m ), p = p,..., p l ) ē p := e, e,..., e m, e m, 0,, p,..., p l ) {0, } 2m+2+l 5) B 2 l = 2) A 0 A 0 ē p, x) := Be, p, x), e, p, x {0, }. 8 min = 5

21 z = ē p Az, x) A 0 ē A p, x) = Ap, x) K A0 y x) K A y x) + 2Le A ) + 2, x, y {0, }. c A0 A := 2Le A ) A 0 c > 0 K A0 y x) K A 0 y x) < c, x, y {0, }. 6) 6 A 0 Ky x) := K A0 y x), x, y {0, } x y x Ky) y Kolmogorov s complexity) 6 A 0 6) c 4 i) c > 0 x {0, } n Kx n) n + c ii) n > c > 0 9 #{x {0, } n Kx n) n c } 2 n 2 n c. i) x Ax, n) := x K A x n) = n ii) n c p 2 n c 20 4 Kx) c n x {0, } n Kx) n Kx) n x {0, } n random number) 6 π ) π x {0, } x {0, } 5 x {0, } 5 Kx) 9 #

22 . Kx) p n function p n : {0, } - ; begin l := l x {0, } l Kx) n x end; p n {0, }- {0, }- x Kx) n x p n Kx) L n L n n n L n = Olog n) 2L n < n n Kx) x Kx) n > 2L n K 2.2 = N {0, } U i) U recursively enumerable set) φ : N N {0, } 2 U = φn) ii) U m := {x {0, } m, x) U} U m U m+ m N iii) # U m {0, } n ) 2 n m n > m > 0 U m 2 m U m U x) := max{m N x U m } 7) m U x) x U U 6 [5]) V universal test) : U c = c VU N U m+c V m, m N. 8) U 2 m c x {0, } V 2 m 2 φ [27].7.4) φ φn) φ N 7

23 . U φ U {φ U } U: ψ : N N N {0, } U e U N ψe U, ) = φ U ) h : N N N {0, } hē n) := e, ψe, n)) ē n 5) ) Ṽ := hn) Ṽ U Ṽ eu := {m, x) e U, m, x) Ṽ} = ψe U, N) = U. τ : N N {0, } N {0, } τe, m + e, x) := m, x) e, m, x) m e τe, m, x) ) V := τṽ) V V m = e= Ṽ e ) m+e V m V m+ 22 #{x V m Lx) = n} #{x Ṽ e ) m+e Lx) = n} e= n m e= 2 n m+e) 2 n m V U U m+eu V m 8) 7) m U x) m V x) + c 9) V V c N m V x) m V x) < c, x {0, }, V m V x) mx) = Kx Lx)) Lx) 7 [5]) c N Lx) Kx Lx)) mx) c, x {0, }. 0). ) Lx) Kx Lx)) mx) + c : 22 e e U Ṽ e = U := {m, x) Kx Lx)) < Lx) m} 8

24 4ii) m U x) = Lx) Kx Lx)) 9) mx) + c > Lx) Kx Lx)) 2) Kx Lx)) Lx) mx) + c : V φ φn) = V φ A : {0, } {0, } {0, } φi) =: m i, x i ) V A } {{ } Lx ) m, Lx )) = : x m, Lx )) = m 2, Lx 2 )) m, Lx )) m 2, Lx 2 )) A } {{ } Lx 2 ) m 2, Lx 2 )) = : x 2 ) A } {{ } Lx 2 ) m 2, Lx 2 )) = : x 2 A V m, Lx)) m, x) 2 Lx) m Lx) m A well-defined) K A x Lx)) = Lx) mx), 0) 0) c Lx) Kx Lx)) Lx) mx) Kx Lx)) Lx) computable) ) {0, }- 0 0 N 0 N maximal recursive null set) N random sequence) 0 y {0, } Cy) y {0, }- ) P 9

25 {0, } ) A {0, } 0 m N y m) k {0, } U m = Cy m) k ) A 2) k P Cy m) k ) ) = 2 Lym) ) k < 2 m 3) k k U = {m, x) N {0, } x U m } 4) m, x) U, n m Cy) Cx) = n, y) U 5) A 2) 5) U U m 2 m U sequencial test) U : V V m+c U m, m =, 2,... 6) c > 0 U V U universal sequencial test) [5]) N N 7 π 2 π 20

26 time complexity) [3, 3] [4, 7] 8. f : {0, } {0, } : n N f {0,} rn) =: f n : {0, } rn) {0, } sn) f = { f n } n f f x) ) x {0, } rn) f n T f n) 2. {ln)} n c > 0 n ln) = On c ) 3. f = { f n } n rn), sn) f n : {0, } rn) {0, } sn) f n T f n) 4. Y U {0, } sn) Y {0, } sn) Y Y Pr Y 5. A = {A n } n A n : {0, } rn) {0, } sn) {0, } tn) x {0, } rn) Y U {0, } sn) A n x, Y) T A n) A n x, y) Y A n : {0, } rn) {0, } tn) 9 g n : {0, } n {0, } ln) ln) > n g = {g n } n N pseudorandom generator) 7 g : {0, } n {0, } L n < L 9 n g n : {0, } n {0, } ln) 2

27 Z n U {0, } n. g n {0, } ln) - g n Z n ) ln) > n g n Z n ) {0, } ln) A = {A n } n A n : {0, } ln) {0, } ) δ g,a n) := PrZln) An Z ln) ) = ) Pr Zn A n g n Z n )) = ) 7) 23 ln) n g n A δ g,a n) A δ g,a n) A T A n) S g,a n) := T An) δ g,a n) 0 A S g,a n) g 24 T A n) S g,a n) 0 A : {0, }- {0, }- XOReXclusive OR ) XOR ) cf. [4, 7]) 23 A Y 7) Y 24 ) 25 e t/000 t t t 00 22

28 8 0 A adversary A cryptographically secure pseudorandom generator) W Z ln) U {0, } ln) : W := ψz ln) ) ψ ln) Z ln) g n Z n ) Z n U {0, } n W W := ψg n Z n )) W W W W F W t) := Pr Zln) W t) F W t) := Pr Zn W t) g = {g n } n F W t) F W t) A n A n x) := {ψx) t} x {0, } ln) ψ A n F W t) F W t) = PrZln) An Z ln) ) = ) Pr Zn A n g n Z n )) = ) 3..3 P NP P := NP := L {0, } A : {0, } {0, }, s.t. x {0, } x L Ax) = ) L {0, } A : {0, } {0, }, s.t. x {0, } x L PrAx) = ) > 0) P NP P NP 23

29 8 P = NP 26. ln) > n g = {g n } n g n : {0, } n {0, } ln) M n : {0, } ln) {0, } n {0, }, if g n x) = y M n y, x) := 0, if g n x) y M = {M n } n L := {y {0, } n N, y {0, } ln), x {0, } n, M n y, x) = } L NP P = NP L P A = {A n } n A n : {0, } ln) {0, } y L A n y) = A Z n U {0, } n Z ln) U {0, } ln) Pr Zn A n g n Z n )) = ) =, Pr Zln) A n Z ln) ) = ) 2n 2 ln), δ g,a n) 2 n ln) T A n) S g,a n) = T A n)/δ g,a n) g P NP P NP 3..4 g = {g n } n g n : {0, } n {0, } ln) Z U {0, } n I U {, 2,..., ln)} Pr I,Z à = {à n } n à n : {,..., ln)} {0, } ln) {0, } ) δ g,ã n) = Pr I,Z Ãn I, g n Z) {,...,I } ) = g n Z) I ) 2 g n Z) i i g n Z) {,...,i} {0, } ln) g n Z) i 0 ln) i { }} { g n Z) {,...,i} := g n Z), g n Z) 2,..., g n Z) i, 0,..., 0). 26 P NP 24

30 à S g,ã n) := T à n) δ g,ã n) g 9 g = {g n }. ) g à T à n) S g,ã n) I U {,..., ln)} A : {0, } ln) {0, } A n x) :=, if à n I, x {,...,I } ) = x I 0, if à n I, x {,...,I } ) x I x {0, } ln), δ g,a n) = PrZln) An Z ln) ) = ) Pr Zn A n g n Z n )) = ) = 2 Pr I,Z n Ãn I, g n Z n ) {,...,I } ) = f n Z n ) ) I = δ g,ã n), T A n) S g,a n) g 2) g A T A n) S g,a n) Y U {0, } ln) W U {0, } i {,..., ln)} x {0, } ln) Y i, if A n x,..., x i, Y i,..., Y ln) ) = Ãi, x) := W, if A n x,..., x i, Y i,..., Y ln) ) = 0 S g,ã n) g X := g n Z n ), Pr := Pr Zn,Y,W Pr à n i, X {,...,i } ) = X i ) 2 = Pr X i = Y i, A n X {,...,i }, Y {i,...,ln)} ) = ) +Pr X i = W, A n X {,...,i }, Y {i,...,ln)} ) = 0 ) 2 = Pr X i = Y i, A n X {,...,i}, Y {i+,...,ln)} ) = ) + 2 Pr A n X {,...,i }, Y {i,...,ln)} ) = 0 ) 2 = 2 Pr A n X {,...,i}, Y {i+,...,ln)} ) = ) + Pr An X {,...,i }, Y {i,...,ln)} ) = )) 2 2 = 2 Pr A n X {,...,i}, Y {i+,...,ln)} ) = ) 2 Pr A n X {,...,i }, Y {i,...,ln)} ) = ) 25

31 δ g,ã n) = ln) = 2 = ln) i= ln) Pr ) ) Ã n i, X {,...,i } ) = X i 2 ln) Pr An X {,...,i}, Y {i+,...,ln)} ) = ) i= Pr A n X {,...,i }, Y {i,...,ln)} ) = )) 2ln) PrA nx) = ) PrA n Y) = )) δ g,ã n) = δ g,a n) 2ln) T Ã n) S g,ã n) ω i := f ω i n,..., ω i ) 9 9 BBS [3]) 27 p, q p = 3mod 4) q = 3mod 4) 28 N = pq, 2,..., N N QRN) ) x 0 QRN) x n := Fx n ) = x 2 n mod N, n =, 2,..., y n := Gx n ) = x n mod 2 p, q F p, q 29 x 0 {y n } m n=0 y m+ {y n } n=0 27 BBS QRN) mod M M 29 F F P NP ) [4]) 26

32 3.2 /2 0) [0, ) x + y) mod T -dimensional torus) d i x) x T 2 i 0 ) 30 x = d i x)2 i. 8) i= 2. T, B, P) Lebesgue) B T = [0, ) P 3 T, B, P) k k ) T k, B k, P k ) 3. m N D m := {i2 m i = 0,..., 2 m } T 9) I m := { [a, b) a, b D m } ) B m B m I m 4. m N 32 x m := 2 m x /2 m D m, x T. 20) x := x {Y n m) x; α)} n=0 3 x, α T m N Y m) n x; α) := m d i x + nα) mod 2), n = 0,... 2) i= d i ) 8) 30 /2 = 0. = d /2) = 3 B P σ- ) B 32 t t 27

33 2) 2 : x, α T x := x m+ D m+, α := α m+ D m+ 22) F m+,α : Ω Ω G m : Ω {0, } F x) = F m+,α x) := x + α) mod, 23) m G x) = G m x) := d i x) mod 2, 24) i= Y m) n x; α) = GF n x)), n = 0,,..., 2. F n x) x F n {Y n m) ; α)} 2 n=0 : D m+ {0, } m+ {0, } 2 33 α m Weyl transformation) α T T x x + α 5 [25] {Y n m) ; α)} 2 n=0 m 34 G m α 2 l N 0 < k <... < k l {Y m) k x; α)} l 2 =0 Ym) k l x; α) : l F m) k 0,..., k l ; α) := P =0 Y m) k 0 k 0 < < k l, l N. ; α) =, 25) A : {0, } l {0, } {yk0 + +y Ay k0,..., y kl 2 ) := kl 2 = }, if Fm) k 0, k,..., k l ; α), 2 {yk0 + +y kl 2 = }, if Fm) k 0, k,..., k l ; α) < N m 34 22) m 28

34 A Y m) k l x; α) AY m) k 0 x; α),..., Y m) k l 2 x; α)) ) P AY m) k 0,..., Y m) k l2 ) = Y m) k l = Fm) k 0, k,..., k l ; α) ) 2 F m) k 0, k,..., k l ; α) /2 P ) AY m) k 0,..., Y m) k l 2 ) = Y m) k l = P Y m) k Y m) k l = ) = F m) k 0, k,..., k l ; α), F m) k 0, k,..., k l ; α) < /2 P ) AY m) k 0,..., Y m) k l 2 ) = Y m) k l = P Y m) k Y m) k l = ) = F m) k 0, k,..., k l ; α), 26) A /2 26) 0 P α T l N 0 < k <... < k l 0 < ρ < ) P AY m) k 0,..., Y m) k l2 ) = Y m) k l 2 = F m) k 0, k,..., k l ; α) 2 = Oρm ), m. A m l = ρ > ) + 7)/8 = {Y n m) ; α)} n=0 i) ɛ n {0, } n = 0,,..., k P Y n m) ; α) = ɛ n, n = 0,..., k ) k l = 2 k 2ɛ k ) 2F m) k 0,..., k l ; α) ) +. l= 0 k 0 < <k l k =0 ii) l N F m) k 0,..., k l ; α) = /2 iii) F m) k 0,..., k l ; α) = F m) 0, k k 0,..., k l k 0 ; α) k 0 = 0 29

35 l F m) 0, k,..., k l ; α) α T 35 α := k α, =,..., l, α m)l := α m, α m)u := α m + 2 m mod ), β m) := 2 m α α m)l ), {,..., l } σm, ) 36 β m) σm,0) :=, βm) σm,l) > β m) σm,) βm) σm,2) > βm) σm,l ) 0. 27) := 0 α m)u α m),s σm, ) σm, ) :=, s ) α m)l σm, ), > s ) α m),s := α m),s,..., α m),s ), s = 0,,..., l, 2 D := D m. B ) D l = F m) 0, k,..., k l ; α) = l l s=0 m N β m) σm,s) βm) σm,s+)) Bα m),s ). 28) l { }} { D D Bα m),s ) Bα 0),s ) = 0, s = 0,,..., l, Bα m),s 2 Bαm ),s 2 ) + 2 Bαm ),s +s 2 ) s ) ) = Bα m ),s 2 ) ) + Bα m ),s +s 2 ) ) s ) 2 2 s, s 2 s := l = d m α m),s ), s 2 := s d m α σm, ) ). 29) = 35 t t 0 t = t t ) σm, ) 28) 30

36 [9, 34]) P α T {Y n m) ; α)} n=0 m ɛ n {0, } n = 0,,..., k 0 < ρ < P Y n m) ; α) = ɛ n, n = 0,..., k ) 2 k = Oρ m ), m. 3 [35]) α T {Y n m) ; α)} n=0 m ɛ n {0, } n = 0,,..., k lim P Y n m) ; α) = ɛ n, n = 0,..., k ) = 2 k. m {Y n m) ; α)} n=0 N m) k; α) := 6 F m) 0, k; α) 2 ) 2 30) η m) n;k ; α) := Ym) n ; α) + Y m) n+k ; α) mod 2) S m) N;k ; α) := N η m) n;k N ; α) n=0 {Y n m) ; α)} n=0 S N σ 2 N k N E [ S m) N;k ; α)] F m) 0, k; α) = 2 := /4N) 3) S m) N;k ; α) 2 < 2σ N = 32) N {Y n m) ; α)} n=0 32) 95% 37 [32, 33, 34, 35] 2 3

37 m N = N m) k; α) ) 32) 92% ). m {Y n m) ; α)} n=0 S N {η m) n ; α)} n=0 Sm) N;k ; α) σ2 N N S m) N;k ; α) N/2+a, σ2 N ) a = F m) 0, k; α) /2 N = N m) k; α) = /6a 2 ) a = σ N /2 Sm) N;k 2 < 2σ N 5σ ) N 2 < Sm) N;k 2 + a < 3σ N 2 3σ ) N 2 < Sm) N;k 2 + a < 5σ N 2 3/2 5/2 92% 2π e x2 /2 dx = a > 0) a < 0) 3) {Y n m) ; α)} n=0 N m) k; α) m m 8 α = 5 )/2 m = 40 k = 305 F 40) 0, 305; α) = F 40) 0, 305; α) 2 ) 2 = = ) 2 S 40) 7022;305 2 <, 33) 7022 : {Y 40) n 0; α)} n= i =, 2,..., 0 6 p i := #{7022i ) i η40) ;305 0; α) = }, 7022 p i ) 0 6 = 0 6 p i /2) = i= 06 6 p i = 0 p i ) 2 = i= 32

38 {Y n m) } n=0 /4 7022) = % p i 2 < 7022 i ) 92.54%. 5 α =. 2 K N a m) K) := max k K Fm) 0, k; α) 2, Nm) c K) := 6 a m) K) ), 34) 2 N c m) K) 38 34) K = 0, 000 a m) K) ) k : m a m) 0000) k) N m) c 0000) b m) 6) k, ) ,9, ) ) ) ) ) ) ) ) ) K- ) l F m) 0, k,..., k l ; α), k < < k l K, K K K = 6 b m) 6) := max k <...<k l 6 Fm) 0, k,..., k l ; α) 2 38 [9] critical sample number N c m) K) 4 33

39 k,... K N m max k < <k l K Fm) 0, k,..., k l ; α) 2 = max k K Fm) 0, k; α) ) {Y n m) } n=0 35) {, }- {Xm) n } n=0 {Y n m) } n=0 {Xm) n } n=0 {r i } i= Rademacher functions) r i x) := 2d i x), x T, i N, α [0, ) m X m) n x; α) := m r i x + nα), n N, 35) i= {X m) n } n=0 {Ym) } n=0 n X n m) x; α) = 2Y n m) x; α), Y n m) x; α) = X m) n x; α) ). 2 : k, h N ɛ {, } k P X m) 0 ; α),..., X m) k ; α)) = ɛ) = P X m) h ; α),..., X m) k +h ; α)) = ɛ) 36) ) 36) 3.3. {X n m) } n=0 34

40 i) l E m) k 0,..., k l ; α) := E X m) k ; α), 0 k 0 <... < k l, l N. ɛ n {, } P X n m) ; α) = ɛ n, n = 0,..., k ) = 2 k k l= =0 0 k 0 <...<k l k l ii) l N E m) k 0,..., k l ; α) = 0 iii) E m) k 0,..., k l ; α) = E m) 0, k k 0,..., k l k 0 ; α) l= 0 k 0 <...<k l k =0 =0 ɛ k E m) k 0,..., k l ; α) +. 37). i) ɛ i {, } k l ɛk X m) k x; α) ) k = + ɛn X n m) x; α) ). 38) k l= 0 k 0 <...<k l k n=0 l =0 n=0 ɛ k E m) k 0,..., k l ; α). 39) k E + ɛn X n m) x; α) ). 40) 40) E[ ] n = 0,..., k X n m) x; α) = ɛ n 2 k 0 40) 2 k P X m) n ; α) = ɛ n, n = 0,..., k ). 4) 39) 4) 37) ii) r x + ) = r 2 x) r i x + ) = r 2 ix) i 2 x + 2 ) ; α X m) k l = X m) k x; α), x [0, ), 42) X m) 0 x; α) X m) k l x; α) = X m) 0 x + 2 ) ; α X m) k l x + ) 2 ; α X m) 0 x; α) X m) k l x; α) = /2 ii) iii) 36) 35 =

41 3.3.2 {X n m) } n=0 E m) 0, k,..., kl ; α) = A ) D l = l s=0 β m) σm,s) βm) σm,s+)) Aα m),s ). 43) l { }} { D D Aα m),s ) Aα 0),s ) =, s = 0,,..., l, Aα m),s ) = )s Aα m ),s 2 ) + Aα m ),s +s 2 ) ). 2 s, s 2 l m E m) 0, k,..., k l ; α) = E r i x)r i x + k α) r i x + k l α). i= α = α,..., α l ) [0, ) l m A m) α) := E r i x)r i x + α ) r i x + α l ) 44) 2 α = α,..., α l ) D m ) l 39 i= A m ) α) = A m) α), m > m.. A m ) α) m A m ) α) = E r i x)r i x + α ) r i x + α l ) i= m i=m+ α D m ) l i > m 39 D m 9) [0, ) r i x)r i x + α ) r i x + α l ). r i x) = r i x + α ), =,..., l. 36

42 l m i=m+ r i x)r i x + α ) r i x + α l ) = m i=m+ r i x) l = m i= Am ) α) = A m) α). 4 α D l Aα) := lim m A m) α) A α m),s α α [0, ) l α = α,..., α l ) [0, ) l α m)l := α m)l,..., α m)l l ), αm)l := α m, α m)l D m ) l α m)u := α m + 2 m mod ) α D m ) α α D m ) α m)u := α m)u,..., α m)u l ) α m)u D m ) l l { }} { 3 i) A 0,..., 0 ) =. ii) α = α,..., α l ) D m ) l r := l = d m α ) Aα) = )r Aα m )U ) + Aα m )L ) ). 45) 2. i) l l { }} { A 0,..., 0 ) = E l m { }} { r i x) r i x) =. i= 37

43 ii) m r i x + α + 2 m) d m α ) =, d m x) = ) i= m m r i x + α 2 m) d m α ) =, d m x) = 0 ) i= r i x + α ) = m ) i= r i x + α d m α ) = 0, d m x) = ) i= m ) r i x + α d m α ) = 0 r m x + α ) = r m x) i= d m α ) = 0, d m x) = 0 ) m r i x + α ) = i= m r i x + α ) r m x). i= 3 4 d m α ) = r m x + α ) = r m x) d m x) = d m x + α ) = 0 i =,..., m d i x + α ) = d i x + α + 2 m ) r i x + α ) = r i x + α + 2 m ) m r i x + α ) = i= m r i x + α ) r m x + α ) = i= m r i x + α + 2 m) i= d m α ) = d m x) = 0 d m x + α ) = i =,..., m d i x+α ) = d i x+α 2 m ) r i x+α ) = r i x+α 2 m ) m r i x + α ) = i= m m r i x + α ) r m x + α ) = r i x + α 2 m) i= i= 2, r, d m α ) = 0, r + l. r = l = d m α ) Aα) = E m r ix) i= r r i x + α ) = l =r+ r i x + α ) 38

44 m = E r i x) i= m +E r i x) i= r m = i= l r i x + α + 2 m) =r+ r m r i x + α 2 m) = i= m l i= =r+ i= r i x + α ) ; d mx) = m r i x + α ) ; d m x) = 0. {d m x) = ɛ} ɛ = 0 ) = m l m 2 E r i x) r i x + α m )U ) ) l r i= = i= + m l m 2 E r i x) i= = i= r i x + α m )L ) ) r r l r r l r Aα) = 2 Aαm )U ) + 2 Aαm )L ), Aα) = 2 Aαm )U ) 2 Aαm )L ).. 3 α D l Aα). C := 2 m s= s 2 β m) σm, ) m 2, s m 2 β m) m σm, +) 2 m, = 0,,..., l, i =,..., m x C = d i x + α σm,p) ) = d i x + α m)u σm,p)), p, d i x + α m)l σm,p)), + p l, = E m) 0, k,..., k l ; α) l m l E r ix) r i x + α m)u σm,p) ) r i x + α m)l =0 i= p= p= + σm,p) ) ; C 39

45 C = l =0 PC )E m r ix) i= p= l r i x + α m)u σm,p) ) p= + r i x + α m)l σm,p) ) = l =0 PC )Aα m), ). PC ) = β m) σm, ) βm) σm, +) 3 α m),s ) m )U = α m ),s +s 2, 46) α m),s ) m )L = α m ),s 2, 47) 47) { ) # α m),s m )L } = α m )U = s 2 48) implications α m),s α m)u = α m),s = α m)l = ) α m),s m )L = α m )L = ) α m),s m )L α m )U, 49) α m),s = α m)u = ) α m),s m )U = α m )U, 50) d m α m),s ) = ) α m),s m )L ) α m),s m )U = ) α m),s m )L α m )U, 5) d m α m),s ) = 0 ) α m),s m )L ) = α m),s m )U. 52) 49) 5) ) α m),s m )L = α m )U = α m),s = α m)u d m α m),s ) = 0 40

46 50) 52) ) α m),s m )L = α m )U α m),s = α m)u d m α m),s ) = 0 { ) α m),s m )L } = α m )U = = = = { } α m),s = α m)u, d m α m),s ) = 0 { } α m),s σm, ) = αm)u σm, ), d mα m),s σm, ) ) = 0 { } s, d m α m),s σm, ) ) = d mα m)u σm, ) ) = 0 { } s, d m α m)l σm, ) ) = d mα σm, ) ) =. s 2 48) 46) { ) # α m),s m )U } { = α m )U ) = # α m),s m )U } α m )L = s + s 2 53) ) α m),s m )U α m )L α m),s ) m )U α m),s ) m )L = α m )L α m),s α m),s ) m )U = α m),s ) m )U α m),s ) m )L α m )L ) m )L ) α m),s m )L α m )L 52) { α m),s ) m )U α m),s ) m )L } = { d m α m),s ) = }, s 48) { ) # α m),s m )L } { α m )L ) = # α m),s m )L = α m )U } = s 2, 53) 4

47 : l N l k < < k l α lim m Em) 0, k,..., k l ; α) = 0 : 3. m s /8) -3/8) +/4) -/2) 0) -) /6) 0 ) -/2 ) 0 ) +) +) /4) -3/8) +/4) -/2) 0) -) /6) +/2) +/2) +) +) +) ) ) ) ) l = 4 α = α, α 2, α 3 ) α = , α 2 = , α 3 = m = 6 α 6)L = 0.000, α 6)U α 6)L 2 = 0.00, α 6)U α 6)L 3 = 0.00, α 6)U = 0.00, 2 = 0.000, 3 =

48 > β 6) = > β 6) 2 = > β 6) 3 = > 0 σ6, ) = =, 2, 3 ) α 6), = 0.00, 0.00, 0.000, 0.000, = 0,, 2, m m = 0,..., 6) s s = 0,..., 3) α m),s α 6),0 ) Aα m),s ) 3 Aα m),s ) m 45) 45) ) r Aα 6),2 ) = 2 Aα 5), ) + Aα 5),3 ) ) 54) 3 m Aα m),s ) 0 54) Aα 6),2 ) m = = Aα 2), ) Aα 6),2 ) 2 4 Aα 2), ) 2 4 Aα 2), ) Aα 6),2 ) 2 ) 2 max 4 s=0,...,3 Aα2),s ) 3 m Aα m),s ) 0 8 ) 3 4 α = α,..., α l ) [0, ) \ D) l m i) ii) iii) d m α m)u ) = d m α m),l ) α m),0 m )L = α m ),0. α m),l ) m )U = α m ),l. ) d m α m),0 ) = d m α m)l ) = d m α ),. 43

49 2 3 2:. m s /8) -3/8) +/4) -/2) 0) -) +) /6) /4) /6) ) /8) /2) /2 ) /4) /2) ) /2) ) ) ) ) ) ) ) ) ) ) iv) v) l = d m α m),0 ) l = α m),l ) m )L = α m),0 ) m )U. d m α m),l ) mod 2).. i) α m),l α m)u α m),0 = α m)u, α m)l, = α m)l, d m α ) = d m α m)l ). ii) s 2 29) s = 0 s 2 = 0 ii) iii) i) s = l s = l = d m α m),l ) = l = dm α ) ) l = l d m α ). = s 2 = l = d m α σm, ) ) = l = d m α ). 44

50 s = l s + s 2 = l iii) iv) i) l = d m α m),0 ) = l = dm α m),l ) ) l iv) v) p, q N ) α m),l m )L = α m ),p, ) α m),0 m )U = α m ),q, 29) i) l = l d m α m),l ) 55) = p = q = l = l = d m α σm, ) ) = d m α m),0 ) = l = l = d m α ), d m α ), p = q 5 L : D m ) l α α m )L D m ) l U : D m ) l α α m )U D m ) l L p U p D m ) l D m p ) l 5 α = α,..., α l ) [0, ) \ D) l r N i) L r α m+r),l = α m),0 s, L r α m+r),s = α m),0 ii) U r α m+r),0 = α m),l s, U r α m+r),s = α m),l iii) =,..., l, m + p m + r, d m+p α ) = 0 56) s, L r α m+r),s = α m),0 iv) =,..., l, m + p m + r, d m+p α ) = 57) s, U r α m+r),s = α m),l 45

51 . i) 29) s 2 s 2 s i) ii) 53) s + s 2 s ii) iii) 56) 4i) p d m+p α m+r),l ) = α m+p ),l > α m+p)l 4ii) L r α m+r),l = α m),0 i) iii) iv) 57) p α m+p ),0 < α m+p)u 4iii) U r α m+r),0 = α m),l ii) iv) 6 [35]) r := 3k l α α := k α 56) 57) m. 56) 57) m N N m > N m d m+ α m ) =... = d m+r α m ) = 0 d m+ α m ) =... = d m+r α m ) = α α 2 N + Step. m > N d m+ α), d m+2 α),..., d m+r k m α) k m k m 2 m α k m α 2 R := k m 2 m α 2 R + 2 m k m α = k m 2 m α + k m 2 m α = k m 2 m α. 2R + d m+ k m α) + 2 m+ k m α = k m d m+ α) + k m 2 m+ α. k m 2 m+ α 2 m+ k m α = k m 2 m+ α + k m 2 m+ α 2 m+ k m α = k m 2 m+ α 0 k m 2 m+ α 2 m+ k m α < k m 2R + d m k m α) k m Q R 2 Q = d m+ α), R 2 = k m 2 m+ α 2 m+ k m α. 2R 2 +d m+ k m α) k m Q 2 R 3 R m+ k m α = k m 2 m+ α Q 2 = d m+2 α), R 3 = k m 2 m+2 α 2 m+2 k m α. 46

52 2R u +d m +u k m α) = k m Q u +R u+ 0 R u+ < k m Q u, R u+ ) d m+ k m α) =... = d m+r k m α) Q u, R u+ ) R u R u k m k m Q u = d m+u α) k m Step 2. a0), a),..., ap ) w 2k p aq), aq + ),..., aq + p ) 0 q < q + p p p 2w w aq), aq + ),..., aq + p ) w w w. u p w u q = w + v Z 0 v < w v + w < 2k p au) = aq + w + v) = aq + v) = aq + v + w ) = aq + w + v + w ) = au + w ). w a0), a),..., ap ) w w = w Step 3. m > N Step d m+ α),..., d m+r k m α) k m d m+ α),..., d m+r kl α) w m d m+2 α),..., d m+r+ kl α) w m Step 2 w m = w m d m+ α),..., d m+r+ kl α) w α N + w 3 l k < < k l α lim m Em) 0, k,..., k l ; α) = 0 58) α := α,..., α l ), α := k α, 59) 58) lim max Aα m),s ) = 0 60) m 0 s l 3 Aα m),s ) = ± 2 { AUα m),s ) + ALα m),s ) } 6) 6) 7 max ),q q l Aαm ) max q l Aαm),q ), m > m. 47

53 8 α r = 3k l {m n } n=0 6 m 2 m n + r + 2 m n+ max Aα mn+r),s ) ) max Aα mn 2),s ). s l. 6) r 2 r+ s l Aα m n+r),s ) = 2 r ɛ U raur α m n+r),s ) + 2 r ɛ LU r ALUr α m n+r),s ) r ɛ UL r AULr α m n+r),s ) + 2 r ɛ L ralr α m n+r),s ), 62) ɛ U r,..., ɛ L r = ± 5 s U r α m n+r),s = α m n),l, L r α m n+r),s = α m n),0, 63) Case. ɛ U r = ɛ L r ɛ, ɛ = ± 6) { ɛ U rau r α mn+r),s ) = ɛ U rɛ 2 AUr+ α mn+r),s ) + } 2 ALUr α mn+r),s ), { ɛ L ral r α mn+r),s ) = ɛ L rɛ 2 AULr α mn+r),s ) + } 2 ALr+ α mn+r),s ). 64) 3 4iv) ɛ ɛ 63) 4v) LU r α m n+r),s = UL r α m n+r),s 65) 64) 62) Aα m n+r),s ) = ɛ U rɛ ɛ L rɛ 65) 2 ɛ r+ U rɛaur+ α mn+r),s ) + 2 ɛ r+ U rɛalur α mn+r),s ) ɛ r+ L rɛ AUL r α mn+r),s ) + 2 ɛ r+ L rɛ AL r+ α mn+r),s ) 66) 2 ɛ r+ U rɛalur α mn+r),s ) + 2 ɛ r+ L rɛ AUL r α mn+r),s ) = 0. 67) Aα mn+r),s ) ) 2 2 r+ max 0 q l Aα mn ),q ). 68) Case 2. ɛ U r ɛ L r 66) ɛ U rɛ = ɛ L rɛ 62) 66) Case Aα mn+r),s ) ) 2 2 max Aα mn 2),q ) 69) r+2 0 q l 48

54 7 68) 69) 69) 3 69) 0 s l max 0 s l max Aα mn+r),s ) Aα ),s ), 2 r+ ) max 0 s l ) 2 max 2 r+ 0 s l Aα mn ),s ) Aα mn 2),s ) ) n max Aα m0),s ) 2 r+ 0 s l ) n 0, as n. 70) 2 r+ 7 60) 9 α {m n } n=0 70) α 60) 0 ) 0 l 4 67) 62) l = {Y n m) } n=0 {X n m) } n=0 0 l N 0 < k < < k l N 0 < ρ < α E [ X m) 0 ; α)x m) ; α) X m) k l ; α) ] = oρ m ), as m. 7) k 49

55 2 f f x, α) := r x)r x + k α) r x + k l α), x, α) T 2, 72) r x) E [ X m) 0 ; α)x m) ; α) X m) k l ; α) ] = 3 2 β : T 3 T 3 k T dx m f 2 i x, 2 i α) βx, y, α) := 2x, 2y, 2α) 73) group extension skew product) i= 6 Ω := T 3 {, } 2 µ Ω T f : Ω Ω µ := P 3 δ + δ 2 δ + δ 2 74) T f x, y, α, ɛ, ɛ 2 ) := 2x, 2y, 2α, ɛ f x, α), ɛ 2 f y, α)) 75) 40 T f µ T 3 C C := {x, y, α) x, y, α) f x, α) f y, α) } 76) C 0 β- T 3 C E =,..., J Ω F {F } 4J = := { E { } { } } J { E { } {} } J = { E {} { } } J { E {} {} } J = = = Ω = 4J = F, µ-a.e. 7 Ω, µ) {, 2, 3,..., 4J}- {ζ m } m=0 ζ m x, y, α, ɛ, ɛ 2 ) = : T m f x, y, α, ɛ, ɛ 2 ) F. 40 [32, 33] [28] T 2 {, } T : x, α, ɛ) 2x, 2α, ɛ f x, α)) 50

56 9 {ζ m } m= pi, ) := µ T f F ) Fi ), i, =,..., 4J, 4 p m i, ) := µζ m = ζ 0 = i) 9 cf. [2] Theorem 8.9) i, =,..., 4J p m i, ) µf ), as m, : i =, 2 Φ i : Ω {, }, Φ i x, y, α, ɛ, ɛ 2 ) := ɛ i, Φ i : {,..., 4J} {, }, Φ i ) := Φ i F ) = F ɛ i -. m dx f 2 i x, 2 i α) T i= = dxφ x, y, α, ɛ, ɛ 2 )Φ T m f x, y, α, ɛ, ɛ 2 )) T = dx Φ ζ 0 x, y, α, ɛ, ɛ 2 )) Φ ζ m x, y, α, ɛ, ɛ 2 )) 77) T 77) y, ɛ 2 ) 2 dα dx Φ ζ 0 x, y, α, ɛ, ɛ 2 )) Φ ζ m x, y, α, ɛ, ɛ 2 )) T T = dα dx Φ ζ 0 x, y, α, ɛ, ɛ 2 )) Φ ζ m x, y, α, ɛ, ɛ 2 )) T T ) dy Φ 2 ζ 0 x, y, α, ɛ, ɛ 2 )) Φ 2 ζ m x, y, α, ɛ, ɛ 2 )) T α Φ ζ m x, y, α, ɛ, ɛ 2 )) Φ 2 ζ m x, y, α, ɛ, ɛ 2 )) x, y, ɛ, ɛ 2 ) = dα dxdy Φ ζ 0 x, y, α, ɛ, ɛ 2 )) Φ ζ m x, y, α, ɛ, ɛ 2 )) T T 2 Φ 2 ζ 0 x, y, α, ɛ, ɛ 2 )) Φ 2 ζ m x, y, α, ɛ, ɛ 2 )) ) = dµ Φ 3 ζ 0 x, y, α, ɛ, ɛ 2 )) Φ 3 ζ m x, y, α, ɛ, ɛ 2 )) Ω = Φ 3 i) Φ 3 )p m i, )µf i ), i, 4 {F } Ω, T f ) irreducible) aperiodic) stationary)) [2] Section 8 5

57 Φ 3 := Φ Φ 2 m Φ 3 i) Φ 3 )p m i, )µf i ) Φ 3 i) Φ 3 )µf )µf i ) = Φ 3 i)µf i ) i, = i, 2 ɛ ɛ 2 dµ) = 0 Ω ) 2 dα dx Φ ζ 0 x, y, α, ɛ, ɛ 2 )) Φ ζ m x, y, α, ɛ, ɛ 2 )) 78) m= T T = Φ 3 i) Φ 3 )p m i, )µf i ) < m= i, 78) 0 < ρ < m= ) 2 ρ m dα dx Φ ζ 0 x, y, α, ɛ, ɛ 2 )) Φ ζ m x, y, α, ɛ, ɛ 2 )) <. 79) T T i 2 T dα m= ρ m/2 ) 2 dx Φ ζ 0 x, y, α, ɛ, ɛ 2 )) Φ ζ m x, y, α, ɛ, ɛ 2 )) <. T ρ m/2 T dx Φ ζ 0 x, y, α, ɛ, ɛ 2 )) Φ ζ m x, y, α, ɛ, ɛ 2 )) 0, as m, a.e.α. 80) α 7) 9 T f µ {ζ m } m µζ m = ζ m = i) = pi, ), i, =,..., 4J, m N. T m f := T m f ), β m := β m ) 8) 0 T m f F =,..., 4J Ω m m < m m m A m A m A A A A = 52

58 . C := ɛ,ɛ 2 =,C {ɛ } {ɛ 2 } C T f - T f C C A m A, B m B A ) A A A B A C m T m f T m f C m = T m m f C C T m f A C T m f A T m f C m T m f A C m ). T m f A) F {ζ m } m=0 µζ 0 = i 0,..., ζ m = i m ) > 0 T m+ f µζ m = ζ 0 = i 0,..., ζ m = i m ) = µ T m f F ) Fi0 T f F i T m+ f F im = µ F i0 T f µ F i0 T f = µ F i0 T f ) F i T m+ f F im T m f F im ) F i T m+ f F im F i T m+ f Fim T f F im )) µ ). F i0 T f F i T m+ f F im F im 8 m 0 l F := F i0 T f F i T m+2 F m 2 8 m l F T m+ f µ F T m+ f Fim T )) f F im µ ) F T m+ f F im T f µ- µζ m = ζ 0 = i 0,..., ζ m = i m ) = µ T m+ f = = f ) Fim T f F im l 8 µ T m+ m f Fim T )) f F im, l 8 µ ) T m+ m f F im. Fim T f F im )) µ ) T m+ f F im = µ ) F im T f F im µf im ) = µζ m = ζ m = i m ) {ζ m } m {ζ m } m T f φ i : T 3 C, i =, 2, φ x, y, α) = φ 2x, 2y, 2α) f x, α), a.e. 82) φ 2 x, y, α) = φ 2 2x, 2y, 2α) f x, α) f y, α), a.e. 83) φ = φ 2 = 0, a.e. 53

59 . i =, 2 f 0 φ i x, y, α) 0 φ i 2x, 2y, 2α) 0 2 β 0 φ i 0 a.e. φ i φ i {, } A T 3 A := x, y, α) < x <, < x + n 2 2 k 2α <, < x + n k α < 3, 2 < y <, < y + n 2 2 k α < A x, y, α) A r x) = r x + n α) = = r x + n k 2 α) =, r x + n k α) =, r y) = r y + n α) = = r y + n k α) =, k f 72). 84) f x, α) =, f y, α) =, x, y, α) A, 85) 8) β m A := { x, y, α) T 3 β m x, y, α) A }. β A A B ) 3 0 := x, y, α) < x <, 3 < x + n 4 4 k 2α <, < x + n k α < 5, 4 3 < y <, 3 < y + n 4 4 k α <. A 85) B ) 0 f x, α) =, f y, α) = 82)83) φ i x, y, α)φ i 2x, 2y, 2α) =, x, y, α) B ) 0, 86) A φ i x, y, α) a.e. B ) 0 φ i 2x, 2y, 2α) a.e. 86) A φ i A φ i x) A A φ i x, y, α)dxdydα =: a i, ) 87) A A m β m A B m) f 0 f x, α) f y, α) C 2 β f x, α) f y, α) B m) D := B m) C β m β m D A β m D β m C = C A C = f x, α) f y, α) A 54

60 m β m A B m) 82)83) φ i x, y, α)φ i 2x, 2y, 2α) φ i x, y, α)φ i 2x, 2y, 2α). 88) B m) φ i x, y, α)dxdydα = ±a i 89) B m) m = 88) x = 2x, y = 2y, α = 2α φ i x, y, α)dxdydα = ± φ i 2x, 2y, 2α)dx = ± φ i x, y, α )dx dy dα 90) B ) B 8 ) A B ) = A 8 B ) φ i x, y, α)dxdydα = ±a i. 9) B ) m 89) m 88) 90) φ i x, y, α)dxdydα = ± φ i 2x, 2y, 2α)dxdydα = ± φ i x, y, α)dxdydα. B m) B 8 m) βb m) βb m) β m+ A B m+) ) B m) = 8 B m+) B m) φ i x, y, α)dxdydα = ± B m) B m+) φ i x, y, α)dxdydα. B m+) m 89) m= β m A T 3 0 < ρ < m = log 2 ρ + β m A δ > 0 S + δ < S S φ i x, y, α)dxdydα < δ. 92) φ i {, }- Sx, y, α; ρ) ρ > 0 x, y, α) lim φ i x, y, α )dx dy dα =, a.e.x, y, α) T 3. ρ 0 Sx, y, α; ρ) Sx,y,α;ρ) 92) 82)83) φ i 0 9 T f φ : Ω = T 3 {, } 2 C T f - φx, y, α, ɛ, ɛ 2 ) = φ2x, 2y, 2α, ɛ f x, α), ɛ 2 f y, α)), µ-a.e., 55

61 φ µ-a.e. ψ x, y, α) := ɛ,ɛ 2 φx, y, α, ɛ, ɛ 2 ) ψ x, y, α) = φ2x, 2y, 2α, ɛ f x, α), ɛ 2 f y, α)) ɛ,ɛ 2 = φ2x, 2y, 2α, ɛ, ɛ 2 ) ɛ,ɛ 2 = ψ 2x, 2y, 2α) 2 β ψ c = a.e. φ φ c/4 ψ 0, a.e. ψ 2 x, y, α, ɛ ) := ɛ 2 φx, y, α, ɛ, ɛ 2 ) ψ 2 x, y, α, ɛ ) = φ2x, 2y, 2α, ɛ f x, α), ɛ 2 f y, α)) ψ 2 x, y, α, ) = ψ 2 2x, 2y, 2α, f x, α)) ɛ 2 = φ2x, 2y, 2α, ɛ f x, α), ɛ 2 ) ɛ 2 = ψ 2 2x, 2y, 2α, ɛ f x, α)) = ψ 2 2x, 2y, 2α, )δ f x, α)) + ψ 2 2x, 2y, 2α, )δ f x, α)) φ 2 2x, 2y, 2α, ) + φ 2 2x, 2y, 2α, ) = ψ x, y, α) 0 ψ 2 x, y, α, ) = ψ 2 2x, 2y, 2α, ) δ f x, α)) δ f x, α))) = ψ 2 2x, 2y, 2α, ) f x, α). ψ 2 x, y, α, ) 0, a.e. ψ 2 x, y, α, ) 0, a.e. ψ 2 x, y, α, ɛ ) 0, a.e.x, y, α, ɛ ) φx, y, α, ɛ, ) + φx, y, α, ɛ, ) = ψ 2 0 φx, y, α, ɛ, ɛ 2 ) = φx, y, α, ɛ, )ɛ 2 ɛ ɛ 2 φ T f φx, y, α, ɛ, ɛ 2 ) = φx, y, α,, ɛ 2 )ɛ φx, y, α, ɛ, ɛ 2 ) = φx, y, α,, )ɛ ɛ 2. φx, y, α,, ) = φ2x, 2y, 2α,, ) f x, α) f y, α) φ 0 T f {ζ m } m 56

62 9 µζ 0 = ζ ) > 0 F := x, y, α) 0 < x <, 0 < x + n 2 k α <, 2 0 < y <, 0 < y + n 2 k α <, 2 F := x, y, α) 0 < x <, 0 < x + n 4 k α <, 4 0 < y <, 0 < y + n 4 k α <, 4 F := F {} {} Ω Ω {F } 4J = F H := F {} {} H F x, y, α) F f x, α) = f y, α) = x, y, α, ɛ, ɛ 2 ) H ζ 0 x, y, α, ɛ, ɛ 2 ) = ζ x, y, α, ɛ, ɛ 2 ) = µh) > 0 {ζ m } m 9 0 0) ) ρ 42 4 [] ρ > ρ 0 := + 7 ) /8 = E [ X m) 0 ; α)x m) k ; α) ] = o ρ m ), as m, k N, a.e. α. [] 5 dα E [ X m) 0 ; α)x m) k ; α) ]) 2 T = m m, m N, k N ) 79) 4 ρ 0 [] 9 43 pi, ) 42 4 ρ

63 ρ 2 0 ) ρ2 0 7 ) / [29] 5. T x kx T k = m N a m := dα E [ X m) 0 ; α)x m) ; α) ]) 2 2 m = dα r i x)r i x + α) dx T T T 5 i= a = a 2 = 3 93) a m+2 = 4 a m+ + 4 a m, m N 94) 93). ) 2 a = dα r x)r x + α)dx = T T T 2 4α ) 2 dα = 3. r x)r 2 x) = r x + 4) a 2 = = = dα r x)r 2 x)r x + α)r 2 x + α)dx T T dα r x + ) r x + α + ) ) 2 dx T T 4 4 ) 2 dα r x)r x + α)dx = a. T T ) 2 94). 44) A m) α) := T m r i x)r i x + α) dx i= α ) E a m = E [ A m) α) 2] ξ m := E [ Aα m)u ) 2 + Aα m)l ) 2] η m := E [ Aα m)u )Aα m)l ) ] 94) 58

64 2 ξm+ η m+ a m = 3 ξ m + 3 η m 95) ) = ξm η m ) 96). A m) α) = 2 m α m ) Aα m)u ) + 2 m α m Aα m)l ). A ) 4 α m := α α m a m = E [ 2 m α m ) 2 Aα m)u ) 2] + E [ 2 m α m ) 2 Aα m)l ) 2] +2E [ 2 m α m ) 2 m α m )Aα m)u )Aα m)l ) ] = E [ 2 m α m ) 2] E [ Aα m)u ) 2] + E [ 2 m α m ) 2] E [ Aα m)l ) 2] +2E [ 2 m α m ) 2 m α m )] E [ Aα m)u )Aα m)l ) ] α m α m)l α m)u 2 m α m = 2 m α α a m = E [ α) 2] E [ Aα m)u ) 2] + E [ α 2] E [ Aα m)l ) 2] +2E [ α)α] E [ Aα m)u )Aα m)l ) ] = 3 E [ Aα m)u ) 2] + 3 E [ Aα m)l ) 2] + 3 E [ Aα m)u )Aα m)l ) ] 95) 3 E [ Aα m+)u ) 2 + Aα m+)l ) 2] [ = E 4 [ = E 4 AUα m+)u ) + ALα m+)u ) ) 2 + AUα m+)l ) + ALα m+)l ) ) ] 2 4 ] Aα m)u ) + Aα m)l ) ) 2 + Aα m)l ) 2 ; d m+ α) = 0 [ + E Aα m)u ) 2 + Aα m)u ) + Aα m)l ) ) ] 2 ; dm+ α) = 4 = [ 2 E Aα m)u ) + Aα m)l ) ) ] 2 + Aα m)l ) [ 2 E Aα m)u ) 2 + Aα m)u ) + Aα m)l ) ) ] 2 4 = 3 4 E [ Aα m)u ) 2 + Aα m)l ) 2] + 2 E [ Aα m)u )Aα m)l ) ] 59

65 E [ Aα m+)u )Aα m+)l ) ] [ = E 2 Aαm)U ) ) ] 2 Aαm)L ) Aα m)l ) ; d m+ α) = 0 [ + E Aα m)u ) 2 Aαm)U ) ) ] 2 Aαm)L ) ; d m+ α) = = 4 E [ Aα m)u ) + Aα m)l ) ) Aα m)l ) ] 4 E [ Aα m)u ) Aα m)u ) + Aα m)l ) )] = 4 E [ Aα m)u ) 2 + Aα m)l ) 2] 2 E [ Aα m)u )Aα m)l ) ] 96) 94) 96) ) 3 2 ) ξm ξm = η m+2 = η m ξm η m ) a m+2 = 3 ξ m η m+2 = ξ m + ) 8 η m ξ m + ) 8 η m = 8 ξ m + 2 η m. 97) a m+ = 3 ξ m+ + 3 η m+ = 6 ξ m 98) a m+2 = c a m+ + c 2 a m, m N, c, c 2 95)97)98) 8 ξ m + 2 η m = c 6 ξ m + c 2 3 ξ m + ) 3 η m = 6 c + ) 3 c 2 ξ m + 3 c 2η m, m N, c = c 2 = 4 94) 5 60

66 T B m - 2 m 4. 2 m L 2 - i.i.d B m L m i.i.d.-.5 {0, } m 2 D m T B m - T 6 [20]) {ψ l } 2m l= L 2 B m ) l T ψ l x)dx = 0 {X n } 2m n= T 2 m l= E N N 2 ψ l X n ) 2m N, N 2m, 99) n=. ψ l L 2 B m ) {X n } N n= D m X n detreministic) {x n } N n= {X n} N n= {x n } N n= D m 6

67 gy) := 2m N f L 2 B m ) N n= N [xn,x n +2 m )y) 00) n= N f x n ) = f, g L 2 B m ) := T f x)gx)dx. {, ψ,... ψ 2 m } L 2 B m ) Parseval) Pythagoras) ) g, L 2 B m ) = 2m g 2 L 2 B m = g, 2 + ) L 2 B m g, ψ ) l 2. 0) L 2 B m ) g 2 L 2 B m ) = 22m N 2 22m N 2 = 22m N 2 N N n= n = N n=n = N n=n = l= T [xn,x n +2 m ) [xn,x n +2 m )dx T [xn,x n +2 m ) [xn,x n +2 m )dx 02) 2 = 2m m N 0) 99) 2 m 2m N + N l= N 2 ψ l x n ). n= 2 [20]) 2 m N > {X n } n= T f L 2 B m ) E N 2 ) f X n ) f x)dx N N 2 m Var f ). 03) n= T 6 ψ l 03) m N ) i.i.d.- i.i.d.- 62

68 6 99) High risk, high return low risk robust ) 8 {X n } 2m n= L2 - L 2 B m )- ) L 2 B m )- f E N 2 f X n ) f x)dx N Var f ) N, N 2m, 04) n= T {x n } N n= 00) gy) ) i.i.d.- 04) L m N 04) L 2 - i.i.d.- low risk return L 2 - i.i.d.- 04) L g : {0, } 2m {0, } Nm N 2 m N {0, } m 2m GF2 m ) cf. [20, 26]) N Z n x, α) := x + nα mod ) m D m, x, α) D m+ D m+, n =, 2, 3,..., 2 +, {Z n } 2 + n= - - random Weyl sampling RWS ) 63

69 7 cf. [20, 26] 44 ) D m+ D m+ P m+,m+ ) {Z n } 2 + n= Z n D m. F,G : R R Fx) = F x m ) Gx) = G x m ) x [0, ) n < n 2 + E[FZ n )GZ n )] = Ft)dt T Gs)ds T 05) E P m+,m+ ) E[FZ n )GZ n )] = = 2 m+ 2 m+ F 2 2m+2 q= q= p= 2 m+ 2 m+ F 2 2m+2 p= ) p 2 + n q G m+ 2 m+ ) p 2 + n n)q G m+ 2 m+ p nq ) + 2m+ 2 m+ p ) 2 m+. 06) 0 < n n = 2 i l i l 2 m+ F 2 m+ q= ) p 2 + n n)q = 2 m+ m+ 2 m+ 2 m+ q= p lq F + 2m+ 2 m+ i ). 07) r =, 2, 3,..., 2 m+ i lq r rmod 2 m+ i ) q r l #{ q 2 m+ lq rmod 2 m+ i )} = #{ q 2 m+ lq lq r mod 2 m+ i )} = #{ q 2 m+ lq q r ) 0mod 2 m+ i )} = #{ q 2 m+ q q r mod 2 m+ i )} = 2 i. 2 m+ p lq F + 2 m+ 2m+ 2 q= m+ i ) = = = 2m+ i 2m+ i 2m+ i r= 2m+ i r= F F p 2 + r ) m+ 2 m+ i r ) 2 m+ i T Ft)dt. 08) 44 7 [20, 26]

70 06)07)08) 2 m+ E[FZ n )GZ n )] = 2 m+ p= 2 m+ = 2 m+ = p= T Ft)dt 2 m+ 2 m+ 2 m+ F q= ) p 2 + n n)q m+ 2 m+ G 2 m+ p lq F + 2m+ 2 q= 2 m+ 2 m+ p= G p ) 2 m+ m+ i = p ) 2 m+ ) G p ) 2 m+ Ft)dt Gs)ds. T T 05) 2 {0, } m D m 7 {Z n } 2 + n= g : {0, } 2m+2 {0, } Nm N 2 + gω ) := Z ω ), Z 2 ω ),..., Z N ω )) D N m {0, } Nm, ω = x, α) D m+ D m+ {0, } 2m ) m = 2 7 = 8 N = 2 9 g : {0, } 292 {0, } S 2 9 gω ) )) P 292 p ) cf.3)) g g 9 g : {0, } 292 {0, } 226 S 2 9 gω )) ω = x, α) D 46 D 46 {0, } ) x = α = S 2 9 gω )) = 204, ) S 2 9 gω )) = = p 45 2m + 2 =

71 RWS ω = x, α) {0, } 2m+2 α α = 0, 0,..., 0) {0, } m+ RWS cf..6.) m RWS RWS {0, } m R ω {0, } 2m+2 m ω ω g : {0, } n {0, } 2m+2 cf. ) g ) i.i.d.- RWS i.i.d.- g 2) g RWS 2) RWS RWS 0 D m m ) T RWS 8 8 [9, 26]) T 2, B 2, P 2 ) T - {x + nα} n Z n n x + nα) x + n α) x + nα) T. f, h L 2 T, B, P) dα T dx f x + nα)hx + n α) T = = dα dx f x)hx + n n)α) T T dx f x) dα hx + n n)α) T T 66

72 = = dx f x) dα hn n)α) T T dx f x) dα hα). T T T, B, P) f L T, B, P) f exp2kπ x) 0 k Z N N n= e 2 πkx+nα) = N πnkα ) e2 e 2 πkx+α) πkα e2 = O, N. N T exp2kπ x)dx = 0 ON ) Fourier) 0 ON ) RWS α T x T α RWS i.i.d.- p < 2 p RWS p 9 [7, 26]) 2 f : T R p < 2 lim N ) p N f x + nα) f y)dy dα dx = 0. T T N T n= ρ > 0 lim N P2 x, α) T2 N N n= f x + nα) T ) f y)dy > ρ = 0. 0). T dx f x) = 0 M N F M : T k R : f M t) := f l)e 2 πlt, l M f l) F Fourier) f l) = dt f t)e 2 T 67 πlt.

73 T dt f t) = 0 f 0) = 0 < p < 2 Hölder) 8 N f x + nα) N := dαdx N p f x + nα) n= T T p N p n= N f M x + nα) N + N n= p f f M )x + nα) N n= p N f M x + nα) N + N n= p f f M )x + nα) N n= 2 = N f M x + nα) N + Var f f M ). ) p ) f M N f M x + nα) = f l)e 2 πlx N N N n= L p T 2, dαdx)- N f M x + nα) N p n= = n= 0< l M 0< l M 0< l M f l) dα T f l) dα T N N n= N n= N n= e 2 πnlα e 2 πnlα e 2 πnα T α lα T dα N e 2 p πnα 2 T = dα N N e 2 p πnα n= 0 + dα N N n= 2 N n= 2 = 2 dα N e 2 p πnα 0 N n= 2 = 2 dα sin πnα p 0 N sin πα N 2 dt = 2 sin πt p 0 N N sin π t Nα = t) N ) p 2 + N 2 π = 2 dt t p N sin πt p N 0 sin π t πt N p N ) p 2 N 2 π = 2 dt t p N sin πt p N 0 sin π t πt N ) p 2 π p < 2 dt sin πt p N 2) πt, 68 0 p p /p /p, e 2 πnα p

74 0 < y < π/2 y/ sin y < π/2 N f M x + nα) N f l) dα N e 2 πnα T p N p n= 0< l M n= /p 0. N lim N N N f x + nα) Var f f M ) p n= 0. M 0) 0) N RWS ρ/ N > 0 x, α) T 2 N N f x + nα) n= T f y)dy 2 dxdα = Var f ) N 2) 0) 2 m RWS α = 0 n X n ω) = x cf. ) 2 m i.i.d.- 2) m RWS i.i.d.- 2 RWS RWS i.i.d ) W W f 20 W Ω, F, P) f W 69

75 . W F W x) := PW x) x R f x) := inf{t R F W t) x}, 0 x <, 3) W a R P f x) a) = P inf F W [x, )) a ) = P x F W a)) = F W a). 20 f 3) f f f x) = f d i x)2 i, x T, i= {d i } i= W W W W 3) {0, }- f x) W ) simulation) W m N B m - 47 m B m - B- ) 46 Wx) d i x) i =, 2, m 70

76 0 ) σx) := inf{n d x) + d 2 x) + + d n x) = 5}, x T, 5 inf = ). σ 5 d i x) σx) σx) 0 20 τ : T N { } {τ m} := {x T τx) m} B m, m N. {B m } m - cf. [2]) {B m } m - τ B σ- B τ B τ := {A B A {τ m} B m, m N} B τ - τ- L p T, B τ, P) L p B τ ) 3 f : T R {± } τ- f x) = f x τx) ), x T, 4). f τ- m N t R {τ m f t} B m τx) m f x) = f x m ) f x) = f x) {τ )=m} x) + f x) {τ )= } x) = = m= f x m ) {τ )=m} x) + f x ) {τ )= } x) m= f ) x τx) {τ )=m} x) + f ) x τx) {τ )= } x) m= = f ) x τx) {τ )=m} x) + f ) x τx) {τ )= } x) = f ) x τx). m= f 4) m N t R { f t} {τ m} = { f ) τ ) t} {τ m} = { f m ) t} {τ m} B m f τ- 0 σ {B m } m - σ σ- 7

77 2 τ {B m } m - τ- f 48. {d i x)} i= d x), d 2 x),... f {B m } m - τ :. m = 2. t := m i= 2 i d i x) = x m ) 3. τt) m f t) 4. τt) > m m := m + 2. τ f x) T - i.i.d. {Z l } l N W Z,..., Z L Z l L l N Z,..., Z l Z l+ W Z l, l l + W Z l 2 K {Z l } l N D K - i.i.d. {Z K) l } l N T, B, P) Z K) n := K 2 i d n )K+i, n N, 5) i= Z K) = 2 d d K d K Z K) 2 = 2 d K d K K d 2K Z K) 3 = 2 d 2K d 2K K d 3K. 48 f 72

78 W τx) := inf{ lk Wx) Z K) x),..., Z K) l x) } τ {B m } m - W τ- 49 W Z l L W τ 2 [6]) [0, )- {Z l } l= [a, b] px) W M > 0 p ξ, η) [a, b] [0, M] Prξ [x, x + dx) pξ) η) = px)dx, a.e.-x,. l := 2. ξ, η) := b a)z 2l + a, MZ 2l ) 3. pξ) η W := ξ 4. pξ) < η l := l + 2. W W 3 0 ) {Y n } n= Y n := 0, if Z n [0, /2), if Z n [/2, ) n =, 2,..., {Y n } n= W := inf{ n Y + Y Y n = 5} W W

79 4.3.3 i.i.d.- f i.i.d.- 22 τ Pτ < ) = {B m } m - f τ- y n x) := 2 n i= τy ix)) x, x T, n N, T, B, P) { f y n )} n N i.i.d. f. y x) = x f y ) f 4) f y n ) = f y n τyn )) { y n τyn )} n N i.i.d. 50 n N a,..., a n D = m N D m P y i τyi ) = a i, i n ) = P y i mi = a i, τy i ) = m i, i n, y n τyn ) = a n, ) = = = m,...,m n N m,...,m n N m,...,m n N m,...,m n N P y i mi = a i, τy i ) = m i, i n, 2 n i= m i x ) n ) = a τ 2 i= mi n, x P y i mi = a i, τy i ) = m i, i n ) 2 n P i= m i x ) n ) = a τ 2 i= mi n x P y i mi = a i, τy i ) = m i, i n ) P x τx) = a n ) = P y i τyi ) = a i, i n ) P x τx) = a n ). P y i τyi ) = a i, i n ) = n P ) x τx) = a i. i= τ {B m } m - f τ- 22 N N f y i x)) 6) i= f 50 i.i.d. 74

80 3 6) NE[τ] E[τ 2 ] = E[τ 2 ] < τ 2) τ E[τ 2 ] < i.i.d.- W i.i.d. {Z, Z 2,...} 2 K ) Z K) l D K function Random m : D m -valued; D m - ) W N function Mean of W : Real; begin S := 0.0; For i := to N do end; i.i.d.- begin Z :=Random K ; W ; while W Z ) do begin Z :=Random K ; W ; end S := S + W ; end; result:= S/N; Mean of W result S/N W Z l Random K 75

81 i.i.d.- 5 [25]) i.i.d.- i.i.d ) i.i.d ) 4.4. τ Pτ < ) = {B m } m - N x l, α l ) D K+ D K+ T T, l N, 7) x n x n := 2 l )K x l + ν n,l α l K T, n =,..., 2 + 8) l= ν n,l : n l = ) ν n,l := #{ u n τx u ) > l )K } l > ) 9) τ {B m } m - ν n,l x n 23 [2]) f τ- { f x n )} 2 + n= f T, B, P) {x n } 2 + n= 4) 23 τ- f 2 [2]) E[τ] < f L B τ ) {x n } 2 + n= E[ f ] N N f x n ), N 2 +, n= dynamic random Weyl sampling DRWS ). 76

82 {x n } 2 + n= τ 3 f L 2 B τ ) DRWS i.i.d.- 2 N E 2 f x N n ) E[ f ] = Var[ f ], N ) N n=0 4 3 E[τ 2 ] < n < n 2 + mn, n ) := max{l ; ν n,l < ν n,l} i =,..., l ν n,l < ν n,l ν n,i < ν n,i mn, n ) = max{l ; ν n,i < ν n,i, i =,..., l}. 2) x n := 2 l )K x l + ν n,l α l K, ν n,l := l= ν n,l l mn, n ) ) n l > mn, n ) ) 22) 4 i) x n T = [0, ) ii) x n x n. i) ii) M N x l + ν n,l α l K, x l + ν n,l α l K, l =,..., M, 23) D K l 2 ν n,l ν n,l x, α ),..., x l, α l ) x l, α l ) ν n,l < ν n,l P x l, α l ) s, t,..., s M, t M D K = = P x l + ν n,l α l K < s l, x l + ν n,l α l K < t l, l =,..., M) P x l + p l α l K < s l, ν n,l = p l, x l + p l α l K < t l, ν n,l = p l, l =,..., M p l <p l ; l=,...,m p l <p l ; l=,...,m P P x M + p M α M K < s M x M + p M α M K < t M x l + p l α l K < s l, ν n,l = p l, x l + p l α l K < t l, ν n,l = p l, l =,..., M, ν n,m = p M. ν n,m = p M 77

83 p M p M 7 { x M + p M α M K < s M } { x M + p M α M K < t M } = P x M + p M α M K < s M ) P x M + p ) Mα M K < t M p l <p l ; l=,...,m P x l + p l α l K < s l, ν n,l = p l, x l + p l α l K < t l, ν n,l = p l, l =,..., M, ν n,m = p M ν n,m = p M = s M t M P x l + p l α l K < s l, ν n,l = p l, x l + p l α l K < t l, ν n,l = p l, l =,..., M p l <p l ; l=,...,m = s M t M P x l + ν n,l α l K < s l, x l + ν n,l α l K < t l, l =,..., M ). P x l + ν n,l α l K < s l, x l + ν n,l α l K < t l, l =,..., M) = M s i t i, i= 23. 4i) f x n ) f 8) n n 22) x n mn,n )K = x n mn,n )K. 24) s := τx n )/K τx n ) > s )K ν n,s < ν n,s 2) s mn, n ). 25) 24) 25) x n sk = x n sk 26) τx n ) sk τ {B m } m - τx n ) x n sk τx n ) = τ x n sk ). 26) 26) 27) τ x n ) = τx n ) sk 27) x n τxn ) = x n τ xn ). 28) f τ- 4) 28) f x n ) = f x n ) 4ii) f x n ) f x n ) 78

84 4.4.3 DRWS N. 29) DWRS l : integer; {x l, α l } l : array variable length) of D K+ ) 2 -valued vectors; function First RWS : D K -valued; begin l := 0; result:=next RWS; end; function Next RWS : D K -valued; begin l := l + ; if x l, α l ) end; then begin x l :=Random K+ ; α l :=Random K+ ; end; x l := x l + α l ; result:= x l K ; function Mean of W : Real; begin S := 0.0; For i := to N do begin Z :=First RWS; W ; while W Z ) do begin Z :=Next RWS; W ; end S := S + W; 79

85 end; end; result:= S/N; DRWS i.i.d ) i.i.d.- DRWS : DRWS Random K Z l First RWS Next RWS Z Z 2, Z 3,... Random K+ Next RWS x l α l DRWS i.i.d.- DRWS Random K+ 2 K N 5 DRWS {x l, α l )} l Random K+ K + Random K DRWS 6 W Z l x l, α l ) DRWS W DRWS DRWS W 0 3, 0 4,..., #define SAMPLE SIZE W i.i.d.- C rand) MT [8] ) 5.2 m90randombit) )) BORLAND C++ COMPILER 5.5 COMMAND LINE TOOLS 80

86 2: rand-i.i.d. MT-i.i.d. m90-i.i.d. DRWS ) DRWS 0 7 DRWS MT i.i.d DRWS 3 DRWS 9 DRWS τ [26]) ) 8

87 C S 2 9 gω )) 204,650 /*==========================================================*/ /* file name: rws_example.c */ /*==========================================================*/ #include <stdio.h> #define SAMPLE_SIZE #define M 28 #define M_PLUS_J 46 /* J = 8 */ /* seed */ char xch[m_plus_j] = "000" "000" " " "00000" " " "000" " " "00000" "000000" "00" "0000" "00000" " " "000" "0000"; char ach[m_plus_j] = "00000" "000000" "00000" " " " " "0000" "000" "000000" " " "000000" "00000" "000" "000000" "000000" "00"; int x[m_plus_j], a[m_plus_j]; void longaddvoid) /* x = x + a long digit addition ) */ { int i, s, carry = 0; for i = M_PLUS_J-; i >= 0; i-- ){ s = x[i] + a[i] + carry; if s >= 2 ) {carry = ; s = s - 2; } else carry = 0; x[i] = s; } } int maxlengthvoid) /* count the longest run of s */ { int len = 0, count = 0, i; for i = 0; i <= M-; i++ ){ if x[i] == 0 ){ if len < count ) len = count; count = 0;} else count++ ; /* if x[i]== */ } if len < count ) len = count; return len; } 82