QDV 19: le printemps est revenu!

La méthode de l'EDO "moyenne" est un outil usuel dans l'analyse des algorithmes d'approximation stochastique (cf ici). Je ne crois pas que les outils développés là-bas s'appliquent tels quels ici, mais il faut voir.

Continuons. Comme $X\leqslant n$, il suffit de montrer les deux assertions suivantes :

(1) Pour tout $\epsilon>0$, $\mathbb{P}[\max\{X_1,\ldots,X_{3n}\}\geqslant n\big(\frac{1}{e}+\epsilon\big)]$ tend vers 0 ;

(2) Pour tout $\epsilon>0$, $\mathbb{P}[\sup\{X_k\mid k\geqslant 3n \}\geqslant n\big(\frac{1}{e}+\epsilon\big)]$ tend vers 0.

Pour $j\ne\ell$, on a
$$\mathbb{E}[X_{k,j}X_{k,\ell}]=\mathbb{P}[X_{k,j}=1,\;X_{k,\ell}=1]=\frac{k(k-1)}{n^2}\Big(1-\frac{2}{n}\Big)^{k-2}.$$

On en déduit que
$$\mathbb{V}(X_k)=n\frac{k}{n}\Big( 1-\frac{1}{n}\Big)^{k-1}+n(n-1)\frac{k(k-1)}{n^2}\Big(1-\frac{2}{n}\Big)^{k-2}-n^2\frac{k^2}{n^2}\Big(1-\frac{1}{n}\Big)^{2k-2}.$$

Il n'est pas difficile de montrer que le membre de droite est un $o(n^2)$. Ici, les $o$ sont "uniformes", c'est-à-dire que $o(f(n))$ est majoré en valeur absolue par $\epsilon(n)f(n)$ pour une fonction "universelle" $\epsilon(n)$, ne dépendant pas de $k$, tendant vers 0 à l'infini. En l'occurrence on pourrait montrer que $\mathbb{V}(X_k)\leqslant 100 n$ pour tout $n\geqslant 2$.

L'inégalité du bien-aimé Tchebycheff, ainsi que le fait que $\mathbb{E}[X_k]\leqslant \dfrac{n}{e}+o(n)$, entraîne alors que pour tout $k$ et pour tout $\epsilon>0$, l'expression $\mathbb{P}[X_k \geqslant n\Big(\frac{1}{e}+\epsilon\Big)]$ tend vers 0.

Fixons $\epsilon>0$. Choisissons un entier $r\geqslant \frac{6}{\epsilon}$. Pour tout $n$, il existe des entiers $k_1\leqslant k_2\leqslant\cdots\leqslant k_r$ tels que pour tout entier $k\in [ 1, 3n]$, $\exists j$, $|k-k_j|\leqslant \dfrac{6n}{r}\leqslant \epsilon n$. Comme $|X_k-X_{k_j}|\leqslant \epsilon n$, on a
\begin{eqnarray*}
\mathbb{P}[\max\{X_1,\ldots,X_{3n}\} \geqslant n\Big(\frac{1}{e}+2\epsilon\Big)]
&\leqslant& \mathbb{P}[\max\{X_{k_1},\ldots,X_{k_r}\} \geqslant n\Big(\frac{1}{e}+\epsilon\Big)]\\
&\leqslant&\sum_{j=1}^r \mathbb{P}[X_{k_j} \geqslant n\Big(\frac{1}{e}+\epsilon\Big)]
\end{eqnarray*}

tend vers 0. Ceci montre l'assertion (1).

La preuve de l'assertion (2) doit être du même acabit mais j'ai eu la flemme de faire tous les calculs. On montre que quand $n$ tend vers l'infini, la probabilité qu'au temps $k=3n$ il y ait au plus $\dfrac{n}{e}$ urnes contenant au plus une boule est proche de 1. Or, à tout instant $\ell\geqslant k$, il y a moins d'urnes contenant exactement une boule que d'urnes contenant au plus une boule à l'instant $k$, ce qui montre que la probabilité que $\sup\{X_k\mid k\geqslant 3n\}\geqslant n\Big(\dfrac{1}{e}+\epsilon\Big)$ tend vers 0.

Sinon, cette page

http://en.wikipedia.org/wiki/Names_of_large_numbers

mentionne le quingentilliard ($10^{3003}$).

Principe de Maurey:

http://fr.wikipedia.org/wiki/Inégalité_d'Azuma#Principe_de_Maurey

(si je mettais dans le même message, ça buggait)

Merci aléa, j'ai bien fait de ne pas terminer tous mes calculs vu la concision de ta démonstration. Quelques éclaircissements pour les lecteurs qui, comme moi, ne manipulent pas fréquemment les probabilités :

1. $Z_1$ est le premier temps où une boule tombe dans l'urne no. 1, $Z_1+Z_2$ est le deuxième temps où une boule tombe dans l'urne no. 1. Donc $P(Z_1+Z_2>n^{3/2})$ est la probabilité qu'à l'instant $n^{3/2}$ il y a au plus une boule dans l'urne no. 1. Et donc $nP(Z_1+Z_2>n^{3/2})$ majore la probabilité qu'à l'instant $n^{3/2}$ il existe une urne contenant au plus une boule.

2. Le principe de Maurey est appliqué à $A=\{1,\ldots,n\}$, $B=\{1,\ldots,k\}$, $B_t=\{1,\ldots,t\}$, $\lambda=\epsilon n$ et à la variable aléatoire $X_k$. L'espace de probabilité $\Omega$ est l'ensemble des lancers de $k$ boules dans $n$ urnes. Le fait que $X_k$ est $\mathcal{B}$-Lipschitzienne signifie que si on modifie juste un des lancers à un instant $t$, le nombre final d'urnes contenant exactement une boule varie d'au plus une unité.

Edit: ce qui suit est FAUX.

Pour des pilules de taille $2^{-m}$, c'est $K=e^{-m}$.

Ici on regarde l'espérance du nombre d'urnes contenant exactement $m$ boules, qui vaut
$$n\times\frac{k(k-1)\cdots (k-m+1)}{n^m}\Big(1-\frac{m}{n}\Big)^{k-m}$$
qui vaut environ $n(xe^{-x})^m$ où $x=\dfrac{k}{n}$. Ceci est maximum lorsque $x=1$, et l'espérance vaut alors $ne^{-m}$.

Oups, oui j'avais oublié de diviser par $m!$ (qui vient du fait que l'on peut permuter les boules dans une urne qui en contient $m$) et en plus j'avais confondu urne et boule en écrivant le dernier terme...

Bref, $K=\dfrac{m^me^{-m}}{m!}$.

Je devrais arrêter d'économiser sur les pilules...

Bonjour les (tu) superchampions (tu) ,

Question 4 :

Oui aléa, c'est dans le Beautiful Mathematics de Martin Erickson que j'ai trouvé l'énoncé : j'ai juste modifié un peu la fin pour adapter l'exercice au niveau des intervenants

J'ai traduit avec ton aide, merci infiniment,

" ... show than the expected maximum number oh half pills in the bottle tends to $\dfrac{n}{e}$ as $n$ tends to infinity."
par

"...montrer que l'espérance du nombre maximal de demi-pilules présentes dans la boîte est équivalent à $Kn$ quand $n$ tend vers l'infini, $K$ étant à déterminer."

Amicalement.

Bonjour,

Question 1bis : recherche d'une équation paramétrique du cercle passant par les points $(1,0,0), (0,1,0),(0,0,1)$.

egoroffski, je suppose que ta réponse proposée ici est exacte, voilà la courbe obtenue avec le "spacecurve" de Maple. Lorsque je tente de calculer pour quelles valeurs du paramètre $t$ la courbe passe par les trois points mentionnés, les calculs sont délicats, même avec Maple.

Qu'as-tu choisi pour $v, w$ ? Merci.

Bon décidément je ne sais plus calculer... :-(:-(:-(

Je n'ai plus mon brouillon, mais de mémoire j'ai pris $v=a(1,-1,0)$ et $w=b(1,1,-2)$ pour $a,b$ bien choisis (du moins je le pensais).

PS : Ah tiens, en l'écrivant, j'ai trouvé mon erreur : j'ai semble-t-il conclu un peu rapidement que $1^2+1^2+(-2)^2=5$ (td) du coup en multipliant tous les sinus par $\sqrt{5/6}$ dans ma réponse erronée, on retombe sur celle de JLT.

Bonjour,

Question 4 : "... montrer que l'espérance du nombre maximal de demi-pilules présentes dans la boîte est équivalent à $\dfrac{n}{e}$ quand $n$ tend vers l'infini".

Par ailleurs, si $S_n$ est l'ensemble des permutations de l'ensemble $[1,n]$, alors le nombre $d_n$ de dérangements [permutations sans point fixe] tend vers $\dfrac{n!}{e}$ quand $n$ tend vers l'infini.

Connaissez-vous d'autres exercices de ce genre dans lequel apparaît également le nombre $e$ ?

Référence : Toutes les questions proposées ici proviennent d'un joli cadeau de mon ami Aleg : le Beautiful Mathematics de Martin Erickson.

Ce Beautiful Mathematics avait déjà été source d'inspiration pour l'exercice Comtet 32 lors de la QDV 12 & H 63 (2): Combinatoriennes, ...

Joyeuses Pâques.

Amicalement.