Discuter:Tirage (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Mathématiques
 Tirage (mathématiques) fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
À évaluer Cet article a été classé comme d'Avancement ? selon le Tableau d'évaluation du projet. (Voir les statistiques)
À évaluer Cet article a été classé comme d'Importance ? selon le Tableau d'évaluation du projet.

[modifier] 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}}{(\frac{i}{m})^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}{(\frac{i}{m}})^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}{(\frac{i}{m}})^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}{(\frac{m-i}{m}})^n}

Soit ui le terme général en valeur absolue de cette somme:

u_i={m \choose i}{(\frac{m-i}{m}})^n

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

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

Que fait donc ui ? Il décroît: En effet, la fonction f:i\mapsto\frac{m-i}{i+1}\cdot ({\frac{m-i-1}{m-i}})^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(1-\frac{1}{m})}

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

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

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

En plus, u0 = 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) ||