Número de diferencias distintas de enteros elegidos entre

Encontré el siguiente resultado durante mi investigación.

$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$ donde $m=\omega(\sqrt n)$ y $a_1,\cdots,a_m$ se eligen al azar de $[n]$ .

Estoy buscando una referencia / una prueba directa.

Crossposted en MO

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

m = \sqrt{n}

$m = \sqrt{n}$ , el número máximo de diferencias diferentes que puede obtener es

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

$m(m-1)/2 < n/2$ . Entonces realmente necesita que

m

$m$ crezca más rápido que

\sqrt{n}

$\sqrt{n}$ para que esto sea cierto. Lo que yo haría es tratar de calcular la probabilidad de que un número

d

$d$ es no una diferencia

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

$d = |a_i - a_j|$ .

Peter Shor

@Shor: gracias, actualicé la pregunta. Y de hecho, dado que

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

$\mathbb E(\sum x_i)=\sum \mathbb E(x_i)$ , es más fácil calcular una diferencia específica

d

$d$ .

Zhu Cao

@ZhuCao, cuando dices "elige

m

$m$ enteros

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

$a_1,...,a_m$ al azar de

[1, n]

$[1,n]$ ", ¿a qué distribución te refieres exactamente? Estaba asumiendo iid uniform

{1, \dots, n}

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

usul

@Andras no, no es el caso. Por ejemplo, si no se elige el número

1

$1$ (lo que ocurre con la probabilidad limitada desde 0), entonces la diferencia

n - 1

$n-1$ no puede aparecer, y

D_{n} < n

$D_n<n$ . Pero, ¿por qué tiene que ser así? La pregunta solo pide que la expectativa de

D_{n} / n

$D_n/n$ se acerque a 1, no que

D_{n}

$D_n$ sea igual a 1 con alta probabilidad.

James Martin

No publique en varios sitios de Stack Exchange. La política de nuestro sitio prohíbe la publicación cruzada simultánea: dice, como mínimo, esperar una semana. Y si no obtiene una buena respuesta, siempre puede marcarlo para que el moderador le pida que migre.

Respuestas:

Suponga como dado que . $m=\omega(\sqrt{n})$

Arregle cualquier . Consideraremos con . El objetivo es mostrar que con alta probabilidad como , se incluye en el conjunto de diferencias. $\epsilon>0$ $r\in[1,n]$ $r<(1-\epsilon)n$ $n\to\infty$ $r$

Primero considere el conjunto . El número de con tal que es binomial con expectativa alrededor de . Entonces, con alta probabilidad como , el número de tales será al menos , que es . Luego (reclamo, "dejado como ejercicio", no es difícil de mostrar) con alta probabilidad como , el conjunto tiene un tamaño de al menos . Escribamos para este "buen 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}$

Supongamos que de hecho cumple, es decir, que hay al menos valores distintos de menores que , para . Tenga en cuenta que para cada valor, hay un valor que es precisamente más grande. Ahora considere los valores de para . Estos son independientes y cada uno tiene probabilidad al menos de ser a una distancia de un elemento del conjunto . La probabilidad de que no se produzca ninguna diferencia es, como 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 va a 0 como ya que . De hecho, la probabilidad de que mantenga pero no exista una diferencia de tamaño tiende a 0 como . $n\to\infty$ $m=\omega(\sqrt{n})$ $G$ $r$ $n\to\infty$

Entonces (uniformemente en ) la probabilidad de que se incluya en el conjunto de diferencias tiende a 1 como . Por lo tanto, utilizando la linealidad de la expectativa, Como es arbitrario, el límite es 1 según lo deseado. $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
fuente

¿Está tratando cada diferencia como independiente en la expresión , y si es así, ¿está justificada?

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

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

usul

@ James Oh, ahora veo dónde me perdí eso . Gracias.

n

$n$

Daniel Soltész

@usul: de hecho, disculpas, mi argumento fue descuidado e incompleto. Lo he expandido, creo que contiene agua ahora.

James Martin