単純な規則で表わされるマルコフ過程の近似解析手法

全文

(1)社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 2004−AL−94 （11） 2004／3／19.

(2) !#" $&% ')( * +-,/.10323432343576-8-9:.74<;:=?> @ +3,-A&BDC:EF2:GIH JIKMLON P<QSR7TFUFVFW3RYX[Z3\^]1_[`SacbSdFeYf^gOhYikj<l:a^m[n[g:oMp?qsrtU<u?a^v<w-\-ex]1_Fy z ocU|{-V?e|}[~ D oMF?vFwsD^ MM/ R^^7/MFIo[1/<Fxg1[a| d[T^<fYgh[ij1lIa^m<nFgR^F7 1R-d?k [¡?¢3#r£rDUFfYghFij1l#?rD¤I¥]1_1¦ § ^bSd¨xe-c©?ª<^<u?aYvFw3\?e|«¬3®?ax¯<°Ic±-²31³M´:<e- [¡Yµ7®7¶Fu?aI·:¸teM¯1°/o {3V-ec}[~Rx¹º¸»©-ªFa|¼7½-^FvFwR?¢-|¶|P<QR7TFU^¾1¿£1a^À[Á)Â¯1°/oÄÃ)rD¤1U|<3vFwac <Å7ÆIx¿1®7¤^Ç<È[/ ÉFÊSËMÊÍÌ Î<Ï^Ð ÑÄÒYÓÔÕUYFxg1 †. Johannes Schneider†. †. 152–8552 E-mail: †[email protected]. †. (. 2–12–1. ). A heuristic analysis for Markov processes expressed by simple rules Yasuaki Niikura† , Johannes Schneider† , and Osamu Watanabe† † Graduate School of Information Science and Engineering, Tokyo Institute of Technology Ookayama 2–12–1, Meguro-ku, Tokyo, 152–8552 Japan E-mail: †[email protected] Abstract In this paper, we define a Markov process that is simple but yet has a large state, and propose a simple calculation that gives an approximateion (which we call “pseudo expectation”) of the average state change of the process. The behavior of some randomized algorithms can be approximated as simple Markov processes. However, it is often the case that the state space of such processes becomes large and that it is difficult to analyze their average behavior. Our proposed pseudo expectation could be a useful and easy tool for estimating the behavior of such processes. This paper considers the approximation performance of pseudo expectation through some experiments and analyses. Key words random walk, randomized algorithm. Ö Ù × Ø Ú Ûó<YôõÜköÄÝ÷Þ-ìùßDø1à:úIáÂâMûüæ[ãÄý<ä<þÂåDÿæç1cèêÿ^écñë^ìDkíMò î^ ï7õÜ[ ðDñMñkì ò

(3) ð å»æ7çFè éÄë õ ßcýYÜ-áÕâkò [ì 7ßÄï7Ü õ !"Fÿ|ÛcÜ$#%<ß kò'&kæ)( ÿ . /!01æ1ì 23Iá ò '<5ì 46 õ à 7ðê÷ÿc>ñ *+-, Ü #-%8xÛcÜ ?$á 9-á ò õ &k) æ ( *+,;:=< õ öx?'@Yñ8AÂý|ÜBCßDò46D"[ßkýcÜ$#-%EFG- õ N ' ì OPRQFßD ÿMIò HKJYâ õ L-MF ò S öÄ÷^õ T UV Rõ WEXRYLM ïFÜ Zc[ð G

(4) ]\-^ _ ý ñ5ì O8PÜ =` 1.. ÿ õ [ì kÿ|ÛÄÜ ð ðùßï<Ü kò õ 7kæ Ü ^ì»ï1kæYÜ ÿ Dð òkí õ Iß ð ^â YÜ xï 7Ü ÿ tõ ò æ1ìtò è |î Û|õÜ ÿõ cIÿxð ñâ ^Ü õ ß |Mâ â ^Ü ý ÿ ò xFâ Fÿ kÜ ò öÄ÷ Fõ Fñý kæ õ ãä æ<ì á ò õ í 3ð [ß Dâkò. i j 1 aDb Rc-de-f z $gh k /lm in8op!q j r E9 & )( * 01 ! s l'm [k-/Elm8 $ x _ y9ECz= tu _ /Biv 5wDG G R{P [4] - R|} ~ - v 5wDG 0 1 k/Dl'm8 , } i./ G {!') G R''B s lm k /El'm i!G ' _ [3]4D P z G ` 9 t-u _ @ i& )( *+ r 9 x 4 6 E 01 5 ^ ,. —1— −73−. n.

(5) Pn. ∃W,. f. zn. f. w  .  .  →W =  . . (n → ∞). ððQ BB õ- ßÛ|Ü |BMò ì2 OF ß ] ^ B 9 wz5wDoi ò B` TUa8b ;ÿ R

(6) S xï<Ü ^;[ ßGMâ I <ï Ü _ ^;[ ` &tæ ( *$+ , 2 ß w A[ ù ß à á âòS õ

(7) ý ì O PÄÜ w.

(8) fG-h . zn-1. . . [5]. zn+1. 2. 2. 1. & )*z +

(9) !

(10) &3"$ #%) '!(! '!(4 z "#% ! $ , $ .. / 2 0 $ 1 * f 5-6 '!(87 9;:4&=<!'2( ->?2@BA-C

(11) D &E-F n. 2. f. n. . õI y1öÄß»ï1÷LÜ M ßð ìKGxJ _ âsð ï1õ Ül'mIð[k-/Elm õR ì!HG 2.. L. M NOQP8RSUTV;W; RBX. k ò k æ Ü. ß ï1Ü. |ÿ|ÛxÜ^ð Dò î. i,j. (N) i,j. N. ∀i, j. >0. 0 < d < S.. Rep.Step: P(An ). +. P. ð Dò. fgG-h . pn = p0 P n → w. (n → ∞). + B0 = S, : [0, S] → [a, b]. T. !. Bn+1.      . An. =. Bn. min {d, An } min {d, Bn }.     . ð ï1Ü. − min {d, Bn }. cÿ ò. n := n + 1. `w yUn P(An ) =.

(12) . !. − min {d, An }. p0. ∃w, ∀p0 ,. 0. ð ï1Ü Gï ^ ì õ V $ì yQn3kðM á âkò'S õ ãkä[ì î[ý |}. An+1. (n → ∞).. w. s.t. PA. s.t. 0 ≤ a ≤ b ≤ 1 .. õ yunMø<ú:û æ ìDò a M yun ìc ý Dæ õ Rwv8xwy ð5gh ðùß»ï1Ü [ß ß <ÄâÜõ

(13) z I ÿ!${ ýGò;|U}9 z Þæð ï<Ü^ð Dæ ( *+ , ß-GÄâkò ì4r T yUnø<úIû. -B

(14) & )( *+, !G ~ _ 1 ` &. →w. P c. Init.Step: n := 0. 0. ∃w, pn = p0 P. Sn. zn = f n (z0 ) , z0 = S0 .. Instance: S, A0 , B0 , d ∈ N. fgG-h E iGj PE J J G N k N yon

(15) p G

(16) ( lQm ) ^ \ 1 ` pq & ( *+, !

(17) r T ysn _8 -t 5 SfgG-h p n. zn. Model: SimpleModel. ðêÿxÛxÜ õ ö ÷ t ò Ä Û Ü ß ò | â ß ÛxÜ Ü xÛxÜ ï<Ü |ÿxÛÄÜ ð ðÕÿ 1 ý æ ÿ k ò k 1 ø / ú û æ ð ß ∃N. [Ü ì ò. 2|w}

(18) ^

(19) [ = d ef $gh! . ? ê á â ò æ 01kæ õ s õ lm<ß àÄï<Ük /Dlm õ õ ì ý |ï1iý Üi&Bæ C (õ;B0 19æ<GkìðÄ8áêÄâkï[òÜ`w Q^ÿ * õ

(20) ýkò - ýDãä7ìÂî1ý

(21) 0-1Mæ1ì ï<Ü. ý ð ì ß ì àá æ. (N) pi,j. õ ùð ñ ð ò õ ß. f (Sn ) = E [ Sn+1 | Sn ] .. & ( * . / ! 546 '

(22) |w}

(23) ' ^ [ 3` |U} _; ^8[ . ^ [ ^ \ ] Q & )( * +, YZ _ 8 ^ ^ [ 1 `ba M P = (p ) 4c-& ( *5 _8 + , 8d e 5 P = p 2. 1. { Sn | n > 0 }. P(An ). !. !. : P(An ) : 1 − P(An ) .. ì. wAn wAn = wAn + Bn (w − 1)An + S. (w ≥ 1). ð á ò òB¡ w õð$g'#h%1ìið»ß»uï1'Ü a M yun! »P; õ P;ß$ GMâkò ^[. (1). w = 1, w > 1. SimpleModel. —2— −74−. ∀n, An + Bn = S.

(24) xß. kò . I z59 fG-h- B E. ". !. An+1 Bn+1 An. !. An. |. Bn. min. Fßý. ;t. −P(An ) + (1 − P(An )). Bn. (. +d. P(An ) − (1 − P(An )). !. |An − A0 | mod 2d =. if. An < d. P(An ) = 1. if. S − An < d. ÿx EÛ|xÜõ BCtò S U|

(25) Mÿ

(26) Dò8|Q} õ ì B ïì % 7õ ÜYð ï?ð ò iÜ Dõ 8SB ð$w<] Üiõ B!ysC n õ õ w^[ ðÂýcÜ _ ^ ` ì 2ß c! (2). pi,j. =. B0. !. Äÿ Dò ð õ õ Fß ¬æ Õò õ 3.. ". ì ß ß ÄÄÜ <ï Ü Mâò õ ÿß Äâ Ü. n. n. n. n. n+1. n. n. õ 7Ü 7ð ì ßà á7-âý. n. ∀n. -z I. . f. n. ÿMÛ G ò a M î . = f (E [ Sn ]),. zn. ÿkò. n→∞. õ

(27) ý D[ìï-. $|Q} ). . O ... . ... O. . pS−d,S. pS,S−d.          . (4)       . ÿ |õ ì ò ß 1ðx7ì áêâ<[â ò Ü xÜ õ tò ÿxò õ [ì cð áÂò õ õ õ < Ü ý î [ ì MÜ . (2) i,j. 2. f. S . w+1. (2). (2). . p0,4d. ···. p0,Se.  (2)  p2d,0. p2d,2d. (2). p2d,4d .. .. (2). ···. pSe ,2d. (2). pSe ,4d. (2). ···. p2d,Se . pSe ,Se. (2). (2). . . .. .. (2). pSe ,0 (2). (2). (2). (2).  ,   . pd,d. pd,3d. pd,5d. ···. pd,So.  (2)  p3d,d. p3d,3d. (2). p3d,5d .. .. (2). ···. (2). pSo ,5d. (2). ···. p3d,So . . .. .. (2). pSo ,d. (Se , So ) =. —3— −75−. (2). p0,2d. Po =  . zn = E [ A n ]. (2). (2) i,j. p0,0. Pe =  . zn = f (zn ). lim zn =. i+d=j. - S

(28) f G-h ^ \ 3` SimpleModel s G ynFE A _; 1G T 2 2ciQ y nB H I n→∞ -z I . 8 BEC A :even O P (odd # % (6) |J

(29) 'w K5LE P8M'G ) - N o JO {p |i + P = p G s 2 f S

(30) 2 - j mod 2d = 0} O P . (w + 1)An − S f (An ) = E [ An+1 | An ] = An − d · (w − 1)An + S ∀n. if. O. ö iLM^õT U'V ß ÷ ÿ ß M Ü Äâ MÜcð ò ðÂý G ò õ # %8 ì$4 A ðêÿ10 z<Ü4|fg} G-õ h

(31) B BP1á ò ý 2Y õ 354 V 2ì c! w=1. i−d=j. p0,d.  ..  .     pd,0   .. P = .   ..  .   ..  . . E [ Sn ] = f n (S0 ) = zn .. SimpleModel $$% G iO P. ∈. otherwise. P = (pi,j. . 2. = E [ f (Sn ) ]. ß. 0. if. n. E [ Sn+1 ] = E [ E [ Sn+1 | Sn ] ]. ?. (i, j. n. z n = E [ Sn ] .. *+)sG. / P. 1 − P(i).  . d. v 5wEG ` # ! $

(32) &% - 46 _ 'w A k/Elm z SimpleModel c de f 3. 1 i Q *+ #-% P ( ) G S , 4c! z ^ \ 2` & ( * + , E [ S | n ≥ 0 ] _8 ^ [ R f *$+ Q f (S ) = E [ S |S ] z S k /lm z -G ;|} fgG-h'!. (3). (n : odd) .. Pr { An+1 = j | An = i }.    P(i). pi,j =. (2). A0. (n : even). {0, 1, . . . , S}). (. 1. 0 d. n. Instance. (1)). (. ;< E õ ß D â =G|ß?> @YýA õö÷ > BCÄï1Ü ð»ìIáÕâ G^Ü B ò ð ï[Ücð ò D. P(An ) = 0. ò. 7BxB [ ^ 1] sP G 68| }yfgG-h'! _98: 1 ` 3. 2 An. !#. ð O ÄP Ü ð$Mÿ|ñÄÜ! w =. G. (. pSo ,3d. (2). (2). pSo ,So.   .  . (S, S − d). (S mod 2d = 0). (S − d, S). (S mod 2d = d) ..

(33) ò . B. (4). ^ßtòyUnkø[úIû æ õ'^

(34) [ ÿ|ÛxÜ. . HG (. (2) pid,jd. >0. if. =0. otherwise. ÿxÛ|Ü ðÂß 8: t ï1Ücð ò. |i − j| ≤ 2. ø<úIû æ. N X. (5). zyon. pˆj = 1,. j=0. ì G òPDâ0 ^8z\ 1Üÿi $ ` õ W , z JY=âGcõßuhÄìÿ|Û ï / õ Pky ß nY !øúO28û Y æ õ'^ HYÿxÛxÜ ß àáÕâùò ß 8: ï<Ücð ∀j ∈ [0, N ].  pe,n = (Pr { A2n = 0 } , Pr { A2n = 2d } ,     . . . , Pr { A2n = Se })  po,n = (Pr { A2n+1 = d } , Pr { A2n+1 = 3d } ,   . pˆj ≥ 0. S+1. [. . . . , Pr { A2n+1 = So }). 4]. pˆ. An. pn = (Pr(An = 0), Pr(An =. . ìâ cõ M&Dæ)î ( *$ðù+-ý|, Ü 2 ßùàá ÿ2

(35) Y õõ ';4^ÿÄ4ÛMf Ü G= hð$»$ò ^9c\ Ü1ÿá â [^; \ uG ò iEG|â'O PcÜFð ò ß G a âMò ß»àáÕâ õ O!Jcâ

(36) pYßý|Ü õ ÿkò ß'DGx

(37) âp;qY ý õ 4 õ H?ß$QMï?Ü 1ßkòG T ì$cE v &Mæ ( *R+!, ÿYÛ^Ü ðB89<Ü. ß A $ð ;i8PÄÜ ï1Ücð ^;\ uG ò z õ &æ ( *+ , ÄÛxÜ ^ H<2ß -Qkï[Ü / Pßò yQnE õ V ßtâSõõ 0

(38) 1ý

(39) kò ÿ1G T ì2ciyUnBH1ìI[Ü , ì4c ðì$y:áÕâ)A æ[ßRGÄâ HG!" õ |U}Äò ð A ÿMò y nH<ß-GMâ'S õ^8\

(40) f G-h' õ ð»ñ ò ^\ sG|}

(41) f G h' _98: ` _ ^8\ ` ß Gâò a M yQn ß»àkï ^Ü H<ì ð ï<Ücð ò

(42) |w}-$f G ò õ ^ H |Q} õ

(43) ý A#BH1ì5Äï h'! 1), . . . , Pr(An = S)). (6). Ae,n = A2n , Ao,n = A2n+1. pe,n. (5). Pek. pn P 2 = pn [. ∃k ≥ S/d. 4]. [. An. n→∞. 2. (Ehrenfest. [2]. An. 2. P. SimpleModel. 0. lim Pr(A2n = j) =. n→∞. (. - z I.. àIÛxÜá ò ^ H [ì. oh W , pî =. if j = i d, i ∈ N. $. if |A0 − j|/d : even. 0. otherwise .. (. fest. n→∞. . õ g<Ü ð $ P

(44) %&'() õ # %8ò8Y8Z[ß w = 1, d = 1. N j. 2−S .. SimpleModel. [ß.

(45) Y

(46) Z. S . 2. Ehren-. w 6= 1. 2 pˆj. if |A0 − j|/d : odd. 0. otherwise . An. lim E [ A2n ] 6= lim E [ A2n+1 ]. n→∞. lim. õ D^ÿ

(47) FñáB& õ ;|Q}MÿxÛ|Ü if. i=0. if. i=S. if. 0<i<S. E [ An ]. 2. 2. P. n→∞. SimpleModel. E [ An ] + E [ An+1 ] d (2M − 1 + w) = . (7) 2 2(1 + w). lim |E [ An ] − E [ An+1 ]| ≤ d .. n→∞. and i/d ∈ N otherwise .. n→∞. n. pˆP = pˆ .. pî−d · pi−d,i + pî+d · pi+d,i 0. Fßò. otherwise .. n→∞. pˆ(A = j) =. 2.   pˆd · pd,0      p  ˆN−d · pN−d,N       . 2]. lim E [ A2n ] = lim E [ A2n+1 ] = lim zn =. 2 pˆj. SimpleModel pˆ. [. ð ùý|ì5MÜ*ï -Cò8õV@YñßG GMâÿ ò8|Q} õ õ + V $fgG TG-hõ v õ B %^Ü ß n ß a M yKD _ ,+ ` ß GÄâk8ò |}-fgG-h ;|Q}^ì BtïyUnø[ú:û æ õ ð ÿ. lim Pr(A2n+1 = j) =. n→∞. ). w=1. n→∞. pˆ = (ˆ p1 , pˆ2 , . . . , pˆS ). . 2. d, w. SimpleModel. 2. M = S/d (M ∈ N). pˆj =. 2. 1. ). M −i−1 {M +i(w−1)} M 1 w 2 i M (w+1)M −1. 3]. (. 1. (. Pr(An = i). Ae,n. Ao,n. 4. (3). -/. 1021436587:9<;>=@?BAC7ED<F<G!HJI [1] K P:Q. —4— −76−. Theorem VIII. (8). L:M<N!K>O.

(48) -z I. . (7). ßGMâ. ß 8: ï1Ücð ò8|} õ õ 10 z <Ü 2. E [ Ak ] + E [ Ak+1 ] lim n→∞ 2 =. S X. _. pˆ(A = i) i. i=0. =. M X 1 wM −i−1 {M + i(w − 1)} M i=0. M (w + 1)M −1. 2. . M −1. w d = 2 M (w + 1)M −1. + (w − 1). M. |. i=0. id. w. w. {z. i. {z. i2. }. . _. . d (2M − 1 + w) . 2(1 + w). (8). ßGÄâò. M :odd. õ # %. `. n. . E [ An ] + E [ An+1 ] − zn 2. M ò õ Fô. P(x) =. . {Pr(Ak = 2i d) |2i d − f (2i d)|}. |. |2i d − f (2i d)| ≤ d. 1. {z. ≤d. }. n. ≤d.. Rep.Step.

(49) M2

(50) X {Pr(Ak = (2i − 1)d)(2i − 1) d lim

(51)

(52) k→∞ i=1

(53)

(54) − Pr(Ak+1 = 2i)2i}

(55)

(56). n. n. 0. d. õ + ð ò . S a) Instance b8cdZ( [e/f 1] gihkjld_A 8.m f I " E )on/ pq su pq z}) vw

(57) x2y/ T,z_oRa{D" d =E5,[ AA ]=rt600 .0 E [ A ] r z 1~rkl/|18f w= {2, .2 ,5,)10}E l) w = 5, A = 600 r|f ) d = {2, 5, 10} .0 8 E [ A ] r z 1~l/22 3 .,,/ 2Q I ( ;A

(58) t(8 2[ n) "!8[ S r I ) E [ A ] r z t(,{BF 8 "t r ,.),V!B8S n ., I E [ A ] ,\ 2/ R2 rD lim |E [ A ] − E [ A ] | [ 2] (8) r A_ % r V8/¡ ¢ £ " O8¤ )¥ d, w, A . I E [ A ] B¦!!§ )V! n .1<8 1\ ¨© 2 ª0 '2)R«¬ l) E [ A ] 3[ g ® F! ol¯c 0. M :even. 8{. wx , w ∈ {1, 2, 5, 10} . wx + (S − x). n.

(59)

(60) − Pr(Ak = 2i d) E [ Ak+1 |Ak = 2i d ]}

(61)

(62). ÿò L ÿxÛ|Ü ð»ß! ÜR k õ ß$%ÄÜ õ # %ùò8|Q}|ßGMâ õ ED[ì»ï R =1ÜR. E M . õò. S = 1000, A0 ∈ [0, S] , d ∈ {1, 2, 5, 10} ,.

(63)

(64) = (2i + 1) d) (2i + 1) d}

(65)

(66). i=0. n. n. i=0. k→∞. n. n. Mc

(67) bX

(68) 2

(69) {Pr(Ak = 2i d) 2i d = lim

(70) k→∞. = lim. d(w − 1) . 2(w + 1). n. i=0. Mc bX 2. ß MÜ. =. # $ % &'() SimpleModel *,+,-/.1022) A 34 526878.9:;<)=> 1?2@BADC!EFGH z I 1" 4. 1 J,KL,M2N OP .RQ I *+7S Instance /A ') A 1T/U2V W .10 RXYZS1[2\9,:

(71) ]S_^`". Mc

(72) bX

(73) 2

(74) = lim

(75) {Pr(Ak = 2i d) 2i d k→∞. − Pr(Ak+1. . 4.. lim

(76)

(77) E [ Ak ] − E [ Ak+1 ]

(78)

(79). k→∞. 2. z5ii n → ∞ $% E [ A ] z v

(80) !" E[A ].

(81)

(82).

(83)

(84). `. 1. lim. +1) (1+ w1 )M −2 w1 M ( M w. =. 2.

(85)

(86)

(87)

(88)

(89) lim E [ An ] − lim E [ An ] + E [ An+1 ]

(90) ≤ d .

(91) 2

(92) n→∞ n→∞ 2. n→∞. }. 2. 2. i. i. (1+ w1 )M −1 w1 M. M X 1 i M. |. i. M X 1 i M i=0.

(93)

(94)

(95)

(96) |b − a| a + b

(97) a + b

(98)

(99)

(100)

(101) =

(102) b −

(103) =

(104) a −. n. n. n. n. n. n. n→∞. n+1. 2. 0. n. n. limit {g (E [ An ])} = max. 2. n. o. lim g (E [ A2n ]) , lim g (E [ A2n+1 ]). r ° I % r . I R" ±³² 2´¶µ¸·k¹º<»½¼¾D¿}À,ºÂÁÃÄ}ÅÆ`ÇÈÉÊ<ËoÌÍÏÎkÐ

(105) Ñ<ÉÒoÓ ÔÖÕ ÄØ×ÙÂÚRÛÝÜÖÍ d = 20, w = 10 É 10 n→∞. n→∞. −3. —5— −77−.

(106) 600. 3.5 E[An] for d=5, w= 2 zn for d=5, w= 2 E[An] for d=5, w= 5 zn for d=5, w= 5 E[An] for d=5, w=10 zn for d=5, w=10. 500. E[An-zn] for d= 1, w=5 E[An-zn] for d= 2, w=5 E[An-zn] for d= 5, w=5 E[An-zn] for d=10, w=5. 3. 2.5 400 2 300 1.5 200 1. 100. 0.5. 0. 0 0. 200. 400. . 2 E [ An ]. w = 2, 5, 10. zn. 600. . d = 5. 800. 1000. 0.

(107) . 500. 1000. 4 E [ An ] − zn d = 10, 5, 2, 1. 600. . 1500. w = 5. 2000. 2500.

(108) 1". 2.5 E[An] for d= 2, w=5 zn for d= 2, w=5 E[An] for d= 5, w=5 zn for d= 5, w=5 E[An] for d=10, w=5 zn for d=10, w=5. 550 500. E[An-zn] for d=5, w= 2 E[An-zn] for d=5, w= 5 E[An-zn] for d=5, w=10. 2. 450 400. 1.5. 350 300. 1. 250 200. 0.5. 150 100. 0 0. 200. 3 E [ An ]. . d = 2, 5, 10. J,K. 400. zn. 600.

(109) . w = 5. 800. 1000. . n. d = 5. 2500. + 1D. 30. n. n. n. n. n. 15. 10. n. 5. E[| An - E[An] |] for d= 1, w=5 E[| An - E[An] |] for d= 2, w=5 E[| An - E[An] |] for d= 5, w=5 E[| An - E[An] |] for d=10, w=5. n. n. 0. 20. n. n. n. 25. n. n. n. C. 2000. 35. 0. n. n. 1500. I : E [ A n ] − zn. n. n. 1000. w = 10, 5, 2. w = 5, A0 = 600 n. 500. 5 E [ An ] − zn. D) d = {1, 2, 5, 10} .02 r

(110) | f E [ A ]−z <_}lR 4 .) d = 5, A = 600 .08 E [ A ] − z r1<l8 |f,k) w = {2,.5,10} , Q I ( ZAo(,t 5 1[ n) ",V/S n . I E [ A ] − z \!( d . l -l,!D!"1<ª" !,o,) a;h ') &% (t/.*( )+[#!R 2](p.5) '$ % rr% w E[A ]−z (2 ,+-\ (XYB.8( limit hA1 {E [ A ] − z }) . \Q I 2

(111) /10 .S" % 23Z4+5 r 67 % r . I " 4. 3 J,K II : E [ |A − E [ A ] | ] ) w = {1, 2, 5, 10} .0/ d = 5, A = 600 rR|,f 2 E [ |A − E [ A ] | ] 2,Q;l/A1 6 ' 8 R"8 E [ A ] − z 2 ( 4) . h:9; < '=">

(112) ? % hÖ) E [ A ] − z ="> @ !.S!A RZ.a REBh<B2 E [ |A − E [ A ] | ] ¨2© 2 2 T / z ' R" % r 4. 2. 0. 0 0. 500. 1000. 1500. 2000. 2500. EF w = 5 * E F EFG. % ',) A .;<=> H . ^D.vw I 18§ 1" d ∈ {2, 5}, w ∈ {1, 2, 5, 10} . a22,) A Rvw . —6— −78−. 6 E [ |An − E [ An ] | ] d = 10, 5, 2, 1. 0. 0. r=. maxn {E [ |An − E [ An ] | ]} limit {|An − E [ An ] |}. (9).

(113) H . ^.1v2w k d 1l8 ) /( © \ A ) " % 22 k) (. 7. ' 8. L J"K. N1OM klim l*)+2'8(). 0. A0 > lim. E [ An ] + E [ An+1 ] 2. L J"K. ^t.a r > 1 r S) I SF=">

(114) ? % r 2t" r ^ % r n→∞. L J"K. 1.2. 1.15. 1.1. 1.05. 1. 0.95 200. 400. 600. 7 maxn {E [ |An − E [ An ] | ]}.

(115) EE F .

(116) 1 "!#'. 5.. $. . 800. 1000. limit {|An − E [ An ] |}. . w = 10, 5, 2, 1 d. %. , -&/.aBknt p,q rosu pq E [ A ] − z 1 1Zk¦8()<X,Y.'( I % r '8Rl"<) , -E2' 2* )+ ,k2 -2[ / ,_\' 8 % r (,)5267 .

(117) Tt DSl"rD. ') Instance . . !() ,-& r (0t &' 1\ QE;^ ¯c T!8 Dl" @ 8 R n .Ra n. n. δn = E [ An+1 ] − f (E [ An ]). n. ∆n = E [ An ] − zn = E [ An ] − f (A0 ). aB{ r ) 31[ f "132 ¯cZ( δ = 0 ' 8 54 F g h

(118) j80!""6.7F98) : 12 ¯cB. ∆ = 0 S8 2( δ 6= 0 ' 8 % r . . 1" % . h`) ∆ 6= 0 r . ;5= ® F<>9?/7 < S @3AZ δ rCB9D I " ∆ . /8) ' ,. 8 AR3t } 2V/,S n 8 ∀n > 0 δ 6= 0 ' ∆ 1\ E <F {

(119) () δ ∃n > m ∆ 6= 0 . ) n − m → ∞ ' 0 .F,- I G9? 8 ®l8F;3= <. R" r B9D O H . h ) ∆ = E [ A ] − z => r ^ 23Z.0 9 2 ) I . ^k. J"K I " n. n. n. n. n. n. n. n. m. n. n. n. ]−zn. δn = E [ f (An ) ] −. '&"R r. {δm |0 < m < n}. V W Y[Z X \] T^ 2) O8P _& GtF! < ""`9.9& r (a SimpleModel . h .b/7S cdfe,ghd9i r j*k I % ' 8 l-tF8aT\*m8 ghd!( O8P . ^<Sn 08r l!A + o !l2" a .p B0 d q [Z.ª808" [ef 1] A0 ktkS <) % n r k]/S!1l5,6Z

(120) ()sr l % r

(121) Ttv. 156?@! ,!2Sv2w("Z x . u rsw B <!S21!,l" . !,2)T'3! ( 7. a A!2{1(" z 9 y { 7. % ". n r ) j*k I % ( }~*o f| r r k B " "]5a I OH !. d ', B5D 2 kZ<cd, e nghd3i jk '8 GF2!l r r A!^.& r <a An RV W TE _ F {E'2

(122) n! pq q n'( "* otR" E [ A n − zn ] r!os,. u p,!, I < w zn . )) nh . ôSp, % .". h9 ~! 8 . q I ." uZ.R(s),u56 hJf ' K /l % r

(123) R ©9V . l" P =C>2 <'! (

(124) )</ 5 An % *Z . 2. 8 l;hÖ)v¡<¢ P

(125) E l , £ 5 ¤ T, ¥ xt. ¦ {§3¨3; U E I " © ª [1] M. A. Berger, An Introduction to Probability and Stochastic Processes, pp.107, 1993. [2] W. Feller, I , , 1961. [3] H. Takahashi and Y. Niikura. An extension of AzumaHoeffding inequalities and its application to an analysis for randomized local search algorithms, 6 (IBIS2003), Kyoto, pp.177–181, 2003. [4] O. Watanabe, T. Sawai and H. Takahashi, Analysis of a randomized local search algorithm for LDPCC decoding problem, In SAGA03. [5] , , , , OR 4 DP , pp.135–152, 1964.. «¬® ¯<°. = E [ f (An ) ] − f (E [ An ]). .r. VQP &SR r. R!(T.U I " & ]). A0. 6.. 1.25. 0. An. An. n. <h tS\Z V. P C = > I R". E[ An ]+E[ An+1 ] 2. ,/3("M .∆U I =R"E [ A. rario of max/lim for d=2, w= 1 rario of max/lim for d=5, w= 1 rario of max/lim for d=2, w= 2 rario of max/lim for d=5, w= 2 rario of max/lim for d=2, w= 5 rario of max/lim for d=5, w= 5 rario of max/lim for d=2, w=10 rario of max/lim for d=5, w=10. 1.3. 2M. f (E [ An. 1.4. 1.35. n→∞. n. n. —7—E −79−. ± ²³"´µ¶·. ºT» ¼n½¾T¿"ÀÁÂÃÄ ÅÆ. Ê Ë ÌTÍ ÎÏ " Ð ÑÒÓ ÔÕ<Ö ÚÇÛ ÈÉ ½ «1 ¬ ÜÞÝ ß à¿. ¸. ×ØEÙ. ¹.

(126)