Annuler
connectez vous
probabilités en post-bac
- Un best-of d'exos de probabilités (après le bac)
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Espaces vectoriels et Applications linéaires - supérieur
- Décomposition des matrices en blocs, exponentielle de matrices - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre ProbabilitésTopics traitant de probabilités [tout]Lister tous les topics de mathématiques
Niveau autre
Nombre moyen de tirages et loi uniforme
Posté par cepamoi
Bonjour.
Je suis confronté à un problème qui me dépasse un peu. Voici le détail :
On tire (avec remise) des nombres compris entre 1 et N selon une loi uniforme et on s'arrête quand on a tiré tous les nombres possibles de 1 à N. Combien en moyenne faut-il de tirages pour tirer tous les nombres ?
Exemple avec N = 5 :
On tire 2, 4, 5, 5, 3, 2, 4, 1. On a donc bien tiré tous les nombre de 1 à 5, et il a fallu 8 tirages. Mais combien en faut-il en moyenne ?
J'ai pu montrer qu'avec N = 2, la réponse est 3 tirages (j'espère que je ne me suis pas trompé), mais je n'ai pas pu le généraliser. J'ai fait un petit programme pour estimer les résultats pour N variant de 2 à 100. Par exemple, pour N = 10, le résultat est environ 29.4, et pour 50 le résultat est environ 223.8.
Comment calculer la formule analytique pour tout N ?
Merci d'avance pour vos réponses.
Bonsoir cepamoi
Notons X la variable aléatoire indiquant le nombre de tirages nécessaires pour tirer tous les entiers de 1 à N, alors X est à valeurs dans l'ensemble des entiers supérieurs ou égaux à N. Par ailleurs, le problème revient alors à calculer l'espérance de X.
Or on a
.
Il "suffit" donc de calculer pour tout entier k supérieur ou égal à N.
Kaiser
Merci pour la formulation du problème. C'est en effet de cette manière que j'ai réussi à calculer le résultat pour N = 2. Dans ce cas, , et le calcul de la somme est relativement simple.
Malheureusement je n'ai pas réussi à généraliser l'expression de pour N > 2.
Merci pour votre aide.
Bonjour cepamoi
Comme les tirages se font avec une loi uniforme, alors il "suffit" de dénombrer tous les cas possibles.
Considérons un entier k supérieur ou égal à N.
Lorsque X=k, cela est équivalent au fait qu'au kème tirage, on a obtenu un entier différent des (k-1) premiers tirages et que, au cours de ceux-ci, les N-1 autres entiers sont tous apparus au moins une fois.
Pour le kème tirage, il y a N possibilités.
Ensuite, il faut choisir la place des N-1 autres entiers.
IL y a donc (k-1) places possibles pour le premier, (k-2) places pour le deuxème ........ et (k-N+1) places pour le N-1 ème.
Enfin, il reste à choisir l'issue des k-N tirages restant soit possibilités.
Par ailleurs, il y a suites de k tirages possibles.
Finalement, si je ne me suis pas trompé, on obtient que :
Reste à faire le calcul de la somme.
Kaiser
Bonjour Kaiser.
Merci pour votre réponse. J'ai fait un programme afin d'essayer la formule de la probabilité, mais elle ne semble pas correcte. En tout cas, avec N=2, on ne retombe pas sur qui me semble correct. Pourtant, je n'arrive pas à voir ce qui est faux dans votre raisonnement. J'ai l'impression que ce sont les
suites de k tirages possibles. Par exemple pour N=2 et k=3, il n'y a que deux tirages possible (1,1,2) et (2,2,1) dont la probabilité est 1/8.
X > k signifie que dans les k premiers tirages on n'a pas eu tous les nombres de 1 à N.
N possibilités pour le nombre qu'on n'a pas eu, et alors (N-1)k tirages possibles.
D'où :
mais quelque chose m'ennuie pour k=0 ou k=1...
Une piste :
On note le nombre de chiffres différents qu'on a rencontrés lors des
premiers tirages (
).
Alors . Si on trouve la loi de
on a alors celle de
.
bonjour,je reprends les dernières notations de kaiser
pour i
2
(yk+1=i)=(yk=i
le k+1ième tirage donne un nombre déjà sorti)
(yk=i-1
on tire au k+1ième tirage un nombre non encore sorti)
en passant aux probabilités
p(yk+1=i)=p(yk=i)(i/N)+p(yk=i-1)(N-i+1)/N
on vérifie que la formule est encore vraie pour i=0 et i=1
aprés quelques calculs un peu laborieux on trouve
E(yk+1)=1+(1-1/N)E(yk)suite arithméticogéométrique et finalement E(yk=N(1-((N-1)/N)k).
sauf erreur de calcul ou de frappe
il y a déjà eu un exercice de ce genre avant les vacances(problème de la collectionneuse)je crois que c'est nicolas qui avait travaillé sur ce topic
j'ai calculé l'espérance du nombre de numéros différents sortis en k
tirages ce n'est pas exactement ce que l'on demande
Bonjour veleda. Je ne trouve pas le topic sur le "problème de la collectionneuse". Mais apparemment tu dis qu'on n'y trouvera pas la loi de Y.
La solution du problème de cepamoi est certainement connue. Et aussi sans doute une réponse "statistique" du genre : si on fait tant de tirages, on a 95% de chances d'avoir visité tous les chiffres.
bonsoir
ce n'est pas le titre du topic c'est moi qui utilisait ce titre quand je faisais cet exo en classe mais la démonstration est fastidieuse,je crois que nicolas avait proposé 3 methodes dont la mienne et deux autres c'était peut ^tre dans une énigme .
avec la formule donnant l'espérance on peut chercher k pour que par exemple E(yk)=N à 10-3prés
bonsoir
ce n'était pas une énigme mais uneJFF 'Toto collectonne les régions' elle est du mois de juin je crois ,je n'ai pas encore eu le courage de refaire la démonstration. bons calculs!