Liczba wyraźnych różnic liczb całkowitych wybranych z

Podczas moich badań spotkałem następujący wynik.

$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$ gdzie $m=\omega(\sqrt n)$ i $a_1,\cdots,a_m$ są wybierane losowo z $[n]$ .

Szukam referencji / bezpośredniego dowodu.

Skrzyżowane na MO

reference-request co.combinatorics pr.probability Zhu Cao
źródło

Jeśli

m = \sqrt{n}

$m = \sqrt{n}$ , maksymalna liczba różnych różnic, które można uzyskać, to

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

$m(m-1)/2 < n/2$ . Tak więc naprawdę potrzebujesz, aby

m

$m$ rosło szybciej niż

\sqrt{n}

$\sqrt{n}$ aby to było prawdą. Co chciałbym zrobić, to spróbować obliczyć prawdopodobieństwo, że liczba

d

$d$ jest nie różnica

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

$d = |a_i - a_j|$ .

Peter Shor,

@Shor: dzięki, zaktualizowałem pytanie. I rzeczywiście, ponieważ

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

$\mathbb E(\sum x_i)=\sum \mathbb E(x_i)$ , łatwiej jest obliczyć dla konkretnej różnicy

d

$d$ .

Zhu Cao

@ZhuCao, kiedy mówisz „wybierz

m

$m$ liczb całkowitych

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

$a_1,...,a_m$ losowo z

[1, n]

$[1,n]$ ”, co to dokładnie rozumiesz? Zakładałem, że iid uniform

{1, \dots, n}

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

usul

@Andras nie, tak nie jest. Na przykład, jeśli nie zostanie wybrana liczba

1

$1$ (co dzieje się z prawdopodobieństwem ograniczonym od 0), wówczas różnica

n - 1

$n-1$ nie może się pojawić, a

D_{n} < n

$D_n<n$ . Ale dlaczego tak musi być? Pytanie tylko pyta, czy oczekiwanie

D_{n} / n

$D_n/n$ zbliża się do 1, a nie, że

D_{n}

$D_n$ jest równe 1 z dużym prawdopodobieństwem.

James Martin

Nie wysyłaj postów na wielu stronach Stack Exchange. Nasze zasady dotyczące witryn zabraniają równoczesnego zamieszczania postów: mówi przynajmniej, że poczekaj tydzień. A jeśli nie otrzymasz dobrej odpowiedzi, zawsze możesz ją oflagować, aby zwrócić uwagę moderatora i poprosić o migrację.

Odpowiedzi:

Załóżmy, jak podano, że . $m=\omega(\sqrt{n})$

Napraw dowolne . Rozważymy z . Celem jest pokazanie, że z wysokim prawdopodobieństwem, jak , jest zawarte w zbiorze różnic. $\epsilon>0$ $r\in[1,n]$ $r<(1-\epsilon)n$ $n\to\infty$ $r$

Najpierw rozważ zestaw . Liczba dla taka, że jest dwumianowa z oczekiwaniami wokół . Zatem z dużym prawdopodobieństwem od liczba takich będzie wynosić co najmniej , czyli . Następnie (twierdzenie, „pozostawione jako ćwiczenie”, trudne do pokazania) z dużym prawdopodobieństwem jako , zestaw ma rozmiar co najmniej . Napiszmy dla tego „dobrego zdarzenia”, że . $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}$

Załóżmy, że rzeczywiście utrzymuje, tzn. Istnieją co najmniej odrębne wartości mniejsze niż , dla . Zauważ, że dla każdej takiej wartości istnieje wartość która jest dokładnie większa. Teraz rozważ wartości dla . Te są niezależne i każdy z nich ma co najmniej prawdopodobieństwo , że jest w odległości od elementu zbioru . Prawdopodobieństwo, że nie wystąpi żadna różnica wynosi co najwyżej $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}$ która przyjmuje wartość 0 jako ponieważ . Tak więc prawdopodobieństwo, że utrzymuje, ale nie istnieje różnica wielkości ma tendencję do 0 jako . $n\to\infty$ $m=\omega(\sqrt{n})$ $G$ $r$ $n\to\infty$

Zatem (równomiernie w ) prawdopodobieństwo, że jest uwzględnione w zbiorze różnic, ma tendencję do 1 jako . Dlatego stosując liniowość oczekiwań, Ponieważ jest arbitralny, limit wynosi 1 zgodnie z życzeniem. $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
źródło

Czy traktujesz każdą różnicę jako niezależną w wyrażeniu , a jeśli tak, to czy jest to uzasadnione?

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

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

usul

@ James Oh, teraz widzę, gdzie tęskniłem . Dziękuję Ci.

n

$n$

Daniel Soltész

@usul: rzeczywiście przepraszam, mój argument był niechlujny i niekompletny. Rozszerzyłem go - myślę, że teraz trzyma wodę.

James Martin