Discussion:Tirage (mathématiques)

Démonstration de la formule des tirages avec remise

Soit l'énoncé : "Une urne contient 3000 boules numérotées de 1 à 3000. On effectue des tirages indépendants (avec remise), et à chaque tirage on note le numéro de la boule extraite. Combien faut-il effectuer de tirages (au minimum) pour avoir la quasi-certitude (Probabilité > 0,99) d'avoir tiré au moins une fois chaque boule ?"

Pour une urne contenant m boules, la probabilité d'avoir tiré k boules différentes au cours de n tirages successifs avec remise est de :

${m \choose k}\sum _{i=0}^{k}{(-1)^{k-i}{k \choose i}}{\left({\frac {i}{m}}\right)^{n}}$

La recherche a nécessité plusieurs conjectures successives après avoir évalué la probabilité dans des cas particuliers (en fixant certaines variables notamment et en observant les relations entre les différents termes des suites construites) et donc plusieurs dizaines de pages de brouillon. Pour vérifier la véracité de cette formule pour tout k, pour tout n et pour tout m, il suffit de considérer la variable aléatoire Xn qui compte le nombre de boules différentes tirées en n tirages. Si l'on nomme k ce nombre de boules, on peut considérer la suite Vn,k définie pour tout k et pour tout n par Vn,k = p([Xn = k]). Cherchons alors une relation de récurrence sur n dans laquelle nous pourrons injecter la formule ci-dessus.

[Xn-1 = k] et [Xn-1 = k-1] forment un système complet d'évènements non négligeables (au n-1 ième tirage, ou les k boules différentes sont déjà tirées ou elles ne le sont pas). D'après la formule des probabilités totales, on peut donc écrire :

p([Xn = k]) = p([Xn-1 = k]) x p([Xn = k] | [Xn-1 = k]) + p([Xn-1 = k-1]) x p([Xn = k] | [Xn-1 = k-1]).

Or, p([Xn = k] | [Xn-1 = k]) = p(Tirer une des k boules différentes déjà tirées au n-1 ième tirage) = k/m. Donc d'après la notation en suite :

Vn,k = Vn-1,k x (k/m) + Vn-1,k-1 x ((m-(k-1))/m)

Il ne reste plus qu'à injecter la formule générale dans cette relation de récurrence (en fixant k et m naturellement) pour la vérifier (environ 1 page de calcul). Ensuite, il s'agit de l'appliquer dans les conditions susdites, c'est-à-dire pour k=3000 et m=3000. On peut alors utiliser la formule suivante, issue de la première mais au cas particulier où m=k :

$\sum _{i=0}^{m}{(-1)^{m-i}{m \choose i}\left({\frac {i}{m}}\right)^{n}}$

On souhaite alors déterminer n tel que p([Xn = 3000) > 0,99. Pour résoudre cette inéquation sans utiliser un supercalculateur, on peut chercher des approximations fiables (i.e. dont la marge d'erreur est connue) de l'expression de p([Xn = k) pour k=3000. On trouve alors : n=37814. Voici le détail de ce dernier calcul (afin de pouvoir le réaliser avec d'autres valeurs) :

"Partons de notre formule générale : $v_{n,m}=\sum _{i=0}^{m}{(-1)^{m-i}{m \choose i}\left({\frac {i}{m}}\right)^{n}}$

Avec un changement de variables i en k-i (k=m), on obtient :

$v_{n,m}=\sum _{i=0}^{m}{(-1)^{i}{m \choose i}\left({\frac {m-i}{m}}\right)^{n}}$

Soit $u_{i}$ le terme général en valeur absolue de cette somme:

$u_{i}={m \choose i}\left({\frac {m-i}{m}}\right)^{n}$

Comme ${m \choose {i+1}}={m \choose i}{\frac {m-i}{i+1}}$, on obtient :

$u_{i+1}=u_{i}\cdot \left({\frac {m-i}{i+1}}\cdot \left({\frac {m-i-1}{m-i}}\right)^{n}\right)$

Que fait donc $u_{i}$ ? Il décroît: En effet, la fonction $f:i\mapsto {\frac {m-i}{i+1}}\cdot \left({\frac {m-i-1}{m-i}}\right)^{n}$ est positive et décroissante (un produit de fonctions positives décroissantes est décroissante). De plus, cette fonction évaluée en i=0 donne :

f(0)=$m(1-{\frac {1}{m}})^{n}=m\cdot e^{n\cdot ln\left(1-{\frac {1}{m}}\right)}$

comme $ln(1+x)<x$ pour $x\neq 0$, cela donne:

$f(0)<m\cdot e^{\frac {-n}{m}}<1$ pour ${\frac {-n}{m}}<ln\left({\frac {1}{m}}\right)$ donc $n>m\cdot ln(m)$

Donc pour $n>m\cdot ln(m)$, on obtient $u_{i+1}=u_{i}\cdot f(i)\leq u_{i}\cdot f(0)\leq u_{i}$

En plus, $u_{0}=1$

Donc pour $n>m\cdot ln(m)$, le terme de la série décroît en valeur absolue. Comme il alterne, on peut le cerner rapidement (théorème spécial des suites alternées). En effet et par exemple, la suite 1-1/2+1/3-1/4... converge et donc la somme fait un certain réel r.

On a alors r<1, r>1-1/2, r<1-1/2+1/3 etc.

Il se trouve que pour n encore plus grand (de l'ordre de 10 fois m), la convergence est extrêmement rapide, on a à peu près $u_{i+1}=u_{i}\cdot 10^{-5}$, les termes suivants sont ainsi très rapidement négligeables.

Cela permet donc de déterminer très rapidement si la probabilité pour n est supérieure à 0.99 ou pas. Ensuite, pour trouver le n limite, il faut rechercher le bon nombre (trop grand, essayons plus bas; trop petit, remontons d'un peu moins, etc...).

Enfin, on prend les 4 premiers termes (le dernier doit être de l'ordre de 10^(-15) qui devient vraiment négligeable) et on voit que l'on peut être sûr qu'il s'agit de 37814, grâce à ce qui a été expliqué avant (le réel inférieur à 1, mais supérieur à 1-1/2, mais inférieur à 1-1/2+1/3, etc.), car la probabilité pour 37814 est supérieure à 0.9900021 et celle pour 37813 est inférieure à 0.98999971."

|| Mayerwin et Meak le 12 avril 2006 à 16:53 (CEST) ||

• Retour à la page Tirage (mathématiques)

"Vous avez une urne avec 19 boules blanches et une boule noire. Si vous faites une suite de tirages avec remise, il vous faut en moyenne tirer 20 fois avant que vous ne tiriez la boule noire. Pour un tirage sans remise, cette moyenne est de 10.5 tirages. On peut donc écrire:Si vous faites une suite de tirages sans remise, il vous faut en moyenne tirer 10.5 fois avant que vous ne tiriez la boule noire.Etes-vous sûr?

Concernant la démonstration de la formule des tirages avec remise

En réfléchissant à la méthode précédente je me demande s'il n'est pas possible de simplifier certaines parties. Je propose ceci et le soumet à vos commentaires:

Premièrement, sur les 3000 boules, quelle est la probabilité de tirer un 3 par exemple.

Ceci nous donne ${\frac {1}{3000}}$

La probabilité de ne pas tirer un 3 au premiers coup est de ${\frac {2999}{3000}}$

Pour n tirages avec remise, la probabilité de ne pas avoir cette boule diminue: $({\frac {2999}{3000}})^{n}$

Donc la probabilité d'avoir cette boule augmente: $1-({\frac {2999}{3000}})^{n}$

Maintenant (c'est ici que je ne suis pas sûr), il s'agit d'appliquer ce principe aux 3000 boules, je propose:

$(1-({\frac {2999}{3000}})^{n})^{3000}$

Pour $n=37813$, on obtient $(1-({\frac {2999}{3000}})^{37813})^{3000}\approx 0.989999164705$

Pour $n=37814$, on obtient $(1-({\frac {2999}{3000}})^{37814})^{3000}\approx 0.990002481603$

Maintenant pour en revenir à l'exemple de l'article:

Pour $n=1985$, on obtient $(1-({\frac {200}{201}})^{1985})^{201}\approx 0.98996801706$

Pour $n=1986$, on obtient $(1-({\frac {200}{201}})^{1986})^{201}\approx 0.990017678716$

--NHLKHS (discuter) 23 mai 2014 à 18:14 (CEST)NHLKHS