Promenade aléatoire dans les groupes.
Bonjour,
Promenade aléatoire dans les groupes :
Soient $f(x)=3x+1$ et $g(x)=2x$ fonctions affines.
On part de $id(x)=x$ à la quelle on compose soit $f$, soit $g$ de manière équiprobable, on note $r(x)$ la fonction résultat.
Quelle est la probabilité qu'au bout de 100 compositions, on ait $r(x)-id(x) \mod 5=0$ ?
PS : il n'est pas nécessaire de résoudre explicitement le problème, il suffit de préciser une attaque réalisable en moins de 10 minutes avec un PC actuel.
Bonne journée.
Promenade aléatoire dans les groupes :
Soient $f(x)=3x+1$ et $g(x)=2x$ fonctions affines.
On part de $id(x)=x$ à la quelle on compose soit $f$, soit $g$ de manière équiprobable, on note $r(x)$ la fonction résultat.
Quelle est la probabilité qu'au bout de 100 compositions, on ait $r(x)-id(x) \mod 5=0$ ?
PS : il n'est pas nécessaire de résoudre explicitement le problème, il suffit de préciser une attaque réalisable en moins de 10 minutes avec un PC actuel.
Bonne journée.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Après N compositions, le probabilité est 0 si N impair et 50% si N pair
EDIT : C'est faux. J'ai oublié de prendre un élément en compte...
énoncé 126 : la très longue marche aléatoire.
Quelle est la probabilité qu'au bout de $2^{100}$, on ait $r(x)-id(x)=0 \mod 5$ ?
PS : inutile de faire les calculs une attaque réalisable (moins de 10 min sur un PC), pour connaître le nombre de chemins souhaités $\mod p$ (avec p entier premier quelconque plus petit que 1000) est suffisant.
Quelle est la probabilité qu'au bout de $2^{2^{100}}$, on ait $r(x)-id(x)=0 \mod 7$ ?
On prendra ici $g(x)=4x+5$.
PS : Une méthode réalisable en moins 10 minutes avec un PC, pour calculer $\mod p$ (avec au moins un p entier plus grand que $2^{100}$), suffit.
il n'y a que $25$ fonctions $\mathbb{Z}_5 \to \mathbb{Z}_5$, donc $25^2$ probabilités de transition à calculer,
puis il faut bidouiller le graphe obtenu (par exemple en diagonalisant la matrice de transition, vu que c'est une chaîne de Markov)
Mais ici on est dans le groupe des transformations affines, qui est d'ordre $20$. On ne peut pas faire plus petit, $f$ et $g$ engendrent le groupe des transformations affines.
Souhaites-tu calculer la probabilité d'être sur l'identité au temps $N$ ou de repasser par l'identité avant le temps $N$ ?
Cela marche pour la première question.
Mais si la matrice de transition ($M$) n'est pas diagonalisable, on fait comment pour calculer $M^{2^{100}}$ ?
Je ne comprends rien non plus à la matrice que tu écris, même en acceptant que tu réponds à une autre question que celle qui est posée. Tu peux expliquer ? Vu qu'on a affaire à deux permutations, la somme des colonnes devrait aussi être égale à $1$, non ?
$$ \lim_n\Pr(r_n(x)\equiv y\bmod 7)=1/6$$ si $x,y\not \equiv 3 \bmod 7.$
2°) Tu ne réponds pas sur la matrice de transition que tu as écrite pour la première situation, et qui est fausse à mon avis.
Ma foi, merci il y a en effet une erreur dans la matrice de transition dans le cas modulo 5, mais je laisserai le lecteur rectifier et poursuivre la methode.
Je ne comprends pas ta remarque numero 1: je dis comment j'avais compris le probleme. En effet, on peut le voir comme toi 'sans les $x$'. C'est a dire qu'on considere la chaine de Markov $r_n$ sur le groupe des transformations affines de $ F_5$, a 20 elements il me semble. Dans ce cas la chaine est bistochastique naturellement comme tu l'observes, et si $3x+1$ et $2x$ engendrent tout le groupe la mesure stationnaire est la loi uniforme, et la probabilite quand $n$ est grand que $r_n=\mathrm{id}$ est approximativement $1/20$- ou $1/d$ si $d$ est la taille du sous groupe engender en esperant qu'il ne se greffe pas un petit probleme d'aperiodicite. Faudrait pour y voir clair ecrire la matrice (20,20), ou au moins faire le diagramme de communication entre les 20 etats de la chaine.
@P. : comme la rappeler GaBuZoMeu, le nombre d'éléments dans le groupe est 20, donc ta matrice de transition devrait-être de tailles $20 \times 20$, ce sont des polynômes de degrés 1, et non des fonctions polynômes.
@Depasse : je n'ai pas de formule explicite, j'en suis resté à la méthode, laisse moi faire les calculs pour vérifier si ta formule est exacte, mais cela me semble bizarre de voir comme limite 1/5, au lieu de 1/20.
Bonne journée.
Dans le cas $n=2^{100}$, il suffit de calculer les carrés successifs de la matrice.
Reste le cas $n=2^{2^{100}}$, où j'ai changé le groupe (il est plus petit) dans lequel on travaille, comment faire le calcul, ici la connaissance de la matrice de transition, seulement, ne sert à rien... alors comment faire ?
Cordialement
Paul
Je vous invite maintenant à réfléchir sur la très très... longue marche aléatoire.
veux-tu me dire que
pour tout élément de $\{0,1,2,3,4\}$
je dois donner,
pour tout $n$, la probalité qu'on retombe sur lui après $n$ coups
alors que je ne donne que
la probabilité que l'on retombe sur le nombre initial, après que j'ai sous-entendu, gratuitement, qu'il y avait équiprobabilité sur ${0,1,2,3,4}$,
ou me dire autre chose?
Cordialement
Paul
On part de $r_0$ qui est l'identité de $\Z/5\Z$.
On pose $r_{n+1}=s_n\circ r_n$ où $s_n$ est $f$ avec probabilité $1/2$ et $g$ avec probabilité $1/2$.
La question est : quelle est la probabilité de $r_n=\mathrm{Id}_{\Z/5\Z}$ ?
Pour les petits N, P = 0% si N impair et P = [0.00%, 12.50%, 9.38%, 10.16%, 9.96%] pour N = [2,4,6,8,10].
Pour l'énoncé 127, il faut construire une matrice 42x42...ce qui est un peu lourd. Mais bon, je parie que P = 1/42 = 2.38%
Pour l'énoncé 127, il faut construire une matric 12x12, ce qui est nettement mieux :)o. Je parie que P = 1/12 = 8.33% pour N mod 3 = 0 et P = 0 % sinon (avec N assez grand).
EDIT : l'énoncé 127 est plus compliqué que cela
Et pardon pour les accents, mes efforts sont toujours vains pour mettre ensemble QWERTY, windows 10 et les US, malgre les remarques d'un Pere Fouettard sur d'autres fils de ce forum.
Dans le deuxième cas, $f$ est un $6$-cycle et $g=f^4$.
PS : pour le 127 le groupe est d'ordre 6 et non 12.
En passant, tu veux calculer la probabilité que r(x) - x mod p = 0 donc (A-1)x+B mod p = 0 (avec r(x) = Ax+B) donc B mod p = 0 et A mod p = 1. Ainsi, chaque élément de la chaine de Markov contient 2 valeurs (1 pour A et l'autre pour . A la base, il y en a 42, mais on peut en supprimer 30 d'après les propriétés que j'ai vu.
J'essaie de voir ce que ça donne avec mon ordi.
PS : je ne suis pas mathématiciens et j'ai très peu de connaissance en algèbre... ce qui rend le challenge plus intéressant B-)-
Il me semble qu'ici la matrice n'est pas diagonalisable... sauf erreur.
(PS : et si $n$ est divisible par $3$, la probabilité est très exactement $1/2$).
Je détaille un peu l'argument de GaBuZoMeu : $f^4=g$, $o(f)=6$, donc $f$ et $g$ commute :
soit $a$ le nombre de fois que l'on a appliqué $f$ et $b$ le nombre de fois que l'on appliqué $g$.
Alors on devrait avoir $a+4b=0 \mod 6$ avec $a+b=2^{2^{100}}$, donc $a+b=0 \mod 3$ ce qui n'est pas possible.
Donc on ne tombe jamais sur $id$, donc il y a 0 chemins.
En passant, la matrice que j'ai obtenue était effectivement non-diagonalisable. Ca paraît simple maintenant, mais j'ai trouvé que ce n'était pas évident de trouver que P = 1/2 si N mod 3 = 0
On se place dans les conditions de l'énoncé 125, déterminer le nombre de chemin, qui ne passe jamais par $id$ de longueur 100.
Réponse :
4225301286417693889465034354
Bonne fin de semaine.
énoncé 128 (bis) : spécial dédicace à Aléa
On se place dans les conditions de l'énoncé 125, déterminer le nombre de chemin, qui ne passe jamais par id de longueur 100, en ne tenant pas compte du départ (id).
Réponse : 4225301286417693889465034354
énoncé 129 : ++++
Même question sauf que l'on ne veut jamais passer par une translation sauf l'identité. (longueur toujours 100).
Réponse : 7921922643285075968
Bonne fin de semaine.
énoncé 128
4.2253e27 chemins
énoncé 129
7.9219e18 chemins
Bravo.
PS : j'avais mis les réponses en blanc.
Bonne journée.
Je l'ai rajouté à ma liste d'exemples de programmes en Julia
http://iecl.univ-lorraine.fr/~Olivier.Garet/linux/#julia
Ceci dit, comme le groupe affine est un produit semi-direct, la matrice a une écriture par blocs dont il est peut être possible de faire quelque chose. Par exemple, on remarque que les entrées de $M^{20}$ ne prennent que les valeurs $0$, $104857$ et $104858$.
@Aléa : merci. Si tu aimes les énoncés incroyables mais vrai, en voici un qui pourrait te plaire : énoncé 119 (je remercie Depasse qui m'a aidé à trouver cette énoncé).