Marche aléatoire: rois sur un échiquier

J'ai une question sur la marche aléatoire de deux rois dans un échiquier 3 × 3.

Chaque roi se déplace au hasard avec une probabilité égale sur cet échiquier - verticalement, horizontalement et en diagonale. Les deux rois se déplacent indépendamment l'un de l'autre sur le même échiquier. Les deux commencent sur le même carré, puis se déplacent indépendamment.

Comment pourrions-nous trouver la probabilité dans le temps deux sont dans le même carré, car va à l'infini? $n$ $n$

self-study markov-chain random-walk cube
la source

Qu'est-ce que "la même zone"? Voulez-vous dire "le même carré?"

Peter Flom

Oh oui, désolé !!!

cube

Utiliser l'approche de la matrice de probabilité de transition

vinux

si je le fais avec la matrice de probabilité de transition, je dois d'abord trouver la matrice de probabilité de transition de la marche aléatoire du premier roi, puis l'augmenter dans le 2?

cube

c'est un exercice que j'ai et j'essaie de le résoudre depuis de nombreux jours maintenant, c'était ma dernière idée pour avoir une bonne idée de comment y faire face.

cube

Réponses:

Exploitons la symétrie pour simplifier les calculs.

L'échiquier et ses mouvements restent les mêmes lorsque le plateau est réfléchi verticalement, horizontalement ou en diagonale. Cela décompose ses neuf carrés en trois types, leurs orbites sous ce groupe de symétrie. De façon correspondante, chaque roi peut être dans l'un des trois "états": un carré d'angle ( ), un carré de bord ( ) ou le carré central ("central") ( ). (Un état ignore quel carré particulier se trouve un roi et ne suit que sa classe d'équivalence sous le groupe de symétries.) $C$ $E$ $M$

Les résultats suivants sont immédiats:

À partir d'un carré d'angle, il y a deux transitions vers des carrés de bord et une transition vers un carré du milieu. Parce que les trois transitions sont équiprobables,

$Pr (C \to E) = 2 / 3, Pr (C \to M) = 1 / 3.$ $\Pr(C \to E) = 2/3,\quad \Pr(C \to M) = 1/3.$
Cela donne une ligne dans une matrice de transition pour les états . $(0, 2/3, 1/3)$ $(C, E, M)$
D'un carré de bord, il y a deux transitions vers des carrés d'angle, deux vers d'autres carrés de bord et une vers le carré du milieu. Cela donne une deuxième ligne dans une matrice de transition. $(2/5, 2/5, 1/5)$
Du carré du milieu, il y a quatre transitions vers les carrés d'angle et quatre vers les carrés du milieu. La troisième ligne d'une matrice de transition est donc . $(4/8, 4/8, 0) = (1/2, 1/2, 0)$

Dans ce graphique représentant cette chaîne de Markov, les probabilités de transition sont représentées à la fois par l'épaisseur du bord et la couleur:

Par inspection ou autrement, nous constatons qu'un vecteur propre gauche de sa matrice de transition

P = (\begin{array}{ccc} 0 & \frac{2}{3} & \frac{1}{3} \\ \frac{2}{5} & \frac{2}{5} & \frac{1}{5} \\ \frac{1}{2} & \frac{1}{2} & 0 \end{array})

$\mathbb{P} = \left( \begin{array}{ccc} 0 & \frac{2}{3} & \frac{1}{3} \\ \frac{2}{5} & \frac{2}{5} & \frac{1}{5} \\ \frac{1}{2} & \frac{1}{2} & 0 \\ \end{array} \right)$

est . Cette affirmation est facilement vérifiée en effectuant la multiplication: La valeur propre est manifestement . Parce que tous les états sont connectés, donne les probabilités limitatives de chaque roi dans chaque état; il suffit de redimensionner ses composants pour résumer à l'unité: $\omega = (3, 5, 2)^\prime$ $\omega \mathbb{P} = 1 \omega.$ $1$ $\omega$

ω = (ω_{C}, ω_{E}, ω_{M}) = (3 / 10, 5 / 10, 2 / 10) .

$\omega = (\omega_C, \omega_E, \omega_M) = (3/10, 5/10, 2/10).$

(C'est là que nous récoltons les avantages de l'exploitation de la symétrie: au lieu de travailler avec une matrice de neuf par neuf de éléments, nous n'avons qu'à calculer avec une matrice de trois par trois de éléments. La réduction du problème de neuf états à trois payé de façon quadratique en réduisant l'effort de calcul d'un facteur ) $81$ $9$ $(9/3)^2 = 9$

La probabilité (limite) que les deux rois soient dans un état de probabilité (limite) est parce que les rois se déplacent indépendamment. La chance que les deux rois soient dans la même cellule est trouvée en conditionnant l'état: par symétrie, chaque cellule dans un état donné a la même probabilité limite, donc si les deux rois se trouvent dans un état ayant cellules, la chance qu'ils sont tous deux dans la même cellule est . D'où vient la solution $s$ $\omega_s$ $\omega_s^2$ $s$ $k_s$ $1/k_s$

\sum_{s \in {C, E, M}} \frac{ω_{s}^{2}}{k_{s}} = {(\frac{3}{10})}^{2} \frac{1}{4} + {(\frac{5}{10})}^{2} \frac{1}{4} + {(\frac{2}{10})}^{2} \frac{1}{1} = \frac{9}{400} + \frac{25}{400} + \frac{16}{400} = \frac{1}{8} .

$\sum_{s\in \{C,E,M\}}\frac{ \omega_s^2 }{k_s} = \left(\frac{3}{10}\right)^2\frac{1}{4} + \left(\frac{5}{10}\right)^2\frac{1}{4} + \left(\frac{2}{10}\right)^2\frac{1}{1} = \frac{9}{400} + \frac{25}{400} + \frac{16}{400} = \frac{1}{8}.$

whuber
la source

Reader @xan fait des commentaires très intéressants après la (belle) réponse du statisticien accidentel dans ce fil. Ces commentaires mettent en évidence une lacune logique dans mon argumentation: il faut aussi montrer que les deux rois peuvent (dans un certain sens intuitif) se déplacer vraiment indépendamment l'un de l'autre. L'exemple de Xan concerne les rois qui ne peuvent pas faire de mouvements diagonaux: si un roi commence dans l'état et l'autre en ou , alors ils ne peuvent jamais occuper le même carré! Cet écart peut être corrigé en considérant une matrice de transition pour les paires d'états ordonnés.

E

$E$

C

$C$

M

$M$

whuber

Merci pour cette réponse, très intéressante et instructive!

cube

@ user929304 C'est exact. Si vous imaginez une situation différente dans laquelle ces probabilités étaient chacune (disons) , ce qui est tout à fait possible - leur total n'est que de pour chaque roi - alors votre formule donnerait une probabilité de ce qui est manifestement faux.

1 / 3

$1/3$

2 / 3

$2/3$

2 (1 / 3 + 1 / 3) = 4 / 3

$2(1/3+1/3)=4/3$

whuber

@ user929304 La probabilité de l'union n'est la somme des probabilités que lorsque les événements sont disjoints (aka "mutuellement exclusifs"). Être disjoint n'est pas la même chose qu'être indépendant - en fait, c'est une violation assez extrême de l'indépendance.

whuber

@ user929304 Cox et Miller est accessible et couvre beaucoup de terrain.

whuber

Étant donné que les deux rois se déplacent indépendamment, vous pouvez les considérer séparément. Si la carte est de taille finie et n'a pas de sous-sections fermées, c'est l'un de ces cas où la distribution stationnaire peut être trouvée en résolvant l'équation détaillée de l'équilibre.

Dans ce cas, lorsque va à l'infini, la probabilité qu'un roi soit dans un carré devient proportionnelle au nombre de carrés qui lui sont adjacents, soit trois pour chaque carré d'angle, cinq pour chaque carré de bord et huit pour le carré du milieu. Cela équivaut à , donc la chance d'être dans le carré du milieu est , dans n'importe quel carré d'angle est et dans n'importe quel carré de bord est . $n$ $40$ $8/40$ $3/40$ $5/40$

Comme cela est vrai pour les deux rois indépendamment, la chance qu'ils soient tous deux dans le carré du milieu est , que les deux soient dans n'importe quel carré d'angle est , et dans tout carré de bord est . Donc, la chance qu'ils soient dans le même carré approche car approche de l'infini. $(8/40)^2 = 64/1600$ $(3/40)^2=9/1600$ $(5/40)^2=25/1600$ $\frac{64+4\times9+4\times25}{1600} = \frac{200}{1600} = \frac{1}{8}$ $n$

Statisticien accidentel
la source

Oh, votre explication est vraiment bonne et je la comprends parfaitement !!

cube

Puis-je vous demander une dernière réflexion? Dans la dernière égalité 1/16 + 8 (9/1024) le nombre 8 est le résultat des dimensions de l'échiquier? Peu importe que nous ayons un échiquier 3x3?

cube

Les carrés de bord sont des carrés qui sont à l'extérieur, mais pas dans un coin. Chaque carré de bord a cinq voisins: le carré du milieu, deux autres carrés de bord et deux carrés de coin.

Statisticien accidentel du

Il suffit que le graphique ne soit pas orienté (si vous pouvez passer de A à B, vous pouvez passer de B à A), fini (nombre fini de carrés) et complet (pas de sous-groupe de carrés d'où il n'y a pas d'échappatoire), et la probabilité de se déplacer dans une certaine direction à partir d'un carré étant la même pour chaque direction. Dans ce cas, la probabilité d'être dans un carré converge avec le temps pour être proportionnelle au nombre de carrés adjacents. Vous pouvez le vérifier en résolvant soit pour comme dans la réponse de vinux, soit en résolvant l'équation d'équilibre détaillée, ce qui est plus facile.

π P = π

$\pi P=\pi$

Statisticien accidentel,

+1 C'est une jolie réponse. Un moyen simple de justifier l'assertion citée par @xan consiste simplement à appliquer la matrice de transition à ce vecteur de proportions: vous obtiendrez le vecteur lui-même (à partir de sa définition même!), En montrant qu'il s'agit d'un vecteur propre de valeur propre . Parce que tous les états sont connectés, c'est la distribution limite. (En d'autres termes, vous n'avez pas réellement à résoudre ; il vous suffit de vérifier la solution que vous avez proposée.)

1

$1$

π P = π

$\pi P = \pi$

whuber

Vous pouvez résoudre en utilisant la matrice de probabilité de transition.

$\begin{bmatrix} C_1 & C_2 & C_3 \\ C_4 & C_5 & C_6 \\ C_7 & C_8 & C_9 \\\end{bmatrix}$

Construire une matrice de probabilité de transition, en utilisant la probabilité d'une cellule à l'autre. Par exemple: . P sera une matrice . $P[C_1, C_2] = P[C_1, C_4]= P[C_1, C_5] = \frac{1}{3}$ $9 \times 9$

Vous pouvez maintenant calculer les probabilités stationnaires (puisque tous les états sont récurrents).

Résolvez telle sorte que . $\pi P = \pi$ $\sum \pi =1$

Cela donne la probabilité qu'un roi dans un carré particulier soit n grand. Utilisez la propriété d'indépendance, vous pouvez arriver à la probabilité requise.

vinux
la source