Page - 449 - in Differential Geometrical Theory of Statistics

Entropy2016,18, 110 3.2. EntropyandStatistics of theGilbert–VarshamovLine TheGilbert–VarshamovlineR=1−Hq(δ)canbecharacterizedstatisticallly. Suchastatistical descriptioncanbeobtainedbyconsideringtheShannonRandomCodeEnsemble (SRCE).Theseare randomcodesobtainedbychoosingcodewordsas independentrandomvariableswithrespect toa uniformBernoullimeasure, so thatacode isdescribedbyarandomlychosensetofdifferentwordsof lengthnoccurringwithprobabilityq−n, see [26,27]. There isnoapriori reasonwhythe typeofcodes weconsiderhere,withcodewords formedusingthesyntacticparametersofnatural languages,would be linear. Thus,weconsider thegeneral settingofunstructuredcodes,as inSectionVof [27]. TheHammingvolumeVolq(n,d= nδ), that is, thenumberofwordsof lengthnatHamming distanceatmostd fromagivenone, canbeestimated in termsof theq-aryShannonentropy Hq(δ)= δ logq(q−1)−δ logqδ−(1−δ) logq(1−δ) in the form q(Hq(δ)−o(1))n≤Volq(n,d=nδ)= d ∑ j=0 ( n j ) (q−1)j≤ qHq(δ)n. Theexpectationvalue for the randomvariable counting thenumberofunorderedpairsofdistinct codewordswithHammingdistanceatmostd is thenestimatedas E∼ ( qk 2 ) Volq(n,d)q−n∼ qn(Hq(δ)−1+2R)+o(n). Thisestimate is thenused(see [26,27]) toshowthat theprobability tohavecodes in theSRCEwith Hq(δ)≥max{1−2R,0}+ isboundedbyq− n(1+o(1)). Byasimilarargument (seeSectionVof [27] and Proposition 2.2 of [16]) it is shown that the probability that Hq(δ) ≥ 1−R+ is bounded byq−n (1+o(1)). While, by this typeof argument, one can see theGilbert–Varshamov line as representing the typicalbehaviorof sufficientlyrandomcodes, theasymptoticbounddoesnothaveasimilarstatistical interpretation. It does have, however, a relation toKolmogorov complexity, which is relevant to thepoint ofviewdiscussed in thepresentpaper. The relationbetweenasymptotic boundof error correcting codesandKolmogorovcomplexitywasdescribed in [16]. We recall it in the rest of this section,alongwith its implications for the linguisticapplicationsweareconsidering. 3.3. KolmogorovComplexity Werefer thereaderto[30] foranextensivetreatmentofKolmogorovcomplexityanditsproperties. Werecallheresomebasic factsweneedin the following. LetTU be auniversal Turingmachine, that is, a Turingmachine that can simulate any other arbitraryTuringmachine,byreadingontapeboth the inputandthedescriptionof theTuringmachine it shouldsimulate.AprefixTuringmachine isaTuringmachinewithunidirectional inputandoutput tapesandbidirectionalwork tapes. ThesetofprogramsPonwhichaprefixTuringmachinehalts formsaprefixcode. Givenastringw inanalphabetA, theprefixKolmogorovcomplexity isgivenbyminimal length ofaprogramforwhichtheuniversalprefixTuringmachineTU outputsw, KTU(w)= minP:TU(P)=w (P). There isauniversalityproperty.Namely,givenanyotherprefixTuringmachineT, onehas KT(w)≤KTU(w)+cT, 449