Besoin d'aide pour un ivrogne qui traverse un pont sans garde-corps

[Médiat]

Donc nous sommes d'accord sur un point : votre solution est absolument fausse !

Au cas où Looper14 reviendrait consulter son post : de nombreuses réponses fausses ont été accumulées sur ce post, y compris sur le nombre de trajectoires possibles, le message #5 donne un indice pour trouver la solution (le même indice permet d'avoir la réponse avec un pont de longueur n, de largeur 2p + 1 avec un départ au centre) ; au besoin (celui de Looper14), plusieurs personnes ici, pourront développer. Cette méthode donne un réponse compatible avec la simulation de Looper14.
-----

[fregoli]

D: votre solution est absolument fausse ...

laquelle?
celle indiquée dans mon post #14?
Merci de le démontrer à votre tour cher ami.

J'ignorai qu'il fallait impérativement fournir,lors du premier post sur une discussion, la bonne réponse à une question donnée. Je pensais naïvement que ce forum était un forum de discussion, donc où on pouvais discuter.
Manifestement, tout le monde ne semble pas de cet avis.

[Médiat]

laquelle?

Toutes

Merci de le démontrer à votre tour

Non, non, non la démonstration de vos résultats vous incombe !

[fregoli]

tout est démontré dans le post #19.

[Médiat]

Une succession d'affirmation ne fait pas une démonstration !

[fregoli]

Ce n'est pas une succession d'affirmation, c'est une démonstration pas récurrence:
alors je la répète, pour ceux qui n'ont pas compris:

on tombera au pas n si et seulement si

on se trouve sur un coté et qu'on se dirige vers la mauvaise direction (1/3 pour chaque coté)

on se trouvera sur le coté D au pas n si et seulement si,

on était sur le coté D et qu'on va tout droit (1/3)

on était au milieu et on va à D (1/3)

raisonnement identique pour la G
on sera au milieu au pas n si et seulement si on

était au milieu et qu'on va tout droit (1/3)

on était à D (resp G) et qu'on va à G (resp D) (1/3 à chaque fois)

D'où les relations par récurrence

P(D,n) = 1/3 * (P(D,n-1) + P(M,n-1))
P(M,n) = 1/3 * (P(M,n-1) + P(D,n-1) + P(G,n-1))
P(G,n) = 1/3 * (P(G,n-1) + P(M,n-1))

P(Tombe,n) = 1/3 * (P(D,n-1) + P(G,n-1)) ' prob de tombé au pas n pas celui d'être tombé au pas n

P(D,0)=0
P(G,0)=0
P(M,0)=1

P(Ok,n) = P(D,n) + P(M,n) + P(G,n)

Fin de la démonstration.

[joel_5632]

oui, c'est juste.

>>> pc = 1; pd=0; pg = 0
>>> 
>>> for i in range(5):
	pc2 = 1/3 * (pc + pg + pd)
	pd2 = 1/3 * (pc + pd)
	pg2 = 1/3 * (pc + pg)
	pc, pd, pg = pc2, pd2, pg2
	print(pc, pd, pg)

	
0.3333333333333333 0.3333333333333333 0.3333333333333333
0.3333333333333333 0.2222222222222222 0.2222222222222222
0.25925925925925924 0.18518518518518517 0.18518518518518517
0.2098765432098765 0.14814814814814814 0.14814814814814814
0.1687242798353909 0.1193415637860082 0.1193415637860082
>>> pc + pd + pg
0.4074074074074073

[fregoli]

Je vais être bon prince, je vais généraliser à un pont de 2*m + 1 de large.

les notations étant les suivantes:

P(0,n) : probabilité de se trouver au milieu du pont au pas n.
P(i,n) : probabilité de se trouver sur une case de coordonnée +- i au pas n, avec 0 < i < m
P(m,n) : probabilité de se trouver sur un des deux bords (en +m ou -m) au pas n

les relations de récurrence obtenues sont les suivantes

P(0,n) = 1/3 (P(0,n-1) + 2 * P(1,n-1))
P(i,n) avec 0<i<m = 2/3 (P(i,n-1) + 2 * P(i-1,n-1))
P(m,n) = 2/3 * (P(m,n-1) + P(m-1,n-1))

P(Ok, n): probabilité d'être toujours sur le pont au pas n

P(Ok,n) = P(m,n) + P(O,n) + somme(P(i,n)) pour i allant de 1 à m-1

P(KO,n) : probabilité d'être tombé au pas n
P(KO,n) = 1 - P(Ok,n)


pourvu qu'il n'y ait pas d'erreur...

[mike.p]

Ce ne sont pas des lignes mais des paires de lignes : on ne peut pas passer d'une position à risque depuis une autre position à risque ... Ce qui implique de traiter la parité aux lignes de départ et d'arrivée ... Ici , une chaine devrait voir les lignes par paires. Non ?

Ce serait sympa de rattacher les propositions de solutions aux données d'entrée correspondantes :
5 lignes , ordonnées de 0 à 4 , abcisses de -1 à 1 , marche en biais seule , pas de recul ( si ce n'est pas le cas, précisez svp )
- départ en (0,0) ---> ( centre 1re ligne ) ( trouvé en simulation : 0.24914 )
- départ en (0,-1) ---> ( centre 1re ligne -1 ) ( trouvé en simulation : 0.12479 )
- départ en (x,0) ---> ( 1re ligne, x aléatoire ) ( trouvé en simulation : 0.16803 )
- départ en (x,-1) ---> ( 1re ligne -1, x aléatoire ) ( trouvé en simulation : 0.12601 )

Traiteriez vous un autre cas ?

 Cliquez pour afficher

function calstativrogne( v_initiale_x0 , v_initiale_y0 , faut_random_initial )
{
var ret = "" ;
	ret = "de (0,0) "+_calstativrogne( 0 , 0 , false ) + "<br/>" ;
	ret += ("de (0,-1) "+_calstativrogne( 0 , -1 , false ) + "<br/>" ) ;
	ret += ( "de (x,0) "+_calstativrogne( 0 , 0 , true )+ "<br/>" ) ;
	ret += ( "de (x,-1) "+_calstativrogne( 0 , -1 , true )+ "<br/>" ) ;

	return ret ;
}

function _calstativrogne( v_initiale_x0 , v_initiale_y0 , faut_random_initial )
{
	var i, nbessais = 100000 , x , y , x0 , y0 , y_max = 5 , echec = 0 , ligne, stat ;

	for( i = 0 ; i < nbessais ; i++ )
	{
		if( faut_random_initial )
		{
			x0 = Math.random() ;
			if( x0 <= 1/3 )
			{
				x0 = -1 ;
			}
			else if( x0 <= 2/3 )
			{
				x0 = 0 ;
			}
			else
			{
				x0 = 1 ;
			}
		}
		else
		{
			x0 = v_initiale_x0 ;
		}
		x = x0 ;
		y = y0 = v_initiale_y0 ;

		for( ligne = y ; ligne < y_max ; ligne ++ )
		{
			if( Math.random()>0.5 )
			{
				x ++ ;
				if( x > 1 )
				{
					echec ++ ;
					break ;
				}
			}
			else
			{
				x -- ;
				if( x < -1 )
				{
					echec ++ ;
					break ;
				}
			}
		}
	}
	stat = ( nbessais - echec )/nbessais ;

	return stat ;
}

[Médiat]

on tombera au pas n si et seulement si

on se trouve sur un coté et qu'on se dirige vers la mauvaise direction (1/3 pour chaque coté)

on se trouvera sur le coté D au pas n si et seulement si,

on était sur le coté D et qu'on va tout droit (1/3)

on était au milieu et on va à D (1/3)

raisonnement identique pour la G
on sera au milieu au pas n si et seulement si on

était au milieu et qu'on va tout droit (1/3)

on était à D (resp G) et qu'on va à G (resp D) (1/3 à chaque fois)

D'où les relations par récurrence

Là je suis d'accord (différence entre affirmation et démonstration)

[mike.p]

Aléatoirement, l'homme se déplace soit 1 pas devant lui, en diagonale vers la gauche (un pas à gauche, un pas devant) ou en diagonale vers la droite (un pas à droite, un pas vers l'avant).

Il manque un "soit" après "devant lui,". C'est ambigu lorsqu'on lit trop vite ...
Ma solution plus haut traite uniquement de zig zags.

[fregoli]

Le regroupement pour les paires de lignes est juste pour simplifier le résultat obtenu.

Si on raisonne par récurrence:

on dispose de 2*m + 1 lignes numérotée de -m à +m.
comme précédemment, si on se trouve sur la ligne 0, alors on ne peut aller que sur la -1, 0 ou 1.

P(0,n) = 1/3 * (P(-1,n-1) + P(0,n-1) + P(1,n-1))

si on est sur la -1, on ne peut aller que sur la -2, -1 ou 0,
si on est sur la -i (0 < i < m) alors on ne peut aller que sur la -i-1, -i ou -i+1
pour aller sur la -m, on peut venir de la -m (1/3=) ou de la -m+1 (1/3)
pour aller sur la +m, on peut venir de la +m (1/3) ou de la m-1 (1/3)

P(-m,n) = 1/3 * (P(-m,n-1) + P(-m+1,n-1))
et
P(m,n) = 1/3 * ((P(m,n-1) + P(m-1,n-1))
par symétrie, P(-m,n) = P(m,n) (si le pont ne penche pas d'un coté par exemple).

P(O,n) = 1/3 * (P(0,n-1) + 2 * P(1,n-1))
P(BORD,n) = 2/3 ((p(m,n-1) + P(m-1,n-1)) probabilité cumulée d'être sur le bord droit (m) ou gauche (-m)

pour i on procède de même:

Pour aller en i on vient de i+1, i ou i-1 (0 < i < m)

donc P(i,n) = 1/3 * (P(i-1,n-1) + P(i,n-1) + P(i+1,n-1))
et P(-i,n) = 1/3 * (P(-i-1,n-1) + P(-i,n-1) + P(-i+1,n-1))

et par symétrie P(i,n-1) = P(-i,n-1)
P(i-1,n-1) = P(-i+1,n-1)
P(-i-1,n-1) = P(i+1,n-1)

donc P(I,n) = P(-i,n) + P(i,n) = 1/3 * (2 * P(i-1,n-1) + 2 * P(i,n-1) + 2 * P(i+1,n-1)) pour 0 < i < m et 0 < I < m
P(I,n) = 2/3 * (P(i-1,n-1) + P(i,n-1) + P(i+1,n-1))

à priori, P(i-1,n-1) <> P(i+1,n-1)


en résumé:

P(OK,n) = P(0,n) + P(BORD,n) + P(I,n)
P(O,n) = 1/3 * (P(0,n-1) + 2 * P(1,n-1))
P(i,n) = 2/3 * (P(i-1,n-1) + P(i,n-1) + P(i+1,n-1)) pour 0 < i < m
P(BORD,n) = 2/3 ((p(m,n-1) + P(m-1,n-1))

P(KO,n) = 1 - P(OK,n)

d'où une erreur sur la formulation précédente où j'ai identifié à tord les deux valeurs P(i-1,n-1) et P(i+1,n-1)

milles excuses.

[mike.p]

Dans le cas de 3 options sans cycle simple, je préfère le formalisme matriciel

On peut définir un vecteur d'état ( pavé de gauche, centre, pavé de droite ) et lui appliquer la matrice de transformation d'une étape à la suivante
M = ( ( 0,1/3,1/3),( 1/3,1/3,1/3),( 1/3,1/3,0) ) . C'est la simple expression de l'énoncé. Le vecteur final représentera les chemins survivants.

S'il y a 5 pas et qu'on démarre d'une des 3 positions équiprobables , donc avec le vecteur initial E_0 = ( 1/3,1/3,1/3) , ca donne
E = E_0 . M^5 = (0.0960219, 0.135802, 0.0960219). La probabilité de ne pas être tombé est la somme des composantes, soit 0.327846 ( simulation 10^6 : 0.327028 )

Avec un pas de plus, on obtient (169/2187,239/2187 , 169/2187) et 0.263832 ( simulation 10^6 : 0.263839 )
et deux de plus ( 136/2187, 577/6561, 136/218) et 0.212315 ( simulation 10^6 : 0.212097 )

[mike.p]

A tout hasard, s'il n'y a pas de pavé central mais seulement un droit et un gauche, la même méthode fonctionne :

E_0 = (1/2,1/2)
M = (1/3,1/3 ; 1/3,1/3 )

Entre parenthèses à la fin de la ligne, le résultat de la simulation ( de 10^6 tirages ) après celui calculé.

E_0 . M^5 = (0.0658436, 0.0658436) et 0.0658436 + 0.0658436 = 0.1316872 ( 0.131941 )
et avec quelques pas de plus :
E_0 . M^6 = (32/729, 32/729) et 32/729+32/729 ≈ 0.0877915 ( 0.087867 )
E_0 . M^7 = (64/2187, 64/2187) et 64/2187+64/2187 ≈ 0.0585277 ( 0.058731 )
E_0 . M^8 = (128/6561, 128/6561) et 128/6561+128/6561 ≈ 0.0390184 ( 0.039209 )

E_0 vaut ici (1/2,1/2) ou (1/3,1/3,1/3) dans le cas à 3. Mais on peut aussi décider de démarrer avec une autre répartition ou depuis une même allée en adaptant E_0.

[Verdurin]

C'est une discussion assez surprenante.

Avez-vous déjà entendu parler des chaînes de Markov ?

[mike.p]

Salut Verdurin,

n'en est ce pas dans les 2 messages précédents ?

mais oui, c'est surprenant ...

[mike.p]

Mais par ailleurs, nous sommes dans la rubrique lycée pour un exercice de classe de seconde ... J'avais vu les matrices en 1re et pas Markov au lycée du tout ; je ne sais pas si c'est maintenant au programme de la seconde. ( non : Chaînes de Markov au lycée )


Pour le résoudre, il faudrait utiliser Markov en 5 pas manuels après avoir constaté que toutes les lignes étaient similaires. Et expliquer pourquoi ...
Surement un très bon exercice dans son contexte et un bon background pour ceux qui creuseront le sujet toujours en dev, visitez le youtube de l' Ihes , plusieurs confs récentes sur les marches et la stochastique.

[Verdurin]

Salut mike.p

Disons qu'un programme en C ne me semble pas non plus du niveau première.

Et que, dans le cas de trois positions sur le pont, j'aurais considéré trois états : au centre, au bord et dans l'eau. Ce qui donne la matrice



Bien sur on trouve le même résultat, en prenant les mêmes conditions initiales c'est à dire dans mon cas (1/3, 2/3, 0).

[mike.p]

Bonjour !

oui, mais je pense que l'autre forme est facile à transformer en phrasé pour une réponse à un exercice de lycée. Je "spacialise" la matrice ce qui crée et entretient les états intermédiaires, des fois que le problème soit étendu à un pont de largeur variable. Vous avez préféré tenir compte de la symétrie et incorporer le 0 du plouf que j'élimine si c'est une condition d'arrêt. On retrouve ses valeurs par différences. Question de style ... Votre matrice est tout aussi défendable mais plus difficile à expliquer à un néophyte qui ne raisonnera pas avec le formalisme.

Ceci dit, le primo posteur n'est pas revenu et le fil s'est endormi.