Dénombrement

[fatal_error]

Hello,

Suite à
http://www.maths-forum.com/a-ont-appris-langage-basic-aide-154412.php

Est énoncé que la moyenne de tirages pour avoir 7 nombres différents sur les 10 est d'environ 11.

J'ai essayé de démontrer sans y arriver...
Quelqu'un saurait?

Je suis parti sur calculer la proba d'avoir pioché 7 nombres différents exactement au nieme tirage.
(dans l'optique de comparer les n)

soit n le nombre de tirages qu'il faut pour obtenir les 7 nombres différents.
soit m le nombre de choix lors d'un tirage : m = 10
soit w le nombre de nombres différents piochés : w = 7
je décompose le tirage comme :

Code: Tout sélectionner

[______]*[... ...]|[_]
   S    *    V    * r
   

Dans S j'ai une combi de base=w-1=6 nombres.
Par exemple 012345
dans V, j'ai n'importe quoi du moment que chaque nombre est présent dans S, par exemple 00000 ou bien 00001 si V est de longueur 5)
taille(V) = n-taille(S)-taille(r)
Dans r, c'est le dernier nombre à tirer (qui doit ne pas etre dans S)

Du coup, le but, c'est de mélanger S et V (pour générer toutes les mains possibles satisfaisant la combi 012345)
sauf que...j'y arrive pas.
Si on prend par exemple V0=0, V1=0, alors on va avoir des doublons dans les mains.
On pourrait éventuellement décomposer V de longueur k, en somme d'entiers inférieurs à k, puis dénombrer pour chaque décomposition...mais ca a l'air fastidieux.

Une idée?

[Ben314]

Salut
On tire de façon aléatoire (et indépendante et "avec remise") éléments d'un ensemble en contenant (ici ).
On appelle la variable aléatoire donnant le nombre d'éléments différents tirés (donc, si , est compris entre 1 et min(n,N))

- La loi de est triviale, il est forcément égal à 1 : (et pour tout )

- La loi de connaissant celle de n'est pas super dure à obtenir : pour que ( entier quelconque), il fallait soit que et qu'on ait tiré un nouvel élément (proba ), soit que et qu'on ait tiré un élément déjà tiré (proba ).
Bilan :

Rien qu'avec ça, tu peut avec un tableur faire calculer les loi des pour k entre 1 et une trentaine (dans le cas N=10) et avoir une valeur super précise du nombre de coup moyen qu'il faut pour obtenir 7 chiffres différents (la proba. d'avoir chiffres différents pour la première fois au -ième tirage est évidement )

Sinon, sauf erreur, en utilisant les polynômes générateurs des , c'est à dire les , on doit pouvoir faire un peu plus de théorie...

P.S. Sinon, il y a une façon extrêmement simple de calculer l'espérance des v.a.r. sans même chercher à calculer leur loi, mais je ne pense pas que ce soit suffisant pour en déduire le nombre de coup moyen qu'il faut pour tirer éléments différents...

P.S.2 : si tu cherche à dénombrer le nombre de tirages de n éléments conduisant au total à seulement k éléments différents, tu raisonne comme çi dessus et ça te donne la même formule de récurrence, mais sans les divisions par N.

P.S. 3 : avec un tableur, j'obtiens 10,9563

[fatal_error]

bien vu la récurrence, presque un classique :(
thx

[DamX]

bien vu la récurrence, presque un classique
thx

Bonjour,

en prolongeant le chemin tracé par Ben, on peut en fait obtenir une expression fermée pour le nmbre de tirage moyen E(k,N) permettant d'obtenir k chiffres distincts tirés chacun entre 1 et N :


On a bien E(7,10) = 10.9563 notamment.

Pour la démo, c'est un peu fastidieux mais ça déroule bien. Vous m'excuserez pour ne pas justifier rigoureusement les convergences des séries que je manipule (liées finalement à l'existence de l'espérance du nombre de lancer).

En repartant de l'expression de Ben sur la proba que l'on ait pour la première fois k chiffres tirés au n-ieme tirage noté Q(k,n) (on oublie le N paramètre fixe du problème pour toute la démo) :

c'est à dire en reprenant l'expression :



en ayant juste décalé l'indice n->n+1, et le delta est le dirac qui vaut 1 si k=1, et 0 sinon.

Pour calculer I_k, on le décompose en fait en deux termes que l'on définit ainsi:





Commençons à travailler avec Yk en utilisant la relation de récurrence sur P(Zn=k) :



ce qui donne :

puis en posant ,

en notant que l'on a y_0 = Y_0 = 0

Du coup on a tout simplement y_k = 1 (pour k>=1)
Et donc

Pour X_k, c'est le même cheminement global, je vais donc aller plus vite.

En utilisant la même formule de récurrence, on trouve la relation de récurrence croisée

qui provient du fait que le décalage n->n+1 dans la somme fait apparaitre du X+Y en distribuant le n+1.

En utilisant l'expression de Y_k déjà calculée, on aboutit à :


et on récupère

Et au final en regroupant tout ce petit monde, en faisant juste attention au cas p=1, finalement ça se simplifie et on obtient l'expression mise en introduction :



avec bien entendu E(k,N) non défini pour k>N (impossible de trouver 11 valeurs distinctes dans un semble de 10 éléments ..)

Hélas on ne s'absout pas du tableur pour calculer les termes ... mais on a quand même obtenu une forme analytique simple pour cette moyenne de tirages !

pour N = 10, ça donne par exemple :

k E(k,10)
1 1,0000
2 2,1111
3 3,3611
4 4,7897
5 6,4563
6 8,4563
7 10,9563
8 14,2897
9 19,2897
10 29,2897

Damien

[chan79]

[TEX]

pour N = 10, ça donne par exemple :

k E(k,10)
1 1,0000
2 2,1111
3 3,3611
4 4,7897
5 6,4563
6 8,4563
7 10,9563
8 14,2897
9 19,2897
10 29,2897

Damien

Bravo !!! :++:

[Ben314]

Effectivement très joli :king2:

Après, vu la simplicité étonnante du résultat à laquelle je ne m'attendais pas, ça ne m'étonnerais que moyennement qu'il y ait une autre voie d'approche donnant le résultat plus rapidement.
Il y a quelques temps, j'avais calculé par des méthodes tout aussi compliquées l'espérance des Zn (i.e. le nombre moyen de boules différentes qu'on peut espérer avoir tiré en n tirages avec remise) puis un collègue (probabiliste bien sûr...) m'avait "cassé la baraque" en me signalant que, pour calculer l'espérance de Zn sans se faire c..., il suffisait de dire que Zn était la somme de N Bernoulli X1,X2,...XN correspondant au fait qu'on ait tiré(=1) ou pas(=0) la boule numéro i.
Ces Bernoulli sont évidement de même loi simple à calculer, mais ne sont pas indépendantes..., sauf que ce n'est pas utile pour dire que l'espérance de la somme est la somme des espérances...

Si j'ai du temps (là j'ai des tas de copies "en retard"...) je regarderais s'il y a une astuce (en partant de la forme très spéciale du résultat, on doit pouvoir trouver...)

[Ben314]

Effectivement,
Une fois qu'on a le résultat sous les yeux, tout s'éclaire :

Le truc qu'on cherche, c'est le temps d'attente moyen pour obtenir (pour la première fois) k boules différentes.

Or ce temps est égal au temps nécessaire pour obtenir la première boule (forcément = à 1) plus le temps nécessaire pour en obtenir une deuxième différente, plus le temps nécessaire pour en obtenir une troisième différente... etc...

Or, une fois qu'on a tiré k boules différentes de l'urne, la v.a.r. mesurant le temps qu'il faut attendre pour en tirer une différentes de celles déjà tiré suit (quasi par définition) une loi géométrique de paramètre (=proba de tirer une boule non déjà tirée)

Or, l'espérance d'une loi géométrique de paramètre est et... on en déduit le résultat...

Edit : en fait, en cliquant autour de "loi géométrique" sur Wiki, je suis tombé sur le "Problème du collectionneur de vignette" qui est quasi le même, sauf que l'on s'intéresse uniquement au cas k=N (=on tire toutes les boules)

[DamX]

Effectivement,
Une fois qu'on a le résultat sous les yeux, tout s'éclaire :
[...]
Or, l'espérance d'une loi géométrique de paramètre est et... on en déduit le résultat...

En effet, c'est beaucoup plus joli comme ça , bien joué ! :++:
Comme souvent en proba, il fallait finalement juste tourner le problème autrement !

Mais parfois déboîter une page de calcul bourrin ça soulage :ptdr:

Damien