Nombre de différences distinctes de

J'ai rencontré le résultat suivant lors de mes recherches.

$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$ oùetsont choisis au hasard parmi. $m=\omega(\sqrt n)$ $a_1,\cdots,a_m$ $[n]$

Je recherche une référence / une preuve directe.

Crossposted sur MO

reference-request co.combinatorics pr.probability Zhu Cao
la source

m = \sqrt{n}

$m = \sqrt{n}$ , le nombre maximum de différences différentes que vous pouvez obtenir est

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

$m(m-1)/2 < n/2$ . Vous avez donc vraiment besoin de

m

$m$ pour croîtreplus viteque

\sqrt{n}

$\sqrt{n}$ pour que cela soit vrai. Ce que je ferais, c'est essayer de calculer la probabilité qu'un nombre

d

$d$ soitpasune différence

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

$d = |a_i - a_j|$ .

Peter Shor

@Shor: merci, j'ai mis à jour la question. Et en effet puisque

, il est plus facile de calculer une différence spécifique

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

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

d

$d$

Zhu Cao

@ZhuCao, quand vous dites "choisir

entiers

au hasard de

", quelle distribution voulez - vous dire exactement? Je supposais l'uniforme iid

m

$m$

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

$a_1,...,a_m$

[1, n]

$[1,n]$

{1, \dots, n}

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

usul

@Andras non, ce n'est pas le cas. Par exemple, si le nombre

n'est pas choisi (ce qui se produit avec une probabilité bornée à 0) alors la différence

ne peut pas apparaître, et

. Mais pourquoi faut-il que ce soit le cas? La question demande seulement que l'espérance de

se rapproche de 1, pas que

soit égal à 1 avec une probabilité élevée.

1

$1$

n - 1

$n-1$

D_{n} < n

$D_n<n$

D_{n} / n

$D_n/n$

D_{n}

$D_n$

James Martin

Veuillez ne pas effectuer de publication croisée sur plusieurs sites Stack Exchange. Notre politique de site interdit la publication croisée simultanée: il est dit, au minimum, attendez une semaine. Et si vous n'obtenez pas de bonne réponse, vous pouvez toujours la signaler à l'attention du modérateur pour demander sa migration.

Réponses:

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

Fixez tout . Nous considérerons avec . Le but est de montrer qu'avec une forte probabilité , $\epsilon>0$ $r\in[1,n]$ $r<(1-\epsilon)n$ $n\to\infty$ $r$ est inclus dans l'ensemble des différences.

Considérons d'abord l'ensemble . Le nombre de avec de telle sorte que est binomiale de confiance autour . Donc, avec une probabilité élevée comme , le nombre de tels sera au moins $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$ , qui est . Ensuite (affirmation, "laissé comme exercice", pas difficile à montrer) avec une probabilité élevée comme, l'ensemblea une taille au moins $\omega(\sqrt{n})$ $n\to\infty$ $A$ . Écrivonspour ce "bon événement", que $\sqrt{n}$ $G$ . $|A|\geq\sqrt{n}$

Supposons que vrai , c'est-à-dire qu'il y ait au moins $G$ valeurs distinctes deinférieures à, pour. Notez que pour chacune de ces valeurs, il existe une valeurqui est précisémentplus grande. Considérons maintenant les valeurs d'pour. Celles-ci sont indépendantes et chacune a au moins une probabilité $\sqrt{n}$ $a_i$ $\epsilon n$ $i<m/2$ $k\in [1,n]$ $r$ $a_i$ $i\geq m/2$ d'être àdistancepartirun élément de l'ensemble. La probabilité qu'aucune différencesoit produite est alors tout au plus $\sqrt{n}/n=1/\sqrt{n}$ $r$ $A$ $r$ qui passe à 0 commepuisque $(1-1/\sqrt{n})^{m/2}$ $n\to\infty$ . Donc en effet, la probabilité quevraimais qu'il n'y ait pas de différence de tailletend vers 0 car $m=\omega(\sqrt{n})$ $G$ $r$ $n\to\infty$ .

Ainsi (uniformément dans ) la probabilité que soit inclus dans l'ensemble des différences tend vers 1 lorsque . Donc en utilisant la linéarité de l'espérance, $r<(1-\epsilon)n$ $r$ $n\to\infty$ Puisqueest arbitraire, la limite est 1 comme souhaité.

\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
la source

Traitez-vous chaque différence comme indépendante dans l'expression

, et si oui, est-elle justifiée?

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

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

usul

@James Oh, maintenant je vois où j'ai raté ce

. Merci.

n

$n$

Daniel Soltész

@usul: en effet, excuses, mon argument était bâclé et incomplet. Je l'ai élargi - je pense qu'il retient l'eau maintenant.

James Martin