Jumlah perbedaan yang berbeda dari

Saya menemukan hasil berikut selama penelitian saya.

$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$ $m=\omega(\sqrt n)$ $a_1,\cdots,a_m$ $[n]$

Saya mencari referensi / bukti langsung.

Crossposted di MO

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

Jika , jumlah maksimum perbedaan yang berbeda yang bisa Anda dapatkan adalah . Jadi Anda benar-benar perlu untuk tumbuh lebih cepat dari agar ini benar. Apa yang akan saya lakukan adalah mencoba untuk menghitung probabilitas bahwa sejumlah adalah tidak perbedaan.

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

@ Guru: terima kasih, saya memperbarui pertanyaan. Dan memang karena , lebih mudah untuk menghitung perbedaan tertentu .

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

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

d

$d$

Zhu Cao

@ZhuCao, ketika Anda mengatakan "pilih integer secara acak dari ", distribusi apa yang Anda maksudkan sebenarnya? Saya mengasumsikan seragam iid

m

$m$

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

$a_1,...,a_m$

[1, n]

$[1,n]$

{1, \dots, n}

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

usul

@Andras tidak, bukan itu masalahnya. Misalnya, jika angka

1

$1$ tidak dipilih (yang terjadi dengan probabilitas dibatasi jauh dari 0) maka perbedaan

n - 1

$n-1$ tidak dapat muncul, dan

D_{n} < n

$D_n<n$ . Tetapi mengapa harus demikian? Pertanyaannya hanya menanyakan bahwa ekspektasi

D_{n} / n

$D_n/n$ mendekati 1, bukankah

D_{n}

$D_n$ sama dengan 1 dengan probabilitas tinggi.

James Martin

Tolong jangan posting silang di beberapa situs Stack Exchange. Kebijakan situs kami melarang posting silang secara bersamaan: katanya, minimal, tunggu seminggu. Dan jika Anda tidak mendapatkan jawaban yang baik, Anda selalu dapat memberi tanda untuk perhatian moderator untuk meminta dimigrasi.

Jawaban:

Asumsikan seperti yang diberikan bahwa $m=\omega(\sqrt{n})$ .

Perbaiki . Kami akan mempertimbangkan dengan . Tujuannya adalah untuk menunjukkan bahwa dengan probabilitas tinggi sebagai , $\epsilon>0$ $r\in[1,n]$ $r<(1-\epsilon)n$ $n\to\infty$ $r$ termasuk dalam set perbedaan.

Pertama-tama pertimbangkan himpunan . Jumlah dengan sedemikian sehingga adalah binomial dengan harapan sekitar . Jadi dengan probabilitas tinggi sebagai , jumlah tersebut setidaknya akan menjadi , yaitu . Kemudian (klaim, "dibiarkan sebagai latihan", tidak sulit untuk ditampilkan) dengan probabilitas tinggi sebagai , set memiliki ukuran setidaknya . Mari kita menulis untuk "acara bagus" ini, bahwa $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}$ .

Misalkan memang memegang, yaitu setidaknya ada nilai yang berbeda dari kurang dari , untuk . Perhatikan bahwa untuk setiap nilai tersebut, ada nilai yang tepatnya lebih besar. Sekarang perhatikan nilai untuk . Ini adalah independen dan masing-masing memiliki probabilitas setidaknya berada pada jarak dari unsur himpunan . Probabilitas bahwa tidak ada perbedaan yang dihasilkan adalah paling banyak $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}$ yang menjadi 0 sebagai sejak . Jadi memang, probabilitas yang dimiliki tetapi tidak ada perbedaan ukuran ada cenderung 0 sebagai . $n\to\infty$ $m=\omega(\sqrt{n})$ $G$ $r$ $n\to\infty$

Jadi (seragam dalam ) probabilitas bahwa termasuk dalam set perbedaan cenderung 1 sebagai . Karenanya menggunakan linearitas ekspektasi, Karena adalah arbitrer, batasnya adalah 1 seperti yang diinginkan. $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
sumber

Apakah Anda memperlakukan setiap perbedaan sebagai independen dalam ekspresi , dan jika demikian, apakah itu dibenarkan?

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

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

usul

@ James Oh, sekarang saya melihat di mana saya melewatkan . Terima kasih.

n

$n$

Daniel Soltész

@ Usul: memang, permintaan maaf, argumen saya ceroboh dan tidak lengkap. Saya telah mengembangkannya - saya pikir itu menampung air sekarang.

James Martin