Bonjour,

 Cliquez pour afficher

Sans grande conviction je propose 43

Bonjour dpi, quelque soit la réponse un minimum de developpement serait apprécié

Bonsoir Flight

Qu'attends-tu exactement ? Le problème fait penser à une variante d'une marche aléatoire dans Z² . Le graphe des déplacements est déjà assez complexe si on se limite au carré [-3,+3] X [-3,+3] alors si on  passe à la 5ème dimension ... Si tu veux une simulation informatique , c'est autre chose

Imod

Bonjour flight,

en résolvant un système de 15 équations à 15 inconnues (avec l'aide d'un logiciel) j'ai trouvé la valeur exacte de l'espérance du nombre de déplacements :

 Cliquez pour afficher

 Cliquez pour afficher

Le résultat trouvé par dpi correspond plutôt à , c'est-à-dire à la sortie du carré et .

Bonsoir,
Je suis parti de l'idée que le minimum est 5
il n'y a pas de maximum puisque  un mobile idiot peut faire exprès de ne pas sortir

Alors j' ai pensé à une spirale "carrée" de 81 segments comme parcours maximum logique...
Toutes les valeurs de 5 à 81 donnent une moyenne de 43 .

@dpi

je comprends ton approche mais cela ne donne pas du tout la moyenne demandée.

Bonjour à tous

@Jandri , j'ai une valeur pas trop voisine de la tienne ....voici mon code quand meme :

Function co(x As Double, y As Double, k As Integer) As Integer
Dim choix As String
Randomize
t = Array("H", "B", "G", "D")
If x = 5 Or x = -5 Or y = 5 Or y = -5 Then  'condition de sortie
    co = k     ' retourne le nombre de deplacements obtenus quand le
                        mobile atteint x=5 ou x=-5 ou y=5 ou y=-5
    Else
     choix = t(Int(Rnd * (UBound(t) + 1)))
     Select Case choix
        Case Is = "H"
          co = co(x, y + 1, k + 1) 'on monte d'une graduation
        Case Is = "B"
          co = co(x, y - 1, k + 1)  'on descend d'une graduation
        Case Is = "G"
          co = co(x - 1, y, k + 1) ' on va vers la gauche d'une graduation
        Case Is = "D"
          co = co(x + 1, y, k + 1) 'on va vers la droite d'une graduation
     End Select
End If
End Function
'****'ici je calcul la moyenne du nbr de déplacements dans la routine ci deesous:
Sub BCRE()
e = 0  'compteur de boucles
q = 0 'valeur qui cumule les déplacements "k"
do
e = e + 1
q = q + co(0, 0, 0)
Loop Until e = 100000
MsgBox q / e  ' me retourne  26.4
End Sub

@Flight

Je ne vois pas d'erreur dans ton code.
Essaie-le avec n=2 (arrêt quand on atteint ou ) : tu dois trouver

Voici le code Maple de la fonction que j'ai utilisée pour un calcul approché (pour une grille de côté 2n) :

x:=0: y:=0: c:=0:
while and do
c:=c+1:
k:=r(): # renvoie un entier aléatoire entre 1 et 4
if k=1 then x:=x+1
elif k=2 then x:=x-1
elif k=3 then y:=y+1
else y:=y-1 fi
od;
return(c)

Bonsoir Jandri , en prenant n =2 , j'obtiens exactement 4,329
(j'ai meme augmenté le nombre d'itérations à 1 million)

Flight

J'ai traduit ton programme en Maple (j'aurais pu le faire en Python) et pour n=5 et 1 million d'itérations je trouve 29,24 (exactement comme avec mon programme) donc ton programme marche bien pour moi.

Je ne connais pas Visual Basic mais j'ai un doute pour la fonction Ubound que tu utilises dans l'instruction :
choix = t(Int(Rnd * (UBound(t) + 1)))

Peux-tu faire des essais pour vérifier que cela donne bien les "H", "B", "G", "D" aléatoirement ?

Il est clair que pour un cadre limité à 2 , la réponse est 4,5 mais il semble que l'estimation par essais successifs fluctue pas mal . Pour une limite à 5 , mon estimation à la louche donnerait plutôt une moyenne 29,36 , mais bon ...

Imod

Bonjour jandri , j'utilise assez couramment l'expression
Int(Rnd * (UBound(t) + 1))   ici cette quantité peux prendre de facon équiprobable ,  les valeurs {0,1,2,3}   , (le tableau t  ayant chacune de ses valeurs indexée aux  rangs :  0,1,2 et 3 . pour  "H", "B", "G", "D".
Aux premieres lignes du programme figure l'instruction "Randomize" qui justement rend ce choix equiprobable via l'instruction Rnd

Bonjour Flight

D'accord mais je ne vois pas du tout pourquoi tu ne trouves pas comme moi avec pratiquement le même programme !

Je suis à peu près sûr de mon résultat (29,24 pour n=5) car je l'obtiens par deux programmes différents et surtout c'est la valeur approchée du résultat exact que j'obtiens par résolution d'un système.

Pour n=2 ta valeur approchée 4,329 est trop loin du résultat exact 9/2=4,5.

Le problème a viré sur l'aspect programmation mais je serais plutôt intéressé par une valeur exacte par exemple pour un cadre [-3 ; +3] X [-3 ; +3] .

Imod

Bonjour Imod

Pour le cas j'obtiens en résolvant un système de 6 équations à 6 inconnues (c'est faisable à la main).

Si est l'espérance du temps d'atteinte du bord en partant du point on a (avec les symétries) :

D'accord , j'avais le graphe des probabilités mais je n'avais pas traduit en termes d'espérances . On obtient un simple système linéaire .

Imod

Bonjour ,

je ne m'explique pas ces ecarts dans nos simulations ....j'ai beau retourner la question dans tout les sens ...

une interrogation qu'il vient est qu'une simulation fournie systematiquement une valeur finie pour l'esperance alors qu'il est tout à fait possible que le mobile n'atteigne jamais les bord du grillage

il y a donc "du presque sûrement certain" que le mobile va atteindre une limite du grillage "

Bonjour
Le point (2,2) ne peut jamais être atteint (alors que .... message de 11h32) car à (2,1) on s'arrête.

Autour de l'origine il y a 4 points possibles d'égale valeur. Pour chacun de ces points (0,1 par exemple) on peut les atteindre en 1 déplacement avec 1chance sur 4 ou en 3d en 3/64 ou en 5d en 5/1024 ou ... soit :
1d/4 + 3d/64 + 5d/1024 + ...
Pour le point (1,1) (4 pts id), on obtient :
4d/16 + 8d/256 + 12d/4096 + ...
Pour le point (0,2) (4 pts id), limite atteinte, on obtient :
2d/16 + 4d/256 + 6d/1024 + ...
Pour le point (1,2) (8 pts id), limite atteinte, on obtient :
5d/64 + 9d/1024 + 13d/16384 + ...
Reste à calculer tout ça.

@Derny

Tu n'as pas bien lu ce que j'ai écrit le 29-07-23 à 11:32

Je me plaçais dans le cas donc on ne s'arrête pas à (2,1).

Excuse jandri
Pour le cas le plus "simple" (de -2 à +2), c'est déjà pas simple ...

@ flight

J'ai traduit ton programme en python, je trouve toujours environ 29,24 (pour n=5) :

import random

def co(x,y,k):
if x==5 or x==-5 or y==5 or y==-5:return(k)
c=random.randint(0, 3)
if c==0:return(f(x, y + 1, k + 1))
elif c==1:return(f(x, y - 1, k + 1))
elif c==2:return(f(x+1, y, k + 1))
else:return(f(x-1, y, k + 1))

q=0
e=100000
for i in range(0,e):
q = q + f(0, 0, 0)
print(q/e)

Bonjour
Les valeurs données un peu vite le 30 à 16h06 ne sont pas bonnes : à revoir

Bonsoir Jandri , impossible pour moi d'expliquer cette difference ...
j'ai meme remodifié mon code en retirant le tableau et en ecrivant simplement :

Function co(x As Double, y As Double, k As Integer) As Integer
Dim choix As String
Randomize

If x = 5 Or x = -5 Or y = 5 Or y = -5 Then
    co = k
    Else
     choix = Int(Rnd * 4)
     Select Case choix
        Case Is = 0
          co = co(x, y + 1, k + 1)
        Case Is = 1
          co = co(x, y - 1, k + 1)
        Case Is = 2
          co = co(x - 1, y, k + 1)
        Case Is = 3
          co = co(x + 1, y, k + 1)
     End Select
End If
End Function
Sub BCRE()
Dim q, e As Double
e = 0
q = 0
Do
e = e + 1
q = q + co(0, 0, 0)
Loop Until e = 1000000
MsgBox q / e
End Sub

j'obtiens 26,9  .... :?

Flight

Je ne comprends pas pourquoi tu utilises le type "Double" pour x et y (ce sont des entiers). Le test d'égalité entre deux variables de type "Double" est approximatif.

Essaie plutôt avec le type "Integer".

Bonsoir Jandri j'ai effectué ce changement , la valeur obtenue est environ 26,9  en changeant les  les types de x et y en "integer"

Bonsoir
J'ai repris plus sérieusement mes chiffres et sommations.
Si cela peut "vous départager" je trouve exactement 4.5 d pour un carré de -2 à 2.

Flight

Merci d'avoir fait le test. Je n'ai donc pas trouvé d'explication.

Derny

Je suis d'accord : 4,5 est la valeur exacte pour n=2.

Bonjour
Je reviens sur ce problème. Coup de chapeau à jandri qui, outre la résolution par programme, à résolu élégamment hors programmation grâce à l'espérance.  C'est le type de problème qui se prête à ce genre de résolution. La méthode avec laquelle j'étais parti est beaucoup trop laborieuse.

@Derny , tu peux maintenant utiliser les mêmes arguments pour répondre ( si tu le souhaites ) à Déplacements 2

Imod

Bonjour
Notons que la simple fonction N=n^2.1 donne une bonne approximation jusqu'à n=5. N'ayant pas les chiffres au-delà je ne peux pas dire si l'approximation continue.

Voici des chiffres au-delà



J'ai comme approximation avec la limite du repère et le nombre de dimensions du repère.

Ça ne marche pas bien pour les petites limites mais ça marche bien pour .

Bonjour
Super LittleFox
Peut-on avoir les valeurs exactes pour quelques valeurs au-delà de 5 en dimension 2 puisque les programmes sont faits (Jandri ou ... ) ?

Bonsoir Derny

Les valeurs exactes sont des nombres rationnels avec des entiers qui deviennent vite grands.

Par exemple pour on trouve

Voici des valeurs approchées avec deux chiffres après la virgule.

Pour n de 2 à 10 : 4.50, 10.38, 18.63, 29.24, 42.20, 57.53, 75.21, 95.25, 117.64

Pour n de 11 à 20 : 142.40, 169.51, 198.98, 230.80, 264.99, 301.53, 340.42, 381.68, 425.29, 471.26

Pour n de 21 à 30 : 519.59, 570.28, 623.32, 678.72, 736.48, 796.60, 859.07, 923.90, 991.09, 1060.64

Pour n de 31 à 35 : 1132.54, 1206.80, 1283.42, 1362.39, 1443.73

Après les temps de calcul deviennent longs : pour n=35 c'est un système de 630 équations à 630 inconnues !

Bonjour
Merci Jandri. On peut même trouver la fonction qui donne le nombre d'équations en fonction de n (je n'ai pas cherché mais ce ne devrait pas être trop difficile).

Pour des raisons de symétrie le nombre d'équations et d'inconnues est n(n+1)/2 .
Imod