Erwartete Werte der Kolmogorov-Komplexität in einer Zufallsstichprobe

9

Die Kolmogorov-Komplexität eines Strings ist nicht berechenbar. Wie wird jedoch erwartet, dass in einer zufälligen Teilmenge der Größe von binären Zeichenfolgen der Länge die Komplexität geringer ist als eine ganze Zahl kleiner als (als Funktion von , und )?n n 0 n M n n 0Mnn0nMnn0

vs.
quelle
Verwenden Sie hier "Standard" -Kolmogorov-Komplexität oder Präfixkomplexität?
Aubrey da Cunha
Eigentlich dachte ich nur an Kolmogorovs Komplexität. Ich vermutete die Grenze, die Domotorp erwähnte, wenn wir das Universum aller Strings betrachten. Mir war nicht klar, ob ein "konsistentes" Ergebnis für eine beliebige zufällige Teilmenge der Größe kann. Würde uns die Komplexität des Präfixes jedoch zu einem anderen Standpunkt führen? M.2noM
gegen
Es würde sicherlich nicht die Größenordnung ändern, tatsächlich denke ich, dass meine Antwort jetzt für beide Versionen gebunden ist.
Domotorp
1
Für jedes und jedes c ist die Wahrscheinlichkeit, dass ein zufälliger n- Bit-String x die Kolmogorov-Komplexität K ( x ) n - c aufweist, größer als 1 - 1ncnxK(x)nc (mitc=n-n0). In einer zufälligen Verteilung vonMStrings sollten Sie alsoMerwarten112cc=nn0M Strings mit... intuitiv besteht eine sehr hohe Wahrscheinlichkeit, einen String mit hoher Kolmogorov-Komplexität auszuwählen. M2(nn0)K(x)<n0
Marzio De Biasi

Antworten:

10

Die Kolmogorov-Komplexität wird nur bis zu einer additiven Konstante bestimmt, so dass es nicht möglich ist, eine genaue Antwort zu geben. Die Grenze, die ich hier beschreibe, ist noch schwächer.

Natürlich kann die erwartete Anzahl leicht berechnet werden, wenn wir wissen, wie viele der Zeichenfolgen eine Komplexität von weniger als haben. Lassen Sie mich dies beantworten. Es ist normalerweise die erste Aussage über die Komplexität von Kolmogorov, dass diese Zahl höchstens beträgt - da es nur diese vielen Zeichenfolgen kleinerer Länge gibt. Wenn Ihr Programm andererseits "von Länge , nehmen Sie die te Zahl" sagt , erhalten Sie -Ketten mit einer Komplexität von weniger als , wobei ist Präfixfreie Version der Kolmogorov-Komplexität von (also höchstensn 0 2 n 0 - 1 n x 2 n 0 - K ( n ) - C n 0 K ( n ) n log n + log n + O ( 1 ) p x n x n O ( 1 ) p x2nn02n01nx2n0K(n)Cn0K(n)nlogn+logn+O(1)). Im Detail enthält die Zeichenfolge zuerst die Beschreibung der Turing-Maschine, die die Eingabe , wobei p die Beschreibung eines präfixfreien Programms ist, das ausgibt und die te Anzahl der Länge ausgibt , die Bits ist und dann folgt .pxnxnO(1)px

Wahrscheinlich ist es möglich, diese Grenzen zu verbessern, aber ich bezweifle, dass Sie eine genaue Antwort erhalten könnten.

domotorp
quelle
Könnten Sie etwas über den Satz "Wenn Ihr Programm" von Länge n, nehmen Sie die x-te Zahl "" erklären?
gegen
Sie haben Recht, es sollte dort ohne Präfix sein, ich habe es korrigiert.
Domotorp
3

Eine genaue Antwort kann gegeben werden. Die Anzahl der Strings der Länge mit (einfacher) Komplexität beträgt höchstens n 0 2 n 0 - K ( n 0 | n ) bis zu einem konstanten Faktor. Daher hat jeder Prozess, der zufällig eine Teilmenge auswählt, mit vernünftiger Wahrscheinlichkeit einen 2 - K ( n 0 | n ) + O ( 1 ) Bruchteil von Zeichenfolgen mit einer Komplexität von weniger als n 0 . Um unseren Anspruch zu zeigen, genügt es zu zeigen, dass die Anzahl der Zeichenfolgen komplex istnn02n0K(n0|n)2K(n0|n)+O(1)n0gleich zu ist auch gegeben durch 2 k - K ( k | n ) . Wir können das notwendige Ergebnis zeigen, indem wir die Summe dieses Wertes über k von 1 bis n 0 bestimmen . Um dies zu zeigen, verwenden wir ein Additivitätsergebnis für die einfache Komplexität (aufgrund von B. Bauwens und A. Shen. Ein Additivitätssatz für die einfache Kolmogorov-Komplexität . Theory of Computing Systems, 52 (2): 297-302, Februar 2013), C. ( a , b ) = K ( a | C ( a , b )k2kK(k|n)kn0 Hier bezeichnet K ( ) die präfixfreie Kolmogorov-Komplexität. Die Wahl a = n , beobachten wirdass für jedes n -BitString b Komplexitäts k haben wir k = C ( b ) = C ( n , b ) + O (

C(a,b)=K(a|C(a,b))+C(b|a,C(a,b))+O(1).
K()a=nnbk Daherhaben wirfür jedes solche b C ( b | n , k ) = k - K ( n | k ) + O ( 1 ) . Sei k ' = k - K ( n |
k=C(b)=C(n,b)+O(1)=K(n|k)+C(b|n,k)+O(1).
bC(b|n,k)=kK(n|k)+O(1) . Nun kann man beobachten, dass es höchstens O ( 2 k ' ) solcher Strings b gibt und jeder der lexikographisch ersten 2 k ' Strings der Länge n C ( b | n , k ) k ' + O ( 1 ) erfüllt. Somiterfüllt Ω ( 2 k ' ) von ihnen C ( b | n , k ) =k=kK(n|k)O(2k)b2knC(b|n,k)k+O(1)Ω(2k) .C(b|n,k)=k+O(1)
Bruno Bauwens
quelle