Cardinal d'un ensemble aléatoire

On a $R_n=|\{X_1,\dots,X_n\}\cap\{0,\dots, a-1\}|+|\{X_1,\dots,X_n\}\cap [a,+\infty\}|\le a+|\{X_1,\dots,X_n\}\cap [a,+\infty[|$.

Bonsoir,
C'est un bon morceau d'analyse.

$\forall k \in \N ,\:\:\:\forall n \in \N^*, \:\:Y_{k,n} := \left\{ \begin {array} {cl}1&\text{si}\: \displaystyle \bigcup_{i=1}^n[X_i=k].\\0&\text{sinon }.\end{array}\right.\quad p_k:= \Pr[X_1=k].\:\:$ Alors: $\quad\ R_n =\displaystyle \sum_{k=0}^{+\infty} Y_{k,n}\:, \quad \mathbb E(R_n) = \sum _{k=0}^{+\infty}\Big(1-(1-p_k)^n\Big) .$
Soit $a\in \N^*.\quad \mathbb E(R_{n+1}) -\mathbb E(R_{n})=\displaystyle \sum _{k=0}^{+\infty}p_k(1-p_k)^n=\displaystyle \sum _{k=0}^{a-1}p_k(1-p_k)^n+\displaystyle \sum _{k=a}^{+\infty}p_k(1-p_k)^n\leqslant \dfrac an +\displaystyle \sum _{k=a}^{+\infty}p_k\leqslant \dfrac an+ \displaystyle \sum _{k=a}^{+\infty}\dfrac { kp_k}a .$
(on a utilisé le maximum de $x\mapsto x(1-x)^n$ sur $[0;1])\quad$ Soit $ \varepsilon >0. \:\:\exists A\in \N$ tel que $\forall a>A,\:\: \displaystyle \sum_ {k=a}^{+\infty} kp_k <\varepsilon.\:\:$Alors:
$\mathbb E(R_{n+1}) -\mathbb E(R_{n})\leqslant \dfrac an + \dfrac {\varepsilon} a. \quad\forall n >\big\lfloor \dfrac {A^2}{\varepsilon}\big \rfloor +1=B,
\quad \:\:\sqrt{\varepsilon n}>A,\:\:$ donc l'inégalité précédente s'applique à $a =\sqrt{\varepsilon n}:$
$ \forall n >B,\quad \mathbb E(R_{n+1}) -\mathbb E(R_{n})\leqslant 2\sqrt{\dfrac {\varepsilon}n},\:\: \quad\mathbb E(R_{n}) -\mathbb E(R_{B}) <\displaystyle\sum _{k=1}^n 2\sqrt{\dfrac {\varepsilon}k }< 4\sqrt {\varepsilon n},\quad \mathbb E(R_{n})< \Big(\dfrac{\mathbb E(R_{B})}{\sqrt n} + 4\sqrt {\varepsilon }\Big) \sqrt n.$
$$\boxed { \mathbb E(R_n) = o(\sqrt n)}$$

A partir de l'inégalité : $\displaystyle \mathbb{E}[R_{n}]\leq a+n\mathbb{P}(X_{1}\geq a),$ on peut appliquer l'inégalité de Markov pour avoir : $\displaystyle \mathbb{E}[R_{n}]\leq a+ \frac{n\mathbb{E}[X_{1}\mathrm{1}_{X_{1}\geq a}]}{a}.$
La quantité $\displaystyle \mathbb{E}[X_{1}\mathrm{1}_{X_{1}\geq a}]$ tend vers $0$ lorsque $a$ tend vers $+\infty.$
Ainsi pour $a\gg 1,$ on a : $\displaystyle \mathbb{E}[R_{n}]\leq a+ \frac{n \varepsilon}{a}.$
En optimisant l'inégalité en $a$ (en choisissant $a\approx \sqrt{\varepsilon n}$), on obtient effectivement : $\displaystyle \mathbb{E}[R_{n}]=o(\sqrt{n}).$

Bonjour,
C'est très malin d'appliquer l'inégalité de Markov à $X_1{\bf 1}_{X_1> a}$, bravo BobbyJoe. C'est une astuce à retenir. (:D

Bonjour,

Je n'ai pas compris en quoi l'argument d'Aléa permettait de conclure pour le deuxième membre.

Suis-je passé à côté de quelque chose d'évident?

Avec une inégalité (les $X_k$ ne sont pas distincts a priori), ça me va : $$

\Big| \{X_1,\ldots,X_n\} \cap [a,+\infty[ \Big| \leq \sum_{k=1}^{n} \mathbf{1}_{X_k\geq a}.

$$ Merci pour le déblocage.