Permutations au hasard

Si tu composes $n$ transpositions la signature des permutations obtenues est $(-1)^n$, donc tu n'en obtiens qu'une sur deux. Il va falloir modifier un poil ta technique si tu veux obtenir toutes les permutations possibles.

J'ai une démonstration du fait que non.

Soit $G$ un groupe fini, et soit $S$ une partie génératrice symétrique de $G$. Soit $\mu$ la mesure de probabilité uniforme sur $S$, et soit $\mu_\infty$ la mesure uniforme sur $G$. Si $n \in \mathbb{N}^*$, on note $\mu_n$ la mesure qui t'intéresse (définition propre plus bas). Je vais démontrer que pour tout $n \in \mathbb{N}^*$, si $\mu_n = \mu_\infty$, alors $\mu = \mu_\infty$.

On considère l'espace vectoriel $V$ des fonctions $f : G \rightarrow \mathbb{C}$ telles que $\sum_{g \in G} f(g) = 0$, muni du produit scalaire usuel. A toute $\mu$ mesure de probabilité sur $G$, on associe $M_{\mu}$ l'endomorphisme qui à toute $f$ associe l'application qui à tout $g$ associe $\sum_{h \in G} \mu(h)f(gh)$ (on note $M$ l'application qui à $\mu$ associe $M_\mu$).

Pour toutes $\mu,\nu$, notons $\mu * \nu$ la "convolée" des mesures, c'est-à-dire la loi du truc qui correspond à choisir un élément de loi $\mu$ et un élément de loi $\nu$ et les multiplier. Autrement dit, pour tout $g \in G$, $\mu * \nu(\{g\}) = \sum_{h,k} \mu(\{h\})\nu(\{k\})$ où la somme porte sur les couples $(h,k)$ tels que $hk = g$.

Si $\mu$ est une mesure de probabilité sur $G$, on dit qu'elle est symétrique si, pour tout $g \in G$, $\mu(\{g^{-1}\}) = \mu(\{g\})$. Notre $\mu$ à nous, elle est bien symétrique.

1) $\mu \mapsto M_\mu$ est injective.

2) Pour toutes $\mu,\nu$ mesures de probabilité $M_{\mu * \nu} = M_\mu M_\nu$ (ou alors dans l'autre sens et dans ce cas il faut changer $gh$ par $h^{-1}g$ dans la définition de $M$).

3) L'endomorphisme $M_\mu$ est autoadjoint (et donc diagonalisable à valeurs propres réelles).

4) Soit $\mu_{\infty}$ la mesure uniforme sur $G$. Alors $M_{\mu_{\infty}} = 0$.

5) Soit $\mu$ une mesure de probabilité sur $G$. On suppose qu'il existe $n \in \mathbb{N}^*$ tel que $\mu * \cdots *\mu = \mu_{\infty}$ ($n$ fois). Alors on a $M^n_{\mu} = 0$. Comme $M_\mu$ est diagonalisable, c'est que $M_\mu = 0$. Et donc, par injectivité, c'est que $\mu = \mu_\infty$.

Au passage, on peut démontrer que $M^n_\mu$ converge (vite !) vers $0$ de la façon suivante : soit $\nu$ une mesure de probabilité symétrique dont le support engendre $G$.

6) Les valeurs propres de $M_{\nu*\nu}$ sont positives (car cet opérateur est un carré).

7) $1$ n'est pas valeur propre de $M_\nu$ (car son support engendre $G$).

8) De 6) et 7) on déduit que $-1$ n'est jamais valeur propre de $M_\nu$, pour $\nu$ mesure de probabilité sur $G$.

9) De 7) et 8) on déduit que le spectre de $M_\nu$ est inclus dans $]-1,1[$ et comme celui-ci est fini, il existe $\epsilon > 0$ tel que le spectre de $M_\nu$ est inclus dans $]-1+\epsilon,1-\epsilon[$. Et donc, pour la norme subordonnée associée au produit scalaire ci-dessus, on a que, pour tout $n \in \mathbb{N}^*$, $\Vert M^n_\nu \Vert \leq (1 - \epsilon)^n$. Ainsi, on a bien convergence vers $0$.

EDIT : Au fait, les trucs utilisés sont très connus des personnes qui connaissent la théorie des chaînes de Markov.

Bonjour à tous,

Ce n'est pas tout à fait la question, mais cela s'en rapproche. Pour produire une permutation de $\mathfrak{S}_n$ au hasard de façon uniforme. Il suffit de $(n-1)$ transpositions (mais pas de la forme demandée par Christophe). C'est une variante du code de Lehmer, qui établit une bijection entre $\mathfrak{S}_n$ et le produit cartésien $[1,1]\times[1,2]\times\dots\times[1,n]$.

On montre facilement par récurrence que pour toute permutation $\sigma\in\mathfrak{S}_n$, il existe une unique suite d'entiers $a_1,a_2,\dots,a_n$ vérifiant $1\leq a_i\leq i$ telle que:
\[\sigma=(n\ a_n)((n-1)\ a_{n-1})\dots(2\ a_2)(1\ a_1).\]

Du coup l'algorithme suivant donne une permutation au hasard avec équiprobabilité:


Entrée: Un tableau A de n clés distinctes:
Pour $i$ allant de $1$à $n$ faire:
--- j:=random($[1,i]$);
--- échanger (A,A[j]); fin-faire;
Sortie: le tableau permuté A.


Bonne journée,

Le p'tit bonhomme

Persi Diaconis a répondu à ces questions, en y pensant comme à des mélanges de paquets de 52 cartes.

Dans cette vidéo, il explique la chose suivante :

Je pars d'un paquet ordonné (as de pique tout en haut, puis 2 de pique, etc, jusqu'au roi de coeur tout en bas)

Puis je mélange comme suit :
je prends la carte tout en haut du paquet, je l'insère au hasard et je recommence.

Au début, il y a une chance sur 52 qu'elle finisse sous le roi de coeur, ça prend en moyenne 52 essais pour se produire.

Une fois que ceci s'est produit, il y aura deux chances sur 52 pour qu'elle passe sous le roi de coeur, ça prend en moyenne $\frac{52}{2}$ nouveaux essais.

Ainsi de suite, et au bout d'un moment le roi de coeur finira au sommet de la pile.

La fois d'après, il sera inséré au hasard, et toute l'information aura disparu.

Si $T$ désigne le nombre de mélanges pour que le roi de coeur soit monté en haut du paquet, puis ait été réinséré, alors la permutation $\sigma_{T}$ est uniforme dans le groupe symétrique.

Et l'espérance de $T$ est $52 \times \big(1 + \frac{1}{2} + \dots \frac{1}{52} \big) \simeq 52 \times \ln(52)$.

Je la programme en scilab, mais évidemment c'est assez lent pour $N$ grand.

function y = inserer(x)
  // insère la carte du sommet quelque part
  N = length(x)
  alea = floor(N*rand()+1)
  y = [x(2:alea),x(1),x(alea+1:$)]
endfunction

function x = melanger(N)
  // mélange jusqu'à avoir ré-inséré le roi
  x = 1:N
  continuer = %T
  while (continuer)
    continuer = (x(1)~=N) // jusqu'à ce que le roi arrive au sommet
    x = inserer(x)
  end
endfunction

Diaconis sait faire l'étude de même pour tout un tas de mélanges possibles
en trouvant la plus grande valeur propre $<1$ de la matrice de transition de la chaîne de Markov, grâce aux représentations du groupe symétrique.

Le plus cool c'est le *riffle shuffle* : celui des gars au casino.
On coupe le paquet en deux (haut/bas du paquet), puis on fusionne les deux sous-paquets en intercalant aléatoirement les cartes.

Là, pour 52 cartes, il faut 7 mélanges et après c'est bon, c'est bien mélangé.

Question bête : c'est quoi SNT ?