Количество различных отличий целых чисел выбранных из

Я столкнулся со следующим результатом во время моего исследования.

$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]$ .

Я ищу ссылку / прямое доказательство.

Кросспост на МО

reference-request co.combinatorics pr.probability Чжу Цао
источник

Если

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|$ ,

Питер Шор

@Shor: спасибо, я обновил вопрос. И действительно, поскольку

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

$\mathbb E(\sum x_i)=\sum \mathbb E(x_i)$ , легче вычислить для конкретной разности

d

$d$ .

Чжу Цао

@ZhuCao, когда вы говорите « случайным образом выберите

m

$m$ целых чисел

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

$a_1,...,a_m$ из

[1, n]

$[1,n]$ », какое распределение вы имеете в виду именно? Я предполагал, что я имел форму

{1, \dots, n}

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

усуль

@ Андрас нет, это не так. Например, если число

1

$1$ не выбрано (что происходит с вероятностью, ограниченной от 0), то разница

n - 1

$n-1$ не может появиться, и

D_{n} < n

$D_n<n$ . Но почему это должно быть так? Вопрос только в том, что ожидание

D_{n} / n

$D_n/n$ приближается к 1, а не что

D_{n}

$D_n$ равно 1 с высокой вероятностью.

Джеймс Мартин

Пожалуйста, не размещайте кросс-посты на нескольких сайтах Stack Exchange. Политика нашего сайта запрещает одновременную кросс-публикацию: как минимум, подождите неделю. И если вы не получили хорошего ответа, вы всегда можете пометить его для внимания модератора и попросить его перенести.

Ответы:

Предположим, что . $m=\omega(\sqrt{n})$

Исправьте все . Мы рассмотрим с . Цель состоит в том, чтобы показать , что с высокой вероятностью , как , входит в множество различий. $\epsilon>0$ $r\in[1,n]$ $r<(1-\epsilon)n$ $n\to\infty$ $r$

Сначала рассмотрим множество . Число с такое, что является биномиальным с ожиданием около . Таким образом, с большой вероятностью при число таких будет не меньше , что равно . Затем (утверждают, что «оставлено как упражнение», не трудно показать) с высокой вероятностью при , множество имеет размер не менее . Запишем для этого «хорошего события», чтобы . $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}$

Предположим, что действительно имеет место, то есть, по крайней мере, различных значений меньше, чем , для . Обратите внимание, что для каждого такого значения есть значение которое на точно больше . Теперь рассмотрим значения для . Они независимы и каждый из них имеет по крайней мере , вероятность быть на расстоянии от элемента множества . Вероятность того, что не будет получено никакой разницы будет не более $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}$ который переходит в 0 как поскольку . Таким образом, вероятность того, что имеет место, но разницы в размере существует, стремится к 0 при . $n\to\infty$ $m=\omega(\sqrt{n})$ $G$ $r$ $n\to\infty$

Таким образом (равномерно по ) вероятность того, что включен в набор разностей, стремится к 1 при . Следовательно, используя линейность ожидания, Поскольку произвольно, предел равен 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$

Джеймс Мартин
источник

Вы рассматриваете каждую разницу как независимую в выражении , и если да, то оправдано ли это?

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

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

усуль

@ Джеймс О, теперь я вижу, где я пропустил это . Спасибо.

n

$n$

Даниэль Солтес

@usul: действительно, извинения, мой аргумент был небрежным и неполным. Я расширил это - я думаю, что это держит воду теперь.

Джеймс Мартин