Bonjour Verdurin

Il me semble que posé comme ça le problème est extrêmement complexe . Une première chose à remarquer , on peut tout à fait supposer que l'abscisse de la puce est repérée par un entier naturel car le problème est clairement symétrique par rapport à 0 . Une deuxième chose , les probabilités élémentaires étant toutes les mêmes , il « suffirait » de compter , pour une case donnée , le nombre de trajets pouvant conduire la case initiale à 0 en un nombre donné de pas pour répondre au problème . Mais on tombe très vite sur un casse-tête car les deux mouvements possibles sont différents dans leur forme  et quand l'abscisse augmente le nombre de possibilités explose .

Je suis peut-être trop pessimiste

Imod    

salut

si on note le signe de n et sa position après le n-ième saut alors on peut peut-être formaliser ainsi :



chacun des deux cas ayant lieu avec la même probabilité 1/2

on peut alors écrire un script permettant de simuler la situation ...

car s(n) n'est autre que pour n non nul

Bonsoir,
oui le problème est complexe et on peut se limiter à rn prenant la valeur absolue de (position - k).
J'ai fait quelles simulations avec différentes valeurs de k et différentes positions de départ.

Pour k=2 on trouve, pour les départs de 1 à 15
E1=8.5,  E2=6.6,  E3=11.1,  E4=11.4,  E5=14.3,  E6=15.6,  E7=18.2,  E8=20.0,  E9= 22.39, E10=24.2,  E11=25.9,  E12=27.9,  E13=30.1, E14=31.9,  E15=33.8
La précision est de l'ordre de 0,2 pour les premiers tirages.

Pour k donné j'ai regardé dans l'autre sens comment remonter vers l'ensemble des entiers . Par exemple avec k=5 , on a une chaine simple 1->2>3>4>... qu'il faut combiner avec ...->15->10->5->0 mais aussi des éléments perturbateurs 1->4 ou 6->1 , 7->2 qui vont générer de nouvelles possibilités . En bref c'est un véritable capharnaüm , mais le problème est amusant et il y a peut-être des questions plus simples qui peuvent être intéressantes . J'en propose deux avec k et n donnés :

1°) Quel est le plus petit entier pouvant arriver à 0 en n étapes ( exactement ) ?

2°) Quel est le plus petit entier au delà duquel on ne pourra jamais atteindre 0 en n étapes ( ou moins ) ?

Je sais que je détourne un peu la question initiale et on peut ne pas s'y intéresser , on peut aussi ajouter ses propres interrogations

Imod

Bonjour,

@verdurin,

Tu écris : "et quand l'abscisse augmente le nombre de possibilités explose . "

Oui mais le nombre de sauts moyens ne grandit pas très vite.

A partir de tes exemples : k = 2
Le saut "moyen" est (-2 * 1/2 + 1 * 1/2) = -0,5

Donc par exemple en partant de la case 100, on revient vers 0 en 200 sauts et puis on se retrouve dans les cases proches de 0 et donc sur le début de ta liste
Donc E100 doit être un peu plus grand que 200 ...et une simulation informatique sur 1000000 tests répétés donnent E100 = 204 en moyenne.

En recommençant pour E50, on estime donc qu'il doit être un peu plus grand que 2*50 = 100 ...et une simulation informatique sur 1000000 tests répétés donnent E50 = 204 en moyenne.

Il n'empêche que trouver une "formule" mathématique pour le nombre moyens de sauts pour toutes cases de départ et toutes valeur de k semble bien ardu.

Zut erreur de copier-coller, dans mon message précédent, lire :

En recommençant pour E50, on estime donc qu'il doit être un peu plus grand que 2*50 = 100 ...et une simulation informatique sur 1000000 tests répétés donnent E50 = 104 en moyenne.

Bonsoir candide2.
Je n'ai jamais écris « quand l'abscisse augmente le nombre de possibilités explose » bien que se soit évidement vrai.
Si on part de la case n avec n grand devant k il est clair que l'on a le résultat que tu signales : l'espérance est à peu près 2n/(k-1)+constante.

On peut aussi remarquer que l'on peut calculer toutes les espérances pour k donné à partir de E(k) et E(k+1).
C'est ce qui me laisse espérer que le problème est résoluble.

Bonjour,
je me suis intéressé d'abord au cas .
Je note l'espérance du nombre de sauts pour atteindre 0 en partant de n.
A l'aide d'une relation de récurrence on peut calculer en fonction de et de :
où est la suite de Fibonacci (avec ).

Il reste à calculer mais si on veut il faut poser .

Cela donne finalement pour le cas :

Bravo jandri !
En te lisant j'ai vu que j'avais raté que E(k+1) s'exprime en fonction de E(k).

Pour les valeurs de k plus grande que 2 on va certainement avoir une formule du même genre, mais il faut résoudre qui a bien 1 comme racine évidente mais dont les autres racines semble compliquées.

Merci.

Bonjour,



pour k >= 2 :

1 solution x = 1
1 solution comprise dans ]2k/(k+1) ; 2[ qu'on peut trouver par approximations successives

Et si k est pair seulement, une 3éme solution comprise dans ]-1 ; -0,6[

Bonsoir candide2.
Les seules solutions qui nous intéressent ont un module strictement inférieur à 1.
Le raisonnement que tu as donné montre que la croissance de l'espérance  n'est pas exponentielle.
Mais on ne peut pas négliger les racines complexes.
Il suffit de regarder le cas k=3 pour s'en convaincre.

Dans le cas général on a polynôme qui a pour racines 1 et les avec et pour (ces sont des complexes).

On en déduit
Comme est de l'ordre de on a nécessairement d'où avec .

Dans le cas on a et

De plus donc tend assez rapidement vers 0.