Page - 450 - in Differential Geometrical Theory of Statistics

Entropy2016,18, 110 where the shift is by a bounded constant, independent ofw. The constant cT is theKolmogorov complexityof theprogramneededtodescribeT so thatTU cansimulate it. A variant of the notion of Kolmogorov complexity described above is given by conditional Kolmogorovcomplexity, KTU(w | (w))= minP:TU(P, (w))=w (P), where the length (w) isgiven,andmadeavailable to themachineTU.Onethenhas K(w | (w))≤ (w)+c, because if (w) isknown, thenapossibleprogramis just towriteoutw. Thismeans that then (w)+c is justnumberofbitsneededfor the transmissionofwplus theprint instructions. Anupperboundisgivenby KTU(w)≤KTU(w | (w))+2log (w)+c. If onedoesnotknowapriori (w), oneneeds to signal the endof thedescriptionofw. For this it suffices tohavea“punctuationmethod", andone can see that this has the effect of adds the term 2log (w) in theaboveestimate. Inparticular, anyprogramthatproduces adescriptionofw is an upperboundonKolmogorovcomplexityKTU(w). OnecanthinkofKolmogorovcomplexityintermsofdatacompression: theshortestdescriptionof w isalso itsmostcompressedform.Upperbounds forKolmogorovcomplexityare thereforeprovided easilybydatacompressionalgorithms.However,whileprovidingupperbounds forcomplexity is straightforward, the situationwith lowerbounds is entirelydifferent: constructinga lowerbound runs into a fundamental obstacle causedby the fact that the haltingproblem is unsolvable. As a consequence,Kolmogorovcomplexity isnotacomputable function. Indeed, supposeonewould list programsPk (with increasing lengths)andrunthemthroughthemachineTU. If themachinehaltson Pkwithoutputw, then (Pk) isanapproximationtoKTU(w).However, theremaybeanearlierPj in the list suchthatTU hasnotyethaltedonPj. IfTU eventuallyhaltsalsoonPj andoutputsw, then (Pj) willbeabetterapproximationtoKTU(w). Soonewouldbeable tocomputeKTU(w) ifonecouldtell exactlyonwhichprogramsPk themachineTU halts,but that is indeedtheunsolvablehaltingproblem. KolmogorovcomplexityandShannonentropyarerelated: onecanviewShannonentropyasan averagedversionofKolmogorovcomplexity in the followingsense (seeSection2.3of [31]). Suppose given independent randomvariablesXk, distributedaccording toBernoullimeasureP= {pa}a∈A with pa=P(X= a). TheShannonentropyisgivenby S(X)=−∑ a∈A P(X= a) logP(X= a). Thereexistsa c>0, suchthat, foralln∈N, S(X)≤ 1 n ∑w∈Wn P(w)K(w | (w))≤S(X)+ #A logn n + c n . Theexpectationvalue lim n→∞E( 1 n K(X1 · · ·Xn |n))=S(X) showsthat theaverageexpectedKolmogorovcomplexity for lengthndescriptionsapproaches the Shannonentropyin the limitwhenn→∞. 450