Transcription

1 ,, / Ver / MSJ Memoirs vol.25 (20)

2

3 i ( ) 940 (von Neumann) (Ulam) ( ) ([56] p.3) 2 ; (Kolmogorov) ([5, 22, 23, 24, 3]) (Blum) ([2, 3, 58]) 2 3 [2]

4 ii ( ) ( ) {0, }- ( ) 2 ( [6, 2, 38, 4, 56]) 2 3 (cf. [20, 53]) (cf. [5, 22, 23, 24, 25, 28, 3, 64]) {0, }- 3 = ([3]) (cf. [29, 40])

5 P NP ([43]) (RWS) 0 RWS i.i.d.- (cf. [46]) (DRWS [45]) RWS C (cf. [5]) 6.2 C ( ) [49] M.Yor H.Niederreiter iii

6

7 v i vii viii T i.i.d

8 vi = = L ( 2) m RWS i.i.d i.i.d.- DRWS DRWS

9 RWS C : random sampler vii

10 viii A := B,, P = Q P Q s.t. B A (B =: A ) P Q ( ) P Q such that N := {0,, 2,...}, 0 N + := {, 2,...}, Z := {..., 2,, 0,, 2,...}, R := C := t := t ( ) t := t ( ) (x B) B (x) := B = 0 (x B) #B := B 2 B := B B c := B A \ B := A B c := Pr := ( ) E[X] := X ( ) E[X; B] := E[X B ] V[X] := X N(m, σ 2 ) := m σ 2 O( f (n)) := (Landau) g(n) = O( f (n)) c > 0 s.t. g(n) c f (n) 0 := O( ) a mod N := a N N = a

11 {0, }-. 0 m ({0, } m, 2 {0,}m, P m ) P m {0, } m ; P m (B) := #B 2 m, B {0, }m (B 2 {0,}m ). m ( ) (E.Borel).. [0, ) (x + y) mod T (-dimensional torus) B T = [0, ) (σ- ) P (Lebesgue measure) (T, B, P) (Lebesgue probability space) 2 (T, B, P) k (k ) (T k, B k, P k ) 2. d i (x) x T 2 i (0 ) ; x = d i (x)2 i. (.) i= d (x) := [/2,) (x), d i (x) := d (2 i x), i N +, x T. 2 B P ( ) B

12 2 3. m N + D m := {i2 m i = 0,..., 2 m } T (.2) I m := { [a, a + 2 m ) a D m } ( ) B m B m I m D m P (m) 4. m N + x T x := x x m := 2 m x 2 m D m, (.3) x m := 2 m x 2 m D m, (.4).2 ([4]) {d i } i=. n N + ϵ,... ϵ n {0, } t := n i= 2 i ϵ i { x T di (x) = ϵ i, i =,..., n } = [ t, t + 2 n) P ( d i = ϵ i, i =,..., n ) = P( [t, t + 2 n ) ) = 2 n 2 D m x (d (x),..., d m (x)) {0, } m m : T D m ( m : T D m ) B m 2 D m ({0, } m, 2 {0,}m, P m ) (D m, 2 D m, P (m) ) (T, B m, P)..2.3 S (Ω, F, P) f S. S F(S ; t) := P(S t) t R f (x) := sup{u R F(S ; u) < x}, 0 < x <, (.5) S { 0 < x < f (x) t } = { 0 < x < x F(S ; t) }, t R, (.6) P( f t) = F(S ; t) (.6) x F(S ; t) t { u R F(S ; u) < x }

13 .2. 3 f (x) t x > F(S ; t) F(S ; ) ε > 0 x > F(S ; t + ε) f (x) t + ε > t (.6).3 f (.5) f f f (x) = f d i (x)2 i, x T, i= {d i } i= 3.3 S S.4 ([39]) Z = 2 d d d d 0 + Z 2 = 2 d d d 9 + Z 3 = 2 d d 8 + Z 4 = 2 d 7 +. {Z n } n= T i.i.d {Z n } n=.3 N(0, ) i.i.d. {ξ n } n=0 B t := t π ξ π n= sin nt n ξ n, 0 t π, {B t } 0 t π ([3] p.93 4).4 {d i } i= i.i.d. {d i } i= [35] Chapter 3 f (x) d i (x) i =, 2,... 4 i.i.d. (independently identically distributed)

14 4.3.3 S f S S (.5) {0, }- f (x) f (simulatable) f 5.3. m N + B m - 6 m B m - B-.5 ( ) σ(x) := inf{ n N + d (x) + d 2 (x) + + d n (x) = 5}, x T, 5 ( inf = ). σ m B m - B- 5 d i (x) σ(x) σ(x).5.6 τ : T N + { } m N +, {τ m} := {x T τ(x) m} B m, {B m } m - (cf. []) {B m } m - τ B B τ B τ := {A B m N +, A {τ m} B m } B τ - τ- L p (T, B τ, P) L p (B τ ) m (Turing machine cf. [6, 20, 53])

15 .3. 5 τ(x) m N + B τ = B m f : T R {± } B m - f (x) = f ( x m ) x T.7 f : T R {± } τ- f (x) = f ( x τ(x) ), x T, (.7). f τ- m N + t R {τ = m f t} B m f (x) {τ=m} (x) B m - f (x) = f (x) {τ=m} (x) + f (x) {τ= } (x) m N + = f ( x m ) {τ=m} (x) + f ( x ) {τ= } (x) m N + = f ( ) x τ(x) {τ=m} (x) + f ( ) x τ(x) {τ= } (x) m N + = f ( ) x τ(x) {τ=m} (x) + f ( ) x τ(x) {τ= } (x) = f ( ) x τ(x). m N + f (.7) m N + t R { f t} {τ m} = { f ( τ( ) ) t} {τ m} = { f ( m ) t} {τ m} B m f τ-.5 σ {B m } m - σ σ- {B m } m - τ τ- f {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.

16 6 τ f (x) f (x) x T m N + f (x) = f ( x m ) m x τ(x) τ(x) N + { } P(τ < ) = τ {B m } m - f (x) d i (x) τ {B m } m - f f {B m } m - τ f τ-.8 ( ) ({ τ (x) := sup n N + d (x) + d 2 (x) + + d n (x) } ) n 3 < 0 {}, x T, {B m } m - τ (x) d i (x) τ (x).3.2 T - T - i.i.d. {Z l } l=.9 7 f {Z l } l= f Z,..., Z T Z l T l N + {T l} Z,..., Z l Z l, l l +.0 f Z l T f.9 T. ( [33]) T - {Z l } l= [a, b] p(x) f M > 0 p (ξ, η) [a, b] [0, M] Pr( ξ [c, d] p(ξ) η ) = d c p(x)dx, a c < d b,

17 l := 2. (ξ, η) := ((b a)z 2l + a, MZ 2l ) 3. p(ξ) η f := ξ 4. p(ξ) < η l := l + 2. f f.9.2 (.5 ) {Y n } n= Y n := 0 ( Z n [0, /2) ) ( Z n [/2, ) ) n =, 2,..., {Y n } n= f := inf{ n N + Y + Y Y n = 5 } f.9 f 5 2 K {Z l } l= D K - i.i.d. {Z (K) l } l= (T, B, P) Z (K) n := K 2 i d (n )K+i, n N +, (.8) 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. f.9 {Z (K) l } l= τ(x) := inf{ lk K N + f (x) Z (K) (x),..., Z (K) l (x) } τ {B m } m - f τ-

18

19 (Monte-Carlo method) ( ) (Ω, F, P) 2 ({0, } L, 2 {0,}L, P L ), L N +, S : {0, } L R ω {0, } L S ω S (ω) (sampling ) 2.: S ( ) ( ) S S ( 2.2.) S

20 0 2 ω A := { ω {0, } L S (ω) S } P L (A) S P L (A) S L L ( L = 0 8 ) ω {0, } L ω {0, } L L = 0 8 2MB 2 ( ) ω {0, } L ( 2.3) P L (A) S P L (A) {0, } L ω ω 3 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 S (g(ω )) g S (g(ω )) S P n (g(ω ) A) g P n (g(ω ) A) g S a b a b a b a b ,000 3

21 2.2. g A ( 2.4.2) S ω A ( ) S i.i.d. S ω A ( 2.5.2) ( ) ( ) 2. r r r + r r /00 : r ( ) r r + /00 ( ) 2.

22 2 2 r 4 X X S S X 2.2 Pr(X < c) = /0000 X c {X k } k= X S := min k X k Pr(S < c) = ( ) e 4 = S 0.98 c p 00 N 6 S N N S N /N p 2.3 N := 0 6 S 0 6/0 6 [ S ] [ E 0 6 S ] = p, V 0 6 p( p) = (Chebyshev s inequality) ( S Pr p 6 ) = 00, (2.) S 0 6/0 6 p x y x y

23 (2.) = 0 8 = S S 0 6 (Ω := {0, } 08, 2 Ω, P 0 8) : X : {0, } 00 {0, } X(ξ,..., ξ 00 ) := max l 00 5 l+5 i=l ξ i, (ξ,..., ξ 00 ) {0, } 00, (ξ,..., ξ 00 ) 6 X = X = 0 X k : {0, } 08 {0, } k =, 2,..., 0 6 X k (ω) := X(ω 00(k )+,..., ω 00k ), ω = (ω,..., ω 0 8) {0, } 08, S 0 6 : {0, } 08 Z S 0 6(ω) := 0 6 k= X k (ω), ω {0, } 08, S 0 6 ω A 0 { S A 0 := ω {0, } (ω) p 0 6 } 200 (2.2) (2.) P 0 8(A 0 ) / ω {0, } 08 ω A 0 ω A 0 / ω {0, } 08 {0, } 08 P 0 8(A 0 ) ω {0, } = 2MB

24 4 2,000 ( 25 ) {0, } 08 6 ω {0, } ( l- 2 l l l = 2 l+ ) {0, } ω {0, } ω {0, } /52 {0, } 08 5/ {0, }- {0, } {0, }- {0, }- 7 L {0, } L 2.4 P 0 8(A 0 ) /00 ω {0, } 08 P 0 8(A 0 ) /00 ω 2.4 S S 0 6(ω) ω {0, } {0, }-

25 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(ω ) {0, } L n N + ω g g : {0, } 238 {0, } 08 0 g ω {0, } 238 ω 238 ( 30 ) S 0 6(g(ω )) ω {0, } g ω {0, } 238 ( S P 0 6(g(ω )) 238 p 0 6 ) (2.3) 200 (2.3) g ω S 0 6(g(ω )) S ( ) ; g : {0, } n {0, } L n < L A {0, } L (secure) P L (ω A) P n (g(ω ) A) 8 9 (randomize)

26 g : {0, } 238 {0, } 08 (2.2) A 0 ω {0, } 238 S (g(ω )) 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 g : {0, } n {0, } L n < L A {0, } L ω {0, } L ω A A {0, } L 2 2L 2 L 2.3 A 2 L L = 0 8 A {0, } A ω A ω A A (computationally secure (cryptographically secure)) ( ) ( ) ( 4.) 2.6 g S 0 6(ω) S 0 6(g(ω )) S 0 6 c, c 2 Z

27 A(c, c 2 ) := {ω c S 0 6(ω) c 2 } ω A(c, c 2 ) p ( S P 0 6(ω) 0 8 p 0 6 ) ( S P 0 6(g(ω )) 238 p ) 200 ( 4..3) 2.5 X m {0, } m X E[X] = 2 m ξ {0,} m X(ξ) m m ( m = 00) (Monte-Carlo integration) ( 2.3) 2.5. i.i.d X N {X k } N k= S N S N Nm X k (ω) := X(ω k ), ω k {0, } m, ω = (ω,..., ω N ) {0, } Nm, (2.4) N S N (ω) := X k (ω). (2.5) k= S N /N X ( P Nm P m ) (E[S N /N] = E[X]) V[S N /N] = V[X]/N S N /N X i.i.d.- 2 P Nm ( S N (ω) N ) E[X] δ 2 {X k } N k= i.i.d. V[X] Nδ 2, δ > 0 (2.6)

28 8 2 3 { } A := ω {0, } Nm S N (ω) N E[X] δ (2.7) ω {0, } Nm ω A ω A S N A 2.7 (cf. [44, 52]) N + Z k (ω ) := x + kα m D m {0, } m, k =, 2, 3,..., 2 +, ω := (x, α) D m+ D m+ {0, } 2m+2, 4 g : {0, } 2m+2 {0, } Nm N 2 + g(ω ) := (Z (ω ), Z 2 (ω ),..., Z N (ω )) D N m {0, } Nm, (2.8) - - (random Weyl sampling RWS ) (2.8) g : {0, } 2m+2 {0, } Nm (2.5) S N E[S N (g(ω ))] = E[S N (ω)] (= NE[X]), V[S N (g(ω ))] = V[S N (ω)] (= NV[X]), ω ω P 2m+2 P Nm (2.6) P 2m+2 (g(ω ) A ) = P 2m+2 ( S N (g(ω )) N ) E[X] δ V[X] Nδ 2 g (2.7) A 3 E[X] V[X] V[X] ( 2.3 X ) 4 m {0, } m D m. 5 [44, 52]

29 (cf. [44, 52]) D m+ D m+ ( ) P (m+ ) P (m+ ) {Z k } 2 + k= Z k D m F, G : T R B m - k < k 2 + E[F(Z k )G(Z k )] = 0 F(t)dt 0 G(s)ds (2.9) E P (m+ ) P (m+ ) F, G B m - E[F(Z k )G(Z k )] = = = 2 m+ 2 m+ F 2 2m+2 q= 2 m+ 2 2m+2 q= q= p= 2 m+ +kq p=+kq 2 m+ 2 m+ F 2 2m+2 p= ( ) ( ) p 2 + k q p kq G + m+ 2 m+ 2m+ 2 m+ F ( ) p 2 + (k k)q ( p ) G m+ 2 m+ 2 m+ ( ) p 2 + (k k)q ( G m+ 2 m+ p ) 2 m+. (2.0) 0 < k k = 2 i l i l 2 m+ ( ) p F 2 m+ 2 + (k k)q = 2 m+ ( ) p lq F +. (2.) m+ 2 m+ 2 m+ 2m+ 2m+ i q= r =, 2, 3,..., 2 m+ i lq r r (mod 2 m+ i ) q r l #{ q 2 m+ lq r(mod 2 m+ i )} q= = #{ q 2 m+ lq lq r (mod 2 m+ i )} = #{ q 2 m+ l(q q r ) 0(mod 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 0 2m+ i r= 2m+ i r= ( F ( F p 2 + r ) m+ 2 m+ i r ) 2 m+ i F(t)dt. (2.2)

30 20 2 (2.0)(2.)(2.2) 2 m+ E[F(Z k )G(Z k )] = 2 m+ p= 2 m+ = 2 m+ = 0 p= F(t)dt 2 m+ 2 m+ 2 m+ F q= ( ) p 2 + (k k)q ( m+ 2 m+ G 2 m+ ( p lq F + 2m+ 2 q= 2 m+ 2 m+ p= ( G p ) 2 m+ m+ i (2.9) 2 Z k (ω ) {0, } m E[S N (g(ω ))] = NE[X] N V[S N (g(ω ( ))] = E X(Zk (ω )) E[X] ) 2 = = N k= k= k = = 0 p ) 2 m+ ) ( G p ) 2 m+ F(t)dt N E [( X(Z k (ω )) E[X] ) ( X(Z k (ω )) E[X] )] N E [ ( X(Zk (ω )) E[X] ) ] 2 k= +2 k<k N = NV[X]. 0 G(s)ds. E [( X(Z k (ω )) E[X] ) ( X(Z k (ω )) E[X] )] g 2.9 RWS ( 2.4.) m = 00 N = 0 6 = g : {0, } 238 {0, } 08 7 ( S P 0 6(g(ω )) 238 p 0 6 ) (2.3) (cf. (2.3)) ω {0, } 238 S 0 6(g(ω )) ( ) ω = (x, α) D 9 D 9 {0, } 238 (2 ) ; = 2 20 > 0 6 = N 2m + 2 = 238 N N

31 x = α = S 0 6(g(ω )) = 546, 77 (C 6.. ) p S 0 6(g(ω )) 0 6 = (2.)(2.3) RWS ω = (x, α) {0, } 2m+2 α α = (0, 0,..., 0) {0, } m+ RWS 2.2 2m+2 RWS ω {0, } 2m+2 g : {0, } n {0, } 2m+2 n 2m + 2 ω {0, } 2m+2 g g : {0, } n {0, } 2m+2 {0, } Nm A X Pr(X < c) = /0000 X, X 2,..., X X S := k= {X k <c} ( ) E[S ] = 4, V[S ] = 40000V[ {X k <c}] = < 4. Pr(S ) Pr ( S 4 < 4 ) = 3 4. min k X k 3/4 c

32 ω {0, } n ω (random sampling) 8 RWS 2. ( α = (0, 0,..., 0) {0, } m+ ) 2.9 ω {0, }- g ω S (g(ω )) 2.9 ω ω {0, } L {0, } [6] () ( ) (2) ω g g(ω ) (3) g 8 random sampling i.i.d.- RWS random sampling ( ) 9 ([6] p.7)

33 () A (2) P n (g(ω ) A) (3) P L (ω A) g A

34

35 25 3 {0, }- x x x {0, }- ([5, 22, 23, 24, 25, 3] cf. [28, 64]) ( ) ([20, 53] ) {0, }- 3.5 = ( 3.20) ( 3.6) {0, }- {0, }- 2 ( 3..3) f : N N ( ) {0, }- f : N N f : N N ( )

36 ( primitive recursive function [20, 53]). ( ) zero : N 0 N, zero( ) := 0 suc : N N, suc(x) := 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 =,..., m f : N n N, f (x,..., x n ) := g(g (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) := g(x,..., x n ) f (x,..., x n, y + ) := h(x,..., x n, y, f (x,..., x n, y)) 4. ( ) g : N n N =,..., m g : N n + +n m N m, g := (g,..., g m ) 5. (N m N n ) 3.2 ( partial recursive function [20, 53]). (µ- ) p : N n+ N 2 µ y (p(,,, y)) : N n N min A p (x,..., x n ) ( A p (x,..., x n ) ), µ y (p(x,..., x n, y)) := ( A p (x,..., x n ) = ) A p (x,..., x n ) ; A p (x,..., x n ) := y N p(x,..., x n, y) = 0 0 z y p(x,..., x n, z). 2 N n N m - g : N n N m N n

37 µ- (N m N n ) µ- ( ) µ- {y N p(x,..., x n, y) = 0 } µ- µ y (p(x,..., x n, y)) (total recursive function) f : N N ( (Kleene) 4 ) f : N n N g, p : N n+ N f (x, x 2,..., x n ) = g(x, x 2,..., x n, µ y (p(x, x 2,..., x n, y))), (x, x 2,..., x n ) N n, (3.) 3.3 [6, 53] f ( µ- ) 3.: (A) Input(x,..., x n ); z := 0 A? yes 2 B no 3 5 C? no E yes 4 D? no yes 0 Output(z) 3 4

38 ( (A) 5 ) f A? C? D? B E ( ) z A? B C? D? A? C? E C? D? u A? C? D? B E u (0 5) (A) Input(x,..., x n ); z := 0 3.2: (B) u := u 0? yes no Output(z) u=? yes A? yes u:=2 no no u:=0 u=2? yes B u:=3 no u=3? yes C? yes u:=4 no no u:=5 u=4? yes D? yes u:= no no u:=0 Q E u:=3 3.2( (B)) u (A) f (B) (B) (3.) (B) Q (x,..., x n ) y Q z g(x,..., x n, y) (x,..., x n ) y Q u p(x,..., x n, y) (3.) 5 (A)(B) [53] p.2 3 p.3 4

39 {0, }- 2 {0, } := n N{0, } n {0, } {0, }- 0 {0, }- (empty word) {0, } (canonical order) ; x, y {0, } x y {0, }- x > y 2 {0, } N = 0 (0) = () = 2 (0, 0) = 3 (0, ) = 4 (, 0) = 5 (, ) = 6 (0, 0, 0) = G n : ({0, } ) n {0, } x i {0, } m i i =, 2 x i = (x i, x i2,..., x imi ), x i {0, }, i =, 2, G 2 (x, x 2 ) := (x, x, x 2, x 2,..., x m, x m, 0,, x 2, x 22,..., x 2m2 ) (3.2) G n (x, x 2,..., x n ) := G 2 (x, G n (x 2,..., x n )), n = 3, 4,..., x,..., x n := G n (x,..., x n ) u = x, x 2,..., x n 6 (u) n i := x i, i =, 2,..., n, () {0, } (,, 0,, ) {0, } 5 (), (,, 0,, ) = (,, 0,,,, 0,, ) =: u {0, } 9 (u) 2 = () (u)2 2 = (,, 0,, ) (), (), () = u (u) 3 = (u)3 2 = (u)3 3 = () 3.4 U N n (recursively enumerable set) f : N n N U f U = {(x, x 2,..., x n ) N n y s.t. f (x, x 2,..., x n ) = y}. 6 (Gödel)

40 30 3 ( (ii)(iii)) 3.5 U N n (i) U (ii) U f : N N n U = f (N) (iii) U f : N N n U = f (N) (iv) p : N n+ N U = {(x, x 2,..., x n ) y s.t. p(x, x 2,..., x n, y) = 0 }. (v) p : N n+ N U = {(x, x 2,..., x n ) y s.t. p(x, x 2,..., x n, y) = 0 }.. n = (i)= (ii): U 3.3 g, p : N 2 N U = {x N y s.t. g(x, µ z (p(x, z))) = y }. a U (u) 2 (u G 2 (N 2 ) p((u) 2 h(u) =, (u)2 2 ) = 0) a ( ) h(n) = U (ii)= (iii): (iii)= (iv): 3.3 f (x) = g(x, µ y (q(x, y))) g, q U = f (N) U = { z N x, y s.t. z = g(x, y), q(x, y) = 0, w < y, q(x, w) > 0 }. q (x, y, z) := 0 (z = g(x, y), q(x, y) = 0, w < y, q(x, w) > 0) ( ) q ((u) 2 p(z, u) :=, (u)2 2, z) (u G2 (N 2 )) (u G 2 (N 2 )) U = { z N u s.t. p(z, u) = 0 }. (iv)= (v): (v)= (i): f (x) := µ y (p(x, y)) f U = { x N y s.t. y = f (x) }.

41 ( ) univ n : N N n N f : N n N e f N ; univ n (e f, x,..., x n ) = f (x,..., x n ), (x,..., x n ) N n. 3.6 univ n (enumerating function) (universal function) e f f (Gödel number) ( [20, 53]) f e f (universal Turing machine cf. [20]) {0, }- 2 e f univ n (e, x,..., x n ) e n e x,..., x n 3.7 univ n. 7 univ n g h(z, x 2,..., x n ) := g(z, z, x 2,..., x n ) + (3.3) h n h e h h(z, x 2,..., x n ) = univ n (e h, z, x 2,..., x n ) h univ n (e h, z, x 2,..., x n ) (z, x 2,..., x n ) N n g univ n h(z, x 2,..., x n ) = univ n (e h, z, x 2,..., x n ) = g(e h, z, x 2,..., x n ) z = e h h (3.3) h(e h, x 2,..., x n ) = g(e h, e h, x 2,..., x n ). h(e h, x 2,..., x n ) = g(e h, e h, x 2,..., x n ) +, (3.3) h h e h

42 univ n : N N n N 3.6 halt n : N N n {0, } (univ n (z, x,..., x n ) ) halt n (z, x,..., x n ) := 0 (univ n (z, x,..., x n ) ) halt n univ n z z x,..., x n 3.8 ([57]) halt n. g : N N n N ; univ n (z, x, x 2,..., x n ) (halt n (z, x,..., x n ) = ) g(z, x, x 2,..., x n ) := 0 (halt n (z, x,..., x n ) = 0) halt n g g univ n halt n u (CPU) x,..., x n n f (x,..., x n ),.5, 20.0, 2. f ( ) {0, }-

43 , 20.0, 2., x, x 2 (3.2) 0, (= ) x f (x) f x halt f (4) (halt (e f, 4) ) (Goldbach) halt p {0, } p {0, } n n L(p) N (p ) p N p {0, }- L(5) = L((, 0)) = 2 L(p) = log 2 (p + ) 3.0 ( ) A : {0, } {0, } {0, } N N N A A y {0, } x {0, } K A (x y) := min{l(p) p {0, }, A(p, y) = x } A(p, y) = x p K A (x y) := 3.0 A A p A p y x K A (x y) A y x p K A A 3. A 0 : {0, } {0, } {0, } A : {0, } {0, } {0, } c A0 A N ; x, y {0, }, K A0 (x y) K A (x y) + c A0 A. A 0 (universal algorithm (asymptotically optimal algorithm))

44 34 3. univ 2 A 0 A 0 (z, y) := univ 2 ((z) 2, (z)2 2, y), z, y {0, }. z = e, p A 0 (z, y) A 0 ( e A, p, y) = A(p, y) (3.2) x, y {0, }, K A0 (x y) K A (x y) + 2L(e A ) + 2. c A0 A := 2L(e A ) + 2 A 0 A 0 c > 0 x, y {0, }, K A0 (x y) K A 0 (x y) < c, (3.4) c K A0 (x y) K A 0 (x y) 3.2 A 0 K(x y) := K A0 (x y), x, y {0, }, y x y K(x) x (Kolmogorov complexity) 8 K(x y) K(x) 3.3 (i) c > 0 x {0, } n y {0, } K(x y) n + c (ii) n > c > 0 y {0, } #{x {0, } n K(x y) n c } > 2 n 2 n c. (i) A(x, y) := p 2 (x, y) = x x {0, }n K A (x y) = n 3. K(x y) n + c (ii) L(p) < n c p {0, } n c = 2 n c K(x y) < n c x {0, } n 2 n c (ii) 9 K(x) K(x y) 3.3 (i)(ii) K(x) c n x {0, } n K(x) n K(x) n x {0, } n (random number) (i)(ii) K(x) (3.4)

45 π ( ) π x {0, } x {0, } 3.5 x {0, } 3.5 y {0, } K(x y) x K(x). {0, } N y {0, } K(x y) x ψ(x) := min{z N K(z y) x} x N x K(ψ(x) y) A A(p, y) := ψ( p, y ) K A (ψ(x) y) = min{l(p) p N, ψ( p, y ) = ψ(x)} x = p, y x K A (ψ(x) y) L(p) L(x) 3. c > 0 x x K(ψ(x) y) L(x) + c (3.5) L(x) = log 2 (x + ) (3.5) x 3.5 ( 3.8) complexity K(x y) function complexity(x, y : {0, } ) : integer; begin l := l z {0, } l A 0 (z, y) = x l end; A 0 K complexity {0, }- z ( ) y x {0, }- x K(x y) complexity 3.8

46 K (t, x, y) (i) t, x, y N K (t, x, y) K(x y) (ii) x, y N K (t, x, y) t K(x y). c > 0 K(x y) = K A0 (x y) < L(x) + c A 0 A 0 (p, y) = g(p, y, µ z (q(p, y, z))), g, q :, µ z<t (q(p, y, z)) := min ({z < t q(p, y, z) = 0} {t}) g g(p, y, z) ( z < t ) (t, x, p, y, z) := x + ( z t ) A(t, x, p, y) := g (t, x, p, y, µ z<t (q(p, y, z))) µ z<t (q(p, y, z)) (t, p, y) A(t, x, p, y) K (t, x, y) := min ({ L(p) L(p) < L(x) + c, A(t, x, p, y) = x } {L(x) + c}) 3.3 = {0, }- ( ) 3.7 ( ) {0, } n n 9 R ( ) := { (x,..., x n ) {0, } n (x, x +,..., x +9 ) (0,..., 0) }, =,..., n 9, U (),..., U (n 9) U ( ) 2 0 x {0, } n =,..., n 9 x R ( ) R := { (x,..., x n ) {0, } n n 9, (x, x +,..., x +9 ) = (0,..., 0) } U n x x U (),..., U (n 9) U = (Martin-Löf) ( 3.9) x x ( 3.20) µ z<t (q(p, y, z)) µ-

47 3.3. = N {0, } U (test) 2 (i) U (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 (iv) (0, 0 (= )) U 3 U m 2 m U m U (x) := max{m N x U m } (3.6) m U (x) x U U 3.9 ([3]) V ( universal test) : U c = c VU N m N, U m+c V m. (3.7) U 2 m c x {0, } V 2 m. {U e } e N m N V m {0, } V m := (U e ) m+e+, (U e ) m+e+ := {x (m + e +, x) U e }, e N V m+ V m U e U = U e U m+e+ = (U e ) m+e+ V m #(V m {0, } n ) #((U e ) m+e+ {0, } n ) 2 n m e = 2 n m. e N V := 0 e n m {(m, x) x V m } m N 2 [6, 2, 4] 3 (iv) 3.9

48 38 3 univ (e, k) = g(e, k, µ z (q(e, k, z))), e, k N, univ g q ψ : N 3 N ψ(e, t, k) := g(e, k, µ z<t (q(e, k, z))) ψ : N 3 N {0, } ; e, t, k N y := ψ(e, t, k) ψ ((y) 2 (e, t, k) :=, (y)2 2 ) ( µ z<t(q(e, k, z)) < t y G 2 (N 2 )), (0, 0) ( ), e, t N Ũ e, t := {(m, x) m m, ψ (e, t, k) =: (m, x), k < t} N {0, }, U e, 0 := {(0, 0)}, U e, 0 Ũ e, t+ U e, t+ := U e, t (U e, 0 Ũ e, t+ ), ( ), t N, {U e, t } t N U e := t N U e, t U e U = U e V m := (U e ) m+e+ = (U e, t ) m+e+, m N, V := = m N e N t N e N {(m, x) x V m } = {(m, x) x (U e, t ) m+e+ } m N t N e N {(m, x) (m + e +, x) U e, t }, m N t N e N V V f : N N {0, } n N n G 4 (N 4 ) m := (n) 4, e := (n)4 2, t := (n)4 3, x := (n)4 4, ψ {Ũ e, s } s t U e, t (m + e +, x) U e, t f (n) := (m, x) f 4 V V 4 f dovetailing

49 3.3. = 39 (3.7) (3.6) m U (x) m V (x) + c (3.8) V V c > 0 x {0, }, m V (x) m V (x) < c, V m V (x) m(x) = 3.20 ( = [3]) c > 0 x {0, } L(x) K(x L(x)) m(x) c. (3.9). L(x) K(x L(x)) m(x) + c : U U := {(m, x) K(x L(x)) < L(x) m} {(0, 0)} m U (x) = L(x) K(x L(x)) (3.8) m(x) + c > L(x) K(x L(x)) U 3.8 (ii) (iii) 3.3(ii) (i) U K K (t, x) := K (t, x, L(x)) K (t, x) t K(x L(x)) x t x > 0 t t x K (t, x) = K(x L(x)) x y (x > y), x y := 0 (x y), U U = {(m, x) t s.t. K (t, x) (L(x) m ) = 0 } {(0, 0)} (3.0) 3.5(iv) 5 K(x L(x)) 3.5(v) U ( (3.0) ) 3.5 K(x L(x))

50 K(x L(x)) L(x) m(x) + c : V ϕ ( 3.5(ii)) ϕ(n) = V ϕ ϕ A : {0, } {0, } {0, } ϕ(i) =: (m i, x i ) V A( } {{ } L(x ) m, L(x )) := x (m, L(x )) = (m 2, L(x 2 )) (m, L(x )) (m 2, L(x 2 )) A( } {{ } L(x 2 ) m 2, L(x 2 )) := x 2 (3.) A( } {{ } L(x 2 ) m 2, L(x 2 )) := x 2 A V (m, L(x)) (m, x) 2 L(x) m L(x) m A (well-defined) K A (x L(x)) = L(x) m(x), K(x L(x)) L(x) m(x) + c K(x L(x)) L(x) x (3.9) c L(x) K(x L(x)) L(x) m(x) K(x L(x)) L(x) 3.4 X Pr( X = a i ) = p i, i =, 2,..., M, (a i a, if i ) H(X) = M p i log 2 p i 0 i= X ( ) 0 < p < {X (p) i i.i.d. } n i=

51 Pr(X (p) = ) = p Pr(X (p) H ( {X (p) i } n i= = 0) = q := p ) = = = x {0,} n Pr ( {X (p) i } n i= = x) log 2 Pr ( {X (p) i } n i= = x) n Pr (S n = r) log 2 p r q n r, S n := r=0 n X i, i= n Pr (S n = r) (r log 2 p + (n r) log 2 q) r=0 = E [ S n log 2 p + (n S n ) log 2 q ] = n( p log 2 p q log 2 q) 6 E[S n ] = np h(p) := p log 2 p q log 2 q {X (/2) i } n i= {0, }n p H ( ) ( {X (p) i } n i= H {X (/2) i } i=) n = nh (/2) = n H(X) X ( (McMillan) cf. [37]) K(x) x {0, } x K(x) x 3.2 (cf. [64]) x = (x, x 2,..., x n ) {0, } n n i= x i = np n x c > 0 K(x) nh(p) log 2 n + c. {0, } n ( n np) x n n np n x ( ) A K A (x) = L( n, np, n ) A( n, np, n, 0) = x. = 2L(n) L(np) L(n ) 2 log 2 (n + ) + 2 log 2 (np + ) + (( ) ) n log np 6 H ( {X (p) i } n i=) n

52 42 3 n! n n e n 2πn ( ) n n! = np (np)!(nq)!, n, 2πnpq p np qnq ( ) n log 2 np 2 (log 2 2πpq + log 2 n) np log 2 p nq log 2 q, n. c > 0 K A (x) nh(p) log 2 n + c. 3. c > c K(x) nh(p) log 2 n + c. 3.2 x ( n np) n 2 nh(p) 2 log 2 n 2 log 2 2πpq 3.3(ii) 3.2 x 2 c c > 0 x K(x) nh(p) 2 log 2 n 2 log 2 2πpq c, c > n ε > 0, Pr X (p) i np nε 0, n, i= 3.22 (cf. [64], Proposition 5.) 0 < p < ε > 0 lim Pr K ( ) {X (p) i } n i= n h(p) n ε = n K(x) n x {0, } n K(x) cn (0 < c < ) x {0, } n ( )

53 ( ) {0, } N 0 N (maximal recursive null set) N (random sequence) 0 y {0, } C(y) y {0, }- ( ) P ( {0, } ) A {0, } P (A) = 0 m N y (m) k {0, } k U m = P ( C(y (m) k ) ) = k k C(y (m) k ) A (3.2) 2 L(y(m) k ) < 2 m (3.3) U = {(m, x) N {0, } C(x) U m } (3.4) (m, x) U, n m C(y) C(x) = (n, y) U (3.5) A (3.2) (3.5) U U m 2 m U (sequential test) V : U m N +, U m+c V m (3.6) c > 0 U V V (universal sequence test) ([3]) N N 3.24 π 2 {0, }- {d i (π 3)} i= n {d i (π 3)} n i= {d i (π 3)} i= 7

54 ( ) [3] 3.26 {0, }- [28] 3.6 ({0, } L, 2 {0,}L, P L ) X : {0, } L R X ω {0, } L P L X(ω) ω {0, } L ω ([54] p.5) 8 {0, } L L L {0, } L P L ω P L {0, } L ({0, } L, 2 {0,}L, P L ) 3.5 {0, } L {0, } L 8 3 [4] Kolmogorov-Chaitin ( ) 4

55 [0]

56

57 [2, 58] [29, 40] 4.. f : {0, } {0, } ; n N + f n := f {0,} r(n) : {0, } r(n) {0, } s(n) f = { f n } n f f (x) ( ) x {0, } r(n) f n T f (n) 2. {l(n)} n c > 0 n l(n) = O(n c ) 3. f = { f n } n r(n), s(n) f n : {0, } r(n) {0, } s(n) f n T f (n) 4. Y U B Y B Y Y Pr Y 5. A = {A n } n A n : {0, } r(n) {0, } s(n) {0, } t(n) x {0, } r(n) Y U {0, } s(n) A n (x, Y) T A (n) A n (x, y) Y A n : {0, } r(n) {0, } t(n) 4.2 g n : {0, } n {0, } l(n) l(n) > n g = {g n } n (pseudorandom generator)

58 g : {0, } n {0, } L n < L 4.2 n g n : {0, } n {0, } l(n) Z n U {0, } n. g n {0, } l(n) - g n (Z n ) l(n) > n g n (Z n ) {0, } l(n) A = {A n } n A n : {0, } l(n) {0, } δ g,a (n) := PrZl(n) ( An (Z l(n) ) = ) Pr Zn (A n (g n (Z n )) = ) (4.) l(n) n g n A δ g,a (n) A δ g,a (n) S g,a (n) := T A(n) δ g,a (n) 4.4 A S g,a (n) ( ) g 2 T A (n) S g,a (n) 4.4 A 3 A Y (4.) Y 2 ( ) 3 e t/000 t t t 00

59 : {0, }- {0, }- XOR(eXclusive OR ) XOR ( ) (cf. [29, 40]) 4.4 A adversary A (cryptographically secure pseudorandom generator) S Z l(n) U {0, } l(n) ; S := S (Z l(n) ) S l(n) Z l(n) g n (Z n ) Z n U {0, } n S S := S (g n (Z n )) S S S S F S (t) := Pr Zl(n) (S t) F S (t) := Pr Zn (S t) g = {g n } n F S (t) F S (t) A n A n (x) := {S (x) t} x {0, } l(n) S A n F S (t) F S (t) = PrZl(n) ( An (Z l(n) ) = ) Pr Zn (A n (g n (Z n )) = ) 4..3

60 50 4 P NP P := L {0, A : {0, } {0, }, s.t. } x {0, } (x L A(x) = ) NP := L {0, } A : {0, } {0, }, s.t. x {0, } (x L Pr(A(x) = ) > 0) P NP P NP 4.5 P = NP 4. g = {g n } n g n : {0, } n {0, } l(n) M n : {0, } l(n) {0, } n {0, } (g n (x) = y) M n (y, x) := 0 (g n (x) y) M = {M n } n L := {y {0, } n N +, y {0, } l(n), x {0, } n, M n (y, x) = } L NP P = NP L P A = {A n } n A n : {0, } l(n) {0, } y L A n (y) = A Z n U {0, } n Z l(n) U {0, } l(n) Pr Zn (A n (g n (Z n )) = ) =, Pr Zl(n) (A n (Z l(n) ) = ) 2n 2 l(n), δ g,a (n) 2 n l(n) T A (n) S g,a (n) = T A (n)/δ g,a (n) g P NP P NP 4 P NP

61 g = {g n } n g n : {0, } n {0, } l(n) Z U {0, } n I U {, 2,..., l(n)} Pr I,Z à = {à n } n à n : {,..., l(n)} {0, } l(n) {0, } ( ) δ g,ã (n) := Pr I,Z (Ãn (I, g n (Z) {,...,I } ) = g n (Z) I ) 2 g n (Z) i g n (Z) i g n (Z) {,...,i} {0, } l(n) g n (Z) i 0 l(n) i { }} { g n (Z) {,...,i} := (g n (Z), g n (Z) 2,..., g n (Z) i, 0,..., 0). à S g,ã (n) := T à (n) δ g,ã (n) g 4.7 g = {g n } n. g à T à (n) S g,ã (n) I U {,..., l(n)} A : {0, } l(n) {0, } (à n (I, x {,...,I } ) = x I ) A n (x) := x {0, } l(n), 0 (à n (I, x {,...,I } ) x I ) δ g,a (n) = ( PrZl(n) An (Z l(n) ) = ) Pr Zn (A n (g n (Z n )) = ) = 2 Pr I,Z n (Ãn (I, g n (Z n ) {,...,I } ) = g 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, } l(n) W U {0, } i {,..., l(n)} x {0, } l(n) à n (i, x) := Y i (A n (x,..., x i, Y i,..., Y l(n) ) = ) W (A n (x,..., x i, Y i,..., Y l(n) ) = 0)

62 52 4 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,..., X i, Y i,..., Y l(n)} ) = ) +Pr ( X i = W, A n (X,..., X i, Y i,..., Y l(n) ) = 0 ) 2 = Pr ( X i = Y i, A n (X,..., X i, Y i+,..., Y l(n) ) = ) + 2 Pr ( A n (X,..., X i, Y i,..., Y l(n) ) = 0 ) 2 = 2 Pr ( A n (X,..., X i, Y i+,..., Y l(n) ) = ) + ( ( Pr An (X,..., X i, Y i,..., Y l(n) ) = )) 2 2 = 2 Pr ( A n (X,..., X i, Y i+,..., Y l(n) ) = ) 2 Pr ( A n (X,..., X i, Y i,..., Y l(n) ) = ) δ g,ã (n) = l(n) = 2 = l(n) i= l(n) ( Pr ( ) ) Ã n (i, X {,...,i } ) = X i 2 l(n) ( ( Pr An (X,..., X i, Y i+,..., Y l(n) ) = ) i= Pr ( A n (X,..., X i, Y i,..., Y l(n) ) = )) 2l(n) (Pr(A n(x) = ) Pr(A n (Y) = )) δ g,ã (n) = δ g,a (n) 2l(n) T Ã (n) S g,ã (n) (cf. (z 0,..., z n ) [, 2, 32, 34]) z i := f (z i n,..., z i ), i = n, n +,... (4.2) 4.7

63 BBS ([2, 40]) 5 p, q p = 3(mod 4) q = 3(mod 4) ( ) N = pq, 2,..., N N QR(N) ( ) x 0 QR(N) x n := F(x n ) = x 2 n mod N, n =, 2,..., (4.3) y n := G(x n ) = x n mod 2 (4.4) p, q F p, q x 0 {y n } m n= y m+ {y n } n 4.8 (4.3) F F F F ( P NP ) G(hard core bit function) BBS (4.4) G (4.3)(4.4) {y n } n ([29]) S (ω) (.3) S (ω) ω - - ( 5.4) 4.2 /2 ( 4.) 5 BBS QR(N) 4..

64 (T, B, P) {0, }- {Y n (m) ( ; α)} n=0 α T m N α T m N + m Y n (m) (x; α) := d i (x + nα) mod 2, n = 0,..., x T. (4.5) i= (4.5) ([63]) α T,, m N + P ( 0 n 2 s.t. Y n (m) ( ; α) Y n (m) ( m+ ; α m+ ) ) < 2 ( 2 ).. (x + nα) ( ) x m+ + n α m+ x x m+ + n α α m+ < 2 m + n2 m = (n + )2 m. P ( + nα m m+ + n α m+ m ) (n + )2 m 2 m = (n + )2. P ( 0 n 2 s.t. Y n (m) ( ; α) Y n (m) ( m+ ; α m+ ) ) < 2 n=0 P ( + nα m m+ + n α m+ m ) 2 (n + )2 n=0 = (2 + )2 2 2 < 2 ( 2 ). 4.0 {Y n (m) ( m+ ; α m+ )} 2 n=0 (4.5) 6 {Y n (m) ( ; α m+ )} 2 n=0 : D m+ {0, } m+ {0, } T x x + α T ( )

65 α 8 m ( ; α m+ )} 2 {Y (m) n n=0 x {0, } m+ D m+ F m+,α : D m+ D m+ G m : D m+ {0, } F( x) = F m+,α ( x) := x + α m+, (4.6) m G( x) = G m ( x) := d i ( x) mod 2, (4.7) i= Y (m) n ( x ; α m+ ) = G(F n ( x)), n = 0,,..., 2, (4.8) F n ( x) x F n G( x) x m 6.2 [5] (4.6)(4.7) {Y n (m) ( ; α m+ )} 2 n=0 BBS (4.3)(4.4) F F m G = G m m 9 G m (4.5) l 2 0 k 0 < < k l {Y (m) k (x; α)} l 2 =0 Y(m) k l (x; α) ; l F (m) (k 0,..., k l ; α) := P =0 Y (m) k ( ; α) =. (4.9) 4.3 Ã : {0, } l {0, } {yk0 + +y Ã(y k0,..., y kl 2 ) := kl 2 = } (F (m) (k 0, k,..., k l ; α) ) 2 {yk0 + +y kl 2 = } (F (m) (k 0, k,..., k l ; α) < ) 2 7, N + m 8 (Weyl transformation) α T T x x + α 9 m

66 56 4 Ã Y (m) k l (x; α) Ã(Y (m) k 0 (x; α),..., Y (m) k l 2 (x; α)) P ( Ã(Y (m) k 0 ( ; α),..., Y (m) k l 2 ( ; α)) = Y (m) k l ( ; α) ) = F(m) (k 0, k,..., k l ; α) (4.0) F (m) (k 0, k,..., k l ; α) /2 P ( Ã(Y (m) k 0 ( ; α),..., Y (m) k l 2 ( ; α)) = Y (m) k l ( ; α) ) = P ( Y (m) F (m) (k 0, k,..., k l ; α) < /2 P ( Ã(Y (m) k 0 ( ; α),..., Y (m) k l 2 ( ; α)) = Y (m) k l ( ; α) ) = P ( Y (m) k 0 ( ; α) + + Y (m) k l ( ; α) = ) = F (m) (k 0, k,..., k l ; α), k 0 ( ; α) + + Y (m) k l ( ; α) = ) = F (m) (k 0, k,..., k l ; α), (4.0) Ã /2 (4.0) 4. P α T l 2 0 k 0 <... < k l α 0 < ρ < m P ( Ã(Y (m) k 0 ( ; α),..., Y (m) k l 2 ( ; α)) = Y (m) k l ( ; α) ) 2 = F (m) (k 0, k,..., k l ; α) 2 = O(ρm ). Ã m l = 2 ρ > ( + 7)/8 = ( ) ( 4.) α {Y n (m) ( ; α)} n=0 0 α P NP

67 (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 l α T F (m) (0, k,..., k l ; α) =, 2,..., l α := k α, α (m)l := α m, α (m)u := α m, β (m) := 2 m (α α (m)l ), β (m) 0 :=, β (m) l := 0, {0,,..., l, l} σ(m, ) = β (m) σ(m,0) > β(m) σ(m,) > β(m) σ(m,2) > > β(m) σ(m,l ) > β(m) σ(m,l) = 0, (4.) σ(m, 0) = 0 σ(m, l) = l α (m)u α (m),s σ(m, ) ( s ), σ(m, ) := α (m)l σ(m, ) ( > s ), α (m),s := (α (m),s,..., α (m),s ), s = 0,,..., l, 2 ; D := D m. m N + l 4.3 F (m) (0, k,..., k l ; α) = l s=0 ( β (m) σ(m,s) β(m) σ(m,s+)) B(α (m),s ). (4.2) t t 0 t = t t.

68 58 4 l { }} { B( ) D 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, ) ). (4.3) = ([43, 6]) P α T {Y n (m) ( ; α)} n=0 m P α T k N + ϵ n {0, } n = 0,,..., k α 0 < ρ < P ( Y n (m) ( ; α) = ϵ n, n = 0,..., k ) 2 k = O(ρ m ), m. 4.5 ([62]) α T {Y n (m) ( ; α)} n=0 m ϵ n {0, } n = 0,,..., k lim P ( Y n (m) ( ; α) = ϵ n, n = 0,..., k ) = 2 k. m (4.2) (cf. [2]) 2 [59, 60, 6, 62] 4.4

69 {Y n (m) ( ; α)} n=0 2 η (m) n;k ( ; α) := Y(m) n ( ; α) + Y (m) ( ; α) (mod 2) n=0 n+k S (m) N;k ( ; α) := N η (m) n;k N ( ; α) {Y n (m) ( ; α)} (m) n=0 S N;k σ 2 N := /(4N) k N+ E [ S (m) N;k ( ; α)] F (m) (0, k; α) = 2 (4.4) S (m) N;k ( ; α) 2 < 2σ N = (4.5) N {Y n (m) ( ; α)} n=0 (4.5) 95% N (m) (k; α) := 6 ( F (m) (0, k; α) 2 ) 2 (4.6) m N = N (m) (k; α) ( ) (4.5) 0.92 ( ) ( ; α)} (m) n=0 S N;k ( ; α)} n=0 σ2 N ( ; α). m {Y (m) n {η (m) n N S (m) N;k N(/2 + a, σ 2 N ) a = F(m) (0, k; α) /2 N = N (m) (k; α) = /(6a 2 ) a = / ( 4 N ) = σ N /2 S (m) N;k 2 < 2σ N 5σ ( ) N 2 < S (m) N;k 2 + a < 3σ N 2 3σ ( ) N 2 < S (m) N;k 2 + a < 5σ N 2 3/2 5/2 2π e x2 /2 dx = (a > 0) (a < 0)

70 (4.4) ( 8%) {Y n (m) ( ; α)} n=0 N(m) (k; α) 4.6 m m α = ( 5 )/2 m = 40 k = F (40) (0, 305; α) = ( F (40) (0, 305; α) 2 ) 2 = = ( ) 2 ( P S (40) 7022;305 ( ; α) ) 2 < 7022 (4.7) ; {Y (40) n (0; α 50 )} n= i =, 2,..., 0 6 p i := 7022 # { 7022(i ) i η (40) ;305 (0; α 50) = }, ( p i ) 0 6 = 0 6 (p i /2) = i= 06 6 p i = 0 (p i ) 2 = i= {Y n (m) } n=0 /(4 7022) = % p i 2 < 7022 i 9254 (4.7) 92.54% ; 5 α =. 2

71 K N + a (m) (K) := max k K F(m) (0, k; α) 2, N(m) c (K) := 6 ( a (m) (K) ), (4.8) 2 N c (m) (K) 4 (4.8) K = a (m) (0000) ( ) k 5 4.: 2 m a (m) (0000) (k) N (m) c (0000) b (m) (9) k, ( 5473 ) ( 449 ) , 5, 3, 4, ( 305 ) ( 305 ) ( 60 ) ( 8484 ) ( 7264 ) ( 7697 ) ( 65 ) ( 520 ) (K- ) l F (m) (0, k,..., k l ; α), k < < k l K, K K 4. K = 9 b (m) (9) := max k <...<k l 9 F(m) (0, k,..., k l ; α) 2 k, K N + m max F(m) (0, k,..., k l ; α) 2 = max k K F(m) (0, k; α) 2. (4.9) k < <k l K 4 [43] critical sample number N c (m) (K) 4 5 α 2 α 50 α 300 ( 4.) 6 K = 9 37 m 00 (4.9)

72 ( 4.29) {Y n (m) } n=0 (4.20) {, }- {X n (m) } n=0 {Y(m) n } n=0 {X n (m) } n=0 {r i } i= (Rademacher functions) r i (x) := 2d i (x), x T, i N +, α T m N + X (m) n (x; α) := m r i (x + nα), n N, (4.20) i= {X n (m) } n=0 {Y(m) n } n=0 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 ( ; α)) = ϵ). (4.2) ( ) (4.2) {X n (m) } n=0 4.2 (i) l E (m) (k 0,..., k l ; α) := E X (m) k ( ; α), 0 k 0 <... < k l, l N +. =0 7

73 ϵ n {, } P ( X n (m) ( ; α) = ϵ n, n = 0,..., k ) = 2 k k l= 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 ; α). (i) k l= 0 k 0 <...<k l k l =0 ( ϵk X (m) k (x; α) ) = =0 ϵ k E (m) (k 0,..., k l ; α) +. (4.22) k n=0 ( + ϵn X (m) n (x; α) ). (4.23) k l= 0 k 0 <...<k l k l =0 ϵ k E (m) (k 0,..., k l ; α). (4.24) k E n=0 ( + ϵn X n (m) ( ; α) ). (4.25) (4.25) E[ ] n = 0,..., k X n (m) (x; α) = ϵ n 2 k 0 (4.25) 2 k P ( X (m) n ( ; α) = ϵ n, n = 0,..., k ). (4.26) (4.24) (4.26) (4.22) (ii) r (x + ) = r 2 (x) r i (x + ) = r 2 i(x) i 2 (x + 2 ) ; α X (m) k l = X (m) k (x; α), x T, (4.27) X (m) k 0 (x; α) X (m) k l (x; α) = ( X (m) k 0 x + ) ( 2 ; α X (m) k l x + ) 2 ; α = X (m) k 0 (x; α) X (m) k l (x; α) = /2 (ii) (iii) (4.2)

74 {X n (m) } n=0 4.3 E (m) (0, k,..., kl ; α) = l s=0 ( β (m) σ(m,s) β(m) σ(m,s+)) A(α (m),s ). (4.28) l { }} { A( ) D l = D D A(α (m),s ) s = 0,,..., l, A(α (0),s ) =, A(α (m),s ) = ( )s ( A(α (m ),s 2 ) + A(α (m ),s +s 2 ) ). 2 s, s l m E (m) (0, k,..., k l ; α) = E r i ( )r i ( + k α) r i ( + k l α). i= α = (α,..., α l ) T l m A (m) (α) := E r i ( )r i ( + α ) r i ( + α l ). (4.29) i= 4.9 α = (α,..., α l ) (D m ) l m m, A (m ) (α) = A (m) (α),. A (m ) (α) m A (m ) (α) = E r i ( )r i ( + α ) r i ( + α l ) i= m i=m+ α (D m ) l i > m r i ( )r i ( + α ) r i ( + α l ). =,..., l, r i (x) = r i (x + α ).

75 l m i=m+ r i (x)r i (x + α ) r i (x + α l ) = m i=m+ r i (x) l = m i= A(m ) (α) = A (m) (α) α D l A(α) := lim m A (m) (α) A A α T l α (m)l := (α (m)l,..., α (m)l α (m)u := (α (m)u,..., α (m)u l ), l α(m)l := α m, ), α(m)u := α m, α (m)l, α (m)u (D m ) l l { }} { 4.2 (i) A( 0,..., 0 ) =. (ii) α = (α,..., α l ) (D m ) l 0 := l = d m (α ) A(α) = ( ) 0 ( A(α (m )U ) + A(α (m )L ) ). (4.30) 2. (i) l l { }} { A( 0,..., 0 ) = E l m { }} { r i ( ) r i ( ) =. i= (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 + α i= ( d m (α ) = 0, d m (x) = 0 ). (4.3)

76 66 4 d m (α ) = 0 r m (x + α ) = r m (x) m m r i (x + α ) = r i (x + α ) r m (x). i= 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 m m ( r i (x + α ) = r i (x + α ) r m (x + α ) = r i x + α + 2 m) i= 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 m m ( r i (x + α ) = r i (x + α ) r m (x + α ) = r i x + α 2 m) i= i= 2 (4.3) ( 0 ), d m (α ) = 0 ( 0 + l ). 0 = l = d m (α ) m 0 l A(α) = E r i( ) r i ( + α ) r i ( + α ) i= m = E r i ( ) i= m +E r i ( ) i= = 0 m = 0 = i= = 0 + ( r i + α + 2 m) l = 0 + m ( r i + α 2 m) i= i= i= m l i= = 0 + i= r i ( + α ) ; d m( ) = m r i ( + α ) ; d m ( ) = 0. {d m (x) = ϵ} (ϵ = 0 ) = m l m 2 E r i ( ) r i ( + α (m )U ) ( ) l 0 i= = i= + m l m 2 E r i ( ) i= = i= r i ( + α (m )L ) ( ) 0.

77 l 0 A(α) = 2 A(α(m )U ) + 2 A(α(m )L ), 0 l 0 A(α) = 2 A(α(m )U ) 2 A(α(m )L ) C := 2 m t= t 2 β (m) σ(m, ) m 2, t 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) ( ) d i x + α (m)l σ(m,p) ( p ), ( + p l ), E (m) (0, k,..., k l ; α) l m = E r i( ) =0 =0 i= i= p= l r i ( + α (m)u σ(m,p) ) p= + C l m l = P(C )E r i( ) r i ( + α (m)u σ(m,p) ) p= r i ( + α (m)l p= + σ(m,p) ) r i ( + α (m)l ; C σ(m,p) ) = l =0 P(C )A(α (m), ). 4.3 P(C ) = β (m) σ(m, ) β(m) σ(m, +) ( α (m),s ) (m )U = α (m ),s +s 2, (4.32) ( α (m),s ) (m )L = α (m ),s 2, (4.33)

78 (4.33) { ( ) # α (m),s (m )L } = α (m )U = s 2 (4.34) (complications) α (m),s α (m)u = α (m),s = α (m)l = ( α (m),s ) (m )L = ( α (m)l ) (m )L = α (m )L = ( ) α (m),s (m )L α (m )U, (4.35) α (m),s = α (m)u = ( α (m),s ) (m )U = ( α (m)u ) (m )U = α (m )U, (4.36) d m (α (m),s ) = ( ) α (m),s (m )L ( ) α (m),s (m )U (4.37) = ( ) α (m),s (m )L α (m )U, (4.38) d m (α (m),s ) = 0 ( ) α (m),s (m )L ( ) = α (m),s (m )U. (4.39) (4.35) (4.38) ( ) α (m),s (m )L = α (m )U = α (m),s = α (m)u d m (α (m),s ) = 0 (4.36) (4.39) α (m),s = α (m)u ( ) α (m),s (m )L = α (m )U J 0 := = = = = d m (α (m),s ) = 0. { ( ) α (m),s (m )L } = α (m )U { } α (m),s = α (m)u, d m (α (m),s ) = 0 { } σ(m, ) α (m),s σ(m, ) = α(m)u σ(m, ), d m(α (m),s σ(m, ) ) = 0 { } σ(m, ) s, d m (α (m),s σ(m, ) ) = d m(α (m)u σ(m, ) ) = 0 { } σ(m, ) s, d m (α (m)l σ(m, ) ) = d m(α σ(m, ) ) = =: J.

79 J s 2 (4.34) 2 2 β (m) i β (m ) i = 2 β(m) i + 2 d m(α i ), i l, {β (m ) i } i d m (α i ) = i β (m ) i β (m ) i 2 3 > β (m ) = d m (α i ) > d m (α ) = 0, d m (α i ) = d m (α ) β (m) i > β (m). J 2 := { i s 2 s.t. i = σ(m, ) } J = J 2 i J s i = σ(m, ) d m (α i ) = s β (m ) i {β (m ) } s 2 i J 2 J J 2. #J = #J 2 = s 2 J = J i J 2 α (m ),s 2 i = α (m )U i i J 2 α (m ),s 2 i = α (m )L i J 2 = J = J 0 i J 0 α (m ),s 2 i = α (m )U i = ( ) α (m),s (m )L i i J 0 α (m ),s 2 i = α (m )L i = ( ) α (m),s (m )L i (4.33) 2 5 (4.32) { # ( ) α (m),s (m )U } { = α (m )U = # ( ) α (m),s (m )U } α (m )L = s + s 2 (4.40) ( ) α (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 8 ) (m )L α (m )L ) (m )L ( ) α (m),s (m )L α (m )L

80 70 4 { ( ) α (m),s (m )U α (m )L { = ( α (m),s } ) (m )U ( α (m),s ) (m )L } { ( ) α (m),s (m )L } α (m )L (4.37) { ( ) # α (m),s (m )U ( ) α (m),s (m )L } { } = # d m (α (m),s ) = = s. (4.34) { ( ) # α (m),s (m )L } α (m )L { = # ( ) α (m),s (m )L } = α (m )U = s 2. (4.40) 2 6 { } J 3 := d m (α (m),s ) = { ( ) α (m),s (m )U } = α (m )U = J 3 J 0 = J 3 J 2 J 4 := { i + s 2 s + s 2 s.t. i = σ(m, ) } J 3 = J 4 α (m),s J 3 = { σ(m, ) s, dm (α σ(m, ) ) = 0 } { σ(m, ) s + l, dm (α σ(m, ) ) = } =: J 5 J 6 {β (m ) i } i s 2 J 0 = J 2 i β (m ) i Step 2.2 J 6 i β (m ) i J 5 i β (m ) i Step 2.5 J 3 = J 4 { ( ) α (m),s (m )U } = α (m )U = J 2 J 4 = { i s + s 2 s.t. i = σ(m, ) } (4.32) 8

81 ; l N + l k < < k l lim m E(m) (0, k,..., k l ; α) = 0 α 4.3 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 = = β (6) 0 > β (6) = > β (6) 2 = > β (6) 3 = > β (6) 4 = 0 σ(6, ) = =, 2, 3 ( ) α (6), = , , , , = 0,, 2, m (m = 0,..., 6) s (s = 0,..., 3) α (m),s α (6),0 ( ) A(α (m),s ) 4.2 A(α (m),s ) m (4.30) (4.30) ( ) 0 A(α (6),2 ) = ( A(α (5), ) + A(α (5),3 ) ) (4.4) m s A(α (m),s ) 0

82 : m s ( 3/8) ( 3/8) (+/4) ( /2) ( 0 ) ( ) (+) ( /6) (+/4) ( /6) ( 0 ) ( 3/8) (+/2) ( /2) (+/4) (+/2) ( 0 ) ( /2) (+) (+) ( 0 ) (+) (+) ( ) (+) (+) (+) (+) (4.4) A(α (6),2 ) m = = ( ) 4.2 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 ) 4.5 m A(α (m),s ) 0 ( 4.27 ) α = (α,..., α l ) (T \ D) l m (i), d m (α (m)u ) = d m (α (m),l ) d m (α (m),0 ) = d m (α (m)l ) = d m (α ). (ii) ( α (m),0 ) (m )L = α (m ),0.

83 ( /6) (+/4) ( /6) ( 0 ) ( 3/8) (+/2) 4.2: m s ( 3/8) ( 3/8) (+/4) ( /2) ( 0 ) ( ) (+) ( /2) (+/4) (+/2) ( 0 ) ( /2) (+) (+) ( 0 ) (+) (+) ( ) (+) (+) (+) (+) (iii) (iv) (v) ( α (m),l ) (m )U = α (m ),l. 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 (4.3) s = 0 s 2 = 0 (ii) (iii) (i) s = l s = l = d m (α (m),l ) = l = ( dm (α ) ) l = l d m (α ). =

84 74 4 s 2 = l = d m (α σ(m, ) ) = l = d m (α ). 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, (4.3) (i) p = q = l = l = l = l d m (α (m),l ). (4.42) d m (α σ(m, ) ) = d m (α (m),0 ) = = l = l = d m (α ), d m (α ), p = q 4.23 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 4.24 α = (α,..., α l ) (T \ 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, p r, d m+p (α ) = 0 (4.43) s, L r α (m+r),s = α (m),0 (iv) =,..., l, p r, d m+p (α ) = (4.44) s, U r α (m+r),s = α (m),l

85 (i) (4.3) s 2 s (i) (ii) (4.40) s + s 2 s (ii) (iii) (4.43) 4.22(i) p d m+p (α (m+r),l ) = α (m+p ),l > α (m+p)l 4.22(ii) L r α (m+r),l = α (m),0 (i) (iii) (iv) (4.44) p α (m+p ),0 < α (m+p)u 4.22(iii) U r α (m+r),0 = α (m),l (ii) (iv) 4.25 ([62]) r := 3k l α α := k α (4.43) (4.44) m. (4.43) (4.44) m N N + m N m d m+ (α m ) =... = d m+r (α m ) = 0 d m+ (α m ) =... = d m+r (α m ) = α α 2 N + m N d m+ (α), d m+2 (α),..., d m+r (α) 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 α. R m+ k m α = k m 2 m+ α.

86 76 4 2R 2 + d m+2 (k m α) k m Q 2 R 3 Q 2 = d m+2 (α), R 3 = k m 2 m+2 α 2 m+2 k m α. 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} r u= R u k m k m Q u = d m+u (α) k m 2 a(0), a(),..., a(p ) w 2w p a(q), a(q + ),..., a(q + p ) 0 q < q + p p p 2w w a(q), a(q + ),..., a(q + p ) w w w. 0 u p w u q = w + v Z 0 v < w v + w < w + w 2w p a(u) = a(q + w + v) = a(q + v) = a(q + v + w ) = a(q + w + v + w ) = a(u + w ). w a(0), a(),..., a(p ) w w = w 3 m N Step d m+ (α),..., d m+r (α) k m w m k m+ d m+2 (α),..., d m++r (α) k m+ w m+ d m+2 (α),..., d m+r (α) Step 2 w m w m+ w m = w m+ α N + w := w m = w m l k < < k l α lim m E(m) (0, k,..., k l ; α) = 0 (4.45) α := (α,..., α l ), α := k α, (4.46) 4.3 (4.45) lim max A(α (m),s ) = 0 (4.47) m 0 s l

87 A(α (m),s ) = ± 2 { A(Uα (m),s ) + A(Lα (m),s ) } (4.48) (4.48) 4.26 max ),s 0 s l A(α(m ) max 0 s l A(α(m),s ), m > m α r := 3k l {m n } n= m 2 m n + r + 2 m n+ max A(α (mn+r),s ) ( ) max A(α (mn 2),s ). 0 s l 2 r+ 0 s l. (4.48) r A(α (m n+r),s ) = 2 r ϵ U ra(ur α (m n+r),s ) + 2 r ϵ LU r A(LUr α (m n+r),s ) r ϵ UL r A(ULr α (m n+r),s ) + 2 r ϵ L ra(lr α (m n+r),s ), (4.49) ϵ U r,..., ϵ L r = ± 4.24 s U r α (m n+r),s = α (m n),l, L r α (m n+r),s = α (m n),0, (4.50) ϵ U r = ϵ L r ϵ, ϵ = ± (4.48) { ϵ U ra(u r α (mn+r),s ) = ϵ U rϵ 2 A(Ur+ α (mn+r),s ) + } 2 A(LUr α (mn+r),s ), { ϵ L ra(l r α (mn+r),s ) = ϵ L rϵ 2 A(ULr α (mn+r),s ) + } 2 A(Lr+ α (mn+r),s ). (4.5) (iv) (4.50) ϵ ϵ (4.50) 4.22(v) LU r α (m n+r),s = UL r α (m n+r),s (4.52) (4.5) (4.49) A(α (m n+r),s ) = 2 ϵ r+ U rϵa(ur+ α (mn+r),s ) + 2 ϵ r+ U rϵa(lur α (mn+r),s ) ϵ r+ L rϵ A(UL r α (mn+r),s ) + 2 ϵ r+ L rϵ A(L r+ α (mn+r),s ) (4.53)

88 78 4 ϵ U rϵ ϵ L rϵ (4.52) 2 ϵ r+ U rϵa(lur α (mn+r),s ) + 2 ϵ r+ L rϵ A(UL r α (mn+r),s ) = 0. (4.54) A(α (mn+r),s ) ( ) 2 2 r+ max 0 q l A(α (mn ),q ). (4.55) 2 ϵ U r ϵ L r (4.53) ϵ U rϵ = ϵ L rϵ (4.49) (4.53) A(α (mn+r),s ) ( ) 2 2 max A(α (mn 2),q ) (4.56) r+2 0 q l 4.26 (4.55) (4.56) (4.56) max A(α (mn+r),s ) ( ) max A(α (mn 2),s ) 0 s l 2 r+ 0 s l ( ) max A(α (mn +r),s ) 2 r+ 0 s l ( ) 2 max 2 r+ 0 s l A(α (mn 2+r),s ) ( ) n max A(α (m0+r),s ) 2 r+ 0 s l ( ) n 0, n. (4.57) 2 r+ (4.47) 4.28 α {m n } n=0 (4.57) α (4.47) ( 4. ) 4.29 l 4 (4.54) (4.49) l = 2

89 {Y n (m) } n=0 {X n (m) } n=0 4. P α T l N + 0 k 0 <... < k l α 0 < ρ < E [ X (m) 0 ( ; α)x (m) ( ; α) X (m) k l ( ; α) ] = o(ρ m ), m (4.58) k (4.58) 2 (cf. (4.64)) l 0 < k < < k l N + 2 f f (x, α) := r (x)r (x + k α) r (x + k l α), (x, α) T 2, (4.59) r (x) f 3 2 β : T 3 T 3 β(x, y, α) := (2x, 2y, 2α) (4.60) (group extension (skew product)) 4.30 Ω := T 3 {, } 2 µ Ω µ := P 3 δ + δ 2 δ + δ 2 (4.6) δ i i δ- T f : Ω Ω T f (x, y, α, ϵ, ϵ 2 ) := (2x, 2y, 2α, ϵ f (x, α), ϵ 2 f (y, α)) (4.62) 9 T f µ T 3 C C := {(x, y, α) (x, y, α) f (x, α) f (y, α) } (4.63) 9 [59, 60] [55] T 2 {, } T : (x, α, ϵ) (2x, 2α, ϵ f (x, α))

90 80 4 C 0 βc C T 3 C E =,..., J Ω F {F } 4J = := { E { } { } } J { E { } {} } J = { E {} { } } J { E {} {} } J = = = Ω = 4J = F, µ-a.e. 4.3 (Ω, µ) {, 2, 3,..., 4J}- {ζ m } m=0 ; T m f (x, y, α, ϵ, ϵ 2 ) F ζ m (x, y, α, ϵ, ϵ 2 ) := 4.32 {ζ m } m=0 p(i, ) := µ ( T f (F ) Fi ), i, =,..., 4J, p m (i, ) := µ(ζ m = ζ 0 = i) 4.32 (cf. [] Theorem 8.9) 4.33 i, =,..., 4J p m (i, ) µ(f ), m, ; i =, 2 Φ i : Ω {, }, Φ i (x, y, α, ϵ, ϵ 2 ) := ϵ i, Φ i : {,..., 4J} {, }, Φ i ( ) := Φ i (F ) = F ϵ i -. X (m) 0 (x; α) X (m) k l (x; α) = f (x, α) f (2 m x, 2 m α) = Φ (x, y, α, ϵ, ϵ 2 )Φ (T m f (x, y, α, ϵ, ϵ 2 )) = Φ (ζ 0 (x, y, α, ϵ, ϵ 2 )) Φ (ζ m (x, y, α, ϵ, ϵ 2 )) 20 {F } (Ω, T f ) ( (irreducible) (aperiodic) (stationary)) [27] [] Section 8

91 y, ϵ, ϵ 2 E [ X (m) 0 ( ; α) X (m) k l ( ; α) ] = dx Φ (ζ 0 (x, y, α, ϵ, ϵ 2 )) Φ (ζ m (x, y, α, ϵ, ϵ 2 )). T ( ) 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 )). (4.64) T α Φ (ζ m (x, y, α, ϵ, ϵ 2 )) Φ 2 (ζ m (x, y, α, ϵ, ϵ 2 )) (x, y, ϵ, ϵ 2 ) P 2 (δ + δ )/2 (δ + δ )/2 (4.64) ( = 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, Φ 3 := Φ Φ m Φ 3 (i) Φ 3 ( )p m (i, )µ(f i ) i, m= Φ 3 (i) Φ 3 ( )µ(f )µ(f i ) = Φ 3 (i)µ(f i ) = i, ( 2 ϵ ϵ 2 dµ) = 0 Ω ( ) 2 dα T dx Φ (ζ 0 (x, y, α, ϵ, ϵ 2 )) Φ (ζ m (x, y, α, ϵ, ϵ 2 )) T (4.65) = Φ 3 (i) Φ 3 ( )p m (i, )µ(f i ) < m= i, (4.65) 0 < ρ < m= ( ) 2 ρ m dα dx Φ (ζ 0 (x, y, α, ϵ, ϵ 2 )) Φ (ζ m (x, y, α, ϵ, ϵ 2 )) <. (4.66) T T i 2

92 82 4 ρ m/2 T dα ( m= ρ m/2 ) 2 dx Φ (ζ 0 (x, y, α, ϵ, ϵ 2 )) Φ (ζ m (x, y, α, ϵ, ϵ 2 )) <. T dx Φ (ζ 0 (x, y, α, ϵ, ϵ 2 )) Φ (ζ m (x, y, α, ϵ, ϵ 2 )) 0, m, a.e.α. T (4.67) α (4.58) 4.32 T f µ {ζ m } m=0 µ(ζ m = ζ m = i) = p(i, ), i, =,..., 4J, m N +. T m f := (T m f ), β m := (β m ) (4.68) 4.34 T m f F =,..., 4J Ω m m < m m m A m A m A A A A =. C := ϵ,ϵ 2 =,C {ϵ } {ϵ 2 } 2 T f C C A m A, B m (B A ) A A A B A T m f C T m f (A T m f C) T m f A T m f T m f C = T m f A T m m f T m f (A) F C T m f A C. {ζ m } m=0 m 2 µ(ζ 0 = i 0,..., ζ m = i m ) > 0 µ(ζ 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 2 C (4.63) ) F i T m+ f F im T m f F ) F i T m+ f F im F i T m+ f ( Fim T f F )) µ ( ). F i0 T f F i T m+ f F im

93 T m+ f F im 8 m 4.34 s F := F i0 T f F i T m+2 f F im 2 ( 8 m s F T m+ f Fim T ) f F im µ ( F T m+ f ( Fim T f F )) µ ( F T m+ f F im ) T f µ- µ(ζ m = ζ 0 = i 0,..., ζ m = i m ) = µ ( T m+ f = = s 8 µ ( ( T m+ m f Fim T )) f F, s 8 µ ( ) T m+ m f F im. ( Fim T f F )) µ ( ) T m+ f F im = µ ( ) F im T f F µ(f im ) = µ(ζ m = ζ m = i m ) {ζ m } m=0 {ζ m } m=0 T f 4.35 ϕ i : T 3 C, i =, 2, ϕ (x, y, α) = ϕ (2x, 2y, 2α) f (x, α), a.e., (4.69) ϕ 2 (x, y, α) = ϕ 2 (2x, 2y, 2α) f (x, α) f (y, α), a.e., (4.70) ϕ = ϕ 2 = 0, a.e.. 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 + k 2 2 l 2α <, < x + k l α < 3, 2 < y <, < y + k 2 2 l α < A (x, y, α) A r (x) = r (x + k α) = = r (x + k l 2 α) =, r (x + k l α) =, r (y) = r (y + k α) = = r (y + k l α) =,. (4.7)

94 84 4 l f (4.59) f (x, α) =, f (y, α) =, (x, y, α) A, (4.72) (4.68) β m A := { (x, y, α) T 3 β m (x, y, α) A }. β A A B ( ) 3 0 := (x, y, α) < x <, 3 < x + k 4 4 l 2α <, < x + k l α < 5, 4 3 < y <, 3 < y + k 4 4 l α <. A (4.72) B ( ) 0 f (x, α) =, f (y, α) = (4.69)(4.70) ϕ i (x, y, α)ϕ i (2x, 2y, 2α) =, (x, y, α) B ( ) 0, (4.73) A ϕ i (x, y, α) a.e. B ( ) 0 ϕ i (2x, 2y, 2α) a.e. (4.73) A ϕ i A ϕ i (x) ϕ i (x, y, α)dxdydα =: a i (, ) (4.74) A A A A m 4.34 β m A B ( m) f (x, α) f (y, α) (4.69)(4.70) B ( m) ϕ i (x, y, α)ϕ i (2x, 2y, 2α) ϕ i (x, y, α)ϕ i (2x, 2y, 2α). (4.75) B ( m) ϕ i (x, y, α)dxdydα = ±a i (4.76) B ( m) m = (4.75) x = 2x, y = 2y, α = 2α ϕ i (x, y, α)dxdydα = ± ϕ i (2x, 2y, 2α)dxdydα = ± ϕ i (x, y, α )dx dy dα B ( ) B 8 ( ) A (4.77) B ( ) = A 8 B ( ) ϕ i (x, y, α)dxdydα = ±a i. (4.78) B ( ) m (4.76) m (4.75) (4.77) ϕ i (x, y, α)dxdydα = ± ϕ i (2x, 2y, 2α)dxdydα = ± ϕ i (x, y, α)dxdydα. B ( m) B 8 ( m) βb ( m)

95 β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 (4.76) m= β m A T 3 0 < ρ < m = log 2 ρ + β m A δ > 0 S T 3 + δ < S S ϕ i (x, y, α)dxdydα < δ. (4.79) ϕ i {, }- S (x, y, α; ρ) ρ > 0 (x, y, α) lim ϕ i (x, y, α )dx dy dα =, a.e.(x, y, α) T 3. ρ 0 S (x, y, α; ρ) S (x,y,α;ρ) (4.79) (4.69)(4.70) ϕ i T f ϕ : Ω = T 3 {, } 2 C T f - ϕ(x, y, α, ϵ, ϵ 2 ) = ϕ(2x, 2y, 2α, ϵ f (x, α), ϵ 2 f (y, α)), µ-a.e., (4.80) ϕ µ-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 = ϕ(2x, 2y, 2α, ϵ f (x, α), ϵ 2 ) ϵ 2 = ψ 2 (2x, 2y, 2α, ϵ f (x, α))

96 86 4 ψ 2 (x, y, α, ) = ψ 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 (4.80) ϕ(x, y, α, ϵ, ϵ 2 ) = ϕ(x, y, α,, ϵ 2 )ϵ. ϕ(x, y, α, ϵ, ϵ 2 ) = ϕ(x, y, α,, )ϵ ϵ 2. ϕ(x, y, α,, ) = ϕ(2x, 2y, 2α,, ) f (x, α) f (y, α) 4.35 ϕ 0 T f {ζ m } m= µ(ζ 0 = ζ ) > 0 F := (x, y, α) 0 < x <, 0 < x + k 2 l α <, 2 0 < y <, 0 < y + k 2 l α <, 2 F := (x, y, α) 0 < x < 4, 0 < x + k l α < 4, 0 < y < 4, 0 < y + k l α < 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 ( 4.)

97 ( 4.) ρ (cf. [47]) ρ > ρ 0 := ( + 7 ) /8 = E [ X (m) 0 ( ; α)x (m) k ( ; α) ] = o (ρ m ), m, k N +, a.e. α dα ( E [ X (m) 0 ( ; α)x (m) k ( ; α) ]) 2 T = m m, m, k N (4.67) (4.66) 4.36 ρ ([47]) 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 4.37 i= a = a 2 = 3 (4.8) a m+2 = 4 a m+ + 4 a m, m N + (4.82) (4.8). r (x)r (x + α)dx = 2 4α (4.83) T ( ) 2 a = dα r (x)r (x + α)dx = ( 2 4α ) 2 dα = T T T ρ

98 88 4 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 (4.82). (4.29) 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 ) ], (4.82) 4.38 ( ξm+ η m+ a m = 3 ξ m + 3 η m, (4.84) ) = ( ξm η m ). (4.85). 4.3 A (m) (α) = ( 2 m α m ) A(α (m)l ) + 2 m α m A(α (m)u ), A( ) 4.20 α m := α α m a m = E [ ( 2 m α m ) 2 A(α (m)l ) 2] + E [ (2 m α m ) 2 A(α (m)u ) 2] +2E [ ( 2 m α m ) A(α (m)l )(2 m α m )A(α (m)u ) ] = E [ ( 2 m α m ) 2] E [ A(α (m)l ) 2] + E [ (2 m α m ) 2] E [ A(α (m)u ) 2] +2E [( 2 m α m ) (2 m α m )] E [ A(α (m)u )A(α (m)l ) ],

99 α m α (m)l α (m)u 2 m α m = 2 m α α a m = E [ ( α) 2] E [ A(α (m)l ) 2] + E [ α 2] E [ A(α (m)u ) 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 ) ] (4.84) 4.2 E [ A(α (m+)u ) 2 + A(α (m+)l ) 2] [ = E 4 [ = E 4 ( A(Uα (m+)u ) + A(Lα (m+)u ) ) 2 ( + A(Uα (m+)l ) + A(Lα (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 ) ] 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 ) ] (4.85)

100 90 4 (4.82) (4.85) ( ξm+2 η m+2 ) = ( ξm η m ) = ( ξm η m ) a m+2 = 3 ξ m η m+2 = ( ξ m + ) 8 η m + 3 ( 6 ξ m + ) 8 η m = 8 ξ m + 2 η m. (4.86) a m+ = 3 ξ m+ + 3 η m+ = 6 ξ m (4.87) a m+2 = c a m+ + c 2 a m, m N +, c, c 2 (4.84)(4.86)(4.87) 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 (4.82) 4.37

101 T B m - 2 m ( ) 2 m L 2 - i.i.d B m - RWS (.3) ( - - ) 5. L m i.i.d (RWS ) 2.5 X {0, } m. D m T B m - 5 T 5. ( [44]) {ψ l } 2m l= L 2 (B m ) := L 2 (T, B m, P) l T ψ l (x)dx = 0

102 92 5 {X n } 2m n= T 2 m E N 2 ψ l (X n ) N 2m N, N 2m, (5.) l= n=. ψ l L 2 (B m ) {X n } 2m n= D m X n (deterministic) {x n } 2m n= {X n} 2m n= {x n } 2m n= D m n= g(y) := 2m N f L 2 (B m ) N f (x n ) = f, g L N 2 (B m ) := N [xn,x n +2 m )(y) (5.2) n= T f (x)g(x)dx {, ψ,... ψ 2 m } L 2 (B m ) (Parseval) ( (Pythagoras) ) g, L 2 (B m ) = (5.3) 2m g 2 L 2 (B m = g, 2 + ) L 2 (B m g, ψ ) l 2. (5.3) L 2 (B m ) g 2 L 2 (B m ) = 22m N 2 (5.) 22m N 2 = 22m N 2 N N n= n = N n= N n=n = l= T [xn,x n +2 m )(x) [xn,x n +2 m )(x) dx T [xn,x n +2 m )(x) dx 2 = 2m m N 2 m 2m N + N l= N 2 ψ l (x n ). 5.2 ([44]) 2 m N > {X n } 2m n= T f L 2 (B m ) E N N f (X n ) n= T n= 2 ( f (x)dx N 2 m ) V[ f ]. (5.4)

103 5.. L ψ l (5.4) m N ( ) i.i.d.- i.i.d.- 5. (5.) High risk, high return 5.3 n N 2 i d i (n) n = i= d i (n)2 i ( ) x n := d i (n)2 i, n N +, i=0 {x n } n= T (van der Corput sequence, cf. [26]) { {x n } n= = 2, 4, 3 4, 8, 5 8, 3 8, 7 8, 6, 9 6, 5 6, 3 } 6,.... f N f (x n ) f (t)dt N c(n) f BV log N N, N 2, n= 0 f BV f T c(n) c(n) = log(n + )/(log 2 log N) ([26] ) (low discrepancy sequence) ( quasi-monte Carlo method) f BV i.i.d.- f BV i.i.d.- f (x) = d 30 (x) n= d 30 (x n ) = 0 0 d 30(t)dt = /2 High risk, high return low risk (robust )

104 {X n } 2m n= L2 - ( L 2 (B m )- ) L 2 (B m )- f E N 2 f (X n ) f (x)dx N V[ f ] N, N 2m, (5.5) n= T ( {x n } 2m n= (5.2) g(y) ) i.i.d.- (5.5) L m N (5.5) L 2 - i.i.d.- RWS (5.5) L ( 2) (RWS) 5.2. RWS RWS 0 ( 5.6) D m (m ) T RWS ([7, 52]) (x, α) T T = T 2 P 2, T - {x + nα} n Z : n n (x + nα) (x + n α) ( ) (x + nα) T. T F, G dα dx F(x + nα)g(x + n α) = dα dx F(x)G(x + (n n)α) T T T T = dx F(x) dα G(x + (n n)α) T T = dx F(x) dα G((n n)α) T T = dx F(x) dα G(α). T T

105 ( 2) 95 (T, B, P) F L (T, B, P) F ([26]) exp(2kπ x) 0 k Z N N n= e 2 πk(x+nα) = N πnkα ( ) e2 e 2 πk(x+α) πkα e2 = O, N. N T exp(2kπ x)dx = 0 O(N ) (Fourier) 0 O(N ) RWS α T x T α RWS i.i.d.- p < 2 p RWS p 5.6 ([5, 52]) 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 P 2 (x, α) T2 N ( ) F(x + nα) F(y)dy N T > ε n= 0, N. (5.6). T dx F(x) = 0 M N + F M : T R F M (t) := F(l)e 2 πlt, l M F(l) F (Fourier) F(l) = dt F(t)e 2 πlt. T T dtf(t) = 0 F(0) = 0 < p < 2 (Hölder) 5.5 N F(x + nα) N := dαdx N p F(x + nα) T T p N p n= n=

106 96 5 = N N N N F M (x + nα) + N p (F F M )(x + nα) N n= p N F M (x + nα) + N p (F F M )(x + nα) N n= 2 N F M (x + nα) + V[F F M ]. (5.7) p (5.7) F M N F M (x + nα) = F(l)e 2 πlx N N N n= n= n= n= 0< l M L p (T 2, dαdx)- N F M (x + nα) N n= p = 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 e 2 π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, 0 < y < π/2 y/ sin y < π/2 N F M (x + nα) N F(l) dα N e 2 /p πnα T p N p 0. N n= 0< l M 0 n= p p /p /p, p

107 ( 2) 97 lim N N N F(x + nα) V[F F M ] p n= 0. M F : T k R (5.6) RWS N 2 F(x + nα) F(y)dy T 2 N dxdα = V[F] (5.8) T N n= (cf. 2.8) (5.6) RWS α = 0 D m+ n X n (x, α) = x m D m (cf. 2.) 2 (m+ ) i.i.d.- m (5.8) RWS i.i.d S 0 6(g(ω ))/0 6 ω = (x, α) D 9 D 9 50,000 S 0 6(g(ω ))/0 6 5.: RWS N(0, ) % % ( ) 0 6 =

108 ( ) 5. 2 ( 99.9%) % 3/4 0.% 3 ( 99%) % 3/5 ( N(0, ) 5. ) 5.: S 0 6(g(ω ))/0 6 50, S 0 6(g(ω ))/0 6 50, ( 5. 3 ) S 0 6(g(ω ))/0 6 S 0 6(ω)/0 6 i.i.d.- i.i.d.- RWS m RWS RWS {0, } m R ω {0, } 2m+2 m ω ω