Anzahl der eindeutigen Unterschiede von ganzen Zahlen, ausgewählt aus

21

Bei meiner Recherche bin ich auf folgendes Ergebnis gestoßen.

limnE[#{|aiaj|,1i,jm}n]=1
wobei und zufällig aus .m=ω(n)a1,,am[n]

Ich suche eine Referenz / einen direkten Beweis.


Am MO gekreuzt

Zhu Cao
quelle
1
Wenn , können Sie maximal unterschiedliche Differenzen erhalten . So dass Sie wirklich brauchen zu wachsen schneller als für diese wahr zu sein. Was ich tun würde , ist zu versuchen , die Wahrscheinlichkeit zu berechnen , dass eine Zahl ist nicht eine Differenz. m=nm(m1)/2<n/2mndd=|aiaj|
Peter Shor
@Shor: danke, ich habe die Frage aktualisiert. Und tatsächlich, da , ist es einfacher, für eine bestimmte Differenz zu berechnen . E(xi)=E(xi)d
Zhu Cao
1
@ZhuCao, wenn du sagst "wähle ganze Zahlen zufällig aus ", welche Verteilung meinst du genau? Ich ging davon aus, dass es sich um eine Uniform . ma1,...,am[1,n]{1,,n}
USUL
1
@Andras nein, das ist nicht der Fall. Wenn zum Beispiel die Zahl nicht gewählt wird (was mit einer von 0 abgegrenzten Wahrscheinlichkeit geschieht), kann die Differenz nicht auftreten und . Aber warum muss das so sein? Die Frage stellt nur die Frage, dass die Erwartung von nahe an 1 kommt, nicht, dass mit hoher Wahrscheinlichkeit gleich 1 ist. 1n1Dn<nDn/nDn
James Martin
2
Bitte posten Sie nicht auf mehreren Stack Exchange-Sites. Unsere Website-Richtlinie verbietet gleichzeitiges Cross-Posting: Sie besagt, dass mindestens eine Woche gewartet werden muss. Und wenn Sie keine gute Antwort erhalten, können Sie den Moderator jederzeit darauf hinweisen, dass er migriert werden soll.
DW

Antworten:

7

Angenommen, .m=ω(n)

Fixiere ein beliebiges . Wir betrachten mit . Das Ziel besteht darin , dass mit hohen Wahrscheinlichkeit zu zeigen , ist in dem Satz von Differenzen enthalten.ϵ>0r[1,n]r<(1ϵ)nnr

Betrachten Sie zunächst die Menge . Die Anzahl von mit so dass mit einer Erwartung um binomial ist . Mit einer hohen Wahrscheinlichkeit von wird die Anzahl solcher mindestens , was . Dann ist (Anspruch, „links als Übung“, nicht schwer , zu zeigen) , mit hohen Wahrscheinlichkeit als , wobei der Satz hat Größe mindestens . Schreiben wir für dieses "gute Ereignis", das .A={ai:i<m/2}[1,ϵn]ii<m/2ai<ϵnϵm/2niϵm/4ω(n)nAnG|A|n

Nehmen wir an, dass tatsächlich gilt, dh es gibt mindestens verschiedene Werte von kleiner als für . Man beachte, dass es für jeden solchen Wert einen Wert gibt, der genau größer ist. Betrachten Sie nun die Werte von für . Diese sind unabhängig und jeder hat eine Wahrscheinlichkeit von mindestens , sich in einem Abstand von einem Element der Menge . Die Wahrscheinlichkeit, dass sich kein Unterschied ergibt, beträgt dann höchstensGnaiϵni<m/2k[1,n]raiim/2n/n=1/nrAr(11/n)m/2was auf 0 als da . Tatsächlich tendiert die Wahrscheinlichkeit, dass gilt, aber kein Unterschied der Größe existiert, zu 0 als .nm=ω(n)Grn

Die Wahrscheinlichkeit, dass in der Menge der Differenzen enthalten ist, tendiert also (einheitlich in ) zu 1 als . Unter Verwendung der Linearität der Erwartung, Da beliebig ist, ist die Grenze wie gewünscht 1.r<(1ϵ)nrn

lim infnE[#{|aiaj|,1i,jm}n]1ϵ.
ϵ
James Martin
quelle
1
Behandeln Sie jeden Unterschied als unabhängig im Ausdruck , und wenn ja, ist dies gerechtfertigt? 1(1ϵ/n)ω(n)
Usul
@ James Oh, jetzt sehe ich, wo ich das verpasst habe . Vielen Dank. n
Daniel Soltész,
@usul: in der Tat, entschuldigung, mein Argument war schlampig und unvollständig. Ich habe es erweitert - ich denke, es hält jetzt Wasser.
James Martin