69:
45:
and the properties are those of the expectations. In contrast, here we deal with individual data strings and the properties of the individual string focused on. In this setting, a property holds with certainty rather than with high probability as in the classical case. The
Kolmogorov structure function precisely quantifies the goodness-of-fit of an individual model with respect to individual data.
44:
properties of the individual data string: for every constrained model class it determines the individual best-fitting model in the class irrespective of whether the true model is in the model class considered or not. In the classical case we talk about a set of data with a probability distribution,
84:
in 1973 at a Soviet
Information Theory symposium in Tallinn, but these results were not published p. 182. But the results were announced in in 1974, the only written record by Kolmogorov himself. One of his last scientific statements is (translated from the original Russian by L.A. Levin):
4921:
of individual finite sequences using
Kolmogorov complexity. Experiments using real compressor programs have been carried out with success. Here the assumption is that for natural data the Kolmogorov complexity is not far from the length of a compressed version using a good compressor.
3037:
additive term in argument and value) is realized by the structure function of some data x and vice versa. Where the graph hits the diagonal first the argument (complexity) is that of the minimum sufficient statistic. It is incomputable to determine this place. See.
4739:
1840:
3278:
3902:
39:
of an individual data string expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. The structure function determines all
30:
proposed a non-probabilistic approach to statistics and model selection. Let each datum be a finite binary string and a model be a finite set of binary strings. Consider model classes consisting of models of given maximal
425:
1928:
4977:
Abstract of a talk for the Moscow
Mathematical Society in Uspekhi Mat. Nauk Volume 29, Issue 4(178) in the Communications of the Moscow Mathematical Society page 155 (in the Russian edition, not translated into
4368:
3133:(MDL) function: The length of the minimal two-part code for x consisting of the model cost K(S) and the length of the index of x in S, in the model class of sets of given maximal Kolmogorov complexity
4840:
3377:
3778:
4976:
125:
of a natural number k—the log of minimal cardinality of x-containing sets that allow definitions of complexity at most k. If the element x itself allows a simple definition, then the function
1225:
3568:
1846:
290:
1468:
1061:
2822:
2643:
968:
4427:
2006:
2679:
2923:
2760:
2370:
1336:
3949:
2493:
2165:
4191:
4150:
1281:
1133:
1008:
716:
675:
2103:
123:
4580:
4903:
4534:
3440:
3119:
3035:
190:
5277:
1588:
4868:
4620:
4600:
4459:
4388:
4082:
3405:
3171:
3151:
3064:
2842:
2600:
1153:
607:
223:
145:
drops to 0 even for small k. Lacking such definition, the element is "random" in a negative sense. But it is positively "probabilistically random" only when function
3658:
2868:
2705:
2032:
494:
4237:
2560:
1645:
1092:
782:
163:
143:
4628:
4266:
4038:
3000:
1637:
811:
563:
4499:
4479:
4286:
4211:
4102:
4062:
4009:
3989:
3969:
3632:
3612:
3592:
3484:
3084:
2963:
2943:
2888:
2780:
2725:
2580:
2533:
2513:
2434:
2414:
2394:
2305:
2285:
2265:
2245:
2225:
2205:
2185:
2052:
1608:
1552:
1532:
1512:
1492:
1384:
1364:
1301:
1245:
883:
863:
835:
756:
736:
627:
587:
534:
514:
468:
448:
3179:
1847:
5151:
de Rooij, Steven; Vitanyi, Paul (1 March 2012). "Approximating Rate-Distortion Graphs of
Individual Data: Experiments in Lossy Compression and Denoising".
5282:, Especially pp. 401–431 about the Kolmogorov structure function, and pp. 613–629 about rate distortion and denoising of individual sequences.
3786:
5362:
323:
5103:
A.Kh. Shen, The concept of (α, β)-stochasticity in the
Kolmogorov sense, and its properties, Soviet Math. Dokl., 28:1(1983), 295--299
1853:
5087:
5114:
Vereshchagin, Nikolai K.; Vitanyi, Paul M.B. (1 July 2010). "Rate
Distortion and Denoising of Individual Data Using Kolmogorov Complexity".
5308:
5261:
4961:
2973:
Within the constraints that the graph goes down at an angle of at least 45 degrees, that it starts at n and ends approximately at
4747:
5102:
4291:
3286:
49:
3663:
5077:
3407:
of complexity the structure function allows us to select the best model S for the individual string x within a strip of
2782:(containing x) for the string x. When it is low the model fits well, and when it is high the model doesn't fit well. If
2603:
1158:
4544:
The MDL function: The length of the minimal two-part code for x consisting of the model cost K(P) and the length of
3492:
3451:
3130:
4870:
of complexity the MDL function allows us to select the best model P for the individual string x within a strip of
228:
53:
1010:
never decreases more than a fixed independent constant below the diagonal called sufficiency line L defined by
5002:
Vereshchagin, N.K.; Vitanyi, P.M.B. (1 December 2004). "Kolmogorov's
Structure Functions and Model Selection".
5332:
V'yugin, V. V. (1 April 1999). "Algorithmic
Complexity and Stochastic Properties of Finite Binary Sequences".
1392:
1016:
1342:. We write `algorithmic' for `Kolmogorov complexity' by convention. The main properties of an algorithmic
2785:
2612:
891:
1937:
2648:
4041:
814:
566:
32:
2893:
2730:
2310:
1306:
4582:, in the model class of computable probability mass functions of given maximal Kolmogorov complexity
4393:
3910:
2439:
2111:
1343:
4155:
4107:
1250:
1097:
977:
680:
632:
2057:
317:
where also the main properties are resolved. The
Kolmogorov structure function can be written as
92:
5271:
5215:
5160:
5123:
5048:
5011:
4430:
57:
4953:
4547:
4873:
4504:
3410:
3089:
3005:
168:
5257:
5083:
4957:
1835:{\displaystyle K(x)\leq K(x,S)+O(1)\leq K(S)+K(x|S)+O(1)\leq K(S)+\log |S|+O(1)\leq K(x)+O(1)}
1557:
27:
5228:
4853:
4734:{\displaystyle \lambda '_{x}(\alpha )=\min _{P}\{\Lambda (P):P(x)>0,\;K(P)\leq \alpha \},}
4605:
4585:
4444:
4373:
4067:
3390:
3156:
3136:
3049:
2827:
2585:
1138:
592:
195:
5341:
5320:
5295:
5240:
5205:
5170:
5133:
5058:
5021:
3637:
2847:
2684:
2011:
473:
5309:"On Randomness Defect of a Finite Object Relative to Measures with Given Complexity Bounds"
4216:
2538:
1070:
761:
148:
128:
4914:
4242:
4014:
2976:
1613:
787:
539:
5286:
Shen, A. (1 April 1999). "Discussion on Kolmogorov Complexity and Statistical Analysis".
3273:{\displaystyle \lambda _{x}(\alpha )=\min _{S}\{\Lambda (S):S\ni x,\;K(S)\leq \alpha \},}
314:
72:
Kolmogorov (left) talks on the structure function (see drawing on the blackboard) in (
4946:
4484:
4464:
4271:
4196:
4087:
4047:
3994:
3974:
3954:
3617:
3597:
3577:
3469:
3455:
3069:
2948:
2928:
2873:
2765:
2710:
2565:
2518:
2498:
2419:
2399:
2379:
2290:
2270:
2250:
2230:
2210:
2190:
2170:
2037:
1593:
1537:
1517:
1497:
1477:
1369:
1349:
1286:
1230:
868:
848:
820:
741:
721:
612:
572:
519:
499:
453:
433:
52:, also known as the theory of Kolmogorov complexity, for describing the structure of a
5356:
68:
313:
It is discussed in Cover and Thomas. It is extensively studied in Vereshchagin and
16:
For an entirely different 'structure function', also introduced by Kolmogorov, see
3897:{\displaystyle h'_{x}(\alpha )=\min _{P}\{-\log P(x):P(x)>0,K(P)\leq \alpha \}}
5345:
5299:
1934:
using straightforward inequalities and the sufficiency property, we find that
297:
81:
41:
17:
5210:
5194:"Kolmogorov's contributions to Information Theory and Algorithmic Complexity"
5193:
5137:
5025:
4918:
420:{\displaystyle h_{x}(\alpha )=\min _{S}\{\log |S|:x\in S,K(S)\leq \alpha \}}
609:
is a nonnegative integer value bounding the complexity of the contemplated
2965:
is the best-fitting model for x. For more details see and especially and.
5039:
Gacs, P.; Tromp, J.T.; Vitanyi, P.M.B. (2001). "Algorithmic statistics".
4461:
of complexity the structure function allows us to select the best model
3066:
of complexity the structure function allows us to select the best model
2307:
has the additional property, apart from being a model of best fit, that
2267:
that are not sufficient statistics. An algorithmic sufficient statistic
1923:{\displaystyle h_{x}(\alpha ),\beta _{x}(\alpha ),\lambda _{x}(\alpha )}
5219:
5174:
2582:.) The algorithmic sufficient statistic associated with the least such
73:
5062:
5053:
5324:
5244:
5165:
5128:
5016:
67:
2227:
is a typical (random) element of S. However, there can be models
4842:
is the total length of two-part code of x with help of model P.
4084:
is an integer value bounding the complexity of the contemplated
3450:
The mathematics developed above were taken as the foundation of
3379:
is the total length of two-part code of x with help of model S.
2762:. This structure function gives the goodness-of-fit of a model
2515:
is a model of best fit that is almost completely determined by
1067:
It is approached to within a constant distance by the graph of
4913:
It turns out that the approach can be extended to a theory of
4622:, is given by the MDL function or constrained MDL estimator:
5254:
An introduction to Kolmogorov complexity and its applications
3173:, is given by the MDL function or constrained MDL estimator:
2681:
is the least randomness deficiency (see above) of any model
1845:
2645:
is explained below. The Goodness-of-fit structure function
4835:{\displaystyle \Lambda (P)=-\log P(x)+K(P)\geq K(x)-O(1)}
4104:'s. Clearly, this function is non-increasing and reaches
4363:{\displaystyle h'_{x}(\alpha )=h_{x}(\alpha )+O(\log n)}
2609:
With respect to the picture: The MDL structure function
629:'s. Clearly, this function is nonincreasing and reaches
3372:{\displaystyle \Lambda (S)=\log |S|+K(S)\geq K(x)-O(1)}
5227:
Kolmogorov, A. N.; Uspenskii, V. A. (1 January 1987).
516:
is a contemplated model (set of n-length strings) for
4876:
4856:
4750:
4631:
4608:
4588:
4550:
4507:
4487:
4467:
4447:
4396:
4376:
4294:
4274:
4245:
4219:
4199:
4158:
4110:
4090:
4070:
4050:
4017:
3997:
3977:
3957:
3913:
3789:
3773:{\displaystyle P(x)=\exp(O(\log n))/|S|=n^{O(1)}/|S|}
3666:
3640:
3620:
3600:
3580:
3495:
3472:
3413:
3393:
3289:
3182:
3159:
3139:
3092:
3072:
3052:
3008:
2979:
2951:
2931:
2896:
2876:
2850:
2830:
2788:
2768:
2733:
2713:
2687:
2651:
2615:
2588:
2568:
2541:
2521:
2501:
2442:
2422:
2402:
2382:
2313:
2293:
2273:
2253:
2233:
2213:
2193:
2173:
2114:
2060:
2040:
2014:
1940:
1856:
1648:
1616:
1596:
1590:
bits, is as concise as the shortest one-part code of
1560:
1540:
1520:
1500:
1480:
1395:
1372:
1352:
1309:
1289:
1253:
1233:
1161:
1141:
1100:
1073:
1019:
980:
894:
871:
851:
823:
790:
764:
744:
724:
683:
635:
615:
595:
575:
542:
522:
502:
476:
456:
436:
326:
231:
198:
171:
151:
131:
95:
3971:is a contemplated model (computable probability of
89:To each constructive object corresponds a function
5079:Information and complexity in statistical modeling
4945:
4897:
4862:
4834:
4733:
4614:
4594:
4574:
4528:
4493:
4473:
4453:
4421:
4382:
4362:
4280:
4260:
4231:
4205:
4185:
4144:
4096:
4076:
4056:
4032:
4003:
3983:
3963:
3943:
3896:
3772:
3652:
3626:
3606:
3586:
3562:
3478:
3434:
3399:
3371:
3272:
3165:
3145:
3113:
3078:
3058:
3029:
2994:
2957:
2937:
2917:
2882:
2862:
2836:
2816:
2774:
2754:
2719:
2699:
2673:
2637:
2594:
2574:
2554:
2527:
2507:
2487:
2428:
2408:
2388:
2364:
2299:
2279:
2259:
2239:
2219:
2199:
2179:
2159:
2097:
2046:
2026:
2000:
1922:
1834:
1631:
1602:
1582:
1546:
1526:
1506:
1486:
1462:
1378:
1358:
1330:
1295:
1275:
1239:
1219:
1147:
1127:
1086:
1055:
1002:
962:
877:
857:
829:
805:
776:
750:
730:
710:
669:
621:
601:
581:
557:
528:
508:
488:
462:
442:
419:
284:
217:
184:
157:
137:
117:
80:The structure function was originally proposed by
4193:where c is the required number of bits to change
2054:self-delimitingly (you can determine its end) in
48:The Kolmogorov structure function is used in the
4658:
3816:
3206:
1220:{\displaystyle \alpha +h_{x}(\alpha )=K(x)+O(1)}
350:
87:
3466:For every computable probability distribution
3086:for the individual string x within a strip of
5082:(Online-Ausg. ed.). New York: Springer.
3907:where x is a binary string of length n with
3563:{\displaystyle -\log P(x)=\log |S|+O(\log n)}
8:
5276:: CS1 maint: multiple names: authors list (
4905:with certainty, not with great probability.
4725:
4667:
4536:with certainty, not with great probability.
4429:is the Kolmogorov complexity version of the
4226:
4220:
4128:
4122:
3891:
3825:
3442:with certainty, not with great probability.
3264:
3215:
3121:with certainty, not with great probability.
771:
765:
653:
647:
414:
359:
285:{\displaystyle \Phi (k)=\Phi _{0}-(k-k_{0})}
3780:. Kolmogorov's structure function becomes
3594:is some computable distribution on the set
2416:is about the same as the information about
2372:and therefore by the Kolmogorov complexity
1639:bits. This can be easily seen as follows:
1366:is an algorithmic sufficient statistic for
5313:Theory of Probability and Its Applications
5233:Theory of Probability and Its Applications
4909:Extension to rate distortion and denoising
4706:
3245:
5209:
5164:
5127:
5052:
5015:
4944:Cover, Thomas M.; Thomas, Joy A. (1991).
4875:
4855:
4749:
4661:
4636:
4630:
4607:
4587:
4549:
4506:
4486:
4466:
4446:
4401:
4395:
4375:
4324:
4299:
4293:
4273:
4244:
4218:
4198:
4157:
4131:
4117:
4109:
4089:
4069:
4049:
4016:
3996:
3976:
3956:
3912:
3819:
3794:
3788:
3765:
3757:
3752:
3737:
3725:
3717:
3712:
3665:
3639:
3619:
3599:
3579:
3534:
3526:
3494:
3471:
3412:
3392:
3319:
3311:
3288:
3209:
3187:
3181:
3158:
3138:
3091:
3071:
3051:
3007:
2978:
2950:
2930:
2895:
2875:
2849:
2829:
2793:
2787:
2767:
2732:
2712:
2686:
2656:
2650:
2620:
2614:
2587:
2567:
2546:
2540:
2520:
2500:
2461:
2452:
2441:
2421:
2401:
2381:
2312:
2292:
2272:
2252:
2232:
2212:
2192:
2172:
2146:
2129:
2121:
2113:
2075:
2067:
2059:
2039:
2013:
1978:
1970:
1950:
1939:
1905:
1883:
1861:
1855:
1782:
1774:
1724:
1647:
1615:
1595:
1575:
1567:
1559:
1539:
1519:
1499:
1479:
1425:
1417:
1394:
1371:
1351:
1308:
1288:
1258:
1252:
1232:
1172:
1160:
1140:
1099:
1094:for certain arguments (for instance, for
1078:
1072:
1018:
985:
979:
919:
893:
870:
850:
822:
789:
763:
743:
738:is the required number of bits to change
723:
682:
656:
642:
634:
614:
594:
574:
541:
521:
501:
475:
455:
435:
376:
368:
353:
331:
325:
273:
251:
230:
209:
197:
176:
170:
150:
130:
100:
94:
5192:Cover, T.M.; P. Gacs; R.M. Gray (1989).
5116:IEEE Transactions on Information Theory
5041:IEEE Transactions on Information Theory
5004:IEEE Transactions on Information Theory
4931:
4602:, the complexity of P upper bounded by
3153:, the complexity of S upper bounded by
2495:: the algorithmic sufficient statistic
1514:and as data-to-model code the index of
1463:{\displaystyle K(S)+\log |S|=K(x)+O(1)}
1056:{\displaystyle L(\alpha )+\alpha =K(x)}
5269:
4997:
4995:
4993:
4991:
4989:
4987:
4985:
4939:
4937:
4935:
4540:The MDL variant and probability models
2817:{\displaystyle \beta _{x}(\alpha )=0}
2638:{\displaystyle \lambda _{x}(\alpha )}
1474:That is, the two-part description of
963:{\displaystyle K(S)+K(x|S)=K(x)+O(1)}
7:
5256:(3rd ed.). New York: Springer.
4917:of individual finite sequences and
2945:is typical (random) for S. That is,
2001:{\displaystyle K(x|S)=\log |S|+O(1)}
841:The algorithmic sufficient statistic
2674:{\displaystyle \beta _{x}(\alpha )}
4751:
4670:
3290:
3218:
248:
232:
173:
152:
132:
97:
14:
1930:and minimal sufficient statistic.
5252:Li, M., Vitányi, P.M.B. (2008).
4850:It is proved that at each level
4441:It is proved that at each level
4268:is the Kolmogorov complexity of
3387:It is proved that at each level
3046:It is proved that at each level
2918:{\displaystyle K(S)\leq \alpha }
2755:{\displaystyle K(S)\leq \alpha }
2365:{\displaystyle K(x,S)=K(x)+O(1)}
2207:is a constant, which means that
1340:algorithmic sufficient statistic
1331:{\displaystyle K(S)\leq \alpha }
225:, then changes approximately as
4422:{\displaystyle h'_{x}(\alpha )}
3944:{\displaystyle -\log P(x)>0}
2488:{\displaystyle K(S|x^{*})=O(1)}
2160:{\displaystyle \log |S|-K(x|S)}
1283:) is called an optimal set for
5363:Algorithmic information theory
5153:IEEE Transactions on Computers
4948:Elements of information theory
4892:
4880:
4829:
4823:
4814:
4808:
4799:
4793:
4784:
4778:
4760:
4754:
4716:
4710:
4694:
4688:
4679:
4673:
4651:
4645:
4569:
4563:
4523:
4511:
4416:
4410:
4357:
4345:
4336:
4330:
4314:
4308:
4255:
4249:
4186:{\displaystyle \alpha =K(x)+c}
4174:
4168:
4145:{\displaystyle \log |\{x\}|=0}
4132:
4118:
4027:
4021:
3932:
3926:
3882:
3876:
3861:
3855:
3846:
3840:
3809:
3803:
3766:
3758:
3747:
3741:
3726:
3718:
3709:
3706:
3694:
3688:
3676:
3670:
3557:
3545:
3535:
3527:
3514:
3508:
3429:
3417:
3366:
3360:
3351:
3345:
3336:
3330:
3320:
3312:
3299:
3293:
3255:
3249:
3227:
3221:
3199:
3193:
3108:
3096:
3024:
3012:
2989:
2983:
2906:
2900:
2844:then there is a typical model
2805:
2799:
2743:
2737:
2668:
2662:
2632:
2626:
2482:
2476:
2467:
2453:
2446:
2359:
2353:
2344:
2338:
2329:
2317:
2154:
2147:
2140:
2130:
2122:
2092:
2086:
2076:
2068:
1995:
1989:
1979:
1971:
1958:
1951:
1944:
1917:
1911:
1895:
1889:
1873:
1867:
1829:
1823:
1814:
1808:
1799:
1793:
1783:
1775:
1762:
1756:
1747:
1741:
1732:
1725:
1718:
1709:
1703:
1694:
1688:
1679:
1667:
1658:
1652:
1626:
1620:
1576:
1568:
1457:
1451:
1442:
1436:
1426:
1418:
1405:
1399:
1319:
1313:
1276:{\displaystyle h_{x}(\alpha )}
1270:
1264:
1214:
1208:
1199:
1193:
1184:
1178:
1128:{\displaystyle \alpha =K(x)+c}
1116:
1110:
1050:
1044:
1029:
1023:
1003:{\displaystyle h_{x}(\alpha )}
997:
991:
957:
951:
942:
936:
927:
920:
913:
904:
898:
800:
794:
711:{\displaystyle \alpha =K(x)+c}
699:
693:
670:{\displaystyle \log |\{x\}|=0}
657:
643:
552:
546:
450:is a binary string of length
405:
399:
377:
369:
343:
337:
279:
260:
241:
235:
112:
106:
50:algorithmic information theory
18:Kolmogorov's turbulence theory
1:
4370:. For every complexity level
2098:{\displaystyle \log |S|+O(1)}
37:Kolmogorov structure function
4952:. New York: Wiley. pp.
2604:minimal sufficient statistic
118:{\displaystyle \Phi _{x}(k)}
5229:"Algorithms and Randomness"
5379:
4575:{\displaystyle -\log P(x)}
4481:for the individual string
3131:Minimum description length
2602:is called the algorithmic
2562:is a shortest program for
63:
60:of increasing complexity.
15:
4898:{\displaystyle O(\log n)}
4529:{\displaystyle O(\log n)}
3446:Application in statistics
3435:{\displaystyle O(\log n)}
3114:{\displaystyle O(\log n)}
3030:{\displaystyle O(\log n)}
1303:, and its description of
1227:and the associated model
185:{\displaystyle \Phi _{0}}
5138:10.1109/TIT.2010.2048491
5076:Rissanen, Jorma (2007).
1583:{\displaystyle \log |S|}
302:announcement cited above
5346:10.1093/comjnl/42.4.294
5300:10.1093/comjnl/42.4.340
5026:10.1109/TIT.2004.838346
4863:{\displaystyle \alpha }
4615:{\displaystyle \alpha }
4595:{\displaystyle \alpha }
4454:{\displaystyle \alpha }
4383:{\displaystyle \alpha }
4077:{\displaystyle \alpha }
3400:{\displaystyle \alpha }
3166:{\displaystyle \alpha }
3146:{\displaystyle \alpha }
3059:{\displaystyle \alpha }
3002:, every graph (up to a
2969:Selection of properties
2837:{\displaystyle \alpha }
2595:{\displaystyle \alpha }
2376:(the information about
2374:symmetry of information
1148:{\displaystyle \alpha }
602:{\displaystyle \alpha }
309:Contemporary definition
218:{\displaystyle k=k_{0}}
165:having taken the value
64:Kolmogorov's definition
5307:V'yugin, V.V. (1987).
5211:10.1214/aop/1176991250
4899:
4864:
4836:
4735:
4616:
4596:
4576:
4530:
4495:
4475:
4455:
4423:
4384:
4364:
4282:
4262:
4233:
4207:
4187:
4146:
4098:
4078:
4058:
4034:
4005:
3985:
3965:
3945:
3898:
3774:
3654:
3653:{\displaystyle x\in S}
3628:
3608:
3588:
3564:
3486:it can be proved that
3480:
3436:
3401:
3373:
3274:
3167:
3147:
3115:
3080:
3060:
3031:
2996:
2959:
2939:
2919:
2884:
2864:
2863:{\displaystyle S\ni x}
2838:
2818:
2776:
2756:
2721:
2701:
2700:{\displaystyle S\ni x}
2675:
2639:
2596:
2576:
2556:
2529:
2509:
2489:
2430:
2410:
2390:
2366:
2301:
2281:
2261:
2241:
2221:
2201:
2181:
2161:
2105:bits.) Therefore, the
2099:
2048:
2028:
2027:{\displaystyle S\ni x}
2008:. (For example, given
2002:
1931:
1924:
1836:
1633:
1604:
1584:
1548:
1534:in the enumeration of
1528:
1508:
1488:
1464:
1380:
1360:
1346:are the following: If
1332:
1297:
1277:
1241:
1221:
1149:
1129:
1088:
1057:
1004:
964:
879:
859:
831:
807:
778:
752:
732:
712:
671:
623:
603:
583:
559:
530:
510:
490:
489:{\displaystyle x\in S}
464:
444:
421:
306:
286:
219:
192:at a relatively small
186:
159:
139:
119:
77:
5198:Annals of Probability
4900:
4865:
4837:
4736:
4617:
4597:
4577:
4531:
4496:
4476:
4456:
4424:
4385:
4365:
4283:
4263:
4234:
4232:{\displaystyle \{x\}}
4208:
4188:
4147:
4099:
4079:
4059:
4042:Kolmogorov complexity
4035:
4006:
3991:-length strings) for
3986:
3966:
3946:
3899:
3775:
3655:
3629:
3614:of strings of length
3609:
3589:
3565:
3481:
3437:
3402:
3374:
3275:
3168:
3148:
3116:
3081:
3061:
3032:
2997:
2960:
2940:
2920:
2885:
2865:
2839:
2819:
2777:
2757:
2722:
2702:
2676:
2640:
2597:
2577:
2557:
2555:{\displaystyle x^{*}}
2530:
2510:
2490:
2431:
2411:
2391:
2367:
2302:
2282:
2262:
2242:
2222:
2202:
2182:
2162:
2107:randomness deficiency
2100:
2049:
2029:
2003:
1925:
1849:
1837:
1634:
1605:
1585:
1549:
1529:
1509:
1489:
1465:
1381:
1361:
1338:bits is therefore an
1333:
1298:
1278:
1242:
1222:
1150:
1130:
1089:
1087:{\displaystyle h_{x}}
1058:
1005:
965:
880:
860:
832:
815:Kolmogorov complexity
808:
779:
777:{\displaystyle \{x\}}
753:
733:
713:
672:
624:
604:
584:
567:Kolmogorov complexity
560:
531:
511:
491:
465:
445:
422:
287:
220:
187:
160:
158:{\displaystyle \Phi }
140:
138:{\displaystyle \Phi }
120:
71:
33:Kolmogorov complexity
5334:The Computer Journal
5288:The Computer Journal
4874:
4854:
4748:
4629:
4606:
4586:
4548:
4505:
4485:
4465:
4445:
4394:
4374:
4292:
4272:
4261:{\displaystyle K(x)}
4243:
4217:
4197:
4156:
4108:
4088:
4068:
4048:
4033:{\displaystyle K(P)}
4015:
3995:
3975:
3955:
3911:
3787:
3664:
3638:
3618:
3598:
3578:
3493:
3470:
3411:
3391:
3287:
3180:
3157:
3137:
3090:
3070:
3050:
3006:
2995:{\displaystyle K(x)}
2977:
2949:
2929:
2894:
2874:
2848:
2828:
2786:
2766:
2731:
2711:
2685:
2649:
2613:
2586:
2566:
2539:
2519:
2499:
2440:
2420:
2400:
2380:
2311:
2291:
2271:
2251:
2231:
2211:
2191:
2171:
2112:
2058:
2038:
2012:
1938:
1854:
1850:Structure functions
1646:
1632:{\displaystyle K(x)}
1614:
1594:
1558:
1538:
1518:
1498:
1478:
1393:
1370:
1350:
1344:sufficient statistic
1307:
1287:
1251:
1231:
1159:
1139:
1098:
1071:
1017:
978:
892:
869:
849:
821:
806:{\displaystyle K(x)}
788:
762:
742:
722:
681:
633:
613:
593:
573:
558:{\displaystyle K(S)}
540:
520:
500:
474:
454:
434:
324:
229:
196:
169:
149:
129:
93:
23:Statistical function
4644:
4409:
4307:
3802:
5175:10.1109/TC.2011.25
4895:
4860:
4832:
4731:
4666:
4632:
4612:
4592:
4572:
4526:
4501:within a strip of
4491:
4471:
4451:
4431:maximum likelihood
4419:
4397:
4380:
4360:
4295:
4278:
4258:
4229:
4203:
4183:
4142:
4094:
4074:
4054:
4030:
4001:
3981:
3961:
3941:
3894:
3824:
3790:
3770:
3650:
3624:
3604:
3584:
3560:
3476:
3462:Probability models
3432:
3397:
3369:
3270:
3214:
3163:
3143:
3111:
3076:
3056:
3027:
2992:
2955:
2935:
2915:
2880:
2860:
2834:
2814:
2772:
2752:
2717:
2697:
2671:
2635:
2592:
2572:
2552:
2525:
2505:
2485:
2426:
2406:
2386:
2362:
2297:
2277:
2257:
2237:
2217:
2197:
2177:
2157:
2095:
2044:
2034:, we can describe
2024:
1998:
1932:
1920:
1832:
1629:
1600:
1580:
1544:
1524:
1504:
1484:
1460:
1376:
1356:
1328:
1293:
1273:
1237:
1217:
1145:
1125:
1084:
1053:
1000:
960:
875:
855:
827:
803:
774:
748:
728:
708:
667:
619:
599:
579:
555:
526:
506:
486:
460:
440:
417:
358:
282:
215:
182:
155:
135:
115:
78:
5089:978-0-387-36610-4
5063:10.1109/18.945257
5010:(12): 3265–3290.
4657:
4494:{\displaystyle x}
4474:{\displaystyle S}
4281:{\displaystyle x}
4206:{\displaystyle x}
4097:{\displaystyle P}
4057:{\displaystyle P}
4004:{\displaystyle x}
3984:{\displaystyle n}
3964:{\displaystyle P}
3815:
3627:{\displaystyle n}
3607:{\displaystyle S}
3587:{\displaystyle P}
3479:{\displaystyle P}
3205:
3079:{\displaystyle S}
2958:{\displaystyle S}
2938:{\displaystyle x}
2883:{\displaystyle x}
2775:{\displaystyle S}
2720:{\displaystyle x}
2575:{\displaystyle x}
2528:{\displaystyle x}
2508:{\displaystyle S}
2429:{\displaystyle S}
2409:{\displaystyle S}
2389:{\displaystyle x}
2300:{\displaystyle x}
2280:{\displaystyle S}
2260:{\displaystyle x}
2240:{\displaystyle S}
2220:{\displaystyle x}
2200:{\displaystyle S}
2180:{\displaystyle x}
2047:{\displaystyle x}
1603:{\displaystyle x}
1547:{\displaystyle S}
1527:{\displaystyle x}
1507:{\displaystyle S}
1487:{\displaystyle x}
1379:{\displaystyle x}
1359:{\displaystyle S}
1296:{\displaystyle x}
1240:{\displaystyle S}
878:{\displaystyle x}
858:{\displaystyle S}
830:{\displaystyle x}
751:{\displaystyle x}
731:{\displaystyle c}
622:{\displaystyle S}
582:{\displaystyle S}
529:{\displaystyle x}
509:{\displaystyle S}
463:{\displaystyle n}
443:{\displaystyle x}
349:
28:Andrey Kolmogorov
5370:
5349:
5328:
5303:
5281:
5275:
5267:
5248:
5223:
5213:
5179:
5178:
5168:
5148:
5142:
5141:
5131:
5122:(7): 3438–3454.
5111:
5105:
5100:
5094:
5093:
5073:
5067:
5066:
5056:
5047:(6): 2443–2463.
5036:
5030:
5029:
5019:
4999:
4980:
4974:
4968:
4967:
4951:
4941:
4904:
4902:
4901:
4896:
4869:
4867:
4866:
4861:
4841:
4839:
4838:
4833:
4740:
4738:
4737:
4732:
4665:
4640:
4621:
4619:
4618:
4613:
4601:
4599:
4598:
4593:
4581:
4579:
4578:
4573:
4535:
4533:
4532:
4527:
4500:
4498:
4497:
4492:
4480:
4478:
4477:
4472:
4460:
4458:
4457:
4452:
4428:
4426:
4425:
4420:
4405:
4389:
4387:
4386:
4381:
4369:
4367:
4366:
4361:
4329:
4328:
4303:
4287:
4285:
4284:
4279:
4267:
4265:
4264:
4259:
4238:
4236:
4235:
4230:
4212:
4210:
4209:
4204:
4192:
4190:
4189:
4184:
4151:
4149:
4148:
4143:
4135:
4121:
4103:
4101:
4100:
4095:
4083:
4081:
4080:
4075:
4063:
4061:
4060:
4055:
4039:
4037:
4036:
4031:
4010:
4008:
4007:
4002:
3990:
3988:
3987:
3982:
3970:
3968:
3967:
3962:
3950:
3948:
3947:
3942:
3903:
3901:
3900:
3895:
3823:
3798:
3779:
3777:
3776:
3771:
3769:
3761:
3756:
3751:
3750:
3729:
3721:
3716:
3660:has probability
3659:
3657:
3656:
3651:
3633:
3631:
3630:
3625:
3613:
3611:
3610:
3605:
3593:
3591:
3590:
3585:
3574:For example, if
3569:
3567:
3566:
3561:
3538:
3530:
3485:
3483:
3482:
3477:
3454:by its inventor
3441:
3439:
3438:
3433:
3406:
3404:
3403:
3398:
3378:
3376:
3375:
3370:
3323:
3315:
3279:
3277:
3276:
3271:
3213:
3192:
3191:
3172:
3170:
3169:
3164:
3152:
3150:
3149:
3144:
3120:
3118:
3117:
3112:
3085:
3083:
3082:
3077:
3065:
3063:
3062:
3057:
3036:
3034:
3033:
3028:
3001:
2999:
2998:
2993:
2964:
2962:
2961:
2956:
2944:
2942:
2941:
2936:
2924:
2922:
2921:
2916:
2889:
2887:
2886:
2881:
2869:
2867:
2866:
2861:
2843:
2841:
2840:
2835:
2823:
2821:
2820:
2815:
2798:
2797:
2781:
2779:
2778:
2773:
2761:
2759:
2758:
2753:
2726:
2724:
2723:
2718:
2706:
2704:
2703:
2698:
2680:
2678:
2677:
2672:
2661:
2660:
2644:
2642:
2641:
2636:
2625:
2624:
2601:
2599:
2598:
2593:
2581:
2579:
2578:
2573:
2561:
2559:
2558:
2553:
2551:
2550:
2534:
2532:
2531:
2526:
2514:
2512:
2511:
2506:
2494:
2492:
2491:
2486:
2466:
2465:
2456:
2435:
2433:
2432:
2427:
2415:
2413:
2412:
2407:
2395:
2393:
2392:
2387:
2371:
2369:
2368:
2363:
2306:
2304:
2303:
2298:
2286:
2284:
2283:
2278:
2266:
2264:
2263:
2258:
2246:
2244:
2243:
2238:
2226:
2224:
2223:
2218:
2206:
2204:
2203:
2198:
2186:
2184:
2183:
2178:
2166:
2164:
2163:
2158:
2150:
2133:
2125:
2104:
2102:
2101:
2096:
2079:
2071:
2053:
2051:
2050:
2045:
2033:
2031:
2030:
2025:
2007:
2005:
2004:
1999:
1982:
1974:
1954:
1929:
1927:
1926:
1921:
1910:
1909:
1888:
1887:
1866:
1865:
1841:
1839:
1838:
1833:
1786:
1778:
1728:
1638:
1636:
1635:
1630:
1609:
1607:
1606:
1601:
1589:
1587:
1586:
1581:
1579:
1571:
1553:
1551:
1550:
1545:
1533:
1531:
1530:
1525:
1513:
1511:
1510:
1505:
1494:using the model
1493:
1491:
1490:
1485:
1469:
1467:
1466:
1461:
1429:
1421:
1385:
1383:
1382:
1377:
1365:
1363:
1362:
1357:
1337:
1335:
1334:
1329:
1302:
1300:
1299:
1294:
1282:
1280:
1279:
1274:
1263:
1262:
1246:
1244:
1243:
1238:
1226:
1224:
1223:
1218:
1177:
1176:
1154:
1152:
1151:
1146:
1134:
1132:
1131:
1126:
1093:
1091:
1090:
1085:
1083:
1082:
1062:
1060:
1059:
1054:
1009:
1007:
1006:
1001:
990:
989:
969:
967:
966:
961:
923:
884:
882:
881:
876:
864:
862:
861:
856:
845:We define a set
836:
834:
833:
828:
812:
810:
809:
804:
783:
781:
780:
775:
757:
755:
754:
749:
737:
735:
734:
729:
717:
715:
714:
709:
676:
674:
673:
668:
660:
646:
628:
626:
625:
620:
608:
606:
605:
600:
588:
586:
585:
580:
564:
562:
561:
556:
535:
533:
532:
527:
515:
513:
512:
507:
495:
493:
492:
487:
469:
467:
466:
461:
449:
447:
446:
441:
426:
424:
423:
418:
380:
372:
357:
336:
335:
304:
291:
289:
288:
283:
278:
277:
256:
255:
224:
222:
221:
216:
214:
213:
191:
189:
188:
183:
181:
180:
164:
162:
161:
156:
144:
142:
141:
136:
124:
122:
121:
116:
105:
104:
5378:
5377:
5373:
5372:
5371:
5369:
5368:
5367:
5353:
5352:
5331:
5325:10.1137/1132071
5306:
5285:
5268:
5264:
5251:
5245:10.1137/1132060
5226:
5191:
5188:
5183:
5182:
5150:
5149:
5145:
5113:
5112:
5108:
5101:
5097:
5090:
5075:
5074:
5070:
5038:
5037:
5033:
5001:
5000:
4983:
4975:
4971:
4964:
4943:
4942:
4933:
4928:
4915:rate distortion
4911:
4872:
4871:
4852:
4851:
4848:
4746:
4745:
4627:
4626:
4604:
4603:
4584:
4583:
4546:
4545:
4542:
4503:
4502:
4483:
4482:
4463:
4462:
4443:
4442:
4439:
4392:
4391:
4372:
4371:
4320:
4290:
4289:
4270:
4269:
4241:
4240:
4215:
4214:
4195:
4194:
4154:
4153:
4106:
4105:
4086:
4085:
4066:
4065:
4046:
4045:
4013:
4012:
3993:
3992:
3973:
3972:
3953:
3952:
3909:
3908:
3785:
3784:
3733:
3662:
3661:
3636:
3635:
3616:
3615:
3596:
3595:
3576:
3575:
3491:
3490:
3468:
3467:
3464:
3448:
3409:
3408:
3389:
3388:
3385:
3285:
3284:
3183:
3178:
3177:
3155:
3154:
3135:
3134:
3127:
3125:The MDL variant
3088:
3087:
3068:
3067:
3048:
3047:
3044:
3004:
3003:
2975:
2974:
2971:
2947:
2946:
2927:
2926:
2892:
2891:
2872:
2871:
2846:
2845:
2826:
2825:
2789:
2784:
2783:
2764:
2763:
2729:
2728:
2709:
2708:
2683:
2682:
2652:
2647:
2646:
2616:
2611:
2610:
2584:
2583:
2564:
2563:
2542:
2537:
2536:
2517:
2516:
2497:
2496:
2457:
2438:
2437:
2418:
2417:
2398:
2397:
2378:
2377:
2309:
2308:
2289:
2288:
2269:
2268:
2249:
2248:
2229:
2228:
2209:
2208:
2189:
2188:
2169:
2168:
2110:
2109:
2056:
2055:
2036:
2035:
2010:
2009:
1936:
1935:
1901:
1879:
1857:
1852:
1851:
1644:
1643:
1612:
1611:
1592:
1591:
1556:
1555:
1536:
1535:
1516:
1515:
1496:
1495:
1476:
1475:
1391:
1390:
1368:
1367:
1348:
1347:
1305:
1304:
1285:
1284:
1254:
1249:
1248:
1229:
1228:
1168:
1157:
1156:
1137:
1136:
1096:
1095:
1074:
1069:
1068:
1015:
1014:
981:
976:
975:
890:
889:
867:
866:
847:
846:
843:
819:
818:
786:
785:
760:
759:
740:
739:
720:
719:
679:
678:
631:
630:
611:
610:
591:
590:
571:
570:
538:
537:
518:
517:
498:
497:
472:
471:
452:
451:
432:
431:
327:
322:
321:
311:
305:
296:
269:
247:
227:
226:
205:
194:
193:
172:
167:
166:
147:
146:
127:
126:
96:
91:
90:
66:
24:
21:
12:
11:
5:
5376:
5374:
5366:
5365:
5355:
5354:
5351:
5350:
5340:(4): 294–317.
5329:
5319:(3): 508–512.
5304:
5294:(4): 340–342.
5283:
5263:978-0387339986
5262:
5249:
5239:(3): 389–412.
5224:
5204:(3): 840–865.
5187:
5184:
5181:
5180:
5159:(3): 395–407.
5143:
5106:
5095:
5088:
5068:
5031:
4981:
4969:
4963:978-0471062592
4962:
4930:
4929:
4927:
4924:
4910:
4907:
4894:
4891:
4888:
4885:
4882:
4879:
4859:
4847:
4844:
4831:
4828:
4825:
4822:
4819:
4816:
4813:
4810:
4807:
4804:
4801:
4798:
4795:
4792:
4789:
4786:
4783:
4780:
4777:
4774:
4771:
4768:
4765:
4762:
4759:
4756:
4753:
4742:
4741:
4730:
4727:
4724:
4721:
4718:
4715:
4712:
4709:
4705:
4702:
4699:
4696:
4693:
4690:
4687:
4684:
4681:
4678:
4675:
4672:
4669:
4664:
4660:
4656:
4653:
4650:
4647:
4643:
4639:
4635:
4611:
4591:
4571:
4568:
4565:
4562:
4559:
4556:
4553:
4541:
4538:
4525:
4522:
4519:
4516:
4513:
4510:
4490:
4470:
4450:
4438:
4435:
4418:
4415:
4412:
4408:
4404:
4400:
4379:
4359:
4356:
4353:
4350:
4347:
4344:
4341:
4338:
4335:
4332:
4327:
4323:
4319:
4316:
4313:
4310:
4306:
4302:
4298:
4277:
4257:
4254:
4251:
4248:
4228:
4225:
4222:
4202:
4182:
4179:
4176:
4173:
4170:
4167:
4164:
4161:
4141:
4138:
4134:
4130:
4127:
4124:
4120:
4116:
4113:
4093:
4073:
4053:
4029:
4026:
4023:
4020:
4000:
3980:
3960:
3940:
3937:
3934:
3931:
3928:
3925:
3922:
3919:
3916:
3905:
3904:
3893:
3890:
3887:
3884:
3881:
3878:
3875:
3872:
3869:
3866:
3863:
3860:
3857:
3854:
3851:
3848:
3845:
3842:
3839:
3836:
3833:
3830:
3827:
3822:
3818:
3814:
3811:
3808:
3805:
3801:
3797:
3793:
3768:
3764:
3760:
3755:
3749:
3746:
3743:
3740:
3736:
3732:
3728:
3724:
3720:
3715:
3711:
3708:
3705:
3702:
3699:
3696:
3693:
3690:
3687:
3684:
3681:
3678:
3675:
3672:
3669:
3649:
3646:
3643:
3623:
3603:
3583:
3572:
3571:
3559:
3556:
3553:
3550:
3547:
3544:
3541:
3537:
3533:
3529:
3525:
3522:
3519:
3516:
3513:
3510:
3507:
3504:
3501:
3498:
3475:
3463:
3460:
3456:Jorma Rissanen
3447:
3444:
3431:
3428:
3425:
3422:
3419:
3416:
3396:
3384:
3381:
3368:
3365:
3362:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3338:
3335:
3332:
3329:
3326:
3322:
3318:
3314:
3310:
3307:
3304:
3301:
3298:
3295:
3292:
3281:
3280:
3269:
3266:
3263:
3260:
3257:
3254:
3251:
3248:
3244:
3241:
3238:
3235:
3232:
3229:
3226:
3223:
3220:
3217:
3212:
3208:
3204:
3201:
3198:
3195:
3190:
3186:
3162:
3142:
3126:
3123:
3110:
3107:
3104:
3101:
3098:
3095:
3075:
3055:
3043:
3040:
3026:
3023:
3020:
3017:
3014:
3011:
2991:
2988:
2985:
2982:
2970:
2967:
2954:
2934:
2914:
2911:
2908:
2905:
2902:
2899:
2879:
2859:
2856:
2853:
2833:
2813:
2810:
2807:
2804:
2801:
2796:
2792:
2771:
2751:
2748:
2745:
2742:
2739:
2736:
2716:
2696:
2693:
2690:
2670:
2667:
2664:
2659:
2655:
2634:
2631:
2628:
2623:
2619:
2591:
2571:
2549:
2545:
2524:
2504:
2484:
2481:
2478:
2475:
2472:
2469:
2464:
2460:
2455:
2451:
2448:
2445:
2436:in x) we have
2425:
2405:
2385:
2361:
2358:
2355:
2352:
2349:
2346:
2343:
2340:
2337:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2296:
2276:
2256:
2236:
2216:
2196:
2176:
2156:
2153:
2149:
2145:
2142:
2139:
2136:
2132:
2128:
2124:
2120:
2117:
2094:
2091:
2088:
2085:
2082:
2078:
2074:
2070:
2066:
2063:
2043:
2023:
2020:
2017:
1997:
1994:
1991:
1988:
1985:
1981:
1977:
1973:
1969:
1966:
1963:
1960:
1957:
1953:
1949:
1946:
1943:
1919:
1916:
1913:
1908:
1904:
1900:
1897:
1894:
1891:
1886:
1882:
1878:
1875:
1872:
1869:
1864:
1860:
1844:
1843:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1810:
1807:
1804:
1801:
1798:
1795:
1792:
1789:
1785:
1781:
1777:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1752:
1749:
1746:
1743:
1740:
1737:
1734:
1731:
1727:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1663:
1660:
1657:
1654:
1651:
1628:
1625:
1622:
1619:
1599:
1578:
1574:
1570:
1566:
1563:
1543:
1523:
1503:
1483:
1472:
1471:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1428:
1424:
1420:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1375:
1355:
1327:
1324:
1321:
1318:
1315:
1312:
1292:
1272:
1269:
1266:
1261:
1257:
1236:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1175:
1171:
1167:
1164:
1144:
1135:). For these
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1081:
1077:
1065:
1064:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
999:
996:
993:
988:
984:
972:
971:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
922:
918:
915:
912:
909:
906:
903:
900:
897:
874:
854:
842:
839:
826:
802:
799:
796:
793:
773:
770:
767:
747:
727:
707:
704:
701:
698:
695:
692:
689:
686:
666:
663:
659:
655:
652:
649:
645:
641:
638:
618:
598:
578:
554:
551:
548:
545:
525:
505:
485:
482:
479:
459:
439:
428:
427:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
379:
375:
371:
367:
364:
361:
356:
352:
348:
345:
342:
339:
334:
330:
310:
307:
294:
281:
276:
272:
268:
265:
262:
259:
254:
250:
246:
243:
240:
237:
234:
212:
208:
204:
201:
179:
175:
154:
134:
114:
111:
108:
103:
99:
65:
62:
22:
13:
10:
9:
6:
4:
3:
2:
5375:
5364:
5361:
5360:
5358:
5347:
5343:
5339:
5335:
5330:
5326:
5322:
5318:
5314:
5310:
5305:
5301:
5297:
5293:
5289:
5284:
5279:
5273:
5265:
5259:
5255:
5250:
5246:
5242:
5238:
5234:
5230:
5225:
5221:
5217:
5212:
5207:
5203:
5199:
5195:
5190:
5189:
5185:
5176:
5172:
5167:
5162:
5158:
5154:
5147:
5144:
5139:
5135:
5130:
5125:
5121:
5117:
5110:
5107:
5104:
5099:
5096:
5091:
5085:
5081:
5080:
5072:
5069:
5064:
5060:
5055:
5050:
5046:
5042:
5035:
5032:
5027:
5023:
5018:
5013:
5009:
5005:
4998:
4996:
4994:
4992:
4990:
4988:
4986:
4982:
4979:
4973:
4970:
4965:
4959:
4955:
4950:
4949:
4940:
4938:
4936:
4932:
4925:
4923:
4920:
4916:
4908:
4906:
4889:
4886:
4883:
4877:
4857:
4846:Main property
4845:
4843:
4826:
4820:
4817:
4811:
4805:
4802:
4796:
4790:
4787:
4781:
4775:
4772:
4769:
4766:
4763:
4757:
4728:
4722:
4719:
4713:
4707:
4703:
4700:
4697:
4691:
4685:
4682:
4676:
4662:
4654:
4648:
4641:
4637:
4633:
4625:
4624:
4623:
4609:
4589:
4566:
4560:
4557:
4554:
4551:
4539:
4537:
4520:
4517:
4514:
4508:
4488:
4468:
4448:
4437:Main property
4436:
4434:
4432:
4413:
4406:
4402:
4398:
4390:the function
4377:
4354:
4351:
4348:
4342:
4339:
4333:
4325:
4321:
4317:
4311:
4304:
4300:
4296:
4275:
4252:
4246:
4223:
4200:
4180:
4177:
4171:
4165:
4162:
4159:
4139:
4136:
4125:
4114:
4111:
4091:
4071:
4051:
4043:
4024:
4018:
3998:
3978:
3958:
3938:
3935:
3929:
3923:
3920:
3917:
3914:
3888:
3885:
3879:
3873:
3870:
3867:
3864:
3858:
3852:
3849:
3843:
3837:
3834:
3831:
3828:
3820:
3812:
3806:
3799:
3795:
3791:
3783:
3782:
3781:
3762:
3753:
3744:
3738:
3734:
3730:
3722:
3713:
3703:
3700:
3697:
3691:
3685:
3682:
3679:
3673:
3667:
3647:
3644:
3641:
3621:
3601:
3581:
3554:
3551:
3548:
3542:
3539:
3531:
3523:
3520:
3517:
3511:
3505:
3502:
3499:
3496:
3489:
3488:
3487:
3473:
3461:
3459:
3457:
3453:
3445:
3443:
3426:
3423:
3420:
3414:
3394:
3383:Main property
3382:
3380:
3363:
3357:
3354:
3348:
3342:
3339:
3333:
3327:
3324:
3316:
3308:
3305:
3302:
3296:
3267:
3261:
3258:
3252:
3246:
3242:
3239:
3236:
3233:
3230:
3224:
3210:
3202:
3196:
3188:
3184:
3176:
3175:
3174:
3160:
3140:
3132:
3124:
3122:
3105:
3102:
3099:
3093:
3073:
3053:
3042:Main property
3041:
3039:
3021:
3018:
3015:
3009:
2986:
2980:
2968:
2966:
2952:
2932:
2912:
2909:
2903:
2897:
2877:
2857:
2854:
2851:
2831:
2811:
2808:
2802:
2794:
2790:
2769:
2749:
2746:
2740:
2734:
2714:
2694:
2691:
2688:
2665:
2657:
2653:
2629:
2621:
2617:
2607:
2605:
2589:
2569:
2547:
2543:
2522:
2502:
2479:
2473:
2470:
2462:
2458:
2449:
2443:
2423:
2403:
2383:
2375:
2356:
2350:
2347:
2341:
2335:
2332:
2326:
2323:
2320:
2314:
2294:
2274:
2254:
2234:
2214:
2194:
2174:
2151:
2143:
2137:
2134:
2126:
2118:
2115:
2108:
2089:
2083:
2080:
2072:
2064:
2061:
2041:
2021:
2018:
2015:
1992:
1986:
1983:
1975:
1967:
1964:
1961:
1955:
1947:
1941:
1914:
1906:
1902:
1898:
1892:
1884:
1880:
1876:
1870:
1862:
1858:
1848:
1826:
1820:
1817:
1811:
1805:
1802:
1796:
1790:
1787:
1779:
1771:
1768:
1765:
1759:
1753:
1750:
1744:
1738:
1735:
1729:
1721:
1715:
1712:
1706:
1700:
1697:
1691:
1685:
1682:
1676:
1673:
1670:
1664:
1661:
1655:
1649:
1642:
1641:
1640:
1623:
1617:
1597:
1572:
1564:
1561:
1541:
1521:
1501:
1481:
1454:
1448:
1445:
1439:
1433:
1430:
1422:
1414:
1411:
1408:
1402:
1396:
1389:
1388:
1387:
1373:
1353:
1345:
1341:
1325:
1322:
1316:
1310:
1290:
1267:
1259:
1255:
1247:(witness for
1234:
1211:
1205:
1202:
1196:
1190:
1187:
1181:
1173:
1169:
1165:
1162:
1142:
1122:
1119:
1113:
1107:
1104:
1101:
1079:
1075:
1047:
1041:
1038:
1035:
1032:
1026:
1020:
1013:
1012:
1011:
994:
986:
982:
974:The function
954:
948:
945:
939:
933:
930:
924:
916:
910:
907:
901:
895:
888:
887:
886:
872:
852:
840:
838:
824:
816:
797:
791:
768:
745:
725:
705:
702:
696:
690:
687:
684:
664:
661:
650:
639:
636:
616:
596:
576:
568:
549:
543:
523:
503:
483:
480:
477:
457:
437:
411:
408:
402:
396:
393:
390:
387:
384:
381:
373:
365:
362:
354:
346:
340:
332:
328:
320:
319:
318:
316:
308:
303:
299:
293:
274:
270:
266:
263:
257:
252:
244:
238:
210:
206:
202:
199:
177:
109:
101:
86:
83:
75:
70:
61:
59:
55:
51:
46:
43:
38:
34:
29:
19:
5337:
5333:
5316:
5312:
5291:
5287:
5253:
5236:
5232:
5201:
5197:
5156:
5152:
5146:
5119:
5115:
5109:
5098:
5078:
5071:
5054:math/0006233
5044:
5040:
5034:
5007:
5003:
4972:
4947:
4912:
4849:
4743:
4543:
4440:
3906:
3634:, then each
3573:
3465:
3449:
3386:
3282:
3128:
3045:
2972:
2608:
2373:
2106:
1933:
1473:
1339:
1066:
973:
844:
429:
312:
301:
88:
79:
47:
36:
25:
2247:containing
1155:'s we have
885:such that
865:containing
5186:Literature
5166:cs/0609121
5129:cs/0411014
5017:cs/0204037
4926:References
2890:such that
2727:such that
298:Kolmogorov
82:Kolmogorov
56:by use of
42:stochastic
5272:cite book
4919:denoising
4887:
4858:α
4818:−
4803:≥
4773:
4767:−
4752:Λ
4723:α
4720:≤
4671:Λ
4649:α
4634:λ
4610:α
4590:α
4558:
4552:−
4518:
4449:α
4414:α
4378:α
4352:
4334:α
4312:α
4160:α
4115:
4072:α
3921:
3915:−
3889:α
3886:≤
3835:
3829:−
3807:α
3701:
3686:
3645:∈
3552:
3524:
3503:
3497:−
3424:
3395:α
3355:−
3340:≥
3309:
3291:Λ
3262:α
3259:≤
3237:∋
3219:Λ
3197:α
3185:λ
3161:α
3141:α
3103:
3054:α
3019:
2913:α
2910:≤
2855:∋
2832:α
2824:for some
2803:α
2791:β
2750:α
2747:≤
2692:∋
2666:α
2654:β
2630:α
2618:λ
2590:α
2548:∗
2463:∗
2135:−
2119:
2065:
2019:∋
1968:
1915:α
1903:λ
1893:α
1881:β
1871:α
1803:≤
1772:
1751:≤
1698:≤
1662:≤
1565:
1415:
1326:α
1323:≤
1268:α
1182:α
1163:α
1143:α
1102:α
1036:α
1027:α
995:α
685:α
640:
597:α
481:∈
412:α
409:≤
388:∈
366:
341:α
267:−
258:−
249:Φ
233:Φ
174:Φ
153:Φ
133:Φ
98:Φ
26:In 1973,
5357:Category
4978:English)
4642:′
4407:′
4305:′
3800:′
1386:, then
295:—
76:, 1973).
5220:2244387
4954:175–178
4288:. Then
4040:is the
813:is the
565:is the
315:Vitányi
74:Tallinn
5260:
5218:
5086:
4960:
4744:where
4433:(ML).
3951:where
3283:where
718:where
496:where
430:where
58:models
54:string
35:. The
5216:JSTOR
5161:arXiv
5124:arXiv
5049:arXiv
5012:arXiv
4213:into
758:into
470:with
5278:link
5258:ISBN
5084:ISBN
4958:ISBN
4698:>
4239:and
4152:for
4064:and
3936:>
3865:>
3129:The
2925:and
2870:for
2707:for
2287:for
784:and
677:for
589:and
5342:doi
5321:doi
5296:doi
5241:doi
5206:doi
5171:doi
5134:doi
5059:doi
5022:doi
4884:log
4770:log
4659:min
4555:log
4515:log
4349:log
4112:log
4044:of
3918:log
3832:log
3817:min
3698:log
3683:exp
3549:log
3521:log
3500:log
3452:MDL
3421:log
3306:log
3207:min
3100:log
3016:log
2535:. (
2396:in
2187:in
2167:of
2116:log
2062:log
1965:log
1769:log
1610:in
1562:log
1554:in
1412:log
817:of
637:log
569:of
363:log
351:min
5359::
5338:42
5336:.
5317:32
5315:.
5311:.
5292:42
5290:.
5274:}}
5270:{{
5237:32
5235:.
5231:.
5214:.
5202:17
5200:.
5196:.
5169:.
5157:61
5155:.
5132:.
5120:56
5118:.
5057:.
5045:47
5043:.
5020:.
5008:50
5006:.
4984:^
4956:.
4934:^
4011:,
3458:.
2606:.
837:.
536:,
300:,
5348:.
5344::
5327:.
5323::
5302:.
5298::
5280:)
5266:.
5247:.
5243::
5222:.
5208::
5177:.
5173::
5163::
5140:.
5136::
5126::
5092:.
5065:.
5061::
5051::
5028:.
5024::
5014::
4966:.
4893:)
4890:n
4881:(
4878:O
4830:)
4827:1
4824:(
4821:O
4815:)
4812:x
4809:(
4806:K
4800:)
4797:P
4794:(
4791:K
4788:+
4785:)
4782:x
4779:(
4776:P
4764:=
4761:)
4758:P
4755:(
4729:,
4726:}
4717:)
4714:P
4711:(
4708:K
4704:,
4701:0
4695:)
4692:x
4689:(
4686:P
4683::
4680:)
4677:P
4674:(
4668:{
4663:P
4655:=
4652:)
4646:(
4638:x
4570:)
4567:x
4564:(
4561:P
4524:)
4521:n
4512:(
4509:O
4489:x
4469:S
4417:)
4411:(
4403:x
4399:h
4358:)
4355:n
4346:(
4343:O
4340:+
4337:)
4331:(
4326:x
4322:h
4318:=
4315:)
4309:(
4301:x
4297:h
4276:x
4256:)
4253:x
4250:(
4247:K
4227:}
4224:x
4221:{
4201:x
4181:c
4178:+
4175:)
4172:x
4169:(
4166:K
4163:=
4140:0
4137:=
4133:|
4129:}
4126:x
4123:{
4119:|
4092:P
4052:P
4028:)
4025:P
4022:(
4019:K
3999:x
3979:n
3959:P
3939:0
3933:)
3930:x
3927:(
3924:P
3892:}
3883:)
3880:P
3877:(
3874:K
3871:,
3868:0
3862:)
3859:x
3856:(
3853:P
3850::
3847:)
3844:x
3841:(
3838:P
3826:{
3821:P
3813:=
3810:)
3804:(
3796:x
3792:h
3767:|
3763:S
3759:|
3754:/
3748:)
3745:1
3742:(
3739:O
3735:n
3731:=
3727:|
3723:S
3719:|
3714:/
3710:)
3707:)
3704:n
3695:(
3692:O
3689:(
3680:=
3677:)
3674:x
3671:(
3668:P
3648:S
3642:x
3622:n
3602:S
3582:P
3570:.
3558:)
3555:n
3546:(
3543:O
3540:+
3536:|
3532:S
3528:|
3518:=
3515:)
3512:x
3509:(
3506:P
3474:P
3430:)
3427:n
3418:(
3415:O
3367:)
3364:1
3361:(
3358:O
3352:)
3349:x
3346:(
3343:K
3337:)
3334:S
3331:(
3328:K
3325:+
3321:|
3317:S
3313:|
3303:=
3300:)
3297:S
3294:(
3268:,
3265:}
3256:)
3253:S
3250:(
3247:K
3243:,
3240:x
3234:S
3231::
3228:)
3225:S
3222:(
3216:{
3211:S
3203:=
3200:)
3194:(
3189:x
3109:)
3106:n
3097:(
3094:O
3074:S
3025:)
3022:n
3013:(
3010:O
2990:)
2987:x
2984:(
2981:K
2953:S
2933:x
2907:)
2904:S
2901:(
2898:K
2878:x
2858:x
2852:S
2812:0
2809:=
2806:)
2800:(
2795:x
2770:S
2744:)
2741:S
2738:(
2735:K
2715:x
2695:x
2689:S
2669:)
2663:(
2658:x
2633:)
2627:(
2622:x
2570:x
2544:x
2523:x
2503:S
2483:)
2480:1
2477:(
2474:O
2471:=
2468:)
2459:x
2454:|
2450:S
2447:(
2444:K
2424:S
2404:S
2384:x
2360:)
2357:1
2354:(
2351:O
2348:+
2345:)
2342:x
2339:(
2336:K
2333:=
2330:)
2327:S
2324:,
2321:x
2318:(
2315:K
2295:x
2275:S
2255:x
2235:S
2215:x
2195:S
2175:x
2155:)
2152:S
2148:|
2144:x
2141:(
2138:K
2131:|
2127:S
2123:|
2093:)
2090:1
2087:(
2084:O
2081:+
2077:|
2073:S
2069:|
2042:x
2022:x
2016:S
1996:)
1993:1
1990:(
1987:O
1984:+
1980:|
1976:S
1972:|
1962:=
1959:)
1956:S
1952:|
1948:x
1945:(
1942:K
1918:)
1912:(
1907:x
1899:,
1896:)
1890:(
1885:x
1877:,
1874:)
1868:(
1863:x
1859:h
1842:,
1830:)
1827:1
1824:(
1821:O
1818:+
1815:)
1812:x
1809:(
1806:K
1800:)
1797:1
1794:(
1791:O
1788:+
1784:|
1780:S
1776:|
1766:+
1763:)
1760:S
1757:(
1754:K
1748:)
1745:1
1742:(
1739:O
1736:+
1733:)
1730:S
1726:|
1722:x
1719:(
1716:K
1713:+
1710:)
1707:S
1704:(
1701:K
1695:)
1692:1
1689:(
1686:O
1683:+
1680:)
1677:S
1674:,
1671:x
1668:(
1665:K
1659:)
1656:x
1653:(
1650:K
1627:)
1624:x
1621:(
1618:K
1598:x
1577:|
1573:S
1569:|
1542:S
1522:x
1502:S
1482:x
1470:.
1458:)
1455:1
1452:(
1449:O
1446:+
1443:)
1440:x
1437:(
1434:K
1431:=
1427:|
1423:S
1419:|
1409:+
1406:)
1403:S
1400:(
1397:K
1374:x
1354:S
1320:)
1317:S
1314:(
1311:K
1291:x
1271:)
1265:(
1260:x
1256:h
1235:S
1215:)
1212:1
1209:(
1206:O
1203:+
1200:)
1197:x
1194:(
1191:K
1188:=
1185:)
1179:(
1174:x
1170:h
1166:+
1123:c
1120:+
1117:)
1114:x
1111:(
1108:K
1105:=
1080:x
1076:h
1063:.
1051:)
1048:x
1045:(
1042:K
1039:=
1033:+
1030:)
1024:(
1021:L
998:)
992:(
987:x
983:h
970:.
958:)
955:1
952:(
949:O
946:+
943:)
940:x
937:(
934:K
931:=
928:)
925:S
921:|
917:x
914:(
911:K
908:+
905:)
902:S
899:(
896:K
873:x
853:S
825:x
801:)
798:x
795:(
792:K
772:}
769:x
766:{
746:x
726:c
706:c
703:+
700:)
697:x
694:(
691:K
688:=
665:0
662:=
658:|
654:}
651:x
648:{
644:|
617:S
577:S
553:)
550:S
547:(
544:K
524:x
504:S
484:S
478:x
458:n
438:x
415:}
406:)
403:S
400:(
397:K
394:,
391:S
385:x
382::
378:|
374:S
370:|
360:{
355:S
347:=
344:)
338:(
333:x
329:h
292:.
280:)
275:0
271:k
264:k
261:(
253:0
245:=
242:)
239:k
236:(
211:0
207:k
203:=
200:k
178:0
113:)
110:k
107:(
102:x
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
