Ereignisse mit hoher Wahrscheinlichkeit ohne Koordinaten mit niedriger Wahrscheinlichkeit

9

XΣnΣH(X)(nδ)log|Σ|δESupp(X)XPr[XE]1εε

Wir sagen, dass ein Paar eine Koordinate mit niedriger Wahrscheinlichkeit von wenn . Wir sagen, dass ein String eine Koordinate mit niedriger Wahrscheinlichkeit von wenn eine Koordinate mit niedriger Wahrscheinlichkeit von für einige .(i,σ)Pr [ X E | X i = σ ] & egr; x & Sigma; n E ( i , x i ) E iEPr[XE|Xi=σ]εxΣn E(i,xi)Ei

Im Allgemeinen können einige Zeichenfolgen in Koordinaten mit niedriger Wahrscheinlichkeit von . Die Frage ist, ob wir immer ein Ereignis hoher Wahrscheinlichkeit finden können, so dass kein String in eine Koordinate mit niedriger Wahrscheinlichkeit von (und nicht von ) enthält.E E 'E E ' E ' E.EEEEEEE

Vielen Dank!

Oder Meir
quelle

Antworten:

4

Hier ist ein Beispiel, das die Antwort von Harry Yuen ergänzt. Für ein Gegenbeispiel genügt es, geeignetes zu definieren und zu zeigen, dass jede große Teilmenge eine Koordinate mit niedriger Wahrscheinlichkeit von - eine Koordinate mit niedriger Wahrscheinlichkeit von ist notwendigerweise eine Koordinate mit niedriger Wahrscheinlichkeit -ordinate von .E 'E E E E 'X,EEEEEE

Außerdem werde ich die Bedingung bezüglich der Entropie ignorieren - das Anhängen von unabhängigen gleichmäßig verteilten Zufallsvariablen an (und das Nehmen von an ) erhöhtauf fast ohne zu beeinflussen, ob ein solches existiert (ich habe dies nicht sorgfältig durchdacht).X E E × Σ N H ( X ) / ( n + N ) log | Σ | 1 E 'NXEE×ΣNH(X)/(n+N)log|Σ|1E

Hier ist das Beispiel. Sei ein zufälliges Element von so dass jeder Vektor mit Hamming-Gewicht (dh Vektoren der Form ) eine Wahrscheinlichkeit und die hat All-One-Vektor hat die Wahrscheinlichkeit . Sei die Menge der Vektoren mit dem Hamming-Gewicht .{ 0 , 1 } n 1 0 010 0 ( 1 - ϵ ) / n 1 1 ϵ E 1X{0,1}n100100(1ϵ)/n11ϵE1

Betrachten wir eine Teilmenge . Wenn nicht leer ist, enthält es einen Vektor des Hamming-Gewichts , beispielsweise ohne Verlust der Allgemeinheit. Aber , was kleiner als wenn ist ungefähr .E ' 1 100 0 Pr [ X E | X i = 1 ] = ( 1 - ϵ ) / nEEE11000 ϵn2/ϵ2Pr[XE|Xi=1]=(1ϵ)/n(1ϵ)/n+ϵϵn2/ϵ2

Colin McQuillan
quelle
6

Wie vergleicht sich mit ? Wenn sein kann , dann denke ich , können wir erreichen , was Sie wollen. Lassen . Man beachte, dass unter eine Wahrscheinlichkeitsmasse erhält . Let bezeichnet die Wahrscheinlichkeitsmasse in Zeichenfolge in zugeordneten , so dass die hat Symbol ten Koordinaten .n ϵ O ( 1 / ϵnϵB=Supp(X)-EBϵXλ(i,σ)ϵBiσO(1/n)B=Supp(X)EBϵXλ(i,σ)ϵBiσ

Angenommen waren eine geringe Wahrscheinlichkeit für einige Zeichenketten in Koordinaten . Let auf diese Zeichenfolgen zugewiesen , um die Wahrscheinlichkeitsmasse bezeichnen. Dann ist per Definition , was impliziert, dass . Wir können diese Zeichenfolgen mit geringer Wahrscheinlichkeit verwerfen, während wir nur einen -Verlust in prob erleiden. Masse .E δ ( i , σ ) δ ( i , σ )(i,σ)Eδ(i,σ)δ(i,σ)δ(i,σ)+λ(i,σ)ϵϵδ(i,σ)2λ(i,σ)ϵ2δ(i,σ)E

Fahren Sie damit für alle möglichen Fehler , und am Ende verwerfen wir höchstens . Dies nutzt die Tatsache , daß für alle , .(i,σ)i,σδ(i,σ)iσ2λ(i,σ)ϵ22iϵ2=2nϵ2iσλ(i,σ)=1

Wenn Sie möchten, dass die Wahrscheinlichkeitsmasse , muss so sein, dass oder genügt. 1 - γ ϵ ϵ + 2 n ϵ 2γ ϵ = O ( γ / E1γϵϵ+2nϵ2γϵ=O(γ/2n)

Mir ist im Moment nicht klar, ob diese Abhängigkeit von beseitigt werden kann; Ich werde weiter darüber nachdenken.n

Henry Yuen
quelle
Oh, ich habe gerade festgestellt, dass sie eine stärkere Forderung freuen - nämlich, dass hat keinen geringe Wahrscheinlichkeit Koordinaten in Bezug auf , nicht . Ich werde heute später darauf zurückkommen. E ' E.EEE
Henry Yuen
Vielen Dank! Ich suche ein Epsilon, das konstant ist, aber beliebig klein sein kann.
Oder Meir