Parcours probabiliste

Olympiades mathématiques, énigmes et défis
Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

Parcours probabiliste

par Doraki » 24 Jan 2011, 00:15

Un pion est posé au début d'une longue série de cases numérotées 0, 1, 2, 3, ...

On lance un dé à 6 faces et on déplace le pion du nombre de cases indiqué sur le dé.
On répète le procédé une infinité de fois.
Pour n >= 0, on définit P(n) = probabilité que le pion s'arrête à un moment sur la case n.

Que dire de P(n) quand n tend vers l'infini ?

Et quand on lance deux dés pour avancer le pion ?



Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 24 Jan 2011, 00:46

Doraki a écrit:Un pion est posé au début d'une longue série de cases numérotées 0, 1, 2, 3, ...

On lance un dé à 6 faces et on déplace le pion du nombre de cases indiqué sur le dé.
On répète le procédé une infinité de fois.
Pour n >= 0, on définit P(n) = probabilité que le pion s'arrête à un moment sur la case n.


C'est un peu contre intuitif, mais j'ai bien envie de dire que P(n) tend vers 1. Est-il possible, en dehors du comportement asymptotique, d'obtenir une expression de P(n) ?

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 24 Jan 2011, 01:05

Moi d'expérience, je passais pas à chaque tour sur "parc gratuit" quand je jouais au monopoly.
Donc ton P(n) tend vers 1, je le trouve en effet pas très intuitif.

On peut obtenir une expression exacte (enfin presque) de P(n). C'est très moche, mais ça peut être une étape.

On peut tout faire en cachant tous les trucs moches et en gardant que des trucs jolis avec presque aucun calcul.

Nightmare
Membre Légendaire
Messages: 13817
Enregistré le: 19 Juil 2005, 19:30

par Nightmare » 24 Jan 2011, 01:15

Doraki a écrit:Moi d'expérience, je passais pas à chaque tour sur "parc gratuit" quand je jouais au monopoly.


C'est sûr ...

En fait, pour avancer sans trop me mouiller que ça tend vers 1, je me suis juste dit que plus n était grand, plus le nombre de partition de n en somme de 1,...,6 était grand. Même si c'est juste, c'est clair a posteriori que ça ne permet surement pas de conclure que P(n) tend vers 1.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 24 Jan 2011, 02:59

Salut,
Pour un unique dés, 2/7 me parait... convenable...
Avec 2 dés, la moitié (de 2/7) semble... raisonable... :zen:

@Nightmare : tu crois vraiment qu'au bout d'un moment le pion passe presque surement par toutes les cases ?????
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

scelerat
Membre Relatif
Messages: 397
Enregistré le: 03 Aoû 2005, 15:37

par scelerat » 24 Jan 2011, 18:42

Ben314 a écrit:Salut,
Pour un unique dés, 2/7 me parait... convenable...
Avec 2 dés, la moitié (de 2/7) semble... raisonable... :zen:

Moi aussi, mais il faudrait quand même montrer que la probabilité tend à devenir constante. Les racines de 6x^6 -x^5 -x^4 - ... -1, peut-être ?

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 24 Jan 2011, 20:51

Et quelle est la proba de tomber sur n=5 par exemple ?

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 24 Jan 2011, 20:53

Nightmare a écrit:C'est sûr ...

En fait, pour avancer sans trop me mouiller que ça tend vers 1, je me suis juste dit que plus n était grand, plus le nombre de partition de n en somme de 1,...,6 était grand. Même si c'est juste, c'est clair a posteriori que ça ne permet surement pas de conclure que P(n) tend vers 1.


Vrai mais il faut le comparer avec le nombre de partitions qui ne tombent pas sur n. Et là, on est loin du 1.

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 24 Jan 2011, 22:43

C'est pas tellement une question de comparer avec les partitions qui ne tombent pas sur n, mais plutôt de mettre un poids correct sur les partitions qui donnent n (en 1/6^longueur de la partition).

Sinon y'a personne pour expliquer comment Ben314 a trouvé ou calculé ses valeurs ?

ffpower
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 24 Jan 2011, 23:14

On atteint n>6 ssi on atteint un n-k pour un certain k dans {1..6} et que l'on fait k au coup juste après. Ce découpage en 6 événements disjoints donne la formule de réccurence . On peut vérifer qu'une telle suite converge (modulo erreurs) vers , donc ya plus qu' a calculer P(1),...,P(6)..ce qui est certes moche et ne se généralise pour un dé à p faces..

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 24 Jan 2011, 23:20

ouais tu devrais vérifier ta formule de récurrence qui pour l'instant, dit que P(n) est constante.

ffpower
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 24 Jan 2011, 23:24

lol en effet, j'édite ça..

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 25 Jan 2011, 01:00

Perso, j'ai commencé (à la bourin) par dire qu'effectivement, si on note les probas de faire ( pour un dés non pipé) et la proba de tomber sur alors, pour tout on a à condition d'avoir posé et .
Pour une telle suite récurrente, il faut considérer le polynôme qui, vu le contexte admet comme racine simple et a toutes ces autres racines de module .
Le terme général s'écrit en fonction des racines de à la la puissance (avec des coeff qui sont des polynôme en de degrés un de moins que l'ordre de multiplicité de la racine dans ) et donc la suite tend vers le coeff. qui apparait devant le .
Sauf que le fait que est racine simple et que la suite commence par les termes fait que ce coeff. n'est autre que .

Arrivé à ce point, on remarque (en utilisant ) que est en fait la moyenne du nombre de case dont on avance et donc que la proba de tomber sur une case tend vers l'inverse de "l'avancement moyen" ce qui et... extrêmement intuitif !!!

Par exemple, avec un dés "normal", on avance en moyenne de cases donc la proba "limite" est
Modifié en dernier par Ben314 le 10 Jan 2016, 23:42, modifié 1 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 25 Jan 2011, 01:40

Tiens je crois pas connaître le coup du 1/P'(x) pour avoir le coefficient devant le terme en x^n dans p(n)

J'avais que à partir de p(n+6) - a1 p(n+5) - a2 p(n+4) ... - a6 p(n) = 0,
en divisant P par (X-1), ça nous dit que la quantité
p(n+5) + (1-a1) p(n+4) + (1-a1-a2) p(n+3) + ... + (1-a1-a2-a3-a4-a5) p(n), est une constante C ne dépendant pas de n.

En évaluant en n= -5, on trouve C = 1,
En évaluant en n = l'infini, on trouve C = lim p(n) * moyenne du dé (de même en utilisant que a1+...+a6=1)


Une fois qu'on a vu que la réponse est 1/moyenne du dé, je suis persuadé que y'a un argument très "simple" qui dit que
P(1) + P(2) + ... + P(n) = espérance du nombre de coups nécessaire pour atteindre la case n
= n / (moyenne du dé) + ;)(n).

Mon intuition me souffle que ;)(n) = espérance du "dépassement" et devrait être borné (<= 6), mais à ce niveau là c'est plutôt nébuleux.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 25 Jan 2011, 01:56

Pour le "coup du 1/P'(1)", tu peut regarder là :
http://www.sendbox.fr/AQ9SCLLPWBYC/suites_recurente.pdf
(QUESTION : pour des PDF, c'est quoi le moins chiant pour les stocker. là il faut attendre 30 secondes puis le charger pour le lire... chiant...)
pour toutes les racines simples r de P, le coeff devant le r^n est Q(r)/P'(r) et, lorsque la suite commence par 0,0,...,0,1 alors le polynôme Q est simplement Q(X)=1 donc...

Aprés, là ou j'ai l'impression d'être comme toi, c'est que d'affirmer que :
"il est clair que la limite de la proba de tomber sur n est l'inverse de l'avancement moyen"
me parrait "un peu short"...
En particulier, c'est faux si par exemple toutes les faces du dés contiennent des nombres pairs (cas dans P(X) est divisible par X-1 donc 1 n'est pas la seule racine de P de module 1)
Je pense qu'on peut voir caché derrière un des théorèmes sur les processus stochastiques qui doit être "je sais plus quoi" (on doit pouvoir passer de n'importe quel état à n'importe quel autre) pour que "ça marche bien".
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 25 Jan 2011, 02:15

Tient, d'ailleurs, à propos du PDF, cela montre que :
Si où les sont distincts alors :


QUESTION (énigme) : c'est quoi le plus simple pour montrer cette "formule" ?
Modifié en dernier par Ben314 le 10 Jan 2016, 23:44, modifié 2 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 25 Jan 2011, 11:15

en fait, j'ai la preuve "facile" :

(espérance du dé) * (p0 + p1 + p2 + ... + pn)
= (espérance du dé) * (espérance du nombre de coups pour atteindre (n+1))
= espérance de (distance parcourue pour atteindre ou dépasser (n+1))
= (n+1) + espérance du dépassement

L'espérance du dépassement est bornée (entre 0 et 5, trivialement),
donc (p0 + ... + pn)/n -> 1/espérance du dé.

Ensuite, oui, pour peu que P(X) n'ait pas d'autre racine de module 1 / que le pgcd des valeurs du dé vale 1, ça conclut.

Judoboy
Membre Rationnel
Messages: 654
Enregistré le: 24 Fév 2012, 16:36

par Judoboy » 13 Jan 2013, 20:34

Je sais pas ce que je fais là mais UP. J'ai envie de dire ce que dirait un élève de seconde sensé : le dé parcourt en moyenne 3.5 cases à chaque lancer donc on tombe sur 1/3.5.

Avec 2 dés il parcourt en moyenne 7 cases donc ça tend vers 1/7.


Ca suffit comme démonstration ou pas ?

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 13 Jan 2013, 22:32

Pour un élève de seconde, probablement. Mais après il vaut mieux savoir donner une vraie justification une fois qu'on a le bagage pour.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 7 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite