Caminata aleatoria sobre un cubo:Probabilidad de volver de nuevo

Question

Hay un cubo y una hormiga es la realización de una caminata al azar en los bordes donde se puede seleccionar cualquiera de los 3 vértices adyacentes con la misma probabilidad. ¿Cuál es la probabilidad de que una hormiga se encuentra en el vértice se inició después de N pasos?

Lo he intentado->

Romper problema más simple, donde vemos a la distancia desde el inicio de vértice. Así que de los 8 vértices, tenemos 1 con distancia 0(nuestro inicio), 3 con la distancia de 1, 3 con la distancia de 2 y 1 con la distancia de 3.

También, y sólo puede volver si N es par. Así que la probabilidad es 0 cuando N es impar.

Answer 1

La probabilidad es cero si $N$ es impar.

Después de dos pasos, comenzando en el vértice, la probabilidad de de regreso de es $1/3$. De lo contrario, el pie se mueve a un vértice a distancia $2$ original desde el vértice.

Partir de un vértice a distancia $2$ original desde el vértice, después de dos pasos, la probabilidad de que vuelve a la original vértice es $2/9$. De lo contrario, se mueve a un vértice a distancia $2$ original desde el vértice.

Por lo que la probabilidad de retorno después de $2n$ pasos es la parte superior izquierda la entrada de la matriz $$\pmatrix{1/3&2/3\\2/9&7/9}^n.$$ Usted puede calcular por cualquier método estándar (diagonalisation, generando funciones, etc.).

Answer 2

Enfoque básico. Me gustaría tomar ventaja de algunas simetrías aquí. Hay tres vértices a distancia $1$ desde el inicio, tres vértices a distancia $2$ desde el inicio, y un vértice a distancia $3$ desde el inicio. Mostrar que la distancia del vértice desde el principio está representado por una de cuatro estados de la cadena de Markov con las siguientes probabilidades de transición:

$$ p_{01} = 1 $$ $$ p_{10} = \frac13, p_{12} = \frac23 $$ $$ p_{21} = \frac23, p_{23} = \frac13 $$ $$ p_{32} = 1 $$

Representar esto como la matriz de $P$. Entonces, si denotamos la inicial de la distribución de probabilidad como $\pi = [1 \quad 0 \quad 0\quad 0]^\text{T}$, $P^N\pi$ representa la distribución de probabilidad de que el sistema después de $N$ pasos, y la probabilidad de estar en la posición de inicio después de $N$ pasos se puede leer como el primer elemento de la resultante de probabilidad del vector (es decir, el elemento superior izquierdo de la matriz). Como usted bien señala, es obvio que la paridad argumento muestra que la respuesta debe ser $0$ por extraño $N$.

Matriz de exponenciación muestra que el resultado es

$$ \frac14+\frac{1}{4\times3^{N-1}} $$