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

  • Published on
    04-Apr-2017

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

  • 2008 1(1)

    519.728

    ..

    , .

    E-mail: sholomov@isa.ru

    ,

    , (-

    ).

    -

    .

    : , , ,

    , W-.

    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) -

    n, aT, T M, nT . , - A0 Kn(n), - . Nn(n) , Kn(n). log Nn(n) ( ) - Kn(n).

    ( . [1]), P = (pT, T M), pT 0, 1TT p = :

    ( ) min log ,T iQ

    T M i T

    H P p q

    =

    Q = (qi, i M), qi 0, 1ii q = . , -

    T |T| 2 pT = 0, H(P)

    0 1 0 1( , , ) log .

    m i ii mH p p p p

    = hn(n) = n H(n/n), n/n = (nT /n, T M).

    [1] . 1. c = c(m), , Kn(n) -

    hn(n) c log n log Nn(n) hn(n) + c log n.

    (., , [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.

    ( ) ( ).n n

    K K

    = s SS s S, n, Nn(n)S -

    Kn(S), Kn(n), log Nn(n)S S- Kn(n).

    [2] S- S ( 6) ( 7 ). -

  • 30 ..

    S, n. , - .

    R = ||rTi|| , T M, i M. rTi 0, rTi = 0 i T,

    ,

    1TiT ir = . R

    ,

    ( ) log .TiTi

    Ti TiT i T i

    rI R r

    r r=

    R , I(R) [3]. P = (pT, T M), pT 0, 1TT p = , Q

    Q = (qi, i M), qi 0, 1ii q = . , R P Q,

    Ti Tir p= Q = (q0, , qm1), ,i TiTq r= Q. infR I(R) R,

    P Q, H(P)Q. , Q Q, H(P)Q. H(P)Q , infR minR. , H(P)W - W - W- [4].

    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

    =S s

    s S

    n n . -

    .. c = c(m), , n S, S n, S--

    Kn(n)

    hn(n)S c log n log Nn(n)S hn(n)S + c log n.

    .. n = (nT, T M) s = (si, i M), , T iT in s= , -

    wTi( ),

    Ti Tiw n T M= ( ),Ti iT w s i M= wTi = 0 (i T) (*)

    , w = (wTi, T M, i M) - 0 0( , , )

    Tiw T M i M= w , 0 1

    Ti Tiw w T i.

    . w uTi = wTi, Ti Ti Tiw w u = , T Tiin w = , i TiTs w = .

    , Tn

    is , (*)

    , T iT in s = . [5]

    s () t (), T, T M, i, i M, (s, T) -

    Tn , (T, i), i T, 1 (i, t) -

    is .

    T iT in s = , -

    (T, i) Tiw . - .

    Tiw ( {0,1})

    Tiw (T, i)

    0Ti Ti Ti

    w u w= + , 0Ti

    w , , , .

    . . 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

    0 1

    0 , 1

    ,

    !! !

    ! ! !

    i

    m i

    T T m Ti

    T T T i

    s

    s s

    w w w

    =

  • 31

    Kn(n),

    { },(*)

    ,

    !

    ( )!

    i

    i

    TiwTi

    T i

    s

    t

    w

    =

    sn

    , wTi , - (*). 0 wTi n , i T ( m),

    1c

    { },(*)

    ,

    !

    ( ) max ,!

    i

    i

    wTi Ti

    T i

    s

    t n

    w

    sn

    c1 = c1(m) .

    1

    { },(*)

    ,

    !

    ( ) max ( ) max max .!

    i

    c i

    wTi Ti

    T i

    s

    t t n

    w =

    S s

    s S s S

    n n

    Kn(n) ! !TTn n . -

    ,

    1,

    { },(*)

    ! !( )( ) min min .

    ( ) ! !

    TiT icn

    nwTi T iT i

    n wKN n

    t n s

    S

    s SS

    n

    n

    n

    , z, z1, , zk, z 2, z1 + + zk = z,

    ( )log ! ! log log logj j jjjz z z z z z z= + , c2 c2, c2 = c2(k).

    { },(*),

    log ( ) min min log log log log log .n T T i i Ti Ti

    wTi T i T i

    N n n n n s s w w c n

    +

    S

    s S

    n

    ,

    T i TiT i T in s w n= = = (*),

    ,

    log log log ITi Ti i i TiT T

    T i T i

    w w s s wn n

    n n

    n n n n n n n

    + + = ,

    { }{ },(*)

    /

    log ( ) min min I log

    min ( / ) log min ( ) log ( ) log .

    Ti

    nwTi

    n n n

    wN n c n

    n

    nH n c n h c n h c n

    = =

    Ss S

    s s Ss S s S

    n

    n n n

    . s, hn(n)s = hn(n)S. - x Kn(n) y Kn(s) 1,2, , ! !TTr n n= 1,2, , ! !iiq n s= .

    ||dqr||, yq, xr, dqr = 1 , yq xr, dqr = 0, . - ; bs(n). bs(n) .

    R = ||rTi|| , H(n/n)s/n. wTi = nrTi (*). { }0Tiw (*), - wTi 1. xr = Kn(n) yq Kn(s), aT, ai, 0Tiw ,

    0

    ,! !

    T TiT T in w .

    0

    ,( ) ! !

    T TiT T ib n w s n .

    0 1 u v , s ,

    (ln 1) 1u vs

    s u

    + + , 1 [6]. -

  • 32 ..

    0

    ,

    !! !

    , ,! ! !

    T

    T

    i T Tii T

    T i

    n

    n n

    u v s

    s n w

    = = =

    0

    ,

    1

    ! !

    ( ) ( ) ,! !

    Ti

    T i

    n n

    T i

    T i

    n w

    N N c nn s

    S s

    n n

    c1 = c1(m) . 0 0

    2

    ,

    log ( ) log log log log log .n T T i i Ti Ti

    T i T i

    N n n n n s s w w c n + + Sn

    , x 1 x log x - O(log x). , T i ( m), 0

    Tiw wTi = nrTi:

    3

    ,

    log ( ) log log log log log ,n T T i i Ti Ti

    T i T i

    N n n n n s s w w c n + + Sn

    log n.

    3log ( ) I log .Ti

    n

    wN n c n

    n

    +

    S

    n

    ,

    ( )I I ( ) ( ) ( ),Ti Ti nw

    n n r nH n h hn

    = = = =

    s s S

    n n n

    . .

    ( , ) log ,T iT i

    H P Q p q=

    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).

    2. H(P, Q) H(P)Q.. H(P)Q R = ||rTi||.

    Ti Ti r p= , .Ti iT r q= T,

    f (x) = x log x ( )( )i i i ii if x f x i i jj Tq q = , xi = rTi / pTqi,

    rTi = 0 i T

    ( ) 1log log log .Ti i Ti TiTi T j Ti j T iT i j T i T i jj T j T

    r q r rr p q p

    p q q p q p q q

    =

    T H(P)Q H(P, Q). . , hn(n, S) hn(n)S, .. c = c(m), ,

    log Nn(n)S hn(n, S) c log n. , hn(n, S) -

    S- . , - .

    . Kn(n) , .. - A = {a0, , am1, }, , A0 = {a0, , am1} ( aM).

  • 33

    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).

    log 0iiq = , H(P, Q) ( , ) logi iiH P Q p q= . ,

    1ii p p= ,

    0 1( , ) (1 ) log (1 ) , , (1 ) .1 1 1 1

    i m

    i

    p p p PH P Q p q p H p H

    p p p p

    = =

    Q0 = P/(1 p), H(P) = H(P, Q0) = (1 p)H(P/(1 p)). R, P Q.

    rii = pi, ri = qi pi, 0 i m 1. ,

    ( ) ( ) log ( ) log

    'log log ( ) .

    i i iQ i i ii i

    i i i

    i i i ii ii i

    p q pH P I R p q p

    p q p q

    q p q p Q Pq q p H Q p H

    p p p

    = = + =

    = + =

    ( )i ii q p p =

    '( ) ( , ) log 0.i iQ ii

    q p Q PH P H P Q p q p H

    p p

    =

    Q = (Q P)/p, .. Q = P/(1 p) = Q0.

    0

    00

    ' ' '( ) ( ) ( ).

    1 1Q

    Q P P PH P H Q p H H p H H P

    p p p

    = = =

    , H(P, Q) H(P)Q, Q0, 0

    0H( ) H( , ) H( )QP P Q P= = . , hn(n, s) hn(n)s,

    , hn(n).

    1. .. // . . 4. .: -, 2004. . 385 399.

    2. .. // - . . 1. 2007. . 14. 1. . 110 139.

    3. . . .: . , 1974. 4. : . .: , 1999. 5. ., . . .: , 1966. 6. .., .., .. // - . . 30. : , 1977. . 46 75.

Recommended

View more >