Ein einfaches (?) Lustiges kombinatorisches Problem!

11

Lassen Sie uns und eine ganze Zahl t > 0 festlegen .0<E<1t>0

für jedes und für jeden Vektor ˉ c[ 0 , 1 ] n, so dass i [ n ] c iE × n istnc¯[0,1]ni[n]ciE×n

Ac¯:=|{S[n]:iS ciE×t}|(E×nt)

Ich weiß nicht, ob die Aussage wahr oder falsch ist. Ich glaube es ist wahr.

Meine Intuition ergibt sich aus der Beobachtung, dass für die Vektoren (mit der gewünschten Eigenschaft über die Summe) A ˉ c = ( E × n) giltc¯{0,1}n ; In diesem Fall können wir nur eine Teilmenge aus der Menge{i|auswählen ci=1}.Ac¯=(E×nt){i | ci=1}

In den anderen Fällen können wir mit der Koordinate in { i | eine gute Teilmenge erstellen (st die Summe ist größer als ) c i > E }, aber vielleicht auch mit wenigen Koordinaten aus der Menge { i | c iE } wir könnten andere gute Mengen erstellen!E×t{i | ci>E}{i | ciE}

Also, beweise es oder finde den Fehler! Ich hoffe, dass es ein lustiges Spiel für dich sein könnte!

Motivation der Frage :

Angenommen, Sie haben eine Zufallsvariable , ein typisches Maß dafür, "wie viel Zufälligkeit" in X vorhanden ist, ist die Min-EntropieX{0,1}nX

H(X)=minx{log(Pr[X=x])}

In einem intuitiven Sinne ist die Min-Entropie der schlimmste Fall der berühmten Shannon-Entropie (das ist der Durchschnittsfall ).

Wir sind daran interessiert, die Min-Entropie der Zufallsvariablen zu senken, wobei Y gleichmäßig über die Menge { y | verteilt ist i y i = t } .(Z=XY|Y)Y{y | iyi=t}

Wenn wir Glück haben, können wir locker die Bits von fangen , die "gute Entropie" haben, und wenn H ( X ) E n, dann ist H ( Z | Y ) E tXH(X)EnH(Z|Y)Et

Wie groß ist die Wahrscheinlichkeit, dass wir Glück haben?

Das Problem ist gut untersucht und es gibt viel Literatur, siehe zum Beispiel Lemma A.3. in der leckagebeständigen Public-Key-Kryptographie im Bounded-Retrieval-Modell

AntonioFa
quelle
3
Ich bin verwirrt von dem Begriff . Wie istE×n definiert, daes nicht unbedingt eine ganze Zahl ist? (E×nt)E×n
Dave Clarke
2
Was ist die Motivation?
Anthony Labarre
6
@ Dave Clarke, die Standardansätze bestehen darin, sie als Gammafunktion oder (vorausgesetzt, ist eine ganze Zahl) als t - 1 k = 0 ( E n - k ) / t zu definieren ! . tk=0t1(Enk)/t!
Peter Taylor
2
Binomialkoeffizienten können auf nicht integrale Argumente verallgemeinert werden (die Wikipedia-Seite enthält einige Details). In diesem Fall ist dies jedoch möglicherweise nicht erforderlich: Beachten Sie, dass es ausreicht, dies im Extremfall zu beweisen, in dem die Summe von gleich E × n ist (dh E ist ihr Mittelwert). ciE×nE
Klaus Draeger
1
@ Dave: Es tut mir leid für meine Ungenauigkeit, aus meiner Sicht können Sie wählen . En
AntonioFa

Antworten:

2

Die Vermutung in der Post gilt nicht, aber die schwächere Vermutung (in Bezug auf den Boden), die in den Kommentaren erwähnt wird, gilt. In der Tat hält etwas Stärkeres.


Lemma 1. Die Vermutung in der Post gilt nicht. Das heißt, es gibt eine Instanz, die die gegebenen Annahmen erfüllt, wobei

|{S[n]:iS ciEt}|<(Ent).

n=3c=(1,1,0.7)E=2.7/3=0.9t=2Et=1.8

|{S[3]:iS ci1.8}|=2
S{1,1}{1,1,0.7}(2.72)=2.71.7/2=2.295>2.   

En

Lemma 2. 0<E<1n,t>0c[0,1]ni[n]ciEn

|{S[n]:iS ciEt}|>(Ent)+(Ent+1)++(EnEn).

a=Ena=EnEciiciEnEtta

S[n]ndd=aat/n0i[n]ciaSdiSciad=at/n=EtEt

S

(nnd)+(nnd+1)++(nn1)+(nn)

=(nd)+(nd1)++(n1)+(n0)

>(ad)+(ad1)++(a1)+(a0)   n>a

=(aad)+(aad+1)++(aa1)+(aa).

ad=at/nta/n=E<1  

Neal Young
quelle