Número de diferenças distintas de números inteiros escolhidos entre

Encontrei o seguinte resultado durante minha pesquisa.

$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$ onde $m=\omega(\sqrt n)$ e $a_1,\cdots,a_m$ são escolhidos aleatoriamente entre $[n]$ .

Estou à procura de uma referência / uma prova direta.

Crossposted on MO

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

m = \sqrt{n}

$m = \sqrt{n}$ , o número máximo de diferenças diferentes que você pode obter é

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

$m(m-1)/2 < n/2$ . Então você realmente precisa que

m

$m$ cresça mais rápido que

\sqrt{n}

$\sqrt{n}$ para que isso seja verdade. O que eu gostaria de fazer é tentar calcular a probabilidade de que um número

d

$d$ é não uma diferença

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

$d = |a_i - a_j|$ .

Peter Shor

@Hor: obrigado, atualizei a pergunta. E, de fato, como

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

$\mathbb E(\sum x_i)=\sum \mathbb E(x_i)$ , é mais fácil calcular uma diferença específica

d

$d$ .

Zhu Cao

@ZhuCao, quando você diz "escolha

m

$m$ números inteiros

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

$a_1,...,a_m$ aleatoriamente entre

[1, n]

$[1,n]$ ", que distribuição você quer dizer exatamente? Eu estava assumindo seu uniforme

{1, \dots, n}

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

usul

@ Andras não, não é o caso. Por exemplo, se o número

1

$1$ não for escolhido (o que acontece com a probabilidade limitada a 0), a diferença

n - 1

$n-1$ não pode aparecer e

D_{n} < n

$D_n<n$ . Mas por que precisa ser o caso? A questão pede apenas que a expectativa de

D_{n} / n

$D_n/n$ se aproxime de 1, não que

D_{n}

$D_n$ seja igual a 1 com alta probabilidade.

James Martin

Não faça postagens cruzadas em vários sites do Stack Exchange. Nossa política de site proíbe a publicação simultânea: diz, no mínimo, esperar uma semana. E se você não obtiver uma boa resposta, sempre poderá sinalizá-la para atenção do moderador e solicitar que ela seja migrada.

Respostas:

Suponha que $m=\omega(\sqrt{n})$ .

Corrija qualquer . Vamos considerar com . O objetivo é mostrar que, com alta probabilidade de , está incluído no conjunto de diferenças. $\epsilon>0$ $r\in[1,n]$ $r<(1-\epsilon)n$ $n\to\infty$ $r$

Primeiro, considere o conjunto . O número de com tal que é binomial com expectativa em torno de . Portanto, com alta probabilidade de , o número de será pelo menos , que é . Então (reivindique "deixado como exercício", não é difícil de mostrar) com alta probabilidade de , o conjunto tem tamanho pelo menos . Vamos escrever para esse "bom evento", que . $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}$

Suponha que de fato seja válido, ou seja, haja pelo menos valores distintos de menores que , para . Observe que, para cada um desses valores, existe um valor que é precisamente maior. Agora considere os valores de para . Estes são independentes e cada uma tem pelo menos probabilidade de estar a uma distância a partir de um elemento do conjunto . A probabilidade de que nenhuma diferença seja produzida é, no máximo $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}$ que vai para 0 como desde que . Portanto, de fato, a probabilidade que possui, mas não existe diferença de tamanho tende a 0 como . $n\to\infty$ $m=\omega(\sqrt{n})$ $G$ $r$ $n\to\infty$

Então (uniformemente em ) a probabilidade de que seja incluído no conjunto de diferenças tende a 1 como . Portanto, usando linearidade de expectativa, Como é arbitrário, o limite é 1, conforme desejado. $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
fonte

Você está tratando cada diferença como independente na expressão e, nesse caso, é justificada?

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

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

usul

@ James Oh, agora eu vejo onde eu perdi isso . Obrigado.

n

$n$

Daniel Soltész

@usul: de fato, desculpas, meu argumento foi desleixado e incompleto. Eu a expandi - acho que agora retém água.

James Martin