Espérance loi de probabilité évolutive

[Benjamin]

Bonjour,

Petit problème que je recherche à résoudre issu de règle d'un jeu vidéo. Je vous avoue que je ne vois pas du tout comment faire
Je vais simplifier, ça ne change pas le fond du problème !

On a une action qui va se résoudre en plusieurs phases, avec un jet d'un dé 10 à chaque phase.
Pour chaque phase, on jette le dé et on additionne un bonus. A la première phase, le bonus vaut B.

Ensuite : si le jet vaut 1, on passe à la phase suivante.
Sinon, en fonction de la valeur de (jet + bonus), on applique les règles suivantes.
2-4 : on passe à la phase suivante
5-9 : bonus augmente de +1 puis phase suivante
10-13 : bonus augmente de +2 puis phase suivante
14-15 : bonus augmente de +3 puis phase suivante
16+ : fin de l'action

La question, c'est que je cherche à savoir de combien de phase en moyenne je vais avoir besoin pour finir l'action, en fonction de mon bonus de départ B. Même avec un arbre, je saurais pas faire puisque le jet 1 qui poursuit d'une phase l'action ferait un arbre infini !
Y a-t-il un moyen analytique ? Faut-il faire forcément une simulation de X tirages très grand ?

Merci

[L.A.]

Bonjour,

je pense que l'outil parfait est une chaîne de Markov : états numérotés de 0 à 16 représentant la valeur du bonus à chaque étape, transitions de k vers k, k+1, k+2 et k+3.

https://fr.wikipedia.org/wiki/Graphe_d%27une_cha%C3%AEne_de_Markov_et_classification_des_%C3%A9tats

Tu pourras calculer la probabilité de terminer (atteindre l'état 16) en n étapes pour n quelconque, puis en déduire l'espérance que tu cherches. En tout cas en théorie, puisque tu vas devoir réduire une matrice 17x17...

La boucle sur 1 ne posera pas de problème vu que la probabilité de tirer une infinité de 1 successif vaut 0.

[zygomatique]

salut

je note d le résultat du dé et b le bonus


1/ quelles sont les valeurs possibles du bonus (en particulier au départ) ?

2/ que signifie "passer à la phase suivante" : est-ce simplement recommencer le lancer du dé ?


si je comprends bien tu lances un dé et tant que tu n'as pas au moins 16 tu recommences avec les conditions :

si d = 1 ou d + b in {2, 3, 4} on recommence
si d + b in {5, 6, 7, 8, 9} alors b = b + 1 et on recommence
si d + b in {10, 11, 12, 13} alors b = b + 2 et on recommence
si d + b in {14, 15} alors b = b + 3 et on recommence
si d + b > 15 on s’arrête


effectivement une simulation semble le plus simple avec 1000 (voire éventuellement 10 000) essais pour donner une bonne approximation ...

et ça se programme simplement ....


maintenant réfléchissons : les lancers sont évidemment indépendants

dans le pire cas : b = 0 (et plus généralement b < 4 donc b + d < 5 donc on recommence :

1/ b = 0 : quelle est la probabilité d'avoir 1000 fois de suite d = 1 ? ( et même simplement déjà 10 fois)

2/ b = 0 : quelle est la probabilité d'avoir 1000 fois de suite d < 5 ? (et même simplement déjà 10 ou 100 fois)

[Benjamin]

1/ quelles sont les valeurs possibles du bonus (en particulier au départ) ?

Je ne pense pas que ça soit très important pour la méthode, mais en gros, de -2 à 8.

2/ que signifie "passer à la phase suivante" : est-ce simplement recommencer le lancer du dé ?

Oui, avec le nouveau bonus en place.

si je comprends bien tu lances un dé et tant que tu n'as pas au moins 16 tu recommences avec les conditions :

si d = 1 ou d + b in {2, 3, 4} on recommence
si d + b in {5, 6, 7, 8, 9} alors b = b + 1 et on recommence
si d + b in {10, 11, 12, 13} alors b = b + 2 et on recommence
si d + b in {14, 15} alors b = b + 3 et on recommence
si d + b > 15 on s’arrête

C'est exactement ça !

[Benjamin]

Bonjour,

je pense que l'outil parfait est une chaîne de Markov : états numérotés de 0 à 16 représentant la valeur du bonus à chaque étape, transitions de k vers k, k+1, k+2 et k+3.

https://fr.wikipedia.org/wiki/Graphe_d%27une_cha%C3%AEne_de_Markov_et_classification_des_%C3%A9tats

Tu pourras calculer la probabilité de terminer (atteindre l'état 16) en n étapes pour n quelconque, puis en déduire l'espérance que tu cherches. En tout cas en théorie, puisque tu vas devoir réduire une matrice 17x17...

La boucle sur 1 ne posera pas de problème vu que la probabilité de tirer une infinité de 1 successif vaut 0.

Merci pour ta réponse, je ne connaissais pas du tout ces chaînes de Markov. Il faudrait que je regarde ça au calme, peut-être ce soir
Pour une réduction de matrice 17x17, on doit pouvoir le faire numériquement sans trop de soucis j'imagine (j'ai déjà fait bien pire avec Matlab ^^).

[Benjamin]

maintenant réfléchissons : les lancers sont évidemment indépendants

dans le pire cas : b = 0 (et plus généralement b < 4 donc b + d < 5 donc on recommence :

1/ b = 0 : quelle est la probabilité d'avoir 1000 fois de suite d = 1 ? ( et même simplement déjà 10 fois)

2/ b = 0 : quelle est la probabilité d'avoir 1000 fois de suite d < 5 ? (et même simplement déjà 10 ou 100 fois)

Merci pour ta réponse. Effectivement, ce n'était pas dit explicitement mais les lancers sont indépendants.

Pour la 1/, 1/10^n a priori.
Pour la 2/, c'est pareil je pense : 0.4^n (épreuve de Bernouilli où le succès est d<5 de probabilité p=4/10=0.4, et je cherche à avoir N succès sur N épreuves, donc loi binomial (n,n) c'est à dire p^n).

Mais je ne vois pas trop où tu veux m'amener...

[zygomatique]

Je ne pense pas que ça soit très important pour la méthode, mais en gros, de -2 à 8.

alors ça pose un pb : si d = -b = 2 alors d + b = 0 ... et que fait-on dans ce cas ?

ce qui ferait une matrice de dimension 19 puisqu'on rajoute les états -1 et 0 ...

soyons fou ...

non ce n'est pas une loi binomiale ... car on peut très bien lancer le dé une infinité de fois .... (même avec la probabilité 0)

Mais je ne vois pas trop où tu veux m'amener...

juste pour dire qu'on peut négliger les cas défavorables (au delà de 10 lancers par exemple (il est évident que P(n > 10) est négligeable (n = nb de lancers nécessaire pour dépasser 16)

et si P(n > 10) est vraiment "trop grand" alors négliger par exemple P(n > 100) qui est encore plus négligeable ...

[Benjamin]

Je ne pense pas que ça soit très important pour la méthode, mais en gros, de -2 à 8.

alors ça pose un pb : si d = -b = 2 alors d + b = 0 ... et que fait-on dans ce cas ?

En fait, j'aurai dû mettre : si d+b < 5, on recommence. Comme je le disais, les vraies règles sont un tout petit peu plus complexes et là j'ai fait une simplification d'où quelques trous Ca ne change rien à la méthode, car je peux te garantir que B prend bien un nombre de valeur fini ^^
Par ailleurs, les transitions sont un peu plus chiadées car il y a 2 bonus au lieu d'un seul, dont un qui est capé à 3. Et pour encore compliquer le truc, ce second bonus capé à 3 s'incrémente en fonction de la valeur de d+b comparé à un nombre qui lui dépend de b initiale... Ca va donc faire beaucoup plus que 19 dimensions... mais de ce que j'ai vu rapidement, toujours modélisable par une chaîne de Markov

Oui, on se demande où ils ont été cherché tout ça... Du coup, pour min/max dans le jeu, et savoir où mettre l'effort sur la valeur de B initiale (il y a plein de moyens d'agir dessus), je cherche à theorycrafter le truc. Genre est-ce que passer de B0 de 2 à 3 est important etc... Où sont les points de rupture, etc...

[zygomatique]

alors bon courage pour prendre en compte toutes les conditions ...

[Benjamin]

alors bon courage pour prendre en compte toutes les conditions ...

Merci,
Finalement, ça va peut-être bien se finir en simulation (mais j'aime pas l'imprécision, et je suis pas sûr de savoir générer proprement une belle suite de nombre aléatoire).

[L.A.]

Pour appliquer les chaines de Markov, il faudrait que tu écrives d'abord la matrice de transition , format 19x19, indexée de -2 à 16, avec la probabilité d'obtenir un bonus j après un lancer et à partir d'un bonus i.

ex : = probabilité d'obtenir entre 4 et 8 au dé = 0,5

Ensuite, tu calcules la matrice , dont le coefficient d'indice {i,16} sera la probabilité de terminer en exactement n étapes à partir d'un bonus initial i. En appelant ce coefficient, le résultat est donc



A toi de voir ce qui en sort...

[Benjamin]

Merci L.A.
J'ai bien fait ma matrice de transition et j'ai bien, pour un bonus initial donné, la probabilité de terminer en 1, 2, 3, etc.... étapes.
Voici par exemple les résultats en fonction de n pour un bonus donné.

Code: Tout sélectionner

    1.0000         0
    2.0000         0
    3.0000         0
    4.0000         0
    5.0000         0
    6.0000         0
    7.0000         0
    8.0000    0.0000
    9.0000    0.0000
   10.0000    0.0003
   11.0000    0.0012
   12.0000    0.0036
   13.0000    0.0087
   14.0000    0.0175
   15.0000    0.0309
   16.0000    0.0493
   17.0000    0.0729
   18.0000    0.1013
   19.0000    0.1339
   20.0000    0.1697
   21.0000    0.2079
   22.0000    0.2477
   23.0000    0.2882
   24.0000    0.3287
   25.0000    0.3687
   26.0000    0.4077
   27.0000    0.4454
   28.0000    0.4816
   29.0000    0.5160
   30.0000    0.5486
   31.0000    0.5794
   32.0000    0.6084
   33.0000    0.6356
   34.0000    0.6610
   35.0000    0.6848
   36.0000    0.7070
   37.0000    0.7277
   38.0000    0.7470
   39.0000    0.7650
   40.0000    0.7817
   41.0000    0.7972
   42.0000    0.8116
   43.0000    0.8251
   44.0000    0.8375
   45.0000    0.8491
   46.0000    0.8599
   47.0000    0.8699
   48.0000    0.8792
   49.0000    0.8878
   50.0000    0.8958
   51.0000    0.9032
   52.0000    0.9102
   53.0000    0.9166
   54.0000    0.9225
   55.0000    0.9281
   56.0000    0.9332
   57.0000    0.9380
   58.0000    0.9424
   59.0000    0.9465
   60.0000    0.9503
   61.0000    0.9539
   62.0000    0.9572
   63.0000    0.9602
   64.0000    0.9631
   65.0000    0.9657
   66.0000    0.9682
   67.0000    0.9704
   68.0000    0.9725
   69.0000    0.9745
   70.0000    0.9763
   71.0000    0.9780
   72.0000    0.9796
   73.0000    0.9810
   74.0000    0.9824
   75.0000    0.9837
   76.0000    0.9848
   77.0000    0.9859
   78.0000    0.9869
   79.0000    0.9879
   80.0000    0.9887
   81.0000    0.9895
   82.0000    0.9903
   83.0000    0.9910
   84.0000    0.9916
   85.0000    0.9922
   86.0000    0.9928
   87.0000    0.9933
   88.0000    0.9938
   89.0000    0.9942
   90.0000    0.9946
   91.0000    0.9950
   92.0000    0.9954
   93.0000    0.9957
   94.0000    0.9960
   95.0000    0.9963
   96.0000    0.9966
   97.0000    0.9968
   98.0000    0.9970
   99.0000    0.9972
  100.0000    0.9974

Mais je ne vois pas comment j'ai mon nombre n moyen ensuite (je ne comprends pas ta formule plutôt). Ta somme donne 4438.8, ce qui me parait très excessif ^^ (et ne correspond pas à la réalité du terrain !)

[Benjamin]

En fait, il me faudrait les probabilités "inverses", quelle est la proba de finir en 1 étape, 2 étapes, etc... Dans mon problème, c'est N ma variable aléatoire. Et là, je pourrais faire le calcul d'espérance avec la formule.

Comment passer des probas d'avoir fini si N=n aux probas de finir en N étapes ? Je sèche là...

[Benjamin]

Ah, je crois que j'ai compris !! Ce que j'ai, c'est la fonction de répartition. C'est P(n<=N).
Il suffit de faire les différences progressives pour passer à la densité de probabilité. Ca donne

Code: Tout sélectionner

    1.0000         0
    2.0000         0
    3.0000         0
    4.0000         0
    5.0000         0
    6.0000         0
    7.0000         0
    8.0000    0.0000
    9.0000    0.0000
   10.0000    0.0002
   11.0000    0.0009
   12.0000    0.0024
   13.0000    0.0051
   14.0000    0.0088
   15.0000    0.0134
   16.0000    0.0185
   17.0000    0.0236
   18.0000    0.0284
   19.0000    0.0325
   20.0000    0.0358
   21.0000    0.0382
   22.0000    0.0398
   23.0000    0.0405
   24.0000    0.0405
   25.0000    0.0400
   26.0000    0.0390
   27.0000    0.0377
   28.0000    0.0361
   29.0000    0.0344
   30.0000    0.0326
   31.0000    0.0308
   32.0000    0.0290
   33.0000    0.0272
   34.0000    0.0255
   35.0000    0.0238
   36.0000    0.0222
   37.0000    0.0207
   38.0000    0.0193
   39.0000    0.0180
   40.0000    0.0167
   41.0000    0.0155
   42.0000    0.0144
   43.0000    0.0134
   44.0000    0.0125
   45.0000    0.0116
   46.0000    0.0108
   47.0000    0.0100
   48.0000    0.0093
   49.0000    0.0086
   50.0000    0.0080
   51.0000    0.0074
   52.0000    0.0069
   53.0000    0.0064
   54.0000    0.0060
   55.0000    0.0055
   56.0000    0.0051
   57.0000    0.0048
   58.0000    0.0044
   59.0000    0.0041
   60.0000    0.0038
   61.0000    0.0035
   62.0000    0.0033
   63.0000    0.0031
   64.0000    0.0028
   65.0000    0.0026
   66.0000    0.0024
   67.0000    0.0023
   68.0000    0.0021
   69.0000    0.0020
   70.0000    0.0018
   71.0000    0.0017
   72.0000    0.0016
   73.0000    0.0015
   74.0000    0.0014
   75.0000    0.0013
   76.0000    0.0012
   77.0000    0.0011
   78.0000    0.0010
   79.0000    0.0009
   80.0000    0.0009
   81.0000    0.0008
   82.0000    0.0007
   83.0000    0.0007
   84.0000    0.0006
   85.0000    0.0006
   86.0000    0.0006
   87.0000    0.0005
   88.0000    0.0005
   89.0000    0.0004
   90.0000    0.0004
   91.0000    0.0004
   92.0000    0.0004
   93.0000    0.0003
   94.0000    0.0003
   95.0000    0.0003
   96.0000    0.0003
   97.0000    0.0002
   98.0000    0.0002
   99.0000    0.0002
  100.0000    0.0002

Dont l'espérance est : 32.2218 qui est dans les bons ordres de grandeur

Merci !! C'est génial ces chaînes de Markov !

[L.A.]

Ah, je crois que j'ai compris !! Ce que j'ai, c'est la fonction de répartition. C'est P(n<=N).
Il suffit de faire les différences progressives pour passer à la densité de probabilité.

Effectivement, il faut tenir compte du fait qu'une fois arrivé sur l'état 16 on boucle indéfiniment. Et aussi qu'une moyenne des n se fait avec des coefficients dont la somme vaut 1...

[Ben314]

Salut,
J'ai l'impression qu'au niveau des calculs, dans un cas pareil, c'est plutôt plus simple de prendre comme "pseuso chaine de Markov" celle uniquement constituée des états "Bonus=0", "Bonus=1", ..., "Bonus=16" sans avoir d'état correspondant à "Fin de l'action".
Ta matrice de transition est alors où est la proba de passer de l'état "Bonus=j" à l'état "Bonus=i" et où les proba. de "Fin de l'action" n'apparaissent pas.
Ce n'est donc pas une vraie chaine de Markov vu que la somme des proba par colonne ne fait pas systématiquement 1 (*), mais ça a l'énorme avantage que est une matrice triangulaire inférieure dont les terme de la diagonale sont <1 donc tend vers 0 et ça simplifie (grandement) les différentes preuves (en fait, on est dans un cas extrêmement simple de chaine de Markov dans lequel on ne peut "aller que dans un sens").

Donc, si on note le vecteur colonne contenant les proba. d'être dans les situation "Bonus=?" après étapes alors est connu (des 0 partout et un 1 correspondant au bonus de départ) et la "règle" de calcul est évidement donc .
La somme des coordonnées de , c'est à dire où L est le vecteur colonne formé de 1 correspond alors à la proba de ne pas avoir fini l'action au bout de étapes.
Donc la proba d'avoir fini au bout de n étapes est et la proba de finir exactement à la -ième étape () est .
L'espérance cherchée est donc

Or, vu que est triangulaire avec des valeur sur la diagonale dans [0,1[ la série converge vers (qui existe) et tend vers la matrice nulle et on a en fait le résultat suivant :
où est la solution du système .

Bref, le seul calcul qu'il y a à faire, c'est la résolution du système linéaire (et triangulaire !!!) qui contient précisément les espérances cherchées (i.e. celle correspondant à un bonus de départ=0, =1, ...)

(*) Par rapport à la "vrai" matrice de transition avec un état de plus "Fin de l'action", on a simplement enlevé la dernière ligne et la dernière colonne.

EDIT : En fait, la formule finale s'explique très simplement :
Si correspond aux espérance partant d'un bonus de départ égal à 0,1,...,16.
Partant d'un bonus égal à on a une proba de de gagner en un coup et, pour de 0 à 16 une proba de de passer au coup suivant à l'état "Bonus = " où on gagnera en moyenne en un temps égal à donc, c'est que :

Ce qui, matriciellement parlant, signifie que et c'est bien la même chose que le trouvé ci dessus.

[Benjamin]

Bonjour Ben, et merci pour ta réponse détaillée.
Effectivement, on ne revient pas en arrière dans la chaine et j'avais bien constaté que la matrice était triangulaire. Pour le reste, j'étais bien loin de pouvoir faire cette démarche algébrique de simplification
Petite question en passant : sur Wikipedia, ils fonctionnent en transposé de ce que tu dis i.e. que Xn est un vecteur ligne et la matrice de transition fonctionne par ligne et non par colonne. Y a-t-il une règle officielle à suivre ? J'avais tout fait dans l'autre sens jusqu'à présent (et oui, je suis d'accord que ça ne change rien aux conclusions )

Pour le fond, je vais faire comme tu dis, ça évite effectivement tous les problèmes de limite de choisir le n à partir duquel s'arrêter etc... Par contre, je crois que je vais devoir faire une matrice par bonus de départ En effet, dans les vraies règles, l'accroissement du bonus possède une borne max fixée à 12. Donc l'état bonus = 5 (par exemple), n'est pas le même selon qu'on vient de b0=2 ou b0 = 4. Je vais avoir 13 états (de b0+0 à b0+12), et autant de matrice 13x13 que de possibilités pour b0. A moins que tu vois à nouveau une autre astuce ?

[Benjamin]

L'espérance cherchée est donc

Or, vu que est triangulaire avec des valeur sur la diagonale dans [0,1[ la série converge vers (qui existe)

Je t'embête encore un peu. Déjà, je pense qu'il y a une petite erreur dans la formule (mais on s'en fout), c'est .
Par contre, je ne comprends pas du tout comment tu trouves la convergence de la somme de A^k (je rappelle que niveau math, je me suis arrêté à un niveau L2 en gros et c'était il y a très longtemps )

[Ben314]

Concernant les conventions d'écritures des "matrices de transitions", vu que perso, j'ai appris "sur le tas" (i.e. en faisant des casse têtes et pas en lisant des livres) je pense qu'il vaudrait mieux prendre celle de Wiki.
A la limite, regarde sur d'autres sites (universitaires par exemple) de quoi il retourne. Moi j'ai jamais enseigné ce truc là...

Ensuite, concernant ton histoire de borne max du bonus fixé à 12, comme de toute façon, les calculs, tu va évidement les faire avec un logiciel, une fois le code tapé pour une matrice donnée (i.e. un b0 donné), si tu t'y es pas pris trop comme un manche, il va juste y avoir a englober le truc dans une boucle et à rajouter des bricoles pour que ça marche pour toutes les matrices, non ?

Enfin, concernant "ma prose", il y a effectivement une erreur d'indice (mais qui effectivement ne change rien).
Et concernant la fameuse somme, c'est au fond la même chose que dans R avec les séries entières où lorsque et la façon la plus simple de le montrer, ben c'est évidement de faire le produit des sommes partielles par .
Avec des matrices, tu développe et ça te donne qui, si toutes les valeur propres (réelle ou complexes) de sont de module <1 converge vers la matrice ce qui démontre que est inversible et que son inverse, c'est .

[Benjamin]

Salut !

Oui tout à fait, je fais tout avec un logiciel donc je m'en fous d'avoir 20 matrices à traiter ou autre. Ma question était plus pour la beauté des maths, si jamais il y avait encore une belle petite astuce
Merci pour tous tes compléments en tout cas, je crois que j'ai tout ce qu'il me faut