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

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

$lim_{n \to \infty} E [\frac{# {| a_{i} - a_{j} |, 1 \leq i, j \leq m}}{n}] = 1$ $\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1$ wobei und zufällig aus . $m=\omega(\sqrt n)$ $a_1,\cdots,a_m$ $[n]$

Ich suche eine Referenz / einen direkten Beweis.

Am MO gekreuzt

reference-request co.combinatorics pr.probability Zhu Cao
quelle

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 = \sqrt{n}

$m = \sqrt{n}$

m (m - 1) / 2 < n / 2

$m(m-1)/2 < n/2$

m

$m$

\sqrt{n}

$\sqrt{n}$

d

$d$

d = | a_{i} - a_{j} |

$d = |a_i - a_j|$

Peter Shor

@Shor: danke, ich habe die Frage aktualisiert. Und tatsächlich, da , ist es einfacher, für eine bestimmte Differenz zu berechnen .

E (\sum x_{i}) = \sum E (x_{i})

$\mathbb E(\sum x_i)=\sum \mathbb E(x_i)$

d

$d$

Zhu Cao

@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 .

m

$m$

a_{1}, . . ., a_{m}

$a_1,...,a_m$

[1, n]

$[1,n]$

{1, \dots, n}

$\{1,\dots,n\}$

USUL

@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.

1

$1$

n - 1

$n-1$

D_{n} < n

$D_n<n$

D_{n} / n

$D_n/n$

D_{n}

$D_n$

James Martin

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.

Antworten:

Angenommen, . $m=\omega(\sqrt{n})$

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

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=\{a_i:i<m/2\}\cap[1,\epsilon n]$ $i$ $i<m/2$ $a_i<\epsilon n$ $\epsilon m/2$ $n\to\infty$ $i$ $\epsilon m/4$ $\omega(\sqrt{n})$ $n\to\infty$ $A$ $\sqrt{n}$ $G$ $|A|\geq\sqrt{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öchstens $G$ $\sqrt{n}$ $a_i$ $\epsilon n$ $i<m/2$ $k\in [1,n]$ $r$ $a_i$ $i\geq m/2$ $\sqrt{n}/n=1/\sqrt{n}$ $r$ $A$ $r$ $(1-1/\sqrt{n})^{m/2}$ was auf 0 als da . Tatsächlich tendiert die Wahrscheinlichkeit, dass gilt, aber kein Unterschied der Größe existiert, zu 0 als . $n\to\infty$ $m=\omega(\sqrt{n})$ $G$ $r$ $n\to\infty$

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-\epsilon)n$ $r$ $n\to\infty$

\underset{n \to \infty}{lim inf} E [\frac{# {| a_{i} - a_{j} |, 1 \leq i, j \leq m}}{n}] \geq 1 - ϵ .

$\liminf \limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}\right] \geq 1-\epsilon.$

ϵ

$\epsilon$

James Martin
quelle

Behandeln Sie jeden Unterschied als unabhängig im Ausdruck , und wenn ja, ist dies gerechtfertigt?

1 - (1 - ϵ / n)^{ω (n)}

$1-(1-\epsilon/n)^{\omega(n)}$

Usul

@ James Oh, jetzt sehe ich, wo ich das verpasst habe . Vielen Dank.

n

$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