Battage de cartes - chaîne de Markov

Bonsoir Estelle,

Je n'ai pas trop de réponse à ta demande de référence, mais je recommande à tout le monde les vidéos où Persi Diaconis explique le coup des mélanges.

(c'est lui qui a tout inventé sur les maths du mélange de cartes, je crois)

Bonjour,

L'ensemble des états de la chaîne $(X_n)_n$ est le groupe $\mathfrak S_N$ des permutations de $[\![1;N]\!]$
Soit $\mathcal S= \{\sigma_1, \sigma_2, ...\sigma_N\}\subset \mathfrak S_N $ où $\:\forall x \in [\![1;N]\!],\:\:\sigma_k(x) =\left\{ \begin{array}{cl} x+1&\text{si}\: x<k.\\ 1&\text{si}\: x=k .\\ x &\text{si}\: x>k. \end{array}\right.\qquad \mathbb P\Big(X_{n+1} = \sigma | X_n = \tau \Big) = \left\{\begin{array}{cl} \dfrac 1N &\text{si}\: \sigma \tau^{-1}\in \mathcal S.\\ 0 & \text{sinon}. \end{array}\right.$

Le caractère irréductible de cette chaîne résulte du fait que $ \mathcal S$ est un système générateur de $\mathfrak S_N$ et que $\sigma_k^{-1} = \sigma_k ^{k-1}.$
$\forall \sigma, \tau \in \mathfrak S_N, \quad \exists i_1, i_2, ...i_s \in [\![1;N]\!]$ tels que $\:\sigma\tau^{-1} = \sigma_{i_1} \sigma_{i_2} ... \sigma_{i_s}: \quad \mathbb P^{(s)} ( \tau \to \sigma)>0.$

Son "apériodicité" est encore plus simple à justifier: $ \: \forall \sigma \in \mathfrak S_N, \:\: \mathbb P ^{(1)}( \sigma \to \sigma) = \dfrac 1N, \:\: \mathbb P^{(2) } ( \sigma \to \sigma) = \dfrac 2{N^2}, \quad \mathrm {PGCD}\left\{n \in \N^*\mid \mathbb P^{(n) } ( \sigma \to \sigma)>0 \right\} =1.$

Bonjour Elleest

La construction de la marche aléatoire dans $\mathfrak S_N$ fait que la probabilité de passage de l'état $\tau$ à l'état $\sigma$ est non nulle si et seulement si il existe un élément $ \alpha$ de $ \mathcal S$ tel que $\sigma = \alpha \tau$, c'est-à-dire si $\sigma \tau^{-1}\in \mathcal S.$
En d'autres termes, les états accessibles en une étape à partir de $\tau$ sont les $\alpha \tau$ où $\alpha \in \mathcal S.$
Chacun d'entre eux est atteint avec la probabilité $\dfrac 1N$ parce qu'à chaque pas, on choisit aléatoirement et de manière équiprobable un élément dans $\mathcal S.$