La marche de la fourmi

[invite970ffd48]

Bonjour à tous,

Je viens de mettre la main une série de problèmesde logique et de math vraiment difficile que je n’arriverai sûrement jamais à résoudre alors évidemment je me suis dit qu’il serait agréable de vous partager mes maux de têtes … un à la fois …


La Marche de la fourmi:


Une fourmi se tien au centre d’un cercle de 3 mètres de diametre et décide de marcher en ligne droite dans une direction aléatoire (entre 0 et 360 degrés ) Cependant, elle ne peut que marcher 1 mètre à la fois car elle doit se reposer entre chaque déplacement. Comme si ce n’était pas suffisant , la fourmi à une mémoire de poisson et elle oubli toujours la direction vers laquelle elle vient de marcher, ainsi elle repart toujours dans une direction aléatoire ( entre 0 et 360 degrés)

Comme vous vous en doutez, elle peut quitté le cercle après 2 déplacements, mais elle pourrait aussi prendre 20 000 déplacements sans jamais quitter le cercle…

Alors, selon vous; Quel est le nombre moyen de déplacement nécessaire afin de quitter le cercle ?

Je vous rappel que je n'ai pas la réponse !
-----

[Gunman]

A priori je dirais qu'il n'y a pas de nombre moyen de déplacements puisque celui-ci est compris entre 0 et l'infini. A la limite on peut calculer les probabilités pour la fourmi de sortir du cercle en un nombre n de déplacements(ou l'inverse).

[Médiat]

En faisant un petit dessin et un calcul d'angle au centre je trouve 4arcos(0.75)/360 (sans garantie, il est tard ), soit environ 46%, pour la probabilité de le faire en deux mouvements, mais après ... , cela me rappelle un autre petit problème où le résultat était e (2.718...), je ne serais pas étonné que ce soit la même chose.

[Médiat]

A priori je dirais qu'il n'y a pas de nombre moyen de déplacements puisque celui-ci est compris entre 0 et l'infini. A la limite on peut calculer les probabilités pour la fourmi de sortir du cercle en un nombre n de déplacements(ou l'inverse).

En appelant p(k) la probabilité pour la fourmi de sortir du cercle en un nombre k de déplacements, l'espérance mathématique, si elle existe, est :

Pour te donner un exemple plus intuitif, si tu lances un dé et que tu te demandes quel est le nombre moyen de lancers pour obtenir le six, tu pourrais faire la même objection "il n'y a pas de nombre moyen de lancers puisque celui-ci est compris entre 1 et l'infini", et pourtant, ce nombre est égal à 6 (assez intuitif et facile à démontrer).

[A voir en vidéo sur Futura]

[invite970ffd48]

intéressant tout ça Médiat,


mais on va voir si certain auront d'autre propositions ...

par ailleur, Gunman le nombre de déplacement est compris entre 2 et l'infini et non 0 ...

[cherve]

Bonjour!
Au moment d'effectuer son deuxième déplacement , la fourmi est à 0.5 m du bord .si on considère son "rayon d'action" de 1 m (on trace donc le cercle de 1 m de rayon ayant comme centre la fourmi, on peut alors
déterminer les angulations qui lui permettent avec un trajet de 1 m de sortir du cercle et on a la probabilité de réussite en 2 coups.

Je ne suis pas assez doué en trigonométrie ou en géométrie pour faire le calcul mais c'est de l'ordre de 45 %. pour les coups suivant cela dépasse mes capacités (hélas!).
CHERVE

[cherve]

Remarque complémentaire . si après le deuxième coup , la fourmi se trouve à la limite de la sortie (quasiment sur le cercle..) tracer le cerlce de 1 m de rayon donnant son autonomie montre qu'elle a encore une probabilité avoisinant (je ne sais toujours pas calculer...) les 30 % de ne pas sortir!).
CHERVE

[invite970ffd48]

effectivement, je constate qu'avec un simple compas et un rapporteur d'angle on peut calculé assez précisement certaines probabilité ...

[Gunman]

En appelant p(k) la probabilité pour la fourmi de sortir du cercle en un nombre k de déplacements, l'espérance mathématique, si elle existe, est :

Pour te donner un exemple plus intuitif, si tu lances un dé et que tu te demandes quel est le nombre moyen de lancers pour obtenir le six, tu pourrais faire la même objection "il n'y a pas de nombre moyen de lancers puisque celui-ci est compris entre 1 et l'infini", et pourtant, ce nombre est égal à 6 (assez intuitif et facile à démontrer).

Et je me demande pourquoi j'ai eu une mauvaise note en probabilités l'année dernière

(et oui évidemment je voulais dire entre 2 et l'infini, pas fait attention)

[danyvio]

Hello ! Je me suis amusé à simuler le parcours de la fourmi. Pour cela, j'ai considéré le point d'arrvée de la fourmi à chaque étape comme le troisième sommet d'un triangle, ayant pour autres sommets le centre du cercle et le point d'arrivée de l'étape précédente. L'angle étant donné par une fonction aléatoire, en l'occurence ALEA()*2*PI() d'Excel.

J'ai dû réviser un peu mes connaissances sur la résolution des triangles quelconques .

A défaut d'un approche théorique du problème, que je laisse à d'autres, le résultat est intéressant. 100 expériences donnent la sortie de la fourmi du cercle au bout de :
2 fois : jamais
3 fois : 34 fois
4 fois : 19 fois
5 fois : 13 fois
6 fois : 12 fois
7 fois : 5 fois
8 fois : 3 fois
9 fois : 5 fois
10 fois : 2 fois
12, 13, 15, 17, 18,19,26 fois : 1 fois chacun
Voili voilou... et vive Excel...
Il est intéressant aussi de remarquer que lorsuqe la fourmi est franchement sortie du cercle (à 2,5 du contre) elle n'y revient pratiquement jamais...

[Médiat]

2 fois : jamais

Je trouve cela très bizarre, non parce que j'ai trouvé 46% de chance (je peux planter lamentablement), mais parce que "à vue de nez", 46% est une valeur tout à fait plausible.

[invite970ffd48]

effectivement, il ce "jamais" me semble surprenant, car avec une certaine logique l'angle de déplacement lui permettant de sortir du cercle lors du deuxième déplacement est relativement large non ?

[danyvio]

Je dois préciser que par nombre de déplacements, j'inclus le déplacement initial à partir du centre du cercle. C'est peut-être là l'origine de nos différences d'appréciation. Il est en tout cas peu probable de sortir en deux déplacements: le deuxième impliquerait un angle de exactement , et placerait la fourmi sur la circonférence.

[invite35452583]

Je trouve à peu près 3,5 comme moyenne en simulation numérique.
Sinon un traitement rigoureux me semble impossible.
On peut certes utiliser la symétrie circulaire pour passer de la situation après n déplacements à la situation après n-1 déplacements. Il suffit de connaître la distance au centre L ou plus exactement la densité (pour n>1) de probabilité de la distance au centre.
Au départ P(L₁=1)=1.
Ensuite, à calculer la probabilité que L₂ soit entre 1+r et 1+r+dr vaut, on passe à la limite on a la densité de la loi de L₂. On peut calculer (de manière compliquée mais par cette voie on peut attaquer les rangs suivants) la probabilité de sortie au 2ème rang.
Ensuite le procédé ci-dessus permet de calculer les probabilités conditionnelles P(L_n+1=r' / L_n=r) (indépendante de n celle là)
On peut alors calculer la densité de L_n+1.
On peut alors calculer la probabilité de sortie au rang n+1, puis itérer pour calculer d_n+2...
Il n'y a plus qu'à...
Et je ne vois guère d'autres méthodes que ce calcul (qui à mon avis est impossible à mener jusqu'au bout)
Autant simuler numériquement.

[invite35452583]

Je dois préciser que par nombre de déplacements, j'inclus le déplacement initial à partir du centre du cercle. C'est peut-être là l'origine de nos différences d'appréciation. Il est en tout cas peu probable de sortir en deux déplacements: le deuxième impliquerait un angle de exactement , et placerait la fourmi sur la circonférence.

tu as pris un rayon de combien ? Pas de 1,5 apparemment.

[invite970ffd48]

Bonjour,

il semble effectivement ne pas avoir pris 1,5 comme rayon, car avec un simple shéma à l'échelle on voit que la fourmi aura au environs de 45% de chance de sortir au deuxième déplacement ...

Je crois que pour calculé les chances de sortir en 2 déplacement on peut le faire en calculant le rapport de l'aire possible du cercle correspondant à l'endroit où peut se situé la fourmi dans l'espace après 2 déplacement où 2 est ldonc e r du cercle (1m par déplacement)

exemple : après 2 déplacement la fourmi doit se situé dans un cercle possédant un rayon de 2m par rapport à son point d'origine

Ainsi le disque central mesurant 1,5m X 1,5m X 3,1416 = 7,0686

Et le cercle correspondant à l'endroit où elle se situe mesurant 12,5664

on peut calculé la probabilité pour que la fourmi e toruve dans le disque en faisant un simple rapport des aires puisqu'au deuxieme déplacement chaque des point du cercle #2 à une probabilité égale de voire la fourmi s'y trouver ...

donc : 7,0686 / 12,5664 = 0,5625 donc 56,25% de chance que la fourmi soit sur le disque et ainsi donc 43,75% de chance qu'elle n'y soit pas,

sur 100 essai elle sera donc à l'extérieur 44 ou peut-être 43 fois ...

par contre je ne sais pas trop comment calculer pour 3 déplacement car pour un point donné les chances de voir la fourmi s'y trouvé ne sont pas les même ( à partir de 2m de distance du point d'origine il y a moins de chance d'y voir la fourmi après 3 déplacement ... )

( j'ai fais le calcul alors que j'écrivais ces lignes vous devrai m'excuser si cela semble confus ... )

[invite35452583]

on peut calculé la probabilité pour que la fourmi e toruve dans le disque en faisant un simple rapport des aires puisqu'au deuxieme déplacement chaque des point du cercle #2 à une probabilité égale de voire la fourmi s'y trouver ...

Non, la densité de probabilité est plus fortement concentré vers r=2 (bien que "diluée" sur des cercles grands mais ça ne compense pas) et vers r=0.

Réglons le cas "en 2 pas". Soit O le centre du cercle, M un point (où on supposera où est la fourmi après "un pas") situé à une distance de 1 de O. I et J les points d'intersection du cercle C de centre 0 et de rayon 1,5 et du cercle C' de centre M et de rayon 1. La probabilité de sortie en 2 pas est égale à (360-mesure de l'angle en degré (IMJ) contenant O)/360. or en mesure d'angle on a (IMJ)=2(IMO)=4(PMO) où P est le pied de la hauteur issue de M du triangle isocèle en M IMO. On a puisque ce triangle est isocèle en M OP=IO/2=0,75. Donc dans le triangle rectangle en P MPO, sinus(PMO)=0,75.
Ainsi, proba =1-arcsin(0,75))/90 si on travaille en degré ou encore
proba=1-2arcsin(0,75)/pi si on travaille en radian.
proba=0,46011.

[Médiat]

proba =1-arcsin(0,75))/90 si on travaille en degré [...] proba=0.46011

Nous n'avons pas raisonné de la même façon, mais les résultats sont identiques (ouf !)

je trouve 4arcos(0.75)/360 (sans garantie, il est tard ), soit environ 46%,

[invite35452583]

Nous n'avons pas raisonné de la même façon, mais les résultats sont identiques (ouf !)

Oups, la lumière extérieure cachait une partie de mon écran.
En plus, mon ordinateur a refusé de faire apparaître le post#3.


Bon d'accord, je réapprends à lire l'entièreté des posts, désolé.

[Médiat]

Bon d'accord, je réapprends à lire l'entièreté des posts, désolé.

Il n'y a aucune raison, au contraire, je suis ravi que tu confirmes

[danyvio]

tu as pris un rayon de combien ? Pas de 1,5 apparemment.

Oh Honte J'ai pris un rayon de 2 ! Je m'y recolle

[invite970ffd48]

Bha je suis complètement largué !! mais au moins j'ai la satisfaction d'avoir trouvé un bon problème à présenter sur FS chose rare depuis quelques mois !


Je voudrais ramener à la question initale par contre,

Quel sera le nombre de déplacement moyen ?

[danyvio]

Citation:
Posté par homotopie
tu as pris un rayon de combien ? Pas de 1,5 apparemment.

Après avoir changé un p'tit paramètre (le rayon = 1.5 et non 2) voici le résultat : la première colonne est le nombre de trajets pour sortir du cercle, la deuxième colonne est le nombre de fois (sur 100 tests) où la fourmi est sortie par ce nombre de trajets.
Nombre 2 53
Nombre 3 16
Nombre 4 11
Nombre 5 7
Nombre 6 7
Nombre 7 3
Nombre 8 2
Nombre 9 1
Nbval 100

[invite970ffd48]

intéressant, le résultat ne correspond pas au résultat donné par homotppie et médiat ...

qui a raison ?

[prgasp77]

Bonjour à toutes et à tous.
Je me suis penché sur cet exercice, et j'ai tenté de le résoudre complètement en calculant la probabilité pour que la fourmi sorte du disque pour la première fois au n-ième "pas".

Le soucis est qu'on arrive à un résultat non intégrable (pas même pour Mathematica). J'ai tenté de faire avec, mais ça alourdi violemment les calculs et j'ai commis une erreur de calcul.

Voila comment j'ai procédé si ça intéresse :

1. Le problème est invariant par rotation autour du centre du disque, on ne s'intéresse donc qu'à la distance entre la fourmi et ledit centre O ;
   
2. Soit la variable aléatoire de la direction prise par la fourmi lorsqu'elle commence un "pas" ;
   
3. On a évidemment
   
   
4. Soit la variable aléatoire décrivant la longueur rapportée d'un "pas", définie par , du coup
   
   
   
5. Soit la variable aléatoire décrivant la distance de la fourmi au n-ime "pas", définie par
   
   
   Ainsi,
   
   
   Et,
   
   
6. Enfin, la probabilité que la fourmi soit sortie au bout du n-ieme "pas" est la valeur de . Alors, la probabilité que la fourmi sorte du disque pour la première fois au n-ieme "pas" est
   

En conclusion,
je dirais que cette probabilité est soit impossible à exprimer explicitement, soit que j'ai fais une grosse bourde. Si quelqu'un est motivé pour reprendre les calculs ... bonne chance.
À vous Cogna-G ! À vous les studios !

[prgasp77]

Erratum
à partir du "Ainsi" du point 5, prendre n=n-2 (erreur de borne) pour les termes de droite (les exposant en n)

[invite35452583]

intéressant, le résultat ne correspond pas au résultat donné par homotppie et médiat ...

qui a raison ?

Médiat et moi... et aussi danyvio. Le "hic" est que danyvio ne l'a fait que sur une population relativement faible (100 simulations) donc que très partiellement représentative mais dans des bornes "acceptables" malgré tout.

Pour ma part, j'ai simulé ainsi par Excell :
1) approximation discrète de la formule exacte donnée au #14 (en laissant quelques fonctions non définies, la flemme à ce moment là de les calculer).
Le principe est le suivant : on calcule pour les premiers rangs (Excell l'a fait jusqu'au rang 250 environ, limite de sa capacité) la probabilité que la fourmi soit dans un intervalle de longueur dr (en l'occurence j'ai pris dr=0,01 après excell et ma bécane ont du mal, ça commence par deux tableaux de 150x150=22500 cellules quand même).
L'approximation (en plus de l'approximation due aux limites de la bécane : elle ne calculera jamais toutes les décimales) qui est faite est : pour passer de l'étape n à l'étape n+1, on suppose que lorsque la fourmi est dans un intervalle [R-dr/2;R+dr/2[ elle est en R.

Comment passer de l'étape n à l'étape n+1 ?
Pour un intervalle [R-dr/2;R+dr/2[, on calcule toutes les possibilités (c'est la bécane qui va calculer, ...ouf!)
On a P_n+1([R-dr/2;R+dr/2[)=
Probabilité (fourmi va de r=0+dr/2 à [R-dr/2;R+dr/2[)xProba que la fourmi soit à l'étape n en r=dr/2 (ce qui correspond, selon l'approximation, r est entre 0 et dr)
+Probabilité (fourmi va de r=dr+dr/2 à [R-dr/2;R+dr/2[)xP)xP_n(r=dr+dr/2)
+P({R-dr/2 <= r <R+dr/2} / {r=2dr+dr/2})xP_n(r=2dr+dr/2)
...
+P({R-dr/2 <= r <R+dr/2} / {r=k.dr+dr/2})xP_n(r=k.dr+dr/2) (k étant un entier allant de 0 à 1,5/dr, dr est choisi pour que ce soit un entier N qui est le nombre d'intervalles de même longueur qui "découpent" l'intervalle 0 ; 1,5] càd toutes les k possibles tels que 0<k.dr+dr/2<1,5)
...
+P({R-dr/2 <= r <R+dr/2} / {r=1,5-dr/2})xP_n(r=1,5-dr/2)

Calcul des P({R-dr/2 <= r <R+dr/2} / {r=S}), les S seront les k.dr+dr/2
Ramenons ceci à un seul autre calcul (plus "élémentaire")
P({R-dr/2 <= r <R+dr/2} / {r=k.dr+dr/2})=P({r <R+dr/2} / {r=k.dr+dr/2})-P({ r <R-dr/2} / {r=k.dr+dr/2}) La fourmi se trouve entre R-dr/2 et R+dr/2 s'il est à une distance moindre que R+dr/2 mais n'est pas à une distance moindre que R-dr/2 (en français plus conventionnelle mais plus long à écrire)
On est ramené (pour l'instant) à calculer les P({r<T} / {r=S}) (càd quelle est la probabilité que r<T quand la fourmi est en r=S).
Deux cas faciles :
i) T<lS-1l (l.l=valeur absolue) donc dans ce cas P({r<T} / {r=S})=0
ii) TS+1<T donc dans ce cas P({r<T} / {r=S})=1
Un petit dessin montre tout de suite que lS-1l est la valeur minimale pour la distance d'un point Q à O si Q est à une distance de 1 de M celui-ci étant à une distance S de O et S+1 est la valeur maximale.
iii) un cas plus délicat : lS-1l<T<S+1 (les cercles se coupent)
Sinon on fait un dessin, on place un point O (le départ de la fourmi), un point M (le point auquel elle strouve) OM=S. On trace les cercles C de centre M et de rayon 1, et C' le cercle de centre O de rayon T. Ils se coupent en deux points (symétriques par rapport à (OM)) I et J, on peut projeter ceux-ci en un même point P. On prend un repère northonormé d'origine M, le 1er vecteur i va de O vers M (en tout cas c'est celui que j'ai choisi) et un deuxième orthogonal. On a :
M : (0,0)
O : (-S,0)
I : (x,y) J : (x,-y) P : (x,0)
On a x²+y²=1 (I et J sont sur C)
et (x+S)²+y²=R² (I et J sont sur C')
D'où R²=x²+2Sx+S²+y²=2Sx+x²+y²+S²=2 Sx+1+S²
x=(R²-S²-1)/(2S)
On vérifie qu'en R=lS-1l x=-1 qu'en R=S+1 x=+1.
On peut donc calculer le cosinus de l'angle (i,OI) (c'est x) donc une bécane peut calculer cet angle (ACOS(angle) sur Excell, il le donne en radian.)
La probabilité recherchée vaut 1-(2xangle calculée)/(2pi)=1-angle/pi (mon choix n'était peut-être pas le plus intelligent).
A remarquer que, cette formule reste valide dans les cas i) et ii) en prenant comme cosinus -1 dans i) et +1 dans ii).
Un tableau Excell calcule les cosinus pour les les multiples de dr (les bornes des intervalles) et les S (les centres de ces intervalles). (SI(lS-1l>R;-1;SI(R>S+1;+1;(R²-S²-1)/(2S))
Un autre tableau calcule les probabilités P({R-dr/2 <= r <R+dr/2} / {r=S=k.dr+dr/2})=(ACOS(cosinus calculé pour R-dr/2)-Acos(cosinus calculé pour R-dr/2))/PI() (Par soustraction les "1" de la formule disparaissent)

Il reste à initier ceci : donc à calculer la répartition pour n=2, on utilise les formules ci-dessus appliquées à S=1 (la fourmi au rang 1 est toujours à une disatnce égale à 1) La formule pour x devient x=R²/2-1 (valide pour toutes les valeurs de R, pour la proba la même formule avec les ACOS.

Proba que la fourmi soit sortie avant l'étape n (comprise)=1-proba qu'elle soit encore là au rang n=1-somme des probas qu'elle soit en r=k.dr+dr/2
Proba qu'elle sorte au ran g n=proba "avant n"-proba "avant n-1"
Moyenne du rang de sortie=somme sur n (proba "rang=n"xn)

Cette méthode est sur de converger vers les valeurs cherchées mais il faut faire un calcul théorique pour estimer l'erreur (que je n'ai pas envie de faire). Cette erreur peut être estimé en comparant avec des simulations (mais nettement plus nombreuses que 100).

2) simulation numérique

en n=2, r=1
ALEA*PI() pour simuler un angle (en radian) pris par rapport à la direction et le sens éloignant la fourmi (autrement dit r augmente de 1 si cet angle=0) C’est équivalent à prendre cet angle avec comme référence à chaque direction fixe car ça attribue à chaque angle de direction la même valeur.
pour calculer la distance suivante (r' la distance au rang n, égale à 1,5 si la fourmi est sortie, a l'angle aléatoire) nouvelle distance:
SI(r'=1,5 ; 1,5 ; MAX(1,5 ; RACINE((r'+COS(A))^2+sin(A)^2) ))
N lignes allant jusqu'au rang (ou étape) n.
Stockage des valeurs de plusieurs séries.
2 séries de simulations :
50x5.000 (250.000 simulations) allant jusque n=20
10x10.000 (1.000.000 simulations) allant jusque n=6.
Calcul des sorties grace à un NB.SI([les r pour un n donné] ; =1,5).
Le traitement des résultats est simple après.

Résultats (en %) :


Les résultats à partir de n=14 se font sur moins de 901 "fourmis", à partir de n=18 sur moins de 73 "fourmis",, 26 "fourmis" cherchaient encore la sortie.
Les résultats même pour n relativement grands sont très concordants, l'approximation dr=0,01 est donc suffisante pour sortir quelques conclusions.

Et la moyenne :
pour le 50x5.000 3,52807, pour le calcul par approximation 3,52945 soit un écart de 0,04%
pour le 10x10.000 le calcul est limité à n=6 mais ceci donne 2,73657 et pour l'approximation 2,73748 soit un écart de 0,03%
L'approxiamtion donne de surcroît ceci : la répartion entre le rang n et le rang n+1 est une simple division par 1,586 environ (dès n=6, ceci est vraie pour toutes les r à qqes % près max en gros, pour n=15 c'est vrai à 1/1000) (C'est encore plus rapide pour la proba de sortir)*. Ceci implique que la somme des termes nP(fourmi sort en n) pourn>N est du même ordre que NxProba de sortir en N (donc négligeable ici).
* ça converge vers une fonction propre indépendante après quelques autres essais de répartition autres pour n=2 (répartition uniforme, concentrée en r=0,5...)
On peut donc affirmer raisonnablement que la fourmi sort en moyenne en 3,529 coups à +/-0,002.

prgasp77, ta méthode par transformée de Fourier peut sans doute être intéressante mais n'as-tu pas oublié qu'il fallait empêcher la fourmi de revenir à moins de 1,5 du point d'origine une fois fait (je ne vois trace de cela nul part dans tes formules).

[prgasp77]

homotopie, cf le point 6 de mon message :

6. Enfin, la probabilité que la fourmi soit sortie au bout du n-ieme "pas" est la valeur de . Alors, la probabilité que la fourmi sorte du disque pour la première fois au n-ieme "pas" est

[invite35452583]

Certes, mais j'ai l'impression que est la probabilité qu'une fourmi se trouve au rang n à une distance au moins de 1,5 m mais cette fourmi se déplace "librement" dans le sens où elle peut très bien faire un parcours r=0->r=1->r=1,6->r=1,3->r=1,9->r=1,7->r=1,4 (elle respecte la règle "un déplacement unitaire aléatoire avec la bonne densité à chaque étape" mais pas la règle "elle ne revient jamais à moins de 1,5m quand elle l'a déjà fait une fois").
(désolé si je me trompe je ne suis plus au point sur cette branche de l'analyse)

[prgasp77]

En réalité, on est dans le faux tout les deux (moi plus que toi, certes).
soit la probabilité pour qu'au n-ieme "pas" la fourmi soit sur le disque.

Ainsi, la valeur est bien la probabilité pour que la fourmi soit hors disque au n-ieme "pas".

En continuant, est la probabilité pour que la fourmi soit sortie du disque au n-ieme "pas" ; mais comme tu l'as fait remarquer, rien ne nous dit qu'il s'agit de la première sortie.

Il doit bien exister une manière de traiter le problème autrement que par simulations ...