¿Cómo puedo calcular el tiempo golpea en una cadena de Markov finita? (para cuantificar mi Machi Koro pwnage)

Question

En un juego de Machi Koro, tuve la Barra de Sushi (activo), mientras que mi oponente tenía un Campo de Trigo y Panadería con ninguna baja rollo de edificios disponibles. Quiero saber cuánto tiempo tienen que rodar antes de que puedan permitirse el lujo de la Estación de Tren.

Es decir, están inmersos en una cadena de Markov, donde el espacio de estado es "0 a 4 monedas" ($\{0, 1, 2, 3, 4\}$) y quiero saber la probabilidad de que, para cada una de las $n$, que llegan a $4$ por primera vez después de exactamente $n$ transiciones (preferiblemente de partida para todos los estados, pero sólo por cero es bastante interesante). Yo también podría estar interesado en la versión acumulativa: para cada una de las $n$, ¿cuál es la probabilidad de que ellos han alcanzado $4$ al menos una vez después de $n$ transiciones.

Las probabilidades de transición son como sigue: de $k$ monedas, $k < 4$: $1$ con una probabilidad de $1/6$; de lo contrario, a $k$ con una probabilidad de $3/6$ $k+1$ con una probabilidad de $2/6$. Dado que las transiciones de $4$ a algo no muy interesante, voy a definir arbitrariamente como $4$ $4$con una probabilidad de $1$ (de verdad que voy a pasar de todas sus monedas, pero las preguntas no te importa lo que sucede después de la $4$ es alcanzado).

Enunciados:

$\left[ \begin{matrix} 3/6 & 3/6 & & & \\ & 4/6 & 2/6 & & \\ & 1/6 & 3/6 & 2/6 & \\ & 1/6 & & 3/6 & 2/6 \\ & & & & 1 \end{de la matriz} \right]$

(La probabilidad en la fila $i$ columna $j$ es la probabilidad de transición de la $i$ $j$monedas en un solo paso.)

Algunos análisis: en la transición de la gráfica, hay fuertemente de los componentes conectados a $\{0\}, \{1, 2, 3\}$ $\{4\}$ con transiciones $0 \rightarrow 1$$3 \rightarrow 4$. Tal vez ayuda a analizar cada uno de scc por separado. Ir de cero monedas de a uno en $k$, $k > 0$, con una probabilidad de $2^{-k}$; el grande esencialmente se reduce a "¿qué tan rápido incremento de su estado tres veces en una fila (cada w. prob. $2/6$) sin volver a caer en $1$ (w. p. $1/6$ cada paso)". No estoy seguro de cómo analizar esto, sin embargo.

Yo probablemente podría deletrear mi camino a través de https://en.wikipedia.org/wiki/Markov_chain pero dado que mi matriz-fu es un poco oxidado, algunos sostener la mano se agradece.

Edit: vamos a pensar en ello, dado que el Ayuntamiento de la Ciudad de la transición de la $0$ $1$ con una probabilidad de $1$. El 50/50-fuera-de-0 ocurriría si yo tenía tres Cafés en lugar de la Barra de Sushi, y fuimos a jugar sin el Puerto de expansión. Siéntase libre de analizar-o ambos! También, para efectos de simplificar los cálculos, en ambos casos estoy ignorando el hecho de que mi oponente gana una moneda cada vez que me levanto un 1.

Answer 1

Un poco de simulación puede decir algo acerca de la forma de la distribución. Vea a continuación la simulación de código.

Basado en 100.000 juegos, el cuartil inferior () límites a las 8, 12 y 20; es decir, en menos del 25% de los juegos de cuatro monedas son alcanzados por turno de 8 o anterior, y en más de 25% de los juegos de cuatro monedas son alcanzados por la curva 9 (o anterior).

El decil (inferior) los límites son 5, 7, 8, 10, 12, 14, 18, 22, 29.

Basado en un poco simplista de la simulación de dos competidores estrategias que se centran en la Tienda de Conveniencia y una Fábrica de Quesos, respectivamente, la mediana y el modo de juego de la longitud de entre 25 y 30 (en 1000 juegos), que van desde los 20 a los 60, caerse rápidamente de 40 y más allá.

El acumulativa de probabilidad de llegar a 4 por primera vez por turno $n$, empezando con 0 monedas, se da a continuación, hasta el 50%. Tenga en cuenta que no se puede hacer antes de la curva 4. La cola derecha va hacia el 100% como $n$ va al infinito, por supuesto; se cruza el 99% en los giros, 54-55, el 99,9% en los giros, 79-80 y 99.99 en las curvas 108-109.

$\begin{array}{r|r} \textrm{turn} & \textrm{cumul. prob.} \\ \hline 4 & 1.825\% \\ 5 & 5.787\% \\ 6 & 11.450\% \\ 7 & 17.811\% \\ 8 & 24.228\% \\ 9 & 30.599\% \\ 10 & 36.591\% \\ 11 & 42.104\% \\ 12 & 47.358\% \\ 13 & 52.032\% \\ \end{array}$

Aquí está la simulación de código:

#!/somewhere/over/the/rainbow/python
from random import choice
from collections import Counter

probs = [(0, 1),
         (1, 1, 2),
         (1, 2, 2, 2, 3, 3),
         (1, 3, 3, 3, 4, 4)]

def simulation(state=0, target=4):
    k = 0
    while state != target:
        state = choice(probs[state])
        k += 1
    return k

def many(n, state=0, target=4):
    return Counter(simulation(state, target) for _ in range(n))

n = 100000
histogram = many(n)
cumulative = 0.0
pct = lambda x: 100 * x / float(n)
for i in range(max(histogram.keys())):
    cumulative += histogram[i]
    print '%5d: % 7.3f%% (cumulative % 7.3f%%)' % \
        (i, pct(histogram[i]), pct(cumulative))

Diviértete corriendo a sus propias simulaciones. En una analítica de respuesta, y una explicación de las técnicas para encontrar, todavía va a ser muy apreciado :-)

Answer 2

He encontrado la siguiente respuesta a una pregunta relacionada con: http://math.stackexchange.com/a/1317088/234337.

Yo también deriva la principal fórmula de mí mismo. Deje $t_i$ ser el número esperado de transiciones antes de las 4 monedas se alcanza, cuando se comienza con $i$ monedas. A continuación,$t_0 = 1 + (\frac12 t_0 + \frac12 t_1)$, lo que implica que $t_0 = 2 + t_1$. Por similares sustituciones y un poco de complejo de álgebra, $t_1 = 3 + t_2$$t_2 = \frac92 + t_3$$t_3 = \frac{81}{12}$. Poner esto juntos, $t_0 = \frac{65}4 = 16.25$.

También leí un poco del libro vinculado en la respuesta, que me ayudó a entender lo álgebra lineal a hacer. Aquí un poco de código para calcular una respuesta exacta a la pregunta "¿cuál es la probabilidad de haber alcanzado 4 monedas al menos una vez en turno $n$ o anterior":

import numpy
from fractions import Fraction as frac

p = [[frac(1, 2), frac(1, 2),          0,          0,          0],
     [         0, frac(4, 6), frac(2, 6),          0,          0],
     [         0, frac(1, 6), frac(3, 6), frac(2, 6),          0],
     [         0, frac(1, 6),          0, frac(3, 6), frac(2, 6)],
     [         0,          0,          0,          0,          1]]

p = numpy.matrix(p)
cumulative = p.copy() * p * p

pct = lambda frac: float(100 * frac)
for i in range(4, 60):
    before = cumulative[0, 4]
    cumulative *= p
    after = cumulative[0, 4]
    print '%2d %7.3f (%5.3f)' % (i, pct(after), pct(after - before))

La distribución se imprime aproximadamente coincide con el resultado de mi simulaciones en otra respuesta; las desviaciones son lo suficientemente pequeños que no tengo la sospecha de una equivocada aplicación o una aplicación correcta de la cosa equivocada.

Estoy atascado con una observación: el segundo cuartil de corte es de entre 12 y 13, sin embargo, la espera de golpear tiempo es $\not \in [12, 13]$, que yo ingenuamente esperar. Sospecho que esto es debido a que la frecuencia de corte es la mediana de golpear tiempo, mientras que la expectativa es la media; en la tierra de los ciegos, todos, pero el tuerto rey por debajo del promedio de la visión.

El código siguiente puede ser útil si desea editar el anterior para tomar el otro jugador del Campo de Trigo en cuenta; cada estado es entonces Una de las monedas en el inicio de la B del turno, donde B (me) tiene las tres Cafés.

from collections import Counter
for k in range(4):
    histogram = Counter()
    for me in range(1, 7):
        for you in range(1, 7):
            coins = k + (me == 1)
            if you == 1:
                coins = max(coins - 3, 0) + 1
            elif you in (2, 3):
                coins += 1
            histogram[coins] += 1
    print k, sorted(histogram.items())