Passeio aleatório: reis em um tabuleiro de xadrez

Eu tenho uma pergunta sobre a caminhada aleatória de dois reis em um tabuleiro de xadrez 3 × 3.

Cada rei está se movendo aleatoriamente com igual probabilidade neste tabuleiro de xadrez - vertical, horizontal e diagonal. Os dois reis estão se movendo independentemente um do outro no mesmo tabuleiro de xadrez. Os dois começam no mesmo quadrado e depois se movem de forma independente.

Como poderíamos encontrar a probabilidade no tempo ambos estão no mesmo quadrado, como vai para o infinito? $n$ $n$

self-study markov-chain random-walk cubo
fonte

O que é "a mesma área"? Você quer dizer "o mesmo quadrado?"

Peter Flom

Ah sim, desculpe !!!

Cube8

Use abordagem matriz de probabilidades de transição

vinux

se eu fizer isso com a matriz de probabilidade de transição, primeiro tenho que encontrar a matriz de probabilidade de transição do passeio aleatório do primeiro rei e depois aumentá-lo no 2?

Cube

é um exercício que eu tenho e eu estou tentando resolvê-lo para um monte de dias agora, que foi a minha última idéia para obter uma boa idéia de como lidar com isso ..

cubo

Respostas:

Vamos explorar a simetria para simplificar os cálculos.

O tabuleiro de xadrez e seus movimentos permanecem os mesmos quando o tabuleiro é refletido na vertical, na horizontal ou na diagonal. Isso decompõe seus nove quadrados em três tipos, suas órbitas sob esse grupo de simetria. Da mesma forma, cada rei pode estar em um dos três "estados": um quadrado de canto ( ), um quadrado de extremidade ( ) ou o quadrado central ("do meio") ( ). (Um estado ignora em que quadrado particular um rei está e rastreia apenas sua classe de equivalência no grupo de simetrias.) $C$ $E$ $M$

Os seguintes resultados são imediatos:

De um quadrado de canto, há duas transições para quadrados de aresta e uma transição para um quadrado do meio. Como as três transições são equiprobáveis,

$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.$
Isso fornece uma linha em uma matriz de transição para os estados . $(0, 2/3, 1/3)$ $(C, E, M)$
De um quadrado de aresta, há duas transições para quadrados de canto, duas para outros quadrados de aresta e uma para o quadrado do meio. Isso fornece uma segunda linha em uma matriz de transição. $(2/5, 2/5, 1/5)$
No quadrado do meio, existem quatro transições para quadrados de canto e quatro para quadrados médios. A terceira linha de uma matriz de transição é, portanto, . $(4/8, 4/8, 0) = (1/2, 1/2, 0)$

Neste gráfico que representa essa cadeia de Markov, as probabilidades de transição são representadas pela espessura e cor da aresta:

Figura

Por inspeção ou não, descobrimos que um vetor próprio esquerdo de sua matriz de transição

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)$

é . Essa afirmação é facilmente verificada executando a multiplicação: O valor próprio manifestamente é . Como todos os estados estão conectados, fornece as probabilidades limitantes de cada rei estar em cada estado; precisamos apenas redimensionar seus componentes para somar à unidade: $\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).$

(É aqui que colhemos os benefícios de explorar a simetria: em vez de trabalhar com uma matriz de nove por nove de elementos, precisamos apenas calcular com uma matriz de três por três de elementos. A redução do problema de nove estados para três compensado quadraticamente, reduzindo o esforço computacional por um fator de ) $81$ $9$ $(9/3)^2 = 9$

A chance (limitadora) de que ambos os reis estejam em um estado de probabilidade (limitativa) é porque os reis se movem independentemente. A probabilidade de que ambas as reis estão na mesma célula é encontrado por condicionado no estado: por simetria, cada célula num determinado estado tem a mesma probabilidade limitando, por isso, se ambos os reis são encontrados num estado possuindo células, a chance de que eles ambos estão na mesma célula é . De onde a solução é $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
fonte

O Reader @xan faz alguns comentários muito interessantes após a (bela) resposta do Statistical Accidental neste tópico. Esses comentários apontam para uma lacuna lógica em meu argumento: é necessário também mostrar que os dois reis podem (em algum sentido intuitivo) realmente se mover independentemente um do outro. O exemplo de Xan diz respeito a reis que não podem fazer movimentos diagonais: se um rei começa no estado e o outro em ou , eles nunca podem ocupar o mesmo quadrado! Essa diferença pode ser corrigida considerando uma matriz de transição para pares de estados ordenados.

E

$E$

C

$C$

M

$M$

whuber

Obrigado por esta resposta, muito interessante e esclarecedor!

Cube

@ user929304 Está correto. Se você imaginar uma situação diferente em que essas probabilidades sejam cada (digamos) , o que é bem possível - o total delas é apenas para cada rei -, sua fórmula daria uma probabilidade de que está obviamente errado.

1 / 3

$1/3$

2 / 3

$2/3$

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

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

whuber

@ user929304 A probabilidade da união é a soma das probabilidades somente quando os eventos são desassociados (também conhecido como "mutuamente exclusivos"). Desarticular não é o mesmo que ser independente - na verdade, é uma violação bastante extrema da independência.

whuber

@ user929304 Cox e Miller são acessíveis e cobrem muito terreno.

whuber

Como os dois reis estão se movendo de forma independente, você pode considerá-los separadamente. Se o quadro é de tamanho finito e não possui subseções fechadas, esse é um daqueles casos em que a distribuição estacionária pode ser encontrada resolvendo a equação de balanço detalhada.

Nesse caso, quando vai ao infinito, a probabilidade de um rei estar em um quadrado se torna proporcional ao número de quadrados adjacentes a ele, ou seja, três para cada quadrado de canto, cinco para cada quadrado de borda e oito para o quadrado do meio. Isso significa , então a chance de estar no quadrado do meio é , em qualquer quadrado do canto é e em qualquer quadrado da borda é . $n$ $40$ $8/40$ $3/40$ $5/40$

Como isso é verdade para os dois reis independentemente, a chance de ambos estarem no quadrado do meio é , de ambos estarem em qualquer quadrado de canto é , e em qualquer quadrado da aresta é . Portanto, a chance de eles estarem no mesmo quadrado se aproxima de quando aproxima do infinito. $(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$

Estatístico acidental
fonte

Oh, sua explicação é realmente boa e eu entendo perfeitamente !!

cubo

Posso perguntar mais uma vez: na última igualdade 1/16 + 8 (9/1024), o número 8 é o resultado das dimensões do tabuleiro de xadrez? Não importa se temos um tabuleiro de xadrez 3x3?

cubo

Quadrados de borda são quadrados que estão do lado de fora, mas não em um canto. Cada quadrado de borda tem cinco vizinhos: o quadrado do meio, dois outros quadrados de borda e dois quadrados de canto.

Estatística acidental

É suficiente que o gráfico não seja direcionado (se você pode passar de A para B, você pode passar de B para A), finito (número finito de quadrados) e completo (sem subgrupo de quadrados dos quais não há escapatória) e pois a probabilidade de se mover em uma determinada direção a partir de um quadrado é a mesma para todas as direções. Nesse caso, a probabilidade de estar em um quadrado converge ao longo do tempo para ser proporcional ao número de quadrados adjacentes. Você pode verificar isso resolvendo para como na resposta do vinux ou resolvendo a equação detalhada do balanço, que é mais fácil.

π P = π

$\pi P=\pi$

Estatístico acidental

+1 Esta é uma resposta bonita. Uma maneira simples de justificar a afirmação citada por @xan é apenas aplicar a matriz de transição a esse vetor de proporções: você obterá o próprio vetor (a partir de sua própria definição!), Mostrando que é um vetor próprio do valor próprio . Como todos os estados estão conectados, essa é a distribuição limitadora. (Em outras palavras, você realmente não precisa resolver ; você só precisa verificar a solução que você propôs.)

1

$1$

π P = π

$\pi P = \pi$

whuber

Você pode resolver usando a matriz de probabilidade de transição.

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

Construa a matriz de probabilidade de transição, usando a probabilidade de uma célula para outra. Por exemplo: . P será uma matriz . $P[C_1, C_2] = P[C_1, C_4]= P[C_1, C_5] = \frac{1}{3}$ $9 \times 9$

Agora você pode calcular probabilidades estacionárias (como todos os estados são recorrentes).

Resolva modo que . $\pi P = \pi$ $\sum \pi =1$

Isso dá a probabilidade de um rei em particular quadrado como n grande. Use a propriedade independência para chegar à probabilidade requerida.

vinux
fonte