ЭНТРОПИЯ НЕДООПРЕДЕЛЕННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРИ ОГРАНИЧЕНИЯХ НА ДООПРЕДЕЛЕНИЯ

  • Published on
    04-Apr-2017

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>2008 1(1)</p><p> 519.728</p><p>.. </p><p> , . </p><p>E-mail: sholomov@isa.ru</p><p> , </p><p> , (-</p><p>). </p><p> -</p><p>.</p><p> : , , , </p><p> , W-.</p><p> M = {0, 1, , m 1} T M aT. aT A, {a0, a1, , am1}, M, A0. A0 , A . aT ai, i T, - A A0, - . n A. - n = (nT, T M), TT n n= , Kn(n) -</p><p> n, aT, T M, nT . , - A0 Kn(n), - . Nn(n) , Kn(n). log Nn(n) ( ) - Kn(n).</p><p> ( . [1]), P = (pT, T M), pT 0, 1TT p = :</p><p>( ) min log ,T iQ</p><p>T M i T</p><p>H P p q </p><p> = </p><p> Q = (qi, i M), qi 0, 1ii q = . , -</p><p> T |T| 2 pT = 0, H(P) </p><p>0 1 0 1( , , ) log .</p><p>m i ii mH p p p p</p><p> = hn(n) = n H(n/n), n/n = (nT /n, T M).</p><p> [1] . 1. c = c(m), , Kn(n) -</p><p> hn(n) c log n log Nn(n) hn(n) + c log n.</p><p> (., , [2]). - s = (s0, , sm1), s0 + + sm1 = n, Kn(s) - (A0)n, ai, iM, si . , s n, Kn(s) ( ) Kn(n). -, S (A0)n n, S n. </p><p>( ) ( ).n n</p><p>K K</p><p>= s SS s S, n, Nn(n)S -</p><p> Kn(S), Kn(n), log Nn(n)S S- Kn(n).</p><p> [2] S- S ( 6) ( 7 ). -</p></li><li><p>30 .. </p><p> S, n. , - .</p><p> R = ||rTi|| , T M, i M. rTi 0, rTi = 0 i T, </p><p>,</p><p>1TiT ir = . R </p><p>,</p><p>( ) log .TiTi</p><p>Ti TiT i T i</p><p>rI R r</p><p>r r=</p><p> R , I(R) [3]. P = (pT, T M), pT 0, 1TT p = , Q </p><p>Q = (qi, i M), qi 0, 1ii q = . , R P Q, </p><p>Ti Tir p= Q = (q0, , qm1), ,i TiTq r= Q. infR I(R) R,</p><p> P Q, H(P)Q. , Q Q, H(P)Q. H(P)Q , infR minR. , H(P)W - W - W- [4].</p><p> S, n, hn(n)S = n H(n/n)S/n, S/n s/n, sS. S s, hn(n)s. n hn(n)s , ( ) min ( )nh h</p><p>=S s</p><p>s S</p><p>n n . -</p><p> .. c = c(m), , n S, S n, S--</p><p> Kn(n) </p><p>hn(n)S c log n log Nn(n)S hn(n)S + c log n.</p><p> .. n = (nT, T M) s = (si, i M), , T iT in s= , -</p><p> wTi( ),</p><p>Ti Tiw n T M= ( ),Ti iT w s i M= wTi = 0 (i T) (*)</p><p> , w = (wTi, T M, i M) - 0 0( , , )</p><p>Tiw T M i M= w , 0 1</p><p>Ti Tiw w T i.</p><p>. w uTi = wTi, Ti Ti Tiw w u = , T Tiin w = , i TiTs w = .</p><p>, Tn </p><p>is , (*) </p><p> , T iT in s = . [5] </p><p> s () t (), T, T M, i, i M, (s, T) - </p><p>Tn , (T, i), i T, 1 (i, t) -</p><p> is . </p><p>T iT in s = , -</p><p> (T, i) Tiw . - . </p><p>Tiw ( {0,1})</p><p>Tiw (T, i) </p><p> 0Ti Ti Ti</p><p>w u w= + , 0Ti</p><p>w , , , .</p><p> . . tS(n) - Kn(n), Kn(S). - x Kn(n) y Kn(S), , x y. y Kn(S), s = (si, i M). wTi aT x, y ai. wTi (*). - wTi y </p><p>0 1</p><p>0 , 1</p><p>,</p><p>!! !</p><p>! ! !</p><p>i</p><p>m i</p><p>T T m Ti</p><p>T T T i</p><p>s</p><p>s s</p><p>w w w</p><p>=</p></li><li><p> 31</p><p> Kn(n), </p><p>{ },(*)</p><p>,</p><p>!</p><p>( )!</p><p>i</p><p>i</p><p>TiwTi</p><p>T i</p><p>s</p><p>t</p><p>w</p><p>=</p><p>sn</p><p> , wTi , - (*). 0 wTi n , i T ( m), </p><p>1c</p><p>{ },(*)</p><p>,</p><p>!</p><p>( ) max ,!</p><p>i</p><p>i</p><p>wTi Ti</p><p>T i</p><p>s</p><p>t n</p><p>w</p><p>sn</p><p> c1 = c1(m) . </p><p>1</p><p>{ },(*)</p><p>,</p><p>!</p><p>( ) max ( ) max max .!</p><p>i</p><p>c i</p><p>wTi Ti</p><p>T i</p><p>s</p><p>t t n</p><p>w = </p><p>S s</p><p>s S s S</p><p>n n</p><p> Kn(n) ! !TTn n . -</p><p>, </p><p>1,</p><p>{ },(*)</p><p>! !( )( ) min min .</p><p>( ) ! !</p><p>TiT icn</p><p>nwTi T iT i</p><p>n wKN n</p><p>t n s</p><p> S</p><p>s SS</p><p>n</p><p>n</p><p>n</p><p> , z, z1, , zk, z 2, z1 + + zk = z, </p><p>( )log ! ! log log logj j jjjz z z z z z z= + , c2 c2, c2 = c2(k). </p><p>{ },(*),</p><p>log ( ) min min log log log log log .n T T i i Ti Ti</p><p>wTi T i T i</p><p>N n n n n s s w w c n</p><p> + </p><p> S</p><p>s S</p><p>n</p><p> ,</p><p>T i TiT i T in s w n= = = (*), </p><p>,</p><p>log log log ITi Ti i i TiT T</p><p>T i T i</p><p>w w s s wn n</p><p>n n</p><p>n n n n n n n</p><p> + + = ,</p><p>{ }{ },(*)</p><p>/</p><p>log ( ) min min I log</p><p>min ( / ) log min ( ) log ( ) log .</p><p>Ti</p><p>nwTi</p><p>n n n</p><p>wN n c n</p><p>n</p><p>nH n c n h c n h c n</p><p> = = </p><p>Ss S</p><p>s s Ss S s S</p><p>n</p><p>n n n</p><p> . s, hn(n)s = hn(n)S. - x Kn(n) y Kn(s) 1,2, , ! !TTr n n= 1,2, , ! !iiq n s= . </p><p> ||dqr||, yq, xr, dqr = 1 , yq xr, dqr = 0, . - ; bs(n). bs(n) .</p><p> R = ||rTi|| , H(n/n)s/n. wTi = nrTi (*). { }0Tiw (*), - wTi 1. xr = Kn(n) yq Kn(s), aT, ai, 0Tiw , </p><p>0</p><p>,! !</p><p>T TiT T in w . </p><p>0</p><p>,( ) ! !</p><p>T TiT T ib n w s n .</p><p> 0 1 u v , s , </p><p> (ln 1) 1u vs</p><p>s u</p><p>+ + , 1 [6]. -</p></li><li><p>32 .. </p><p>0</p><p>,</p><p>!! !</p><p>, ,! ! !</p><p>T</p><p>T</p><p>i T Tii T</p><p>T i</p><p>n</p><p>n n</p><p>u v s</p><p>s n w</p><p>= = =</p><p> 0</p><p>,</p><p>1</p><p>! !</p><p>( ) ( ) ,! !</p><p>Ti</p><p>T i</p><p>n n</p><p>T i</p><p>T i</p><p>n w</p><p>N N c nn s</p><p> S s</p><p>n n</p><p> c1 = c1(m) . 0 0</p><p>2</p><p>,</p><p>log ( ) log log log log log .n T T i i Ti Ti</p><p>T i T i</p><p>N n n n n s s w w c n + + Sn</p><p> , x 1 x log x - O(log x). , T i ( m), 0</p><p>Tiw wTi = nrTi:</p><p>3</p><p>,</p><p>log ( ) log log log log log ,n T T i i Ti Ti</p><p>T i T i</p><p>N n n n n s s w w c n + + Sn</p><p> log n. </p><p>3log ( ) I log .Ti</p><p>n</p><p>wN n c n</p><p>n</p><p> + </p><p> S</p><p>n</p><p> , </p><p>( )I I ( ) ( ) ( ),Ti Ti nw</p><p>n n r nH n h hn</p><p> = = = = </p><p> s s S</p><p>n n n</p><p> . . </p><p>( , ) log ,T iT i</p><p>H P Q p q= </p><p> H(P), H(P)Q, . [1, 2] , minQ H(P, Q) = minQ H(P)Q (= H(P)) , , Q0. - H(P, Q) , H(P)Q I(R) R, - . H(P, Q) H(P)Q hn(n)S - hn(n, S), hn(n, S) = minsS hn(n, s), hn(n, s) = n H(n/n, s/n).</p><p> 2. H(P, Q) H(P)Q.. H(P)Q R = ||rTi||. </p><p> Ti Ti r p= , .Ti iT r q= T, </p><p>f (x) = x log x ( )( )i i i ii if x f x i i jj Tq q = , xi = rTi / pTqi, </p><p> rTi = 0 i T</p><p>( ) 1log log log .Ti i Ti TiTi T j Ti j T iT i j T i T i jj T j T</p><p>r q r rr p q p</p><p>p q q p q p q q</p><p>= </p><p> T H(P)Q H(P, Q). . , hn(n, S) hn(n)S, .. c = c(m), , </p><p>log Nn(n)S hn(n, S) c log n. , hn(n, S) -</p><p> S- . , - .</p><p>. Kn(n) , .. - A = {a0, , am1, }, , A0 = {a0, , am1} ( aM). </p></li><li><p> 33</p><p>n = (n0, , nm1, n) Kn(s), s = (s0, , sm1), s0 n0, , sm1 nm1. , n/n = P = (p0, , pm1, p), P = (p0, , pm1), s/n = Q = (q0, , qm1).</p><p> log 0iiq = , H(P, Q) ( , ) logi iiH P Q p q= . , </p><p>1ii p p= , </p><p>0 1( , ) (1 ) log (1 ) , , (1 ) .1 1 1 1</p><p>i m</p><p>i</p><p>p p p PH P Q p q p H p H</p><p>p p p p</p><p> = = </p><p> Q0 = P/(1 p), H(P) = H(P, Q0) = (1 p)H(P/(1 p)). R, P Q. </p><p> rii = pi, ri = qi pi, 0 i m 1. ,</p><p>( ) ( ) log ( ) log</p><p>'log log ( ) .</p><p>i i iQ i i ii i</p><p>i i i</p><p>i i i ii ii i</p><p>p q pH P I R p q p</p><p>p q p q</p><p>q p q p Q Pq q p H Q p H</p><p>p p p</p><p>= = + =</p><p> = + = </p><p> ( )i ii q p p = </p><p>'( ) ( , ) log 0.i iQ ii</p><p>q p Q PH P H P Q p q p H</p><p>p p </p><p> = </p><p> Q = (Q P)/p, .. Q = P/(1 p) = Q0. </p><p>0</p><p>00</p><p>' ' '( ) ( ) ( ).</p><p>1 1Q</p><p>Q P P PH P H Q p H H p H H P</p><p>p p p </p><p> = = = </p><p> , H(P, Q) H(P)Q, Q0, 0</p><p>0H( ) H( , ) H( )QP P Q P= = . , hn(n, s) hn(n)s,</p><p> , hn(n).</p><p> 1. .. // . . 4. .: -, 2004. . 385 399.</p><p> 2. .. // - . . 1. 2007. . 14. 1. . 110 139.</p><p> 3. . . .: . , 1974. 4. : . .: , 1999. 5. ., . . .: , 1966. 6. .., .., .. // - . . 30. : , 1977. . 46 75.</p></li></ul>

Recommended

View more >