Forum de mathématiques - Bibm@th.net

LoneRetrievr

Membre

Inscription : 08-09-2020

Messages : 2

Probabilité que tous les éléments de l'univers de l'expérience sortent

Bonjour,
J'aimerais avoir de l'aide concernant un problème de probabilité. Voilà "l'énoncé" :
- on considère un univers composé de n éléments, indépendants les uns des autres
- on répète une expérience aléatoire, avec remise et indépendante de la suivante, qui consiste à prendre un élément de l'univers au hasard (donc probabilité de 1/n)
Comment calculer le nombre d'essais (donc le nombre de tirages) nécessaires pour que la probabilité que tous les éléments de l'univers aient été tirés au moins une fois soit supérieure à x (x = 90% par exemple) ?

Mon intuition me dit que cette probabilité est au minimum de (1/n)^n (et encore je ne sais pas vraiment pourquoi), mais mes compétences en probabilités étant assez limitées, je préfère avoir un avis extérieur.

Je voudrais appliquer le résultat à un programme, qui teste au hasard des éléments d'une liste tant qu'un élément correspondant aux conditions fixées n'a pas été trouvé. Je pourrai alors éviter de créer une boucle infinie en définissant cette limite au-delà de laquelle tous les éléments ont probablement été testés, et donc qu'aucun ne convient. Cela permettra d'être presque sûr que tous les éléments ont été testés, tout en ayant l'impact le moins fort possible sur les performances.

Je poste ce message dans cette discussion, même si ce n'est pas à proprement parler un problème qui m'est posé dans mes études, mais je ne sais pas quelle discussion correspond plus.

Merci !

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 049

Re : Probabilité que tous les éléments de l'univers de l'expérience sortent

Bonjour,

  C'est un problème très intéressant et pas si facile. Je vais te donner une réponse pas tout à fait définitive mais qui devrait te suffire. Si j'ai bien compris, on se donne un ensemble à $n$ éléments, une probabilité $p$, et tu cherches le nombre minimum de tirages $k$ pour que la probabilité que tous les éléments sortent lors des $k$ premiers tirages soit égale à $p$.

Je vais noter $A(k)$ l'événement contraire : "il existe un élément qui ne sort pas lors des $k$ premiers tirages",
ainsi que $A(k,j)$ l'événement : "l'élément numéro $j$ ne sort pas lors des $k$ premiers tirages" (pour fixer les idées, j'ai supposé qu'on avait numéroté les éléments de ton ensemble de $1$ à $n$).

On a donc $A(k)=\bigcup_{j=1}^n A(k,j)$. Tu cherches $k$ tel que $P(A(k))\leq 1-p$. Puisque
$$P(A(k))\leq \sum_{j=1}^n P(A(k,j)),$$
il suffit de choisir $k$ tel que $\sum_{j=1}^n P(A(k,j))\leq 1-p$. Par symétrie des éléments, tu as
$$\sum_{j=1}^n P(A(k,j))=nP(A(k,1))$$ et il suffit donc de choisir $k$ tel que
$$P(A(k,1))\leq \frac{1-p}n.$$

Maintenant, c'est relativement facile de calculer $P(A(k,1))$. En effet, en notant $B(\ell)$ l'événement : "l'élément 1 ne sort pas lors du $\ell$-ème tirage", tu as $A(k,1)=\bigcap_{l=1}^k B(\ell)$ et comme les événements $B(\ell)$ sont indépendants, tu peux en déduire que
$$P(A(k,1))=\prod_{l=1}^k P(B(\ell)).$$

Maintenant, on a $P(B(\ell))=\frac{n-1}n$
et donc on cherche $k$ tel que
$$\left(1-\frac 1n\right)^k\leq\frac{1-p}n$$
inéquation que l'on résout en prenant le logarithme et on trouve finalement
$$k\geq\frac{\ln\left(\frac{1-p}n\right)}{\ln\left(1-\frac 1n\right)}.$$

En particulier, si $n$ tend vers $+\infty$, on trouve que $k$ se comporte comme $n\ln n$, ce qui finalement assez peu!

F.

LoneRetrievr

Membre

Inscription : 08-09-2020

Messages : 2

Re : Probabilité que tous les éléments de l'univers de l'expérience sortent

Merci beaucoup pour cette réponse ! Il va me falloir un peu plus de temps pour bien la comprendre, mais je suis certain que ça va m'aider. Merci !