Nombre de retenues dans une addition

GaBuZoMeu

Bonjour,

Une question issue de

https://les-mathematiques.net/vanilla/discussion/comment/2496891#Comment_2496891

On a une chaîne de Markov à deux états $A$ et $B$ et  matrice de transition $\begin{pmatrix} 11/20 & 9/20\\9/20& 11/20\end{pmatrix}$. On part de $\begin{pmatrix} 1 \\ 0\end{pmatrix}$. A-t-on un TCL pour le nombre de passages en l'état $B$ en $n$ étapes, quand $n$ tend vers l'infini ?

On pourra voir le fil en lien pour le rapport avec le nombre de retenues dans l'addition de deux entiers tirés uniformément et indépendamment entre $0$ et $10^n-1$.

gebrane

Comme dans l'autre fil demandons l'avis de ChatGPT, pas mal

La chaîne de Markov est définie par deux états \( A \) et \( B \) avec la matrice de transition :

\[P = \begin{pmatrix}  \frac{11}{20} & \frac{9}{20} \\\frac{9}{20} & \frac{11}{20}\end{pmatrix}.\]

Cette chaîne est irréductible  et apériodique ( wiki dit toutefois, si tous les éléments de la matrice de transition sont strictement positifs, la chaîne de Markov est irréductible et apériodique)

Distribution stationnaire

La distribution stationnaire \( \pi \) (un vecteur ligne) est la solution de l'équation \( \pi P = \pi \), ce qui donne (En prenant les transposée, on retombe sur le problème classique des vecteurs  propres ici la vp est 1):

\[\pi_1 = \frac{9}{20}, \quad \pi_2 = \frac{11}{20},\]

où \( \pi_1 \) est la probabilité de l'état \( A \) et \( \pi_2 \) celle de l'état \( B \). La distribution stationnaire nous indique la proportion de temps que la chaîne passe dans chaque état à long terme.

Nombre de passages dans l'état \( B \)

Le nombre de passages dans l'état \( B \) jusqu'à l'étape \( n \), noté \( S_n \), est donné par :

\[S_n = \sum_{k=1}^n \mathbb{1}_{\{X_k = B\}},\]

où \( \mathbb{1}_{\{X_k = B\}} \) est une variable indicatrice qui vaut 1 si la chaîne est en état \( B \) à l'étape \( k \), et 0 sinon.

Loi des grands nombres (LLN)

La loi des grands nombres (LLN) affirme que, lorsque \( n \) tend vers l'infini, la proportion de temps que la chaîne passe dans l'état \( B \) converge presque sûrement vers la probabilité stationnaire de l'état \( B \), c'est-à-dire :

\[\frac{S_n}{n} \to \pi_B = \frac{11}{20} \quad \text{presque sûrement quand } n \to \infty.\]

Ceci  est une conséquence directe de la LLN pour les chaînes de Markov irréductibles et apériodiques.

Théorème central limite (TCL)

Le théorème central limite (TCL) peut s'appliquer au nombre de passages \( S_n \) sous certaines conditions, même si les variables indicatrices \( \mathbb{1}_{\{X_k = B\}} \) ne sont pas indépendantes. Pour une chaîne de Markov irréductible et apériodique, il existe un TCL pour les fonctions additives comme \( S_n \). En d'autres termes, on peut écrire :

\[\frac{S_n - n \pi_B}{\sqrt{n \sigma^2}} \xrightarrow{d} \mathcal{N}(0, 1),\]

où \( \sigma^2 \) est la variance asymptotique qui dépend de la chaîne de Markov. Cette variance n'est pas simplement celle d'une somme de variables indépendantes, mais tient compte de la dépendance entre les états successifs.

 Conclusion

Dans le contexte d'une chaîne de Markov irréductible et apériodique. Le TCL s'applique bien au nombre de passages en l'état \( B \),

GaBuZoMeu

Pas mal ?? @Gebrane, tu me déçois !

La distribution stationnaire est facile à trouver, et ce n'est bien sûr pas celle indiquée par ChatGPT.

Dans le fil mis en référence, j'ai indiqué la fréquence limite des retenues :

https://les-mathematiques.net/vanilla/discussion/comment/2496690/#Comment_2496690

gebrane

On sait tous qu'il se trompe dans des calculs simple mais j'ai dit pas mal car  il a remarqué que la matrice de transition est irréductible et apériodique, ce qui lui permet d'appliquer un théorème central limite.  https://www.imo.universite-paris-saclay.fr/~pierre-loic.meliot/agreg/markov.pdf

marco

Je trouve que le nombre moyen de passages à l'état $B$ en $n$ étapes, est $n/2-\frac{1}{20}(\sum_{k=0}^{n-1} \frac{1}{10^k})$.

marco

.

GaBuZoMeu

Oui, je suis d'accord (voir le message que j'ai indiqué ci-dessus, il suffit de sommer les $p_k$).

@gebrane : merci pour la référence. Ça au moins c'est du sérieux, le détour par ChatGPT était complètement inutile (et énervant).

gebrane

Mais Gabu, c'était juste une plaisanterie car dans l'autre conversation, ils se sont précipités vers ce Chat pour le code.