On veut tirer au hasard une permutation des entiers \(1,\dots,n\) et on envisage les deux méthodes suivantes.

  1. On fixe un entier \(N\), et on tire \(2N\) entiers \(i_{1},j_{1},\dots,i_N,j_N\in \textlbrackdbl 1,n\textlbrackdbl\) de manière uniforme et indépendante. On calcule alors \(\sigma =(i_{1}\ j_{1})\circ \dots\circ (i_N\ j_N)\) avec la convention \((i_k\ j_k)=\mathop{\rm id}\nolimits\) si \(i_k=j_k\).

    1. Comment choisir \(N\) pour être sûr de pouvoir obtenir chaque permutation ?

    2. Lorsque cette condition est remplie, permutation obtenue est-elle uniformément distribuée sur \(S_n\) ?

  2. On tire de manière uniforme et indépendante des entiers \(k_{1}\in \textlbrackdbl 0,1\textlbrackdbl\), \(k_{2}\in \textlbrackdbl 0,2\textlbrackdbl ,\dots,k_{n-1}\in \textlbrackdbl 0,n-1\textlbrackdbl\) et on calcule \(\sigma =(1\ 2)^{k_{1}}\circ (1\ 2\ 3)^{k_2}\circ \dots\circ (1\ \dots\ n)^{k_{n-1}}\). Peut-on ainsi obtenir toutes les permutations ? Sont-elles équiprobables ?


Barre utilisateur

[ID: 4852] [Date de publication: 16 avril 2024 14:08] [Catégorie(s): Calculs de probabilités ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Michel Quercia ]




Solution(s)

Solution(s)

Permutation aléatoire
Par Michel Quercia le 16 avril 2024 14:08
    1. La composée de \(N\) transpositions a au moins \(n-N\) orbites si \(N<n\) et il existe des permutations à une seule orbite (les \(n\)-cycles) donc il faut \(N\geq n-1\). Cette condition est suffisante, toute permutation de \(n\) éléments peut être décomposée en au plus \(n-1\) transpositions.

    2. Non, la taille de l’univers est \(n^{2N}\) qui n’est pas un multiple de \(n!\) si \(n\geq 3\).

  1. Oui.


Documents à télécharger