Paseo aleatorio por las aristas de un cubo

Question

Una hormiga se coloca en una esquina de un cubo y no puede moverse. Una araña parte de la esquina opuesta y puede moverse por las aristas del cubo en cualquier dirección $(x,y,z)$ con igual probabilidad $1/3$ . En promedio, ¿cuántos pasos necesitará la araña para llegar a la hormiga?

(Esto no son deberes, era una pregunta de la entrevista).

Answer 1

Sugiero modelar el problema como una cadena de Markov donde cada estado representa la distancia entre la araña y la hormiga. En este caso tenemos 4 estados posibles $S_i$ como las distancias $i$ puede ser $\{0,1,2,3\}$ .

Cuando la araña se encuentra en la esquina opuesta del cubo, está a una distancia de 3 pasos de la hormiga. Se encuentra en el estado $S_3$ .

Construcción de la matriz de transición $\mathbf{P}$ .

• Si dibujamos un cubo vemos que cuando estamos en el estado $S_3$ Cada movimiento reduce la distancia entre la araña y la hormiga a 2 pasos. Así, cuando estamos en el estado $S_3$ nos trasladamos al estado $S_2$ con probabilidad 1.

• Cuando estamos en el estado $S_2$ podemos volver al estado $S_3$ utilizando la arista a la que llegamos desde allí o podemos disminuir la distancia a un solo paso si elegimos otras dos aristas. Así, cuando estamos en el estado $S_2$ podemos pasar al estado $S_1$ con una probabilidad de 2/3 y para afirmar $S_3$ con una probabilidad de 1/3.

• Cuando estamos en el estado $S_1$ podemos ir al estado $S_0$ utilizando una de las tres aristas posibles. Si utilizamos las otras dos, volvemos al estado $S_2$ . Por lo tanto, cuando estamos en el estado $S_1$ podemos pasar al estado $S_0$ con una probabilidad de 1/3 y para afirmar $S_2$ con una probabilidad de 2/3.

• Cuando lleguemos al estado $S_0$ Nos quedamos allí ya que es nuestro objetivo. $S_0$ es un estado absorbente.

\begin{equation} \mathbf{P} = \left[\begin{array}{cccc} P_{S_3 \to S_3} & P_{S_3 \to S_2}& P_{S_3 \to S_1} & P_{S_3 \to S_0} \\ P_{S_2 \to S_3} & P_{S_2 \to S_2}& P_{S_2 \to S_1} & P_{S_2 \to S_0} \\ P_{S_1 \to S_3} & P_{S_1 \to S_2}& P_{S_1 \to S_1} & P_{S_1 \to S_0} \\ P_{S_0 \to S_3} & P_{S_0 \to S_2} & P_{S_0 \to S_1}& P_{S_0 \to S_0} \\ \end{array} \ right] = \left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1/3 & 0 & 2/3 & 0 \\ 0 & 2/3 & 0 & 1/3 \\ 0 & 0 & 0 & 1 \\ \end{array} \[derecha] \N - fin {equation}

Se trata de una cadena de Markov absorbente con tres estados transitorios ( $S_3$ , $S_2$ , $S_1$ ) y un estado absorbente ( $S_0$ ).

Según la teoría, la matriz de transición de una cadena de Markov con $t$ estados transitorios y $r$ los estados absorbentes se pueden reescribir como \begin{equation} \mathbf{P} = \left[\begin{array}{cc} \mathbf{Q}_t &\mathbf{R} \\ \mathbf{0}_{r \times t} & \mathbf{I}_r \\ \end{array} \[derecha] \N - fin {equation}

donde $\mathbf{Q}_t$ es un $t \times t$ que muestra la probabilidad de pasar de un estado transitorio a otro estado transitorio, mientras que $\mathbf{R}$ es un $t \times r$ matriz con las probabilidades de transición de uno de los $t$ estados transitorios a uno de los $r$ estados absorbentes. La matriz de identidad $\mathbf{I}_r$ nos muestra que cuando alguno de los $r$ se alcanza el estado de absorción, no hay transición fuera de ese estado. La matriz de todos los ceros $\mathbf{0}_{r \times t}$ puede interpretarse como que no hay transición de ninguno de los $r$ estados absorbentes a cualquiera de los $t$ estados transitorios.

El $(i,j)$ entrada de $\mathbf{Q}_t$ representa la probabilidad de pasar de un estado $i$ a un estado $j$ en exactamente un paso. Para obtener la probabilidad de $k$ pasos que necesitamos el $(i,j)$ entrada de $\mathbf{Q}_t^k$ . Suma para todos $k$ obtenemos una matriz que contiene en su $(i,j)$ entrada el número esperado de visitas al estado transitorio $j$ tras partir del estado transitorio $i$ .

\begin{equation} \sum_{k=0}^{\infty} \mathbf{Q}_t^k = (\mathbf{I}_t - \mathbf{Q}_t)^{-1} \end{equation}

Para obtener el número de pasos hasta ser absorbido, basta con sumar los valores de cada fila de $(\mathbf{I}_t - \mathbf{Q}_t)^{-1}$ . Esto puede representarse mediante

\begin{equation} \mathbf{t} = (\mathbf{I}_t - \mathbf{Q}_t)^{-1} \mathbf{1} \end{equation}

donde $\mathbf{1}$ es un vector columna con todos los componentes iguales a 1.

Apliquemos esto a nuestro caso:

Como ya se ha dicho, en nuestro caso tenemos $t$ =3 estados transitorios y $r$ =1 estado absorbente, por lo tanto: \begin{equation} \mathbf{Q}_t = \left[\begin{array}{ccc} 0 & 1 & 0 \\ 1/3 & 0 & 2/3\\ 0 & 2/3 & 0 \\ \end{array} \[derecha] [cuadrado] [cuadrado] \mathbf{R} = \left[ \begin{array}{c} 0 \\ 0\\ 1/3 \\ \end{array} \[derecha] \N - fin {equation}

La matriz con el número esperado de visitas es \begin{equation} (\mathbf{I}_t - \mathbf{Q}_t)^{-1} = \left[\begin{array}{ccc} 2.5 & 4.5 & 3 \\ 1.5 & 4.5 & 3\\ 1 & 3 & 3 \\ \end{array} \[derecha] \N - fin {equation}

Esta matriz puede interpretarse como sigue. Partiendo del estado $S_3$ y antes de ser absorbido en $S_0$ que visitamos, por término medio, $S_3$ 2,5 veces, $S_2$ 4,5 veces, y $S_1$ 3 veces.

El número esperado de pasos desde el estado $S_3$ al estado $S_0$ viene dada por la primera componente del siguiente vector:

\begin{equation} \mathbf{t} = \left[\begin{array}{ccc} 2.5 & 4.5 & 3 \\ 1.5 & 4.5 & 3\\ 1 & 3 & 3 \\ \end{array} \[derecha] [izquierda] \begin{array}{c} 1 \\ 1\\ 1\\ \end{array} \ right] = \left[ \begin{array}{c} 10 \\ 9\\ 7\\ \end{array} \[derecha]. \fin{s} {equipamiento}

El segundo y tercer componente de $\mathbf{t}$ son el número esperado de pasos para $S_0$ si partimos de $S_2$ y $S_1$ respectivamente.

Answer 2

Dejemos que $x^*$ sea el número de pasos esperados. Sea $x_1$ sea el número de pasos esperados desde cualquier esquina adyacente al origen de la araña y $x_0$ lo mismo para la hormiga.

Entonces $x^* = 1 + x_1$ y $x_0 = 1 + \frac{2}{3}x_1$ . Desde $$x_1 = 1 + \frac{2}{3}x_0 + \frac{1}{3}x^*= 1 + \frac{2}{3}x_0 + \frac{1}{3} + \frac{1}{3}x_1$$

conseguimos que $x_1 = x_0 + 2$ . Así que $x_0 = 1 + \frac{2}{3}x_0 + \frac{4}{3}$ lo que implica que $x_0=7$ y $x_1=9$ .

Obtenemos nuestra respuesta como $x^*=10$ .

Editar:

Si dibujamos el cubo con coordenadas $(x, y, z)$ entonces $111$ es la posición inicial de la araña y $000$ la posición de la hormiga.

La araña puede moverse a cualquiera de los dos $011$ , $101$ o $110$ .

Por la simetría del cubo estos deben tener el mismo número de pasos esperados hasta la hormiga, denotado por $x_1$ . Desde $x_1$ podemos volver al origen (con probabilidad $1/3$ ) o (con probabilidad $2/3$ ) podemos ir a uno de los puntos $001$ , $100$ , $010$ dependiendo del estado en el que nos encontremos.

De nuevo, por simetría, estos puntos tendrán el mismo número de pasos esperados que llamamos $x_0$ . Desde estas posiciones podemos llegar a la meta en un paso con probabilidad $1/3$ o volver a uno de los $x_1$ -posiciones con probabilidad $2/3$ . Esto significa que $x_0 = \frac{1}{3}1 + \frac{2}{3}(1 + x_1) = 1 + \frac{2}{3}x_1$ .

Answer 3

Una buena abstracción para pensar en ello es esta:

Piensa en la posición de la hormiga como $(0,0,0)$ y la araña $(1,1,1)$ Ahora, cada movimiento que la araña pueda hacer cambiará exactamente uno de los tres componentes de $1\to0$ o $0\to1$ . Así que la pregunta es:

If I randomly switch bits in (1,1,1) after how many steps in average do I get 0,0,0

Vemos que el camino más corto son 3 interruptores. Como no importa con qué bit empiezo la probabilidad de que eso ocurra es 1 * 2/3 * 1/3 = 2/9 . Si cometemos 1 error (cambiar un bit de vuelta a 1) necesitaremos 5 pasos. Y las probabilidades de cometer un error son 7/9 - si queremos cometer un solo error, tenemos que volver desde allí y hacer todo bien de nuevo - así que la probabilidad de cometer exactamente 1 error que resulte en 5 pasos es 7/9 * 2/9 y la posibilidad de cometer 2 errores aka 7 pasos es (7/9)² * 2/9 y así sucesivamente.

Por lo tanto, la fórmula para el número medio esperado de pasos es:

$$\mathbb E(\mathrm{steps}) = \sum_{n=0}^{\infty} (3 + 2n) \cdot \frac{2}{9} \cdot \left ( \frac{7}{9} \right ) ^{n} = 10$$

Answer 4

Sólo para complementar la respuesta de tiagotvv:

No pienso naturalmente en este tipo de problemas como matrices (aunque lo sean). Tengo que dibujarlo, lo que he hecho a continuación. Puedes ver que hay 3 lugares para moverse desde S, todos los cuales son As. Desde cualquier A, puedes volver a la S, o moverte a una de las dos B. Desde cualquier B, puedes moverte a la E, o a uno de los dos As. Todo esto se traduce en la matriz de transición dada por tiagotvv, que también puede dibujarse en forma de gráfico.

Como se me dan fatal las matemáticas, sólo trataría de simular tu problema. Puedes hacerlo con el paquete markovchain en R.

  library(markovchain)
  library(ggplot2)

  # Create a markovchain object, given the states and their transition matrix

  mcCube <- new("markovchain", 
                states = c("S", "A", "B", "E"),
                transitionMatrix = matrix(data = c(0,   1,   0,   0,
                                                   1/3, 0,   2/3, 0,
                                                   0,   2/3, 0,   1/3,
                                                   0,   0,   0,   1), 
                                          byrow = T, nrow = 4),
                name = "cube")

  # The following code calcuates the probability of landing on E after taking
  # between 1 and 100 steps from the start, given the above set of transition
  # probabilities.

  start <- c(1, 0, 0, 0)

  list <- list()

  for (i in 1:100){

    list[[i]] <- (start * mcCube^i)[4] 

  }

   a <- do.call(rbind, list)

   data <- data.frame(propE = a, 
                      steps = c(1:100))

   ggplot(data, aes(x = steps, y = propE)) +
    geom_line(size = 1) +
    ylab("Probability you reached the spider") +
    xlab("Number of steps taken") +
    theme_bw() +
    theme(panel.grid.minor = element_blank())

  # This code simulates 1000 different applications of the markov chain where you 
  # take 1000 steps, and records the step at which you landed on E

  list <- list()
  for (i in 1:1000) {

    b <- rmarkovchain(n = 1000, object = mcCube, t0 = "S", include.t0 = T)

    list[[i]] <- 1001 - length(b[b == "E"])

  }

  data <- as.data.frame(do.call(rbind, list))

  ggplot(data, aes(x = V1)) +
    geom_density(fill = "grey50", alpha = 0.5) +
    geom_vline(aes(xintercept = mean(V1))) +
    ylab("Density") +
    xlab("Number of steps to reach E") +
    theme_bw() +
    theme(panel.grid.minor = element_blank())

  mean(data$V1)  # ~10 is the average number of steps to reach E in this set of
                 # simulations

La respuesta de tiagotvv se puede calcular en R como

q = matrix(c(0,   1,   0,   
             1/3, 0,   2/3, 
             0,   2/3, 0), byrow = T, nrow = 3)

(solve(diag(3) - q) %*% c(1, 1, 1))[1] # = 10

Answer 5

Paridad Las consideraciones dan una solución muy limpia, utilizando una maquinaria sorprendentemente sencilla: sin cadenas de Markov, sin expectativas iteradas y sólo con sumas de nivel escolar. La idea básica es que si la araña se ha movido un número par de veces en el $x$ dirección, ha vuelto a su $x$ coordenada así que no puede estar en la posición de la hormiga. Si se ha movido un número impar de veces en el $x$ dirección, entonces su $x$ coordenada coincide con la de la hormiga. Sólo si se ha movido un número impar de veces en las tres direcciones coincidirá con la $x$ , $y$ y $z$ coordenadas de la hormiga.

Inicialmente la araña ha hecho cero movimientos en cualquiera de las tres direcciones, por lo que la paridad para cada dirección es par. Las tres paridades tienen que ser volteadas para llegar a la hormiga.

Después del primer movimiento de la araña (etiquetemos esa dirección $x$ ), exactamente una dirección tiene paridad impar y las otras dos ( $y$ y $z$ ) son pares. Para atrapar a la hormiga, sólo hay que invertir esas dos paridades. Como eso no se puede conseguir en un número impar de movimientos posteriores, a partir de ahora consideramos pares de movimientos. Hay nueve combinaciones posibles para el primer movimiento emparejado:

$$(x,x), \,(x,y), \,(x,z), \,(y,x), \,(y,y), \,(y,z), \,(z,x), \,(z,y), \text{or} \,(z,z)$$

Tenemos que movernos en el $y$ y $z$ direcciones para llegar a la hormiga después de un movimiento emparejado, y dos de cada nueve combinaciones lo conseguirán: $(y,z)$ y $(z,y)$ garantizaría que las tres paridades son impar.

Las otras siete combinaciones dejan un impar y dos paridades. Los tres movimientos repetidos, $(x,x)$ , $(y,y)$ o $(z,z)$ , deja todas las paridades sin cambiar, por lo que seguimos necesitando una $y$ y una $z$ movimiento para llegar a la hormiga. Los otros pares contienen dos movimientos distintos, incluyendo uno en el $x$ dirección. Esto cambia la paridad de $x$ y una de las otras paridades (ya sea $y$ o $z$ ) por lo que aún nos queda un impar y dos paritarios. Por ejemplo, el par $(x,z)$ nos hace falta uno más $x$ y uno más $y$ para llegar a la hormiga: una situación equivalente (después de reetiquetar los ejes) a la que teníamos antes. A continuación, podemos analizar el siguiente movimiento emparejado de la misma manera.

En general, los movimientos emparejados comienzan con un impar y dos paridades, y terminarán con tres paridades de impar (con probabilidad $\frac{2}{9}$ ) y la captura inmediata de la hormiga, o con un impar y dos paridades (con probabilidad $\frac{7}{9}$ ) que nos devuelve a la misma situación.

Dejemos que $M$ sea el número de movimientos emparejados necesarios para llegar a la hormiga. Es evidente que $M$ sigue la distribución geométrica en el soporte $\{1, 2, 3, \dots\}$ con probabilidad de éxito $p = \frac{2}{9}$ por lo que tiene de medio $\mathbb{E}(M) = p^{-1} = \frac{9}{2} = 4.5$ . Dejemos que $N$ sea el número total de movimientos necesarios, incluyendo el movimiento inicial y el $M$ posteriores movimientos emparejados. Entonces $N = 2M + 1$ así, aplicando la linealidad de las expectativas, $\mathbb{E}(N) = 2\mathbb{E}(M) + 1 = 2 \times 4.5 + 1 = 10$ .

Como alternativa, puede observar $P(M \geq m) = (\frac{7}{9})^{m-1}$ y aplicar la conocida fórmula del media de una distribución discreta que sólo toma valores enteros no negativos , $\mathbb{E}(M)=\sum_{m=1}^\infty P(M\geq m)$ . Esto da $\mathbb{E}(M)=\sum_{m=1}^\infty (\frac{7}{9})^{m-1}$ que es una serie geométrica con el primer término $a=1$ y la relación común $r=\frac{7}{9}$ por lo que ha sumado $\frac{a}{1-r} = \frac{1}{1-7/9}=\frac{1}{2/9}=\frac{9}{2}$ . Podemos entonces tomar $\mathbb{E}(N)$ como antes.

Comparación con las soluciones de la cadena de Markov

¿Cómo podría haber detectado esto a partir de la matriz de transición de la cadena de Markov? Utilizando la notación de @DLDahly, los estados de la matriz de transición corresponden a mi descripción del número de direcciones con paridad impar.

La matriz de transición de un paso es

\begin{equation} \mathbf{P} = \left[\begin{array}{cccc} P_{S \to S} & P_{S \to A}& P_{S \to B} & P_{S \to E} \\ P_{A \to S} & P_{A \to A}& P_{A \to B} & P_{A \to E} \\ P_{B \to S} & P_{B \to A}& P_{B \to B} & P_{B \to E} \\ P_{E \to S} & P_{E \to A} & P_{E \to B}& P_{E \to E} \\ \end{array} \ right] = \left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1/3 & 0 & 2/3 & 0 \\ 0 & 2/3 & 0 & 1/3 \\ 0 & 0 & 0 & 1 \\ \end{array} \[derecha] \N - fin {equation}

La primera fila nos muestra que después de un movimiento, la araña está garantizada en el estado A (un impar y dos paridades). La matriz de transición de dos pasos es:

\begin{equation} \mathbf{P}^{(2)} = \mathbf{P}^{2} = \left[\begin{array}{cccc} 1/3 & 0 & 2/3 & 0 \\ 0 & 7/9 & 0 & 2/9 \\ 2/9 & 0 & 4/9 & 1/3 \\ 0 & 0 & 0 & 1 \\ \end{array} \[derecha] \N - fin {equation}

La segunda fila nos muestra que una vez que la araña ha entrado en el estado A, en dos movimientos de tiempo ha vuelto al estado A con probabilidad $7/9$ o ha alcanzado el estado E (todas las paridades Impares) y ha capturado a la hormiga, con probabilidad $2/9$ . Así que habiendo alcanzado el estado A, vemos a partir de la matriz de transición de dos pasos que el número de movimientos de dos pasos requeridos puede ser analizado usando la distribución geométrica como arriba. No es así como encontré mi solución, pero a veces vale la pena calcular las primeras potencias de la matriz de transición para ver si se puede explotar un patrón útil como éste. A veces he descubierto que esto da soluciones más sencillas que tener que invertir una matriz o realizar una eigendecomposición a mano, algo que, hay que reconocerlo, sólo es realmente relevante en una situación de examen o entrevista.