Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
171 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Promenade aléatoire dans les groupes.

Envoyé par pourexemple 
Promenade aléatoire dans les groupes.
24 novembre 2016, 11:19
avatar
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.



Modifié 1 fois. Dernière modification le 24/11/2016 11:23 par pourexemple.
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 11:36
avatar
En fait c'est classique : [www.math.ens.fr]
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 11:49
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...



Modifié 2 fois. Dernière modification le 24/11/2016 11:57 par Alcar.
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 12:06
avatar
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.



Modifié 3 fois. Dernière modification le 24/11/2016 12:32 par pourexemple.
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 12:32
avatar
é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.



Modifié 2 fois. Dernière modification le 24/11/2016 13:14 par pourexemple.
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 13:25
avatar
indice : la solution utilise l’algèbre (c'est pour cela que je l'ai mis en algèbre).
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 17:00
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)
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 17:04
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.



Modifié 1 fois. Dernière modification le 24/11/2016 17:12 par GaBuZoMeu.
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 17:30
avatar
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$ ?
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 22:09
avatar
De calculer le nombre de chemins qui passent par l'identité aux temps indiqués ($100$, $2^{100}$ et $2^{2^{100}}$).



Modifié 2 fois. Dernière modification le 25/11/2016 03:57 par jacquot.
Re: Promenade aléatoire dans les groupes.
24 novembre 2016, 22:16
avatar
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}}$ ?
P.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 14:50
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$.



Modifié 1 fois. Dernière modification le 25/11/2016 15:01 par P..
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 14:59
$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)
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 15:13
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 ?
P.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 15:27
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.$
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 15:32
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).
P.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 15:35
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.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 15:42
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.



Modifié 2 fois. Dernière modification le 25/11/2016 15:47 par GaBuZoMeu.
P.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 16:03
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.



Modifié 1 fois. Dernière modification le 25/11/2016 16:10 par P..
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 16:12
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.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 16:14
avatar
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.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 16:16
Depasse répond aussi à la question qui n'est pas posée.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 16:24
avatar
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 ?
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 16:31
@pour exemple: tu te promènes "aléatoirement" entre 5 villes. Il est assez naturel d'heuristiquer qu'au bout d'un grand nombre de déplacements tu as une chance sur cinq, environ, de te retrouver à ton point de départ. Non?

Cordialement
Paul
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 16:43
avatar
Non, c'est 20 villes : [www.les-mathematiques.net]
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 16:49
avatar
@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.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 17:04
@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
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 17:11
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}$ ?
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 17:24
Merci, (j'espère que) j'ai compris!
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 17:54
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 drinking smiley. 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



Modifié 7 fois. Dernière modification le 25/11/2016 21:32 par Alcar.
P.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 18:04
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.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 18:14
avatar
@Alcar : pour l'énoncé 127, le groupe est plus petit que 20 (sauf erreur, il est de cardinal 6).
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 18:15
@ P. : Tu peux vérifier que $g$ est d'ordre $4$ et $f\circ g: x\mapsto x+1$ d'ordre $5$



Modifié 1 fois. Dernière modification le 25/11/2016 18:22 par GaBuZoMeu.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 18:16
avatar
PS : dans le 127 g n'a pas la même valeur que pour les énoncés d'avant.
P.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 18:22
GBZM Ok, merci.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 18:26
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$.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 19:51
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.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 20:00
avatar
@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.



Modifié 2 fois. Dernière modification le 25/11/2016 20:02 par pourexemple.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 20:05
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 B). 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 smoking smiley



Modifié 3 fois. Dernière modification le 25/11/2016 20:13 par Alcar.
Re: Promenade aléatoire dans les groupes.
25 novembre 2016, 20:10
avatar
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.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 151 881, Messages: 1 545 603, Utilisateurs: 28 396.
Notre dernier utilisateur inscrit flavie_12442.


Ce forum
Discussions: 9 397, Messages: 71 499.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page