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.
Réponses
-
En fait c'est classique : https://www.math.ens.fr/enseignement/telecharger_fichier.php?fichier=1127
-
La solution est assez simple :
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... -
Non, c'est plus difficile que cela.
é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. -
énoncé 127 : la trés trés... longue marche aléatoire.
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. -
indice : la solution utilise l’algèbre (c'est pour cela que je l'ai mis en algèbre).
-
Pour le premier :
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) -
Hum... Il y a $5^5$ fonctions de $\Z/5\Z$ dans $\Z/5\Z$, et pas $25$. Ca fait un petit peu plus. Et le groupe des permutations de $\Z/5\Z$ est d'ordre $120$.
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. -
La question n'est pas très claire.
Souhaites-tu calculer la probabilité d'être sur l'identité au temps $N$ ou de repasser par l'identité avant le temps $N$ ? -
De calculer le nombre de chemins qui passent par l'identité aux temps indiqués ($100$, $2^{100}$ et $2^{2^{100}}$).
-
Ok, en combinant ce qu'à dit Reuns et GaBuZoMeu on a un plan d'attaque (avec la matrice de transition).
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}}$ ? -
Pour $(3x+1,2x),$ il suffit de considerer la chaine de Markov sur $(0,1,2,3,4)$ de probabilite de transition $$P=\left[\begin{array}{cc}A&B\\0&C\end{array}\right], \mathrm{avec}\ A=1/2, \ B=(0,1/2,0,0),\ \ C=\left[\begin{array}{cccc}0&1/2&0&1/2\\0&1/2&0&1/2\\1/2&1/2&0&0\\0&0&1&0\end{array}\right].$$ On voit que $\{0\}$ est une classe transiente et que la probabilite stationnaire $p=(p_1,p_2,p_3,p_4)$ de la classe recurrente aperiodique $\{1,2,3,4\}$ solution de $pC=p$ est $p=(1/8,3/8,1/4,1/4).$ donc avec la notation $1_4=(1,1,1,1)$ on a $$P^n\rightarrow \left[\begin{array}{cc}0&0\\0&1^T_4p\end{array}\right].$$ La valeur exacte de $P^n$ est calculable, mais quel interet? Bref avec les notations du fil $\Pr(r_n(x)\equiv y\bmod 5)\simeq 0$ si $y\equiv 0\bmod 5$ et $p_y$ si $y\equiv 1,2,3,4 \bmod 5$.
-
$1/5(1+e/2^{n-1})$ avec $e=0, 1 , -1 $ selon que $n=1$ mod $2$, $0$ mod $4$, $2$ mod 4. (n est le nombre de coups)
-
Euh, P., je ne comprends pas trop ce que tu écris. En quoi cela a-t-il un rapport avec la question "quelle est la probabilité pour que la transformation affine $r_n$ soit l'identité" ?
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 ? -
Pour (3x+1,4x+5) modulo 7, la chaine de Markov n'est pas irreductible. Elle a deux classes $\{3\}$ et $\{0,1,2,4,5,6\}$ aperiodiques et evidemment recurrentes. La probabilite stationnaire de la seconde est uniforme. En resume $\Pr(r_n(x)\equiv y\bmod 7)=1$ si $x\equiv y\equiv 3\bmod 7$ et
$$ \lim_n\Pr(r_n(x)\equiv y\bmod 7)=1/6$$ si $x,y\not \equiv 3 \bmod 7.$ -
P., m'est avis que tu ne réponds pas à la question posée. (Pas formulée très clairement, mais éclaircie par le contexte "marche aléatoire dans un groupe", ici le groupe des transformations affines sur un corps fini).
-
GBZM: j'ai compris la question ainsi: si $X_0=x$ est un entier modulo 5, on prend avec une probabilite un demi l'entier $X_1=3x+1$ modulo 5 et $X_1=2x$ modulo 5. Alors $r_n(x)=X_n$ modulo 5.
-
1°) Tu ne formules pas la question. Tu répètes juste la définition de $r_n$. Il me semble clair que la question est "Quelle est la probabilité que $r_n$ soit l'identité" ? PS : voir l'échange alea - pourexemple.
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. -
GBZM
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. -
Si tu relis le fil, tu verras que la question est bien celle que j'ai rappelée, et pas la question telle que tu l'as interprétée. Tout le monde peut faire des erreurs de lecture.
-
Bonjour,
@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. -
Depasse répond aussi à la question qui n'est pas posée.
-
Tout le monde, voit qu'avec la matrice de transition le calcul est facile (dans le cas n=100).
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 ? -
Non, c'est 20 villes : http://www.les-mathematiques.net/phorum/read.php?12,1364120,1364610#msg-1364610
-
@Depasse : si tu vois, notre point de désaccord, cela me dispense du calcul de la matrice de transition.
Je vous invite maintenant à réfléchir sur la très très... longue marche aléatoire. -
@GBMZ:
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 -
Encore une fois :
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}$ ? -
Merci, (j'espère que) j'ai compris!
-
Première fois que j'utilise les chaînes de Markov... ce qui rend le problème donné par l'énnoncé 126 super-super simple. J'ai obtenu (et ce n'est pas surprenant), P = 10% si N est pair et P = 0% si N est impair en prenant N suffisament grand (erreur absolue sur la probabilité plus petite que 1e-14 (1e-12 %) pour N = 100).
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 -
GBZM tu dis dans ton premier fil que si $f(x)=3x+1$ et $g(x)=2x$ alors le sous groupe du groupe $G$ des 20 transformations affines de $F_5$ engendre par $f$ et $g$ est $G.$ Pourquoi? Meme en traduisant avec des matrices de $F_5$ de la forme $[a,b;0,1]$ quelle est l'astuce autre que de faire 400 produits?
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. -
@Alcar : pour l'énoncé 127, le groupe est plus petit que 20 (sauf erreur, il est de cardinal 6).
-
@ P. : Tu peux vérifier que $g$ est d'ordre $4$ et $f\circ g: x\mapsto x+1$ d'ordre $5$
-
PS : dans le 127 g n'a pas la même valeur que pour les énoncés d'avant.
-
GBZM Ok, merci.
-
Dans le premier cas (modulo $5$), $f$ et $g$ sont des permutations impaires : la probabilité qu'un composé d'un nombre impair de telles permutations soit l'identité est naturellement nulle.
Dans le deuxième cas, $f$ est un $6$-cycle et $g=f^4$. -
Voila, j'ai corrigé le post précédent. J'avais effectivement oublié de prendre en compte ce changement de g(x), qui rend le problème nettement plus élégant.
-
@Alcar : même avec une matrice (de transition), cela ne suffit pas, en effet il faudrait calculer $M^{2^{2^{100}}}$, il y a des astuces de calcul qu'il faut expliciter.
PS : pour le 127 le groupe est d'ordre 6 et non 12. -
Il faut juste diagonaliser M, non ? Et pour une puissance autant grande, toutes les valeurs propres qui ne sont pas 1 deviennent un nombre super-proche de 0.
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-)- -
Oui, en fait, il faut compter le nombre de chemins, modulo un nombre entier premier de son choix plus grand que $2^{100}$.
Il me semble qu'ici la matrice n'est pas diagonalisable... sauf erreur. -
Dans le deuxième cas (modulo 7), la probabilité pour que $r_n=\mathrm{Id}_{\Z/7\Z}$ est très exactement nulle si $n$ n'est pas divisible par $3$. En particulier, si $n=2^{2^{100}}$.
(PS : et si $n$ est divisible par $3$, la probabilité est très exactement $1/2$). -
Bravo.
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. -
Ok, j'ai rien dit B-)- Je viens de comprendre ce qu'il se passe.
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 -
énoncé 128 : 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.
Réponse :
4225301286417693889465034354
Bonne fin de semaine. -
0 parce que tu commences avec id ?
-
Bien joué.
é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. -
Je n'ai pas fait dans la finesse donc j'ai juste construit un matrice 20x20 avec des 1 au lieu des probabilités et j'ai mis certains 1 à 0 de tel sorte que le chemin ne passe pas là où il ne devrait pas passer. J'obtiens :
énoncé 128
4.2253e27 chemins
énoncé 129
7.9219e18 chemins -
Bonjour,
Bravo.
PS : j'avais mis les réponses en blanc.
Bonne journée. -
Visibilement, je n'arrive pas à avoir la même précision. Est-ce parce que je suis allé sans finesse ou tu utilises un autre programme ? J'ai utilisé Octave et je ne peux pas avoir mieux que des double (8 bytes) en utilisant les librairies standards.
-
Joli problème de programmation.
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$. -
@Alcar : j'utilise Maple, je pense qu' il te faut des Big Integer (même des lon long ne seraient pas suffisant).
@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é).
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 771 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 17
+11 Invités