On The Algorithmic Foundation Of Information Theory
IEEE TRANSACTIONSON INFORMATTONTHEORY,VOL.IT-25NO.5,SEPTEMBERwhereo(N) p-%lA(N-‘lnN)“2-N-‘ln.(A-14)Note that o(N) is independent of I and thatlim[o(N)/(N-‘lnN)“2] /3-‘lnA.(A-15)N C ZThat is, o(N) goes to zero as fast as (N -‘In N)‘12.REFERENCES[l][2]13)[4][5]R. G. Gallager, Information Theory and Reliable Communication.New York: W iley, 1968.T. Berger, Rate Distortion Theory-A Maihematical Basis for DataCompression. Englewood Cliffs, NJ: Prentice-Hall, 1971.J. Ziv, “Coding of sources with unknown statistics-Part II:Distortion relative to a fidelity criterion,” IEEE Trans. Inform.Theov, vol. IT-18, pp. 389-394, May 1972.D. L. Neuhoff, R. M. Gray, and L. D. Davisson, “Fixed rateuniversal block source coding with a fidelity criterion,” IEEETrans. Inform. Theov, vol. IT-21, pp. 51 l-523, Sept. 1975.J. Ziv, “Coding theorems for individual sequences,”IEEE Trans.Inform. Theory, vol. IT-24, pp. 405-412, July 1978.1979(61 J. K. Omura, “‘A coding theorem for discrete-time sources,” IEEETrans. Inform. Theory, vol. IT-19, pp. 490-498, July 1973.[7] S. Singh and N. S. Kambo, “Source code error bound in the excessrate region,” IEEE Trans. Inform. Theov, vol. IT-23, pp. 65-70,Jan. 1977.[8] J. K. Omura, “Universal source coding of finite alphabet sources,”in Proc. Inter. Telemetering Conf., vol. 12, pp. 146-153, 1976.[9] R. M. Gray and L. D. Davisson, “The ergodic decomposition ofdiscrete stationary sources,” IEEE Trans. Inform. Theory, vol.IT-20, pp. 625-636, Sept. 1974.[IO] R. M. Gray and L. D. Davisson, “Source coding theorems withoutthe ergodic assumption,” IEEE Tram Inform. Theory, vol. IT-20,pp. 502-516, July 1974.[ 1 l] V. A. Rohklin, “Lectures on the entropy theory of measure-preserving transformations,” Russian Math. Surueys, vol. 22, no. 5, pp.l-52, 1967.[12] M. B. Pursley and L. D. Davisson, “Variable rate coding fornonergodic sources and classes of ergodic sources subject to afidelity constraint,” IEEE Trans. Inform. Theory, vol. IT-22, pp.324-337, May 1976.[13] D. R. Martin, “Robust source coding of finite alphabet sources viacomposition classes,” Ph.D. dissertation, UCLA., Los Angeles,CA, 1976.[14] J. Nedoma, “Gber die Ergodizitiit und r-Ergodizitiit Station&rerWahrscheinlichkeitsmase,” 2. Wahr., vol. 2, pp. 90-97, 1963.On the Algorithm icof he information content of binary sequences is defined byminimal program complexity measures and is related to computablemartingales. The equivalence of the complexity approach and themartingale approach after restriction to effective random tests is used toestablish generalized source coding theorems and converses. Fiuite statecomplexity and decomposable martingales are related to classical blockcodes and the relative frequency behavior of sequences.This paper is devoted to a generalization of universalsource coding using Turing-computableprocedures. Jnitiated by Kolmogoroff[5], Martin-Liif[6], and Chaitin[8]-[lo], the algorithmic approach to a measure of information content and the closely related concept of randomness is now an intriguing alternative to the wellestablished statistical and measure theoretic one. TheI. INTRODUCTIONfollowing discussion is based on the important contributions of Schnorr [l], [2], [4], who reintroducedtheNFORMATIONtheory, usually viewed as a branchof classical probability theory, has inherently com- martingales of Ville [17] and proposed a uniform definiputational concepts. Block coding schemes are examples tion of a random sequence. Whereas Schnorr’s concernof how to apply an algorithmic procedure when some was to construct a consistent algorithmic theory of probaregularities of an informationsource or channel are bility, the aim of this paper is to indicate how algorithmicknown. On the other hand, most coding algorithms thus information theory could be formulated. One attractivefar considered in the classical theory are of the finite state feature of this approach is its complete independence oftype and are, from a computational point of view, not the any probabilistic concepts. Minimal program complexitymeasures are a quite natural and intuitively appealing waymost general way to handle data.to quantify the information content of a message.In the next section we restate the basic definitions ofManuscript received November 5, 1976; revised January 8, 1979. Thiswork was supported in part by the Deutsche Forschungsgemeinschaft the so-called effectiverandom tests introducedbyunder Grant Pf 74/7,8 and is part of the author’s doctoral goroff’sproThe author is with the Institute for Information Sciences, Universitygram complexity measure and to the martingales firstof Tiibingen, 7400 Tiibingen, West Germany.I001 S-9448/79/0900-0557SOO.750 1979 IEEE
558IEEE TRANSACTIONSinvestigated by Ville [ 171 in his criticism of early, tentativedefinitions of random sequences [15], [16]. In Section IIIwe formulate the familiar block codes of classical information theory in terms of martingales instead of probabilities and demonstrate the relationship between finite-statecomplexityand relative frequency. In Section IV weestablish a generalized source coding theorem by showingthat Schnorr’s effective random tests can be translatedinto each other by a constructive procedure. We show thatsequential coding schemes also can be derived frommartingales. In Section V, starting with Fine’s theoremabout apparently convergent relative frequencies [ 131, westate the conditions under which an infinite sequence hasa maximal compression factor H(p).II.EFFECTIVE TESTS ANDRANDOMV(A) 1,XEA*.(WWe can think of V(z(n)) as our fortune after n plays ina fair binary game when we bet according to a recursivestrategy, start with an initial capital of one, and thesequence z E A” denotes the outcomes of the game. Weassume that debts are forbidden and the payoff is according to an assumed equal distribution of the zeros and onesin z. It is straightforwardto generalize this martingaleconcept to arbitrary distributions.Definition 2.2: A computable probability function (cpf) isa computable mapping p: A * [O, l] with the propertyP(4 1,xEA*.P(X) p(xO) p(xl),(2.1)Definition 2.3: A computable p-martingale is a computable mapping P’: A* R u {co} with the propertyVP(R) 1p(x) V”(x) p(xO) VP(xO) p(x1)V”(xl),THEORY,VOL.IT-25,NO.5,WTBMBER1979for a cpf p. If p(x) 0, we set VP(x) cc andp(x) VP(x) 0.Corollary 2.1: For a cpf p and a computable martingaleVP, the product pa VP is again a cpf.Comparing (M) and (M,), we see that (M) is thespecial case where p(xa)/p(x) p(aJx) f, a E A, for allXEA*.We next establish an interesting relation between pmartingales.Lemma 2.1: Let VP be a p-martingaleand p,q cpf’swith the property that p(x) 0iff q(x) 0 for all x EA*.Then the function VP withP(X) V”(x) 4(x) V4(x),is a q-martingale.XEA*,(2.2)Proof: This is evident from (M,).SEQUENCESWe start with some basic definitions of effective random tests and random sequences. We omit Martin-Lof’srecursive sequential tests [6], based on constructivemeasure theory, which form the bridge between classicalprobability theory and the algorithmic approach. Instead,we will concentrate on the computationalaspects of anycoding procedure. For a thorough discussion of randomtests and their interrelations see [l].For simplicitywe restrict ourselves to the binaryalphabet A (0, 1 }. We denote the set of all finite (infinite) binary sequences by A * (A “). A EA * is the emptysequence. For z EA*uAmwe write z(n) zlzZ* * sz,,,.z,form n.Also N, Q and R denotez(m,n) z,z, 1.the natural, rational, and real numbers, respectively. Thecardinality of a set is denoted by #.Definition 2.1: A computable martingale is a computable function V: A* R with the following properties:V(x) V(x0) f V(xl),ON INFORMATIONXEA*,by,)As an instructive example, let us consider the Bernoullicpf p(x) roS,cX)rS1cx),where s,(x) denotes the number ofoccurrences of w E A* in the sequence x, and r,,, r, arecomputablepositive reals with r0 r, 1. As a pmartingale, we choose the constant function VP(x) 1 forall x E A*, the result of taking no risk. For the specialBernoulli cpf p(x) 2- ‘ 4 , Z(x) being the length of x, thetransformationrule (2.2) reads p(x) VP(x) 2-(“‘V(x)orV(x) 2’(X)r (X)rS1(X).Now let z E A” have the propertyclim , ,-n -‘s,(z(n)) qO, a E A (where clim denotes constructive limit or equivalentlythat q0 is a computablereal). Then we can write (with log log,, exp exp,)V(z(n)) exp[n q,logr, q,logr, o(n)] exp[ 41 -ff(r,q)) o(n)](2.3)where H(r,q) is the “subjective” entropy which reflectsthe uncertainty of an observer who estimates the distribution to be r when the true distribution is q.The role of a p-martingale as a random test is based onthe intuitive idea that if the tested sequence has distribution p but no further regularities, then there is no strategyresulting in an unlimited growth of the gambler’s capital.In the above example the selection of a constant pmartingale is equivalent to the assumption of having ap-distributedrandom sequence, since taking no risk isalways the best we can do in this case. On the other hand,a martingale (p(x) 2-‘(“))is an absolute random testsince an equal distribution of zeros and ones is a necessary condition for maximal irregularity. In (2.3) we havean exponentially growing martingale V unless H(r, q) 1.The speed of growth is essentially determined by theredundancy 1 - H(r, q).Later we will show the intimate relationship betweenexponentially growing martingales and relative frequencies of words w E A *. As a consequence, martingales arefiner random tests than statistical ones, as the growingspeed may be polynomial, logarithmic, etc.Before giving a precise definition of randomness andp-randomness in the algorithmic framework we introducethe set 8 of growth functions and a partial ordering 9with respect to growth rate.
HEIM:ALOORITHMICFOUNDATIONOF INFORMATIONDefinition 2.4: A growth function is a recursive, nondecreasing, unbounded function f: I% N.Definition 2.5: Let g, h be arbitrary functions g, h: NAR. The relation g is given byg shwYfEC3 : qn N:559THEORYg(n) h(n) f(n),where V means for all and i means for all but finitelymany. For a set of functions 5? we call g E 9 9 -maximaliff h gg for all hE9.It is clear how to define the relations g, g, g, g.For instance, g ,hiff g gh and h sg. Now we areready for the martingale definition of randomness andp-randomness.Definition 2.6: A sequence z E A m is random (p-random) iff V(z(n)) ,l ( VP(z(n)) gl) for all martingales(p-martingales).Note that in Definition 2.6 we do not require that themartingale be bounded. The essential point is that thegrowth rate of the martingale is effective only if theunderlying sequence has regularities. A justification of thetwofold effective Definition 2.6 is given at the end of thissection.Now we give an important theorem of Schnorr andFuchs [23].In general, the program complexity K is not recursive.Otherwise we could construct a sequence’of high complexity by a recursive procedure, a contradiction. More formally, the problem of the recursiveness of K can be reducedto the undecidable halting problem of Turing machines.To get a counterpart to effective martingales, it is necessary to restrict the class of complexity measures to effective complexity measures.Definition 2.8: A program complexity K is effective iffK: A* fW is a recursive function.Unless otherwise stated we assume complexity measuresto be effective. W e omit the subscript \k if a specificationis not necessary and write R(x) for the program redundancy R(x) Z(x) - K(x).As an example of an important class of effective complexity measures, take the block coding schemes of classical information theory, e.g., Huffman coding. The encoded sequence plays the role of the program p, thealgorithm q is the mapping codeword block. W e willtreat this in full detail in Section III.W e can characterize the same class of randomsequences by effective complexity measures as we can bymartingales. The correspondingdefinitionreads asfollows.Definition 2.9: A sequence z E A * is random iffTheorem 2.1: A sequence z E A m is p-random iff thereis a martingaleV with the propertylog V(z(n)) glog V’(z(n)) for all martingales V’.Proof:a) Let z be p-random. Then by definition we haveVP(z(n)) ,l for allp-martingales. By applying thetransformation rule (2.2) we see that V(z(n)) 2”p(z(n)) is 4 -maximal.b) Let V be a 9 -maximal martingale on z. ByCorollary 2.1, p(x) 2 - ‘(“)V(x) is a cpf . Then wehave with (2.2)0Vp(4n) 2-“V(z(n))/p(z(n)) 1.The significance of Theorem 2.1 lies in the fact that, aswe will see in Section IV, the existence of a 4 -maximalmartingale is equivalent to the existence of an optimalcoding scheme. Since there is a maximal amount of datacompression using effective methods, we may say thatp-random sequences have a definite information content.Now let us turn to the minimal program complexitymeasures. Let ? be the set of partial recursive mappings‘I’: A*- A*.Definition 2.7: Let x E A* and q E 9. The programcomplexity K,(x) isK,(x) Imin { Z(p)l\E(p) x} , if x is in the range of \E,PEA*otherwise.l(x),(There is no loss of generality in defining K (x) I(x)when x is not in the range of ‘k, instead of the more usualq(x) cc.) It is also possible to define the universalprogram complexity with respect to all partial recursivefunctions, but we do not need the definition here.for all effective complexity measures.It is not possible to characterizep-randomnessfor arbitrary cpf’s by complexity measures. W e will return to thisproblem in Section V.The reason why we use infi ,R(z(i))rather thanR(z(n)) itself as a test for randomness is the oscillation ofsome complexity measures, as first noted by Martin-LGf[7]. Let us consider the following example. W e selectZEA” and construct an enumeration 7: R&A* of A* inlexicographical order. Then we define the algorithm q byq(x) dl(x))x,i X,if 3i: T(I(x))x z(i),otherwise,where 3 means exists. For any z there are infinitely manyintegers i such that z(i) r(l(x))x. Because 1(7(n)) logn,we have, for infinitely many n, n - K,Jz(n)) R,(z(n)) logn. In fact the following theorem holds [7].Theorem 2.2: Select f E 9 such that E nErm2-f(“) diverges. Then for all sequences z E A m, there is a complexity measure q such that limsup,,,(R,(z(n))- f(n)) 0.When f(n) [logn] the series indeed diverges. As anapplication of martingales, we will prove in Appendix Ithat Martin-Lof’stheorem cannot be improved.After this digression, we now introduce some specialclasses of algorithms. In contrast to classical source and
560IEEE TRANSACTIONSchannel coding procedures, successive representation ofinitial segments of a z E A O”by programs is in general nota sequential procedure. That is, from q(p) x we cannotconclude that there are q,y #A such that *(pq) xy.Schnorr proposed the following modification [2]:Definition 2.10: An algorithm \k E? is a process iff\k(xy) \k(x)A*for all x,xy domain(\k).Process complexity measures are much easier to handleand do not exhibit oscillatory behavior. In the next section we will prove that limsup,,,(R(z(n))-f(n)) 0 imV withpliesthe existenceof a martingalelimsup, V(z(n))/g(n) 0, f,g E 9, for any process redundancy R .While decoding from a process representationissequential, encoding in general is not. If * is a processand q(p) x, q(q) xy, y#A,q is not necessarily anextension of p. In analogy to classical coding schemes, wenow define coding procedures which are sequential inboth directions.Definition 2.11: A sequential coding scheme is a set( , P,g) of processes 1c/,9 and a growth function gE 9such that (z( g(n))) Z(h(n)) and 9(Z(h(n))) z( g(n)) forz,.?E A” with z( g(n)) E domain( ), T(h(n)) E domain(n E M and h(n) nondecreasing.Thus any sequential coding scheme produces an infinitesequence as a code of another infinite sequence, whereas aprogram representation by general algorithms is an infinite collection of finite sequences. A different class ofprogram-representingalgorithmsis investigatedbyChaitin [12], who restricted the admissible domains toprefix-free subsets of A*. In classical information theorysuch prefix-free sets are known as instantanous codes. Asa justification for Chaitin’s point of view, suppose we arerepresenting successive initial segments of a z E A” by,e.g., Fortran programs. No valid Fortran program can bethe prefix of another.The reason why we have defined random sequences bytwofold effective (i.e., effective complexity tests and effective growth rates) random tests is the following. Of course,it is possible to characterize z E A m as random by requiring any computable martingale, respectively, the infimumof any program redundancy measure, to be bounded.However it turns out that this definition yields a differentclass of random sequences, and one that also differs fromthe class of sequences passing Martin-Liif’srecursivesequential tests [ 11, [4]. Schnorr’s modification overcomesthis difficulty in a quite natural way. For instance, we getan effective program complexity measure by circumventing the halting problem and limiting the number of computation steps in any procedure. Since all “real” algorithms are step-limited, this is as irrelevant in practice asthe restriction to observable growing speeds.The other important reason is that the equivalence ofthe different approaches can be demonstrated constructively through constructive translations between the complexity measures. These translations will enable us toestablish generalized universal source coding theorems.ON INITE-STATE COMPLEXITY AND RELATIVEFREQUENCYIn this section we will study the algorithmically simplestclass of sequential coding schemes, the well-known blockcodes of classical informationtheory. There is an intimate relationshipbetweenthe relativefrequencylim,,,n-‘s,,,(z(n))of words WEA* in an infinite z andthe possibility of data compression by a coding procedurerealizable by a finite-state automaton. From our algorithmic point of view, the Shannon entropy H is the finitestate complexity per symbol. The only tribute to ourtwofold constructive approach is a sometimes necessaryrestriction to computable reals and computable limits(clim). But this is also irrelevant, as computable numbersare the only ones encountered in practice.For a subset C c A*, we use the notation C* for the setof all finite concatenations of elements of C. Ak is the setof the 2k finite sequences of length k. To indicate thatXEA , we write xk.A classical block coding scheme is a pair of homomorphisms (w,, Qk) and a codeword set C, c A* such thatwk(Pd “k(P)ok(d,forp,qEok(xY) forx,yE[wk(Ck)]*c(Ak)*.ak(X)Qk(Y),C,*,Thus wk and Qk are finite state processes and form asequential coding scheme (Definition 2.11) with growthfunction g(n) kn. Without loss of generality we assumeC, to be a complete code, that is, XpEck2-Kp) 1.Now let us formulate noiseless coding in terms ofmartingales instead of probabilities.We define themartingale V,: A * Q byVk(Xk) 2k - @ M x ’9) 9i 0,if xkEWk(Ck)otherwiseandn-1Vk(xk”) aVk(xk”(ik l,(i fornElV.l)k)),i O(3.1)Because Z ,,,Cc,,Vk(x) 2k,V, agrees with (M) on (A k)*and can be extended to a martingale on A* via thisfunctional equation. Assume there is a z E A M with n(kn)-‘Z(Q,(z(kn))) c&III( )-‘Kuk(z(krz)) H.Then from (3.1) it follows immediately&(z(kn))that exp(R&(kn)))orVk(z(n) exp[n(l - H) o(n)].This is an example of an effective translation of acomplexity measure into a martingale. Given a complexitymeasure K, we can construct a martingale V such that thegrowth rate of the redundancy R corresponds to thegrowth rate of V by an exponential relationship. Conversely, assume there is a martingale V, decomposable
HEIM:ALGORITHMICFOUNDATIONOF INFORMATION561THEORYFrom (3.4) we haveinto factors as in (3.1), that is,where x6) means the ith block of length k. The construction of a codeword set C, and the pair of homomorphicprocesses (ak,Qk) is immediate if there are integers Ii suchthat 2k-‘a V,(x&),V,(x&) 0. Note that Ei2-ji z xEAk2-kVk( ) 1. If k-log Vk(xk) is not integer valued,then we can proceed as in the well-known classical conqk(xjk”) structions: take a coarser decompositionn? , Vjk(x ) and order the values Vjk(xjk) according totheir magnitude. Then by applying one of the well-knownprocedures, e.g., the Huffman coding scheme, to the tableof the martingale values rather than the probabilitiesp(xjk), we get a process ajk in the limit j-see, where therelation R,(z(jkn)) log q,(z(jkn))holds asymptotically.The decomposable martingale of (3.1) is of course alsoof the finite state type, since we only have to know the2k 1 - 1 values Vk(x), for x E u :-,,A i. In order to establish the announced relationship between finite state complexity and relative frequency, we state the followingtheorem.Theorem 3. I :a) Assume for a sequence z E A”there existsclim,,, n-‘s,,,(z(n)) r,,, for all w EA*. Then there isa sequence of codes C, and homomorphisms wk,k 6 N, such thatclim clim (kn)-‘K (z(kn)) clim H(AIAj) k- m” j wH,.loglIk (z(kn))i l(3.3)iff 2) there is a w E AA* such that limn oo n-‘L(z(n))#2-4”) or the limit does not exist.Proof: For any martingale V, we define the factorization IIkV by IIkV(xkn j) V(xG,) . . * . V(x&) * V(x’).Clearly lIkV is again a martingale.To prove part a), we have to show the existence of amartingale V whose factorization IIkV has, in the limitk-co, the same growth rate as V on z. W e do not knowthe values rW; therefore we adopt an adaptive strategy bydefiningif xaEA*wOotherwise(3.4)where q(w,x) (s,,(x) - s,,,o(x))/s,,,(x), w E A’ with theconvention s*(x) 1 for all x and q(w, x) 0 iff s,,,(x) 0.l ].Because of the existence of clim,,,n-‘s(z(n)),there is anh E 9 such that, for all n E lV, Ip(z(n)) - rl Q h(n)-‘. From[s(z(ki)) - s(z&)]/k(i - 1) p(z(k(i - l))), it follows thatP(z(ki))--p(z(k(i-1))) (i-l -’4’tO 7-p(z(ki))1.Assuming constructively convergent relative frequencies, there are functions gi E 9 such that for all k E NS(Zt))-p(z(ki))lCombiningk g,(k)-‘.the above relations we obtain h(ki)-‘ g,(k)-‘.(3.6)Furthermore, clim, mn-‘Z ,S(t,p(z&)) exists for t 0,.1where6(t,t’) 1if t t’, 0 otherwise. Thisl/k,2/k*is because all relative frequency limits exist. From (3.6) wehave the desired resultclim n ooclim n - ’ , FM4, )Kim(3.7) F(r).In the case w E AA* we have to take into account theboundary effect that the expression Zy ls,,,(z, f(w) Gk,does not count the w-blocks overlapping the boundarybetween z&y z( 1)’i 0, n - 1. W e have the inequalityp (z(h))- (n-l)(r(w)-l) 21knwif xaEA*wl,,,E.yjP(z )) P(z(ki)) (z(kn)) On- cuSEAwhere z[) abbreviates z((i - 1)k 1, ik). For simplicity we.only treat the case w A; the generalization is obvious.W ithout loss of generality we assume k Z(w) j.Inspection of (3.5) reveals that we have to relate theexpression n-*X? lF[k-lsa(z[ )]to F[(kn)-‘s,(z(kn))],aEA, where F: [0, l]- Iw is computable and continuous.W e omit the subscript a and write p(z(n)) n-‘s(z(n)). Bydefinition we have(3.2)b) For a sequence z E A m there is an injective homomorphism o: (C)*- (A k)* with the property 1) kn 1 i[pw(zf,)I ,Implementing this modification,we have,k co, the same result (3.7) as for w A.Now we construct a complete code Ckjhomomorphism wkj: (C,,.)*- (A k)* for anyIIkVj. A suitably chosen diagonal sequenceand homomorphisms satisfies (3.2).I ’in the limitand injectivefactorizationof code sets
562IEEE TRANSACTIONSTo prove part b), assume lim,,,n-‘s,,,(z(n)) 2-‘(“) forall w EA*. Let w: (C)* (Ak)*be an arbitrary bijectivehomomorphism. Then(kn)-‘K,(z(kn)) k-’2n-’ , sw(z ))‘z(ntw))WEAk k-’x[2-““‘ o(l)] Z(Q(w)).WEAkApplying Kraft’s inequalitylog,t t - 1, we obtainand the standard(3.8)inequalityor22 - ‘Wlog,2’(“( )))22--l(w). log,2’(“’WEAkWEAkand, after passing to log,,22-@“Z(ti(w)) H(A “) k.ON ingale. This replacement, however, generally does notpreserve the martingale’sfinite-statecharacter.Butthere is a sequentialcodingschemesuch thatlimk mlimn m (kn)-‘K,(z(kn)) 1. This follows from thegeneralized coding theorem which we will prove in thenext section. After establishing the generalized codingtheorem we will return to the relations between relativefrequencies, p-martingales and complexity measures. Weclose this section with a martingale construction exhibiting a technical advantage of martingales. Let { tn},,I be asequence of computable and nonnegative reals summingto one. Then for a sequence { V,},,Iof martingales,ZnEItn V, is again a martingale.The martingale (3.4) has an exponential growth rateessentially determined by the relative-frequency-basedredundancy 1 - H(A IAj). We now construct a martingale asa superposition of various random tests having a growthrate determined by, for simplicity,the first order redundancy 1 - H(A).Let A; denote the subset of A” containing all sequenceswith exactlyp zeros. We define the martingale Vn,p by(3.9)WEAkFrom (3.8) and (3.9) it follows that lim,,,(kn)-‘K, z(kn)) 1, that is, 1) implies 2).Now assume 2) holds. Then we can construct amartingale whose factorizationgrows exponentially.Ifw E A’, then inspection of (3.4) reveals that, for a suitablychoosen k j, the expressions enclosed in brackets in (3.5)take values c 0 infinitelymany times since eitherliminf,,,n-‘s,(z(n))#2-‘(“)or limsup, ,n-‘s,(z(n))#2-4”‘). Then 1) holds for an injective homomorphismassociated with III”?.clPart a) of Theorem 3.1 is the noiseless coding theoremof classical informationtheory stated algorithmically.Note that the only assumption was the existence of therelative frequencies, not their concrete values. This is inanalogy with the work of Davisson [24], which establishesuniversal coding theorems under the assumptionofstationarity but not ergodicity.From part b) we learn that the possibility of compressing a sequence z E A* by a factor H 1 using afinite state procedure depends on the relative frequencybehavior. Any deviation from the Bernouilli property-?s,(z(n)) 2-‘(“)can be detected by, e.g., anlim,,,nexponential growth rate of a finite state martingale. Anexponential growth rate of a martingale implies a lineargrowth rate of the corresponding program redundancy, anecessary condition for a compression factor less thanone. There are two possibilities. a) The relative frequencylimits exist but are different from 22”“). Then the limit H, 1 exists. H,islimk-*mlimn m (kn)-‘K,(z(kn))computable if the clim’s exist. In this sense H, is thefinite state complexity per letter. b) The relative frequencydoes not exist. Then the finite state martingale as well asthe finite state redundancyoscillate. We show inAppendixII that we can always replace a martingale by a slightly slower growing but strictly increasingYl,p(x) 2”.(3’,if x EAFA*,0,if x @ Ap”A * and I( X) n.Because ExEA”A Vn,p( ) 2n k,Vn,p agrees with (M)on A”A* and can be extended to A* by this functionalequation.Now we define the martingaleV,,(x) and the desired martingale V(x) (n 1)-*X’ proV,p(x)EnEN[n(n l)]-iVn(x).By observing the fact that (nn,),nr integer valued, grows as 2”H@) for large n, it is easyto verify that V(z(n)) exp[n(l - H(r)) o(n)] for any prandomsequence z with Bernoullimeasure p(x) r&)( 1 - r)slw.See [3] for a detailed discussion of finite-state regularities using a different approach.IV.GENERALIZEDSOURCE CODINGApplying a finite-state block coding procedure to z EAm, one starts with a partition of z into blocks of length kaccording to a partition function g(n) kn. Then oneconstructs an invertible mapping between Ak and thecodeword set C, GA*. As a finite-state procedure, theencoding (respectively decoding) is performed independently on previous segments of z (respectively the encoded sequence Z E A “). The asymptotically best result isreached, in general, in the limit k ao.For Turing-computablemartingales we have to adoptthe following modifications.Instead of g(n) dividing zinto blocks of equal length, we have to use growth functions of linear, polynomial, exponential, etc. order. Themapping block H codeword is generally performed byusing the knowledge of all initial segments already coded.Theorem 4.1: Let V: A* R be suchgale and ZEALbe a computable martinthat lim SUP V(z(n))/
HEIM:ALGORITHMICFOUNDATIONOF INFORMATION563THEORYf(n) 0 for some f 4. Then there exists a sequentialcoding scheme (#, Q,g) with g(n 1) -g(n) h(n) E 4such thatlim sup [ Rd4n ccg(n))) - (log f( g(n)) - n) ] - 23.(4.1)Proof: Any martingale V can be written as a pseudofactorizationV(xyz * 6 * ) V(x) * V,(y) * V,,(z) * * * * ,X,Y,Z’ * . E A *. Given the pseudofactorizationn-1growing h E 9limsup V(z(h(n))).exp[-(f(h(n))-logf(n))] O. (4.3)n-tmProofi W e define the recursive sets Y {x E A *(R(x) f( l(x))} and Y Y n A “A *. Ypf denotes the largest prefix-free subset of Y; that is, no element of Ypr is prefix ofanother. Then we define the following function V,: A*- Cl :VJx) z2flr(xy))-r(“) xy E YPJ2Iypl(x(k)).2f(‘(X)),k l(x)(4.4)where 1 is an indicator function. W e show that V, has themartingaleproperty (M). To this end we consider thewhere g(0) -0, we construct (e.g. by the Huffman procefollowingfourcases.dure) an optimal and complete code w ( ( ):CZ(,gj A h(i)1)xistheprefixof an xauE Ypf, aEA, uEA*. Thenfor all i. The code for the initial segment z( g(n)) is simplyin(4.4)xaucontributesthe following (6 1, i O)the concatenationtoV,(x): .2fm”“))-w2f(Kxau))- l(u)toV,(xa):n-1 44g(n))) IJowzjL(i))(z(di)) Mi 1))).(first sum) .The decoding 9 works as follows. Using the martingale Vto VJxZ):0and g E 9, we construct We, C, and identify the uniquelydetermined prefix F(n,) E C, of the encoded FE A M. Then2) x is an element of YPr. Then we have VJI(x) 2f(‘(X))V(n,)) z(g(lN. A ssume we have reconst
was to construct a consistent algorithmic theory of proba- bility, the aim of this paper is to indicate how algorithmic . able function V: A* R with the following properties: V(A) 1, . rS1cx), where s,(x) denotes the number of occurrences of w E A* in the sequence x, and r,,, r, are computable positive reals with r0 r, 1. As a p .
May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)
Silat is a combative art of self-defense and survival rooted from Matay archipelago. It was traced at thé early of Langkasuka Kingdom (2nd century CE) till thé reign of Melaka (Malaysia) Sultanate era (13th century). Silat has now evolved to become part of social culture and tradition with thé appearance of a fine physical and spiritual .
On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.
̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions
Dr. Sunita Bharatwal** Dr. Pawan Garga*** Abstract Customer satisfaction is derived from thè functionalities and values, a product or Service can provide. The current study aims to segregate thè dimensions of ordine Service quality and gather insights on its impact on web shopping. The trends of purchases have
Chính Văn.- Còn đức Thế tôn thì tuệ giác cực kỳ trong sạch 8: hiện hành bất nhị 9, đạt đến vô tướng 10, đứng vào chỗ đứng của các đức Thế tôn 11, thể hiện tính bình đẳng của các Ngài, đến chỗ không còn chướng ngại 12, giáo pháp không thể khuynh đảo, tâm thức không bị cản trở, cái được
Le genou de Lucy. Odile Jacob. 1999. Coppens Y. Pré-textes. L’homme préhistorique en morceaux. Eds Odile Jacob. 2011. Costentin J., Delaveau P. Café, thé, chocolat, les bons effets sur le cerveau et pour le corps. Editions Odile Jacob. 2010. Crawford M., Marsh D. The driving force : food in human evolution and the future.
Le genou de Lucy. Odile Jacob. 1999. Coppens Y. Pré-textes. L’homme préhistorique en morceaux. Eds Odile Jacob. 2011. Costentin J., Delaveau P. Café, thé, chocolat, les bons effets sur le cerveau et pour le corps. Editions Odile Jacob. 2010. 3 Crawford M., Marsh D. The driving force : food in human evolution and the future.
