Fonction préservant une distribution
Bonjour,
Je me pose des questions sur la façon de définir correctement une fonction et sur une intuition de résultat. Je pense que si je savais définir correctement la fonction (mathématiquement), je pourrais déduire une preuve sur le résultat.
Je voudrais vérifier si la suppression de composantes d'une chaîne aléatoire particulière préserve la distribution, à la manière de l'exemple suivant : Supposons que je tire aléatoirement une chaîne de $n$ bits. Si j'efface n'importe quel bit, la chaîne résultante est toujours une chaîne aléatoire de $n-1$ bits. Ainsi, pour générer une chaîne aléatoire de $n-1$ bits, je pourrais générer une chaîne de $n$ bits et puis supprimer un bit, n'importe lequel.
Ma question porte sur les suites finies de nombres permutés. Supposons que je tire au hasard une suite dans $S_n$ (l'ensemble des permutations de $\{1,2, \ldots, n\}$), puis je supprime une composante, noté $i$. Si je remplace la composante $n$ par $i$, je pense que la suite résultante est une permutation aléatoire de $S_{n-1}$. Exemple : Je tire aléatoirement la suite permutée $(5\ 1\ 2\ 4\ 3)$, je supprime $2$, et $5$ devient $2$. La suite résultante est $(2\ 1\ 4\ 3)$.
1) Comment écrire correctement cette fonction (mathématiquement) ?
2) Cette façon de générer une suite de $S_4$ ($S_{n-1}$) est-elle uniformément aléatoire ?
Je vous remercie pour votre aide.
Dingo13
Je me pose des questions sur la façon de définir correctement une fonction et sur une intuition de résultat. Je pense que si je savais définir correctement la fonction (mathématiquement), je pourrais déduire une preuve sur le résultat.
Je voudrais vérifier si la suppression de composantes d'une chaîne aléatoire particulière préserve la distribution, à la manière de l'exemple suivant : Supposons que je tire aléatoirement une chaîne de $n$ bits. Si j'efface n'importe quel bit, la chaîne résultante est toujours une chaîne aléatoire de $n-1$ bits. Ainsi, pour générer une chaîne aléatoire de $n-1$ bits, je pourrais générer une chaîne de $n$ bits et puis supprimer un bit, n'importe lequel.
Ma question porte sur les suites finies de nombres permutés. Supposons que je tire au hasard une suite dans $S_n$ (l'ensemble des permutations de $\{1,2, \ldots, n\}$), puis je supprime une composante, noté $i$. Si je remplace la composante $n$ par $i$, je pense que la suite résultante est une permutation aléatoire de $S_{n-1}$. Exemple : Je tire aléatoirement la suite permutée $(5\ 1\ 2\ 4\ 3)$, je supprime $2$, et $5$ devient $2$. La suite résultante est $(2\ 1\ 4\ 3)$.
1) Comment écrire correctement cette fonction (mathématiquement) ?
2) Cette façon de générer une suite de $S_4$ ($S_{n-1}$) est-elle uniformément aléatoire ?
Je vous remercie pour votre aide.
Dingo13
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
2) la clef est la notion de mesure image. Rappelons que la mesure image de $\mu$ par $f$ est donnée par $\mu_f(A)=\mu(f^{-1}(A))$.
Si $X$ suit la loi $\mu$, $f(X)$ suit la loi $\mu_f$.
Maintenant on dit que la transformation $f$ laisse invariante la loi $\mu$ si $\mu_f=\mu$.
Une bijection sur $E$ fini laisse toujours invariante la loi uniforme sur $E$ (exercice).
Si $X$ suit la loi $\mu$, que $f_1,\dots,f_n$ sont des transformations laissant invariantes $\mu$ et que
$I$ suit une loi quelconque sur $\{1,\dots,n\}$ et est indépendante de $X$, alors $Y=f_I(X)$ suit la loi $\mu$.
Ici, on peut prendre $X$ suivant la loi uniforme sur $\mathfrak{S}(n)$, $I$ suivant la loi uniforme
sur $\{1,\dots,n\}$ et $f_i(\sigma)=\sigma \circ (n\quad i)$.
Maintenant, si je note $\pi_n$ l'application de $\mathfrak{S}(n)$ dans $\mathfrak{S}(n-1)$ qui consiste en la suppression de $n$, on peut montrer que la loi image de la loi uniforme sur $\mathfrak{S}(n)$ par $\pi_n$ est la loi uniforme sur $\mathfrak{S}(n-1)$ car chaque point a $n$ antécédents.
On en déduit que $Z=\pi_n(Y)$ suit bien la loi uniforme sur $\mathfrak{S}(n-1)$ .
Que voulez-vous dire par "on peut montrer", que c'est immédiat ? Ensuite dans $\mathfrak{S}(n-1)$, il y a $n-1$ antécédents non ?
Merci encore pour les éclaircissements.
Pour $n=5$, les $5$ antécédents de $(1,3,2,4)$ par $\pi_5$ sont:
$(5,1,3,2,4)$, $(1,5,3,2,4)$,$(1,3,5,2,4)$,$(1,3,2,5,4)$,$(1,3,2,4,5)$
Bien sûr, j'ai laissé des petits bouts à démontrer; j'essaie de ne pas dire "c'est immédiat", c'est quelque chose de très relatif.