[proba]Nombre moyen de tirages ?

[zoonel]

Bonjour,
Après quelques recherches sur le net je me décide a poster ici. Mes restes de connaissance en stats/proba ne me sont pas d'un grand secours, j'en appelle donc à vos connaissances certainement bien supérieures .(si vous avez la solution ou un bon site où m'aiguiller n'hésitez pas )

Soit une Urne contenant un certains nombre de billes de différentes couleurs , on notera une bille de couleur . Chaque bille peut être tirée avec la probabilité (c'est un tirage avec remise).
A chaque boule de couleur est associé un nombre .
On tire les billes une a une et on additionne à chaque fois le nombre correspondant jusqu'à obtenir le nombre gagnant .
Question: combien faut-il en moyenne de tirage pour obtenir ce nombre

Un petit exemple si ce n'est pas clair:
On a une urne remplie de billes rouges (), vertes (), et noires(). La probabilité d'obtenir un bille d'une certaine couleur est de :
rouge =
verte =
noire =
Une bille verte rapporte 1 point, une rouge 2 points et une noire 0 points. On tire des billes jusqu'à obtenir 10 points ou plus.
ex de lancers:



On voit qu'on a pu obtenir 10(ou plus) avec respectivement 11, 5, et 13 tirages. Mais combien en moyenne faut il de tirages pour obtenir ce 10 ?

Merci
-----

[Jeanpaul]

Peut-être trop simple mais l'espérance mathématique de chaque tirage est, dans l'exemple : 1/4 . 1 + 1/4 . 2 = 3/4 donc en moyenne au bout de n tirages on aura ramassé 3n/4 points et pour obtenir 10 points il faudra 13 ou 14 tirages en moyenne.
Ou alors y a-t-il un gros piège ?
Ca doit facilement se simuler avec un programme et des nombres aléatoires.

[zoonel]

j'y ai pensé mais si maintenant la boule noire rapporte 20000 points
on aura 1/4 . 1 + 1/4 . 2 + 1/2 . 20000 = 10000,75 et donc 1 tirage en moyenne :s ce qui est impossible
Maintenant je sais pas si on peut simplement prendre au lieu de 20000 le min(10 ; 20000)

[Jeanpaul]

Le raisonnement par moyenne ne vaut que pour des nombres raisonnablement grands. Pour le cas extrême que tu évoques, il vaut mieux s'interroger sur la probabilité de tirer le gros nombre.

[A voir en vidéo sur Futura]

[zoonel]

A première vue ça n'a pas l'air d'être ça:
J'ai fait une simulation avec les paramètres suivants
4 couleurs ->(1,2,3,4)
P₁=3/6 valeur = 1
P₂=1/6 valeur = 2
P₃=1/6 valeur = 3
P₄=1/6 valeur = 4

3/6 * 1 + 1/6 * (2 + 3 +4) = 2

donc au bout de n tirage on aura ramassé 2 points.Ce qui pour arriver à G nous donne G/2 tirages

Problème, pour G=100 ou G=1000 j'ai 50,41... et 500,41...
Maintenant si je baisse G à 20 voir 10 j'ai toujours à peut près le même biais de 0,41 (10,41 ; 5,42). Si je baisse encore jusqu'a 3 j'ai en gros G/2 + 0,4x
(j'ai a chaque fois fais 10M simulations)

[God's Breath]

Le problème dans ton exemple avec la boule noire qui rapporte 20000 points, c'est qu'elle assure le gain : si elle ne rapportait que 10000 points, cela ne changerait rien dans la pratique : dès qu'on la tire, on gagne.
Cette valeur trop importante de la boule noire n'a aucune importance numérique, et le calcul de l'espérance du montant obtenu sur un tirage n'a plus de signification.
Je pense que c'est pour cela que tu proposais de raisonner sur min(10;20000) puisque le résultat serait le même avec une boule à 10 points assurant le gain, mais je ne sais pas si cela peut se justifier du point de vue théorique.

[invited6a8e0a5]

A première vue ça n'a pas l'air d'être ça:
J'ai fait une simulation avec les paramètres suivants
4 couleurs ->(1,2,3,4)
P₁=3/6 valeur = 1
P₂=1/6 valeur = 2
P₃=1/6 valeur = 3
P₄=1/6 valeur = 4

3/6 * 1 + 1/6 * (2 + 3 +4) = 2

donc au bout de n tirage on aura ramassé 2 points.Ce qui pour arriver à G nous donne G/2 tirages

Problème, pour G=100 ou G=1000 j'ai 50,41... et 500,41...
Maintenant si je baisse G à 20 voir 10 j'ai toujours à peut près le même biais de 0,41 (10,41 ; 5,42). Si je baisse encore jusqu'a 3 j'ai en gros G/2 + 0,4x
(j'ai a chaque fois fais 10M simulations)

Bonsoir,

Ton biais est visiblement indépendant de ton G puisque il n’est pas de 0.4x mais de 0.4 tout court.

Théoriquement, avec suffisamment de tirages et G > Vi pour tout i, ton calcul est bon.
Cherche plutôt un bug du côté de ton programme en faisant ta simulation pas à pas et en mettant un espion, c’est comme si il te comptait 0.82 tirage supplémentaire au dénominateur ?

[invité576543]

A première vue ça n'a pas l'air d'être ça:
J'ai fait une simulation avec les paramètres suivants
4 couleurs ->(1,2,3,4)
P₁=3/6 valeur = 1
P₂=1/6 valeur = 2
P₃=1/6 valeur = 3
P₄=1/6 valeur = 4

3/6 * 1 + 1/6 * (2 + 3 +4) = 2

donc au bout de n tirage on aura ramassé 2 points.Ce qui pour arriver à G nous donne G/2 tirages

On peut calculer précisément le nombre moyen de tirages pour atteindre ou dépasser n; notons p(n) ce nombre.

p(0)=0

p(1)=1

p(2) = 1/2 + 1/2(1+p(1)) = 1.5

p(3)= = 1/3 + 1/6(1+p(1)) + 1/2(1+p(2)) = 1.82

p(4) = 1/6 (1+p(0)) + 1/6 (1+p(1)) + 1/6 (1+p(2)) + 1/2(1+p(3)) = 2.33

Plus généralement :

p(n) = 1/6 (1+p(n-4)) + 1/6 (1+p(n-3)) + 1/6 (1+p(n-2)) + 1/2(1+p(n-1))
= 1 + p(n-4)/6 + p(n-3)/6 + p(n-2)/6 +p(n-1)/2

Cela donne déjà une méthode rapide pour calculer p(n) par récurrence.

----

On peut même donner une formule pour p(n) :

Soit q(n) = p(n) - n/2

q(n) = q(n-4)/6 + q(n-3)/6 + q(n-2)/6 +q(n-1)/2

Le polynôme a pour racines :



Comme q(n) est réel, c'est de la forme :



avec s(n) = 0 si n impair, si n pair

a, b et c se calculent à partir des premières valeurs. (A faire...)

Le terme dominant pour n grand est a, qui, j'imagine, vaut 0.41

Cordialement,

[invité576543]

Tite faute :

[invited6a8e0a5]

On peut calculer précisément le nombre moyen de tirages pour atteindre ou dépasser n; notons p(n) ce nombre.

p(0)=0

p(1)=1

p(2) = 1/2 + 1/2(1+p(1)) = 1.5

p(3)= = 1/3 + 1/6(1+p(1)) + 1/2(1+p(2)) = 1.82

p(4) = 1/6 (1+p(0)) + 1/6 (1+p(1)) + 1/6 (1+p(2)) + 1/2(1+p(3)) = 2.33

Plus généralement :

p(n) = 1/6 (1+p(n-4)) + 1/6 (1+p(n-3)) + 1/6 (1+p(n-2)) + 1/2(1+p(n-1))
= 1 + p(n-4)/6 + p(n-3)/6 + p(n-2)/6 +p(n-1)/2

Cela donne déjà une méthode rapide pour calculer p(n) par récurrence.

----

On peut même donner une formule pour p(n) :

Soit q(n) = p(n) - n/2

q(n) = q(n-4)/6 + q(n-3)/6 + q(n-2)/6 +q(n-1)/2

Le polynôme a pour racines :



Comme q(n) est réel, c'est de la forme :



avec s(n) = 0 si n impair, si n pair

a, b et c se calculent à partir des premières valeurs. (A faire...)

Le terme dominant pour n grand est a, qui, j'imagine, vaut 0.41

Cordialement,

Ah oui tout de même...

J'ai l'air malin avec mon bug informatique.

[zoonel]

Merci pour toutes ces explications, la formule par récurrence est pas mal, par contre il faut voir ce que ça donne dans des cas plus compliqués (genre des valeurs à 6 3 et 1 par exemple :S)

On peut même donner une formule pour p(n) :

Soit q(n) = p(n) - n/2

q(n) = q(n-4)/6 + q(n-3)/6 + q(n-2)/6 +q(n-1)/2

Le polynôme a pour racines :



Comme q(n) est réel, c'est de la forme :



avec s(n) = 0 si n impair, si n pair

a, b et c se calculent à partir des premières valeurs. (A faire...)

Je ne comprends pas d'où sort le polynôme, je vois bien que si je mets tout sur 6 et égale à 0 je l'obtient en remplaçant q(n-i) par x^i mais je vois pas d'où ça vient , pourquoi on peut le faire etc...
De même d'où vient la forme de q(n)?

Sinon avec la récurrence de q(n) j'obtiens pour n grand: 5/12 (=0.4166666). Ce qui correspond bien au 0.41X des simulations.
Par contre calculer a,b,c à partir des premières valeurs de q(n) n'est pas concluant, j'obtiens différentes valeurs si je choisis n=0,1,2 ou n=1,2,3 et dans aucuns cas a=5/12 même si c'est proche.

ps: et non, mes simulations sont exactes il n'y a pas d'erreurs

[zoonel]

Soit une Urne contenant un certains nombre de billes de différentes couleurs , on notera une bille de couleur . Chaque bille peut être tirée avec la probabilité (c'est un tirage avec remise).
A chaque boule de couleur est associé un nombre .
On tire les billes une a une et on additionne à chaque fois le nombre correspondant jusqu'à obtenir le nombre gagnant .
Question: combien faut-il en moyenne de tirage pour obtenir ce nombre

On peut calculer précisément le nombre moyen de tirages pour atteindre ou dépasser n; notons P(n) ce nombre.

En effet la formule récursive suivante fonctionne parfaitement

!ce n'est valable que si les sont positifs ou nuls

[invité576543]

Je ne comprends pas d'où sort le polynôme, je vois bien que si je mets tout sur 6 et égale à 0 je l'obtient en remplaçant q(n-i) par x^i mais je vois pas d'où ça vient , pourquoi on peut le faire etc...
De même d'où vient la forme de q(n)?

Il y a une théorie générale sur les suites récurrentes de ce type, la plus simple et la plus classique étant la suite de Fibonnaci.

Pour faire court, on montre que les suites forment un espace vectoriel, donc généré par n (ici 4) solutions indépendantes.

L'astuce ensuite consiste à trouver les suites géométriques solutions, et le polynôme est celui dont les raisons des suites géométriques sont solution. On se sert alors de ces suites comme base de l'espace, d'où la formule de q(n).

Par contre calculer a,b,c à partir des premières valeurs de q(n) n'est pas concluant, j'obtiens différentes valeurs si je choisis n=0,1,2 ou n=1,2,3 et dans aucuns cas a=5/12 même si c'est proche.

Je n'avais pas le temps de finir ce matin. Faut que je regarde, je ne me rappelle plus de tête comment on traite le cas de racines complexes. Du coup je n'ai cité que trois solutions, les deux réelles et une évidente à construire à partir des complexes. Il est possible qu'il en faille une 4ème indépendante, mais faut que je retrouve comment on la construit...

---

Sinon, la méthode formelle marche bien parce que le degré était petit. Avec des exemples avec ces gains de 1 et de 20000 on va se retrouver avec un degré de 20000, pas vraiment pratique!

Je voulais surtout montrer qu'il était normal d'avoir n/2 + quelque chose...

Mais effectivement la récurrence est d'application générale.

Cordialement,

[invité576543]

Il est possible qu'il en faille une 4ème indépendante, mais faut que je retrouve comment on la construit...

Ce n'était pourtant pas bien sorcier...



c'est toujours réel, et ça fait quatre paramètres.

Cordialement,