(JAIST) (JSPS) PD URL:

(JAIST) (JSPS) PD URL: http://researchmap.jp/kihara Email: kihara.takayuki.logic@gmail.com 2012 9 5

ii 2012 9 4 7 2012 JAIST

iii #X X X Y X <N Y X {0, 1} N X x X <N x = x 0, x 1,..., x X, X σ τ σ α σ [[σ]] [S] λ σ X <N τ X <N (cocateatio) τ 1 τ = t σ τ σt σ X <N σ σ α = a 0, a 1,... α = a 0, a 1,..., a 1 σ, τ σ τ σ τ σ = τ σ σ {0, 1} N σ σ 1 σ X <N (clope) [[σ]] = {α X N : σ α} S X <N (ope) [S] = σ S [[σ]] (1/2, 1/2) {0, 1} N 0.α α {0, 1} N r (0, 1) 2 r

iv 1 = = 1 1.1...................................... 1 1.2..................................... 3 1.3.................................... 5 1.4............................... 8 1.5.................................. 11 1.6..................................... 15 2 19 2.1..................................... 19 2.2...................................... 23 2.3 vs............................ 23 2.4................................ 26 3 28 3.1................................. 28 3.2.................................. 30 3.3........................................ 34 3.4................................ 37 3.5..................................... 39 4 41 4.1.................................. 41 4.2.................................. 43 4.3................................... 45 4.4.................................. 45 4.5 /........................................ 50 5 56 5.1 1............................... 56 5.2 2............................... 58 5.3..................................... 61

v 6 64 6.1 = =.................................. 64 7 69 7.1.................................... 69 7.2................................. 74 7.3.................................. 74 77

28 3 3.1. 2 A B A B A 70% B 30% C p 1 p 3.1 ( ). p = (p ) N [0, 1] N 3 m p : {0, 1} <N [0, 1] {0, 1} N λ p p (Beroulli measure with bias p) 1. m p ( ) = 1 2. σ {0, 1} m p (σ0) = p m p (σ) 3. σ {0, 1} m p (σ1) = (1 p ) m p (σ) 3.1. p [0, 1] (p, p, p,... ) p λ p p #i(σ) σ {0, 1} <N i {0, 1} #{ < σ : σ() = i} σ {0, 1} <N [[σ]] λ p - λ p ([[σ]]) = m p (σ) = p #0(σ) (1 p) #1(σ). {0, 1} N [[σ]] m(σ) 3.1 ( ). m : {0, 1} <N [0, 1] m( ) = 1 σ {0, 1} <N

3.1 29 m(σ) = m(σ0) + m(σ1) {0, 1} N µ m σ {0, 1} <N µ m ([[σ]]) = m(σ) 0 p 1 1 p 0 1/p 1 1/(1 p) 0 q 0 1 q 1 d(σ0) = d(σ) (q 0 + q 1 ) + q 0 p, d(σ1) = d(σ) (q 0 + q 1 ) + q 1 1 p. p ( ) + (1 p) ( ) d(σ) = pd(σ0) + (1 p)d(σ1) µ 0 1 σ i {0, 1} µ([[σi]] [[σ]]) = µ([[σi]])/µ([[σ]]) 3.2 ( ). µ {0, 1} N d : {0, 1} <N σ {0, 1} <N µ- (µ-martigale) d(σ) = µ([[σ0]])d(σ0) + µ([[σ1]])d(σ1). µ([[σ]]) Ville 1.1 3.2. µ {0, 1} N q 1 d µ- N d(α ) q d( ) α µ- q 1. 1.1 d( ) = 1 S d(σ) q σ {0, 1} <N λ([s]) q 1 µ([s]) q = µ([[σ]]) q µ([[σ]])d(σ). σ S σ S σ S µ([[σ]])d(σ) d( ) = 1 k N S[k] = S {0, 1} <k k N a k = σ S[k] µ([[σ]])d(σ) 1 lim k a k 1. τ {0, 1} <N F {0, 1} <N τ - σ F µ([[σ]])d(σ) µ([[τ]])d(τ) F #F = 1 τ d(τ) σ τ d(σ) (µ([[τ]])/µ([[σ]]))d(τ) µ([[σ]])d(σ) µ([[τ]])d(τ)

30 3 #F = F + 1 τ F {σ : τ σ} i < 2 F i = {σ F : τi σ} µ([[σ]]) µ([[τ]]) d(σ) = µ([[σ]]) µ([[τ]]) d(σ) = µ([[τi]]) µ([[τ]]) µ([[σ]]) µ([[τi]]) d(σ) σ F i<2 σ F i i<2 σ F i µ([[τi]]) d(τi) = d(τ). µ([[τ]]) i<2 µ([[τ]]) σ F µ([[σ]])d(σ) µ([[τ]])d(τ) 3.3 ( ). µ {0, 1} N µ- A {0, 1} N {U } N µ(a) = if µ(u ), A U. {0, 1} N 0 3.3 ( ). µ {0, 1} N N {0, 1} N µ- (effectively µ-ull) {U } N N µ(u ) 2, N U. α {0, 1} N {α} µ- α µ- (Marti-Löf µ-radom) µ- 3.4. µ {0, 1} N α {0, 1} N 2 1. α µ- 2. µ- d : {0, 1} <N [0, ) lim sup d(α ) <.. A 70% B 30% A 10/7 B 10/3 3.2

3.2 31. 2 A B A B A B (p i ) i N 0 < lim if p lim sup p < 1. 3.5 ( 1948). (p i ) i N (q i ) i N [0, 1] λ p λ q (p i ) i N (q i ) i N 3 1. i=0 (p i q i ) 2 <. 2. N {0, 1} N λ p (N) = 0 λ q (N) = 0 3. λ p (N) = 0 λ q (N) = 1 N {0, 1} N. (3) (1) i=0 (p i q i ) 2 = p i, q i [ε, 1 ε] ε > 0 ν ((p i + q i )/2) i N i N ( ) 2 pi + q i = p i q i (1 + (p i q i ) 2 ) p i q i (1 + (p i q i ) 2 ) 2 4p i q i 4ε 2. ( ) 2 ( (1 pi ) + (1 q i ) (p i q i ) 2 ) = (1 p i )(1 q i ) 1 + 2 4(1 p i )(1 q i ) (1 p i )(1 q i ) (1 + (p i q i ) 2 ) 4ε 2. σ {0, 1} <N ν([[σ]]) 2 λ p ([[σ]])λ q ([[σ]]) 1 i=0 (1 + (p σ q σ ) 2 ) i=0 (p i q i ) 2 = k > 0 k N k σ {0, 1} <N ν([[σ]]) kλ p ([[σ]])λ q ([[σ]]) N k λ p ([[σ]]) λ q ([[σ]]) k σ ν([[σ]]) 2 kλ p ([[σ]]) 2 λ p (N k ) ν(n k) k 1 k 4ε 2 λ q ({0, 1} N \ N k ) 1/k λ q (N k ) 1 1/k N = N k>2 N 2 k λ p ( k>2 N 2 k ) 2 λ p (N) = 0

32 3 λ q ( k>2 2 N k ) 1 2 λ q (N) = lim λ q ( k>2 2 N k ) = 1 3.6 (Vovk 1987). λ p λ q (p i ) i N (q i ) i N =0 (p q ) 2 = α {0, 1} N 1. α λ p - λ q - 2. α λ q - λ p - 3.1. µ ν {0, 1} N 2 1. µ(n) = 0 ν(n) = 1 N {0, 1} N 2. µ- ν-. (2) (1): R ν ν- ν(r ν ) = 1 R ν {0, 1} N \ R µ µ(r µ ) = 1 µ(r ν ) = 0 (1) (2): µ(n) = 0 ν(n) = 1 N {0, 1} N N µ U N µ(u ) < 2 N U ν(u ) = 1 V U ν(v ) > 1 2 µ ν V N W = m> U {W } N µ(w ) 2 ν(w ) = 1 N W µ- {0, 1} N \ W ν- α µ- α N W α ν- α N W ( 3.6). 3.5 (3) (1) =0 (p q ) 2 = λ p (N) = 0 λ q (N) = 1 N {0, 1} N 3.1 λ p - λ q - 3.7 (Vovk 1987). λ p λ q (p i ) i N (q i ) i N =0 (p i q i ) 2 < α {0, 1} N λ p - λ q -. α {0, 1} N λ p - d lim d(α ) = d d(σ) = d(σ) λ p ([[σ]]) λ q ([[σ]]) λq([[σ]]) λ p ([[σ]]). d q (σ) = d(σ) λ p ([[σ]])/λ q ([[σ]]) λ q - lim d q (α ) = α λ q - lim d q (α ) < d(σ) = λ q ([[σ]])/λ p ([[σ]]) d lim d(α ) =

3.2 33 d λ p - λ q - d ( c N)( N) log d(α ) d (α ) + c. d N α() d η 0 1 i {0, 1} d(α i) (1 η ) d(α ), if d α(), ( ) 1 p d(α 1 + η d(α ), if i = 0 d α(), i) = p ( ) p 1 + η d(α ), if i = 1 d α(). 1 p d d η d 10% d 10 i {0, 1} d (α i) d (α ) η, if d α(), 1 q d (α η i) = + d (α ), if i = 0 d α(), q η q 1 q + d (α ), if i = 1 d α(). ξ d α() d(α ) η, η ((1 p )/p ), η (p /(1 p )) N 1 d(α ) = (1 + ξ k ). k=0 p q θ > 0 p i q i [θ, 1 θ] m = 1/θ N 0 1/p, 1/(1 p ) m ξ [ 1, m] i = 0 d α() d (α + 1) d (α ) = η 1 q q = ξ η 1 p p 1 q = ξ ξ + η = ξ η (q p ) q p q 1 (1 p )q (q p ) ξ ξ m 2 (q p ) ξ m 2 ξ p q. N 1 1 ξ k m 2 ξ k p k q k d (α ). k=0 k=0 c ξ [ 1.m] log(1 + ξ) ξ cξ 2 1 log d(α ) = log (1 + ξ k ) = k=0 1 1 log(1 + ξ k ) k=0 k 0 1 ξ k c k=0 ξ 2 k.

34 3 =0 (p i q i ) 2 < c t 0 m 2 (p i q i ) 2 t ct + c. i=0-1 m 2 ξ k p k q k m 2 1 (p i q i ) 2 1 1 ξk 2 c ξk 2 + c. k=0 i=0 k=0 k=0 log d(α ) d (α ) + c. lim d(α ) = lim d (α ) = b N N d (α ) > b d = d + max{c, b + 1} d d d 1 d d d lim d (α ) =. 3.3. 100% 0 1 1/2 0 1 0% 0 1 1 : 3 1 : 3 0% 0% 0 3.4 ( 1917). s [0, 1] A {0, 1} N s (s dimesioal outer Hausdorff measure) { } λ s (A) = lim if 2 s σ : A [S], ad S {0, 1}. σ S

3.3 35 1 1 1 2 0 1 1 0 0 0 3.1. A {0, 1} N s [0, 1] 1. t [0, s) λ t (A) = 2. t (s, 1] λ t (A) = 0 3.5 ( 1917). A {0, 1} N (Hausdorff dimesio) dim H (A) = if{s [0, 1] : λ s (A) = 0}. 3.2. A {0, 1} N µ- λ(a) = λ 1 (A) α A {0, 1} N α A α A α α 1 0 Ville 1.2 0 1 3.6 ( ). s [0, 1] A {0, 1} N s λ s (A) {0, 1} <N {S } N N A [S ], 2 s σ 2. σ S A {0, 1} N (effective Hausdorff dimesio) edim H (A) = if{s [0, 1] : λ s (A) }. α {0, 1} N dim H (α) = edim H ({α}) 3.8 (Lutz 2000). A {0, 1} N s [0, 1] 2 1. A s 2. d : {0, 1} <N [0, ) α A t > s lim sup d(α ) =. 2 (1 t)

36 3. (1) (2): s > dim H (A) s λ s (A) = 0 {[U ]} N N A [U ], σ U 2 s σ 2. U Ville 1.2 d U σ {0, 1} <N U σ τ σ τ U d (σ) d ( ) = σ U 2 s σ 2 σ τ U σ 2 s τ, if U σ, d (σ) = 2 (1 s)m, if σ m U for m < σ, 0, otherwise. d(σ) = =1 d (σ) d α A A N U k N α k U k k N t > s d(α k ) 2 (1 t) k d k(α k ) 2 (1 t) k = 2(1 s) k 2 (1 t) k = 2 (t s) k lim sup d(α ) =. 2 (1 t) (2) (1): t > s k N V k {0, 1} <N { } V k = σ {0, 1} <N d(σ) : 2 (1 t) σ 2k. U k V k U k τ σ τ V k σ V k. σ U k 2 t σ 2 k σ U k 2 t σ d(σ) 2 = (1 t) σ 2 k σ U k 2 σ d(σ) 2 k 1.1 (2) A N [U ] λ t (A) t > s edim H (A) s 3.9 (Ryabko 1984; Mayordomo 2002). A {0, 1} N edim H (A) = sup lim if α A K(α ).. α A lim if K(α )/ < s s Q k N N K(α ) s k k N U k = {σ {0, 1} <N : K(σ) s σ k}

3.4 37 {U k } k N 1.2 σ U k 2 (s σ k) σ U k 2 K(σ) 1. σ U k 2 s σ 2 k A k N [U k] edim H (A) s edim H (A) < s s Q {0, 1} <N {U } N A [U ] σ U 2 s σ 2 σ 1 U (σ, s σ ) L (σ,r) L 2 r = σ 1 U 2 s σ =1 σ U 2 s σ 2 = 1 2.1 (σ, s σ ) c N σ 1 U K(σ) s σ + c α A t N α t 1 U lim if K(α ) 3.1 (Mayordomo 2002). α {0, 1} N dim H (α) = lim if s K(α ). =1. 0% 1 3.4. α 0 1 α α 3.7 (Shao 1948). p [0, 1] (Shao etropy) H(p) [0, 1] H(p) = p log p (1 p) log(1 p).

38 3 3.10 (Lutz 2000). α {0, 1} N p [0, 1] Freq(α) = p α H(p) lim if K(α ) H(p).. σ {0, 1} <N i {0, 1} #i(σ) σ() = i σ p = 1/2 p > 1/2 δ (0, p 1/2] Freq(α) = p 1/2 + δ lim sup #0(α ) 1 2 + δ. d 0 2δ d(α ) = (1 + 2δ) #0(α ) (1 2δ) #1(α ) log d(α ) p 1/2 + δ lim sup log d(α ) #0(α ) #1(α ) = log(1 + 2δ) + log(1 2δ) ( ) #0(α ) 1 = 1 + log 2 + δ #1(α ) + log ( 1 2 δ ). ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 + 2 + δ log 2 + δ + 2 δ log 2 δ = 1 H 2 + δ ε > 0 1/2 + δ p δ H(1/2 + δ) < H(p) + ε δ (0, p 1/2] lim sup (log d(α ) (1 H(p) ε)) = lim sup d(α ) =. 2(1 H(p) ε) ε > 0 α H(p) 3.11 (Lutz 2003). p (0, 1) λ p p α {0, 1} N λ p - α p H(p) lim if K(α ) = H(p).

3.5 39. α λ p - Borel 1.3 Freq(ξ) p ξ {0, 1} N λ p - Freq(α) = p 3.10 dim H (α) H(p) dim H (α) H(p) s < H(p) d λ- λ p d p λ p - d p σ {0, 1} <N d p (σ) = 2 σ λ p ([[σ]]) d(σ). log λ p ([[σ]]) = #0(σ) log p + #1(σ) log(1 p) #i(σ) σ {0, 1} <N i {0, 1} Freq(α) = p #0(α )/ p log λ p ([[α ]])/ H(p) N s+log λ p ([[α ]]) < 0 N d p (α ) = 2 λ p ([[α ]]) d(α ) = 1 2 s+log λ p([α ]) d(α ) d(α ) > 2 (1 s) 2 (1 s) α λ p - lim sup d p (α ) < s < H(p) 3.8 dim H (α) H(p) 3.2 (Egglesto 1949). p [0, 1] {α {0, 1} N : Freq(α) = p} H(p). 3.5. 2 0.α [0, 1] 0 1 α {0, 1} N 3.8. α R Ir(α) r R ε > 0 c > 1 p q q c r α p q > 1 q r+ε. α R (irratioality measure) if Ir(α) if = (Liouville umber)

40 3 3.12 (Staiger 1999). α R 0 lim if K(α ) = 0.. N l K(α l) l log. β [0, 1] N β p q < 1 q 0 p q [0, 1] q 2 q J,p,q = [ p q 1 q, p q + 1 q ] β 2 m q 2 m N m = log q 1 [0, 1] 2 m J,p,q 2 J,p,q p 0 (, p, q) p 1 (, p, q) 2 m p 0 (, p, q) p 1 (, p, q) β m = β log q 1 p i (, p, q) β (, p, q) (, p, q) p i (, p, q) [i,, p, q] p i (, p, q) 11 i < 2 0i 2 + 2 log + 2 log p + 2 log q p q 2 + 2 log + 4 log q β N C(β log q 1 ) log q 1 2 + 2 log + 4 log q log q 1 2 log q log. β q β 0 3.3 (Oxtoby 1971). 0. 0 (fiite state dimesio)

64 6 6.1 = =. k N k = {0, 1,..., k 1} X X T : X X (X, T ) (cotiuous dyamical system) x X (T (x) : N) (X, T ) 1 (symbolic dyamical system) X (X i ) i<k x X (T (x) N ) It(x) = (i[x; ] : N) k N T (x) X i i i[x; ] i[t (x); ] = i[x; + 1] T k N (shift map) sh : k N k N α k N sh(α)() = α( + 1) It X,T = {It(x) : x X} sh (It X,T, sh) 6.1 ( ; Adler/Koheim/McAdrew 1965). X U H X (U) = log mi{#f : F U, ad X F}. X U V U V = {U V : U U, ad V V} T 1 U = {T 1 (U) : U U} T : X X

6.1 = = 65 1 H(X, T, U) = lim H X(U T 1 U T ( 1) U). (X, T ) (topological etropy) et(x, T ) = sup{h(x, T, U) : U X }. 6.2. S k N (shift ivariat) N α S sh (α) S S k N (subshift) S k N S k N (S, sh S ) et(s) = et(s, sh S ) 6.1. S k N log(#{α : α S}) et(s) = lim 6.1 (Simpso 201x). S k N K(α ) et(s) = dim H (S) = sup lim if α S 6.2. S k N dim H (S) = edim H (S). dim H (S) edim H (S) S s 0 S I {0, 1} <N S σ I[[σ]], 2 s σ 1 2. I (k) I k I (k) = {σ 1... σ k : σ 1,..., σ k I} S α S σ α α S I S σ α τ I α [[σ τ]] k N S [I (k) ] 2 s σ = σ I (k) (σ 1,...,σ k ) I k 2 s( σ1 + + σk ) = ( σ I 2 s σ 1 ) ( 2 s σ k σ 1 I σ k I σ I ) ( ) k = 2 s σ 2 k I {I (k) } k N S s edim H (S) dim H (S)

66 6 6.2 (Fursteberg 1967). S k N et(s) = dim H (S) 6.3. S k N et(s) dim H (S) ( 6.2). U S I {0, 1} <N U = {[[σ]] : σ I} U S α S I {σ i } i N I α = σ 0 σ 1 σ 2... N k N σ 0... σ k 1 α σ 0... σ k. m = max{ σ : σ I} N S I + m S s 0 S s lim 2 s #S λ s (S) = 0 S I {0, 1} <N S σ I[[σ]], 2 s σ < 1. s I ( ) j 2 s( σ0 + + σk ) = 2 s σ < (σ 0,...,σ k ) I <N j=1 σ I M S I (σ 0,..., σ k ) 2 s < 2 ms 2 s( σ 0 + + σ k ) 2 s #S < 2 ms M lim 2 s #S et(s) s ( 6.1). 3.9, 6.2, 6.2 σ I 6.3 ( ). (X, µ) T : X X (measure-preservig) µ- P X µ(t 1 (P )) = µ(p ) (X, T, µ) (measure-preservig dyamical system) X µ- P P H X,µ (P) = µ(p ) log µ(p ). P P P Q X P Q T 1 (P) H(X, T, µ, P) = lim 1 H X,µ(P T 1 P T ( 1) P)

6.1 = = 67 (X, T, µ) (measure-theoretic etropy) et(x, T, µ) = sup{h(x, T, µ, P) : P X }. 6.4. S k N S µ (ergodic) µ- P S sh 1 (P ) P µ(p ) {0, 1} µ (shift-ivariat) P S µ(sh 1 (P )) = µ(p ) (S, sh S, µ) et(s, µ) 6.3 (Shao/McMilla/Breima). S k N µ S µ- α S et(s, µ) = lim log µ([[α ]]). 6.4 ( ). S k N et(s) = max{et(s, µ) : µ k N }. 6.5 (Simpso 201x). S k N α S et(s) = dim H (S) = dim H (α) = lim if K(α ).. 6.4 S µ et(s) = et(s, µ) s < et(s) s + ε < et(s) ε > 0 Shao/McMilla/Breima 6.3 µ- α S N log µ([[α ]]) > s + ε T = {σ k : µ([[σ]]) < 2 (s+ε) σ } µ- α S N α [T ] N U U = {σ k : K(σ) < s σ }. #U 2 s N µ([u ] [T ]) = µ([u T ]) < 2 s 2 (s+ε) = 2 ε µ([u ] [T ]) < =1

68 6 / µ- α S N α [U ] [T ] µ- α S N α [U ] K(α ) s s < et(s) Q s Q s = {α S : ( c N)( ) K(α ) s c}. s < et(s) µ(q s ) = 1 Q = {Q s : s Q, ad s < et(s)} µ- 1 3.9 α Q S et(s) dim H (α) dim H (α) edim H (S) 6.1.