Proba sur des permutations
Bonjour
Soit $n\in \mathbb N$ et l'espace de proba $\big(\mathfrak S_n,\mathcal P(\mathfrak S_n),\mathbb P\big)$ où $\mathbb P$ est la mesure uniforme.
Soit $k\leq n$ et notons l'évènement $A_{k}= \{\sigma \in \mathfrak S_{k}\mid \sigma (k)= k\}$.
J'aimerais montrer que nos évènements $A_k$ sont indépendants.
Si j'essaye d'un coup, l'intersection d'évènements $A_{k_i}$ pour $k_i\in \mathbb N$ donne un évènement un peu difficile à décrire pour moi...
Merci pour votre aide.
(Note. On peut noter que la proba de chaque $A_k$ est évidemment $\frac{1}{k}$.)
Soit $n\in \mathbb N$ et l'espace de proba $\big(\mathfrak S_n,\mathcal P(\mathfrak S_n),\mathbb P\big)$ où $\mathbb P$ est la mesure uniforme.
Soit $k\leq n$ et notons l'évènement $A_{k}= \{\sigma \in \mathfrak S_{k}\mid \sigma (k)= k\}$.
J'aimerais montrer que nos évènements $A_k$ sont indépendants.
Si j'essaye d'un coup, l'intersection d'évènements $A_{k_i}$ pour $k_i\in \mathbb N$ donne un évènement un peu difficile à décrire pour moi...
Merci pour votre aide.
(Note. On peut noter que la proba de chaque $A_k$ est évidemment $\frac{1}{k}$.)
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
On se donne une famille finie de ces événements, disons sans répétition, disons $(A_{k_1},\dots,A_{k_r})$ avec $r\le n$ et $k_1<\cdots<k_r$. L'intersection des $A_{k_i}$ est l'ensemble des permutations qui fixent $\{k_1,\dots,k_r\}$ (et éventuellement d'autres points). Décrire une telle permutation n'a pas l'air si compliqué, les compter non plus. Commence par un exemple simple : $k_1=n-r+1$, $k_2=n-r+2$,..., $k_r=n$ : connaissant $\sigma(n-r+1)=n-r+1$,..., $\sigma(n)=n$, ne vois-tu pas une façon simple de décrire une bijection $\sigma$ de $\{1,\dots,n\}$ dans $\{1,\dots,n\}$ ?
Mais alors on change d'espace probabilisé ? :-S
C'est difficile à interpréter. Pour expliciter la remarque de Calli, la probabilité de l'ensemble $A_k$ des éléments de $\mathfrak{S}_k$ qui fixent $k$ est bien $1/k$ mais si on plonge $A_k$ dans $\mathfrak{S}_n$ (muni de la proba uniforme), la probabilité devient $\frac{1}{k}\cdot\frac{k!}{n!}$ qui n'est pas en général $1/k$.
Quant à la probabilité de l'ensemble des $\sigma$ telles que $\sigma(\{1,\dots,k\})=\{1,\dots,k\}$, $\sigma(k)=k$ et $\sigma(\{k+1,\dots,n\})=\{k+1,\dots,n\}$, c'est $\frac{(k-1)!(n-k+1)!}{n!}=\frac{k}{\binom{n}k}\ne\frac1k$ (en général).
Tu pourrais préciser ?
Je donne le corrigé que j'ai.
On raisonne par récurrence. Pour $r=1$ c'est clair. Montrons $r$ à partir de $r-1$.
$$\begin{align*}
\mathbb P\Big(\bigcap_{i=1}^r A_{k_i} \Big ) &=\mathbb P\Big(\bigcap_{i=1}^{r-1} A_{k_i}\bigcap A_{k_r}\Big ) \\
&=\mathbb P\Big(\bigcap_{i=1}^{r-1} A_{k_i}\Big )\mathbb P_{k_r}(A_{k_r}) \\
&=\prod_{i=1}^{r-1}\mathbb P_{k_i}(A_{k_i})\ \mathbb P_{k_r}(A_{k_r})
\end{align*}
$$ Peut-être qu'en fait avec l'énoncé tel que je l'ai donné ça n'a pas beaucoup de sens mais c'est en fait une partie d'un plus grand problème de battre des records ($A_k$ est en fait l'évènement "battre le record à la k-ème tentative") donc ça a sûrement plus de contexte dans ce sens là mais dans tous les cas mon corrigé est trop flou.
NB : une telle permutation n'est pas déterminée par sa restriction à $\{1,\dots,k\}$ puisque ce qui arrive aux $l>k$ change la permutation. Elle est déterminée par une permutation de $\{1,\dots,k-1\}$ et une permutation de $\{k+1,\dots,n\}$, de sorte que la probabilité de $A_k$ doit être $\frac{(k-1)!(n-(k+1)+1)!}{n!}=\frac{1}{k\binom{n}k}$ (erreur dans un message précédent, il me semble).
Pour l'indépendance, je commence tout petit avec deux événements $A_{k_1}$ et $A_{k_2}$ avec $k_1<k_2$. Dans l'intersection, on stabilise $\{1,\dots,k_1-1\}$, $\{k_1+1,\dots,k_2-1\}$ et $\{k_2+1,\dots,n\}$ donc la probabilité de $A_{k_1}\cap A_{k_2}$ est \[
\frac{(k_1-1)!(k_2-k_1-1)!(n-k_2-1)!}{n!},\] à comparer à \[\frac{1}{k_1k_2\binom{n}{k_1}\binom{n}{k_2}}.\]Je pourrais me planter complètement mais je n'y crois pas trop.
Prenons $X_1,X_2,\dots$ des v.a. indépendantes ayant la même loi en supposant que la fonction de répartition de cette loi soit continue.
On définit $A_k:=\{\max_{j<k} X_j<X_k\}$ et $A_1:=\Omega$.
On peut montrer que presque sûrement, $X_i\neq X_j\quad \forall i\neq j$.
On peut ainsi en déduire que pour chaque $n\in \mathbb N^*$, il existe presque sûrement une permutation aléatoire $\pi_n$ de $\{1,\dots,n\}$ tel que $X_{\pi_n(1)}<X_{\pi_n(2)}<\dots <X_{\pi_n(n)}$.
On peut aussi montrer et c'est très important, que $\pi_n$ est uniformément distribuée sur $\mathfrak S_n$. C'est la raison pour laquelle on peut écrire que les évènements $A_k:=\{\max_{j<k} X_k<X_k\}$ et $A_{k}= \{\sigma \in \mathfrak S_{k}\mid \sigma (k)= k\}$ donnent la même probabilité.
Le haut fait partie du premier point de mon exercice, le deuxième point demande de montrer que $\mathbb P(A_k)=\frac{1}{k}$ ce qui est facile avec l'interprétation des permutations plus haut, et ensuite de montrer que nos évènements $A_k$ sont indépendants, le point auquel je n'ai pas encore de réponse.
@Codename
Voici un dénombrement qui fournit une preuve de l'indépendance des $A_k=\Big\{\sigma \in \mathfrak S_n \mid \forall i \in [\![1;k-1]\!], \: \sigma(i)<\sigma(k) \Big\}$, une indépendance qui, me semble-t-il, n'a rien de franchement évident.
Notons: $\quad \forall k \in \N, \: [k]:=[\![0;k]\!], \:\:\forall \sigma \in \mathfrak S_n, \forall i \in [\![1;n]\!], \quad a_i(\sigma) := \text{Card}\Big\{j\in [\![1;i-1]\!] \mid \sigma(j) >\sigma(i) \Big\}.\quad(a_1(\sigma) =0)$
Il est opportun dans cette histoire de solliciter cette belle bijection: $\Phi: \left\{\begin{array}{ccl}\mathfrak S_n &\longrightarrow & [0]\times [1]\times \dots \times [n-1] \\ \sigma & \longmapsto &\Big (a_1(\sigma) , a_2(\sigma), \dots a_n(\sigma)\Big ) \end{array}\right.$
(L'injectivité ou la surjectivité de $\Phi$ sont faciles à établir.)
Il est acquis que $\:\:\forall i \in [\![1;n]\!], \:\mathbb P(A_i) = \dfrac 1i.\:\: $ (voir $(\star)$)$\qquad $ Soit $\:E\subset [\![1;n]\!].$
Alors: $\qquad \mathbb P\Big( \displaystyle \bigcap_{i \in E}A_i \Big) = \dfrac 1{n!}\text{Card}\Big \{\sigma \in \mathfrak S_n \mid \forall i \in E, \: a_i(\sigma )= 0 \Big\} \overset {\substack {\Phi \\ \text{bijective}}}=\:\: \dfrac{\displaystyle{\prod_{i \notin E}\text{Card}[i-1]}}{n!}=\:\: \dfrac{\displaystyle{\prod_{i \notin E}i}}{n!} =\dfrac 1 {\displaystyle{\prod _{i \in E} i}} = \displaystyle {\prod_{i\in E}\:}\mathbb P(A_i) \:\square$
$(\star)\quad \mathbb P(A_k) = \dfrac 1k$ est un cas particulier du calcul précédent.
Je bloque déjà sur $\mathbb P(A_i)=\frac{1}{i}$.
En effet par le fait que nos $\sigma$ sont bijectives, on a que $A_k=\Big\{\sigma \in \mathfrak S_n \mid \forall i \in [\![1;k-1]\!], \: \sigma(i)<\sigma(k) \Big\}=\{\sigma\in \mathfrak S_n\mid \sigma(i)<\sigma(k)=k,\quad \forall i<k\}$
La probabilité de cet ensemble ne donne pas $\frac{1}{k}$ à ma connaissance (voir calcul de Math Coss).
$\bullet \: $ Je m'aperçois que ton énoncé initial n'avait pas de sens.
$ \:A_k = \{\sigma \in \mathfrak S_k \mid \sigma (k) =k \}$, parce que ce n'est pas une partie de $\mathfrak S_n$, n'est pas un événement de l'espace $\mathfrak S_n$ muni de la probabilté uniforme.
$\bullet \:$ Si $A_k = \{\sigma \in \mathfrak S_n \mid \sigma (k) =k \} \:\:,$ alors $\:\:\mathbb P(A_k) = \dfrac 1n$ et les $A_k$ ne sont pas indépendants.
$\bullet\:$ Si $A_k = \{ \sigma \in \mathfrak S_n \mid \sigma (k) =k, \: i<k \implies \sigma (i) <\sigma (k)\}, \:\:$ alors:
$\mathbb P(A_1)= \dfrac 1n; \:\: \mathbb P(A_2) =\mathbb P(A_1 \cap A_2) = \dfrac 1 {n(n-1)}, \:\:$ et les $A_k$ ne sont pas indépendants.
$\bullet \:$C'est la raison pour laquelle, ayant lu un peu trop en diagonale les messages précédents (je m'en excuse) et MathCoss ayant évoqué une histoire de records, j'ai pensé que $A_k$ était l'événement
$A_k =\{\sigma \in \mathfrak S_n \mid \forall i \in [\![1;k-1]\!], \:\sigma (i)<\sigma(k)\}\:\:$ (nullement égal à $\{\sigma \in \mathfrak S_n \mid \forall i \in [\![1;k-1]\!], \:\sigma (i)<\sigma(k)=k\}$.)
C'est l'indépendance de ces $A_k$ que j'ai traitée dans mon précédent message, qui ne m'a pas paru du tout évidente et dont j'ai cru qu'elle faisait l'objet de ce fil.
Si $\sigma(k)<k$ alors $\forall i<k$ on a que $\sigma(i)<\sigma(k)\leq k-1$ donc on a pour tous $i\leq k-1$ que $\sigma(i)<k-1$ ce qui casse l'injectivité de $\sigma$.
De même si $\sigma(k)>k$ la surjectivité de $\sigma$ est cassée.
Soit $\sigma \in \mathfrak S_3$ tel que $\sigma(1) =1, \:\sigma(2) =3, \: \: \sigma (3) =2.\quad \sigma \in A_2$ et $\sigma(2) \neq 2$. Je ne vois pas ce que $\sigma$ a de non bijectif.
En fait, bien qu'ayant lu en "diagonale" les précedents messages, j'avais finalement bien compris quelle était la question, à savoir prouver l'indépendance des $E_k= [ \max\{X_i \mid i <k \} <X_k]$.
Cela revient à prouver l'indépendance des $A_k$ que j'ai définis, et que j'ai établie dans mon premier message.
Quel est le lien entre "mes" $A_k$" et les"tiens" ? Aucun.
Je te suggère donc de te concentrer sur la preuve que je t'ai indiquée, en oubliant tout le reste. Je détaille la preuve de $\mathbb P(A_k) = \dfrac 1k$
$\mathbb P(A_k) = \dfrac 1{n!} \text {Card} \Big \{ \sigma \in \mathfrak S_n \mid a_k(\sigma) =0 \Big\} \displaystyle \overset {\substack {\Phi \\ \text{bijective}}} {=} \dfrac {\prod _{i\neq k} i}{n!} = \dfrac 1k.$
- J'aimerais calculer la proba d'un record pour un nombre infini de v.a. $X_1,X_2,\dots$ alors que ton espace de proba pour calculer la proba des permutations est $\mathfrak S_n$ donc s'arrête à $n$ ce qui ne joue pas.
- Dans l'évènement $E_k= [ \max_i\{X_i \mid i <k \} <X_k]$ on a que l'indice de $X_k$ est fixé à $k$ donc pas de permutation ici: $\sigma(k)=k$ non?
Le premier point est la raison pour laquelle j'avais décidé de me placer sur des espaces de proba de "taille" $k$: $\mathfrak S_k$ car on peut bien calculer la proba d'un record malgré la présence d'un nombre infini de v.a. $X_i$.$\bullet\:$ Pour évaluer $ \mathbb P \Big( \displaystyle \bigcap _{i \in E}A_i\Big)$, il est impératif de se placer dans un univers $\mathfrak S_n$ tel que $n\geqslant \sup E$, qui contient tous les événements $A_i$.
C'est ce que je t'ai proposé dans mon premier message où est prouvée (clairement me semble-t-il )l'indépendance des $A_i$
De manière plus élémentaire, pour des petites valeurs de $i$, on a par exemple:
$\mathbb P(E_2) = \mathbb P(X_1<X_2) = \dfrac 12, \quad \mathbb P(E_3) =\mathbb P(X_1<X_2<X_3) + \mathbb P(X_2<X_1<X_3) = \dfrac 16 + \dfrac 16 = \dfrac 13.$
$\mathbb P(E_2\cap E_3)=\mathbb P(X_1<X_2<X_3) =\dfrac 16 =\mathbb P(E_2) \times\mathbb P(E_3).$
$\mathbb P (E_2\cap E_4)= \mathbb P(X_1<X_2<X_3<X_4) +\mathbb P(X_1<X_3<X_2<X_4)+\mathbb P(X_3<X_1<X_2<X_4)=3 \times \dfrac 1{4!}=\dfrac 18 =\mathbb P (E_2)\times \mathbb P (E_4).$