2 personas en una caminata al azar

Question

Digamos que usted tiene un edificio de $HJ$ habitaciones, donde $H$ $J$ son enteros positivos (una cuadrícula rectangular de habitaciones de tamaño $H$ veces $J$). Puede etiquetar las habitaciones $(h,j)$ donde$1 \le h \le H$$1 \le j \le J$. Una persona entra en el edificio de las habitaciones en $(1,j_0)$ y la otra persona entra en $(h_0,1)$. Después de cada minuto, se elige al azar a otra habitación, que debe ser adyacente a la misma ; es decir, si usted está en coordinar $(h,j)$, usted puede ir a $(h \pm 1, j)$ o a $(h, j \pm 1)$ con una probabilidad de $1/4$, pero la probabilidad que va a $1/3$ si usted está en un "lado" (es decir, a coordinar $(1,j)$ ir $(2,j)$ o $(1, j \pm 1)$ con una probabilidad de $1/3$y en coordinar $(1,1)$ ir $(2,1)$ o $(1,2)$ con una probabilidad de $1/2$). Cuando la persona que entró en $(1,j_0)$ llega a la sala de $(h_0,1)$, que "sale" del edificio usando la entrada de la otra persona usa (este no es el caso si la persona a $(1,j_0)$ vuelve a $(1,j_0)$). Lo mismo se aplica a la otra persona ; si la persona 2 se va de nuevo a la entrada de la persona 1 ella sale del edificio.

La pregunta es : ¿Cuál es la probabilidad de que las dos personas están en la misma habitación en algún punto durante su paseo?

Mis intentos : para $H=J=1$, la probabilidad es $1$. Para $H=2$ $J=1$ (o lo contrario) y $h_0 = H$, la probabilidad es cero, ya que las dos personas se cambie de habitaciones y de salida, independientemente de su reunión (los pasillos no cuenta :P). Así que parece que depende mucho de $H$$J$. En realidad, si $H = 1$$J \ge 1$, entonces la probabilidad es $1$ si $j_0$ es impar y $0$ si $j_0$ es aún, porque entonces el número de habitaciones entre las dos es siempre igual, así que para este número para llegar a $0$ debemos tener $j_0$ impar. Por el contrario, si $j_0$ es impar entonces a partir de dos personas que se ven obligadas a cruzar las mismas habitaciones que se deben cumplir en algún momento. Lo mismo va por la simetría si $J = 1$.

Obviamente no depende sólo de la paridad de $H$$J$ ; al $H$ $J$ no $1$ siempre hay caminos donde las dos personas que cumplen y no cumplen. Que puedo hacer a mano los cálculos de $H=J=h_0=j_0=2$, pero en el caso general, no tengo idea de cómo hacer frente a este problema. Esto es en realidad una pregunta en mi amigo de la tarea, y no hay nada en el curso acerca de los procesos estocásticos.

Gracias de antemano,

Answer 1

Aunque la siguiente iba a ser muy difícil en la práctica, en principio, no parece demasiado difícil. Pensé en lo siguiente:

Fijar las longitudes $H, J$ y la partida habitaciones $(1, j_0), (h_0, 1)$ de personas $1, 2$. Entonces, en cualquier momento dado la oportunidad de reunirse en el futuro depende de las posiciones actuales $(x_1, y_1)$$(x_2, y_2)$. Vamos a llamar a $P(x_1, y_1, x_2, y_2)$. (Técnicamente no debe ser una manera de especificar que la persona $1$ o de la persona $2$ ha abandonado el edificio, pero está claro que $P(\text{outside}, x_2, y_2) = 0$ y así sucesivamente.)

Mi idea es escribir $P(x_1, y_1, x_2, y_2)$ en términos de $P(x_1 \pm 1, y_1 \pm 1, x_2 \pm 1, y_2 \pm 1)$ (donde exactamente uno de $x_1, y_1$ cambios y uno de $x_2, y_2$ cambios) por $1 \leq x_i \leq H$$1 \leq y_i \leq J$. En general, habrá $4 \times 4 = 16$ tales términos, pero este enfoque pone fea porque de las paredes de la construcción y en las esquinas (en estos casos especiales, uno de los factores que se convierte en $3$ o $2$ respectivamente). Las entradas/salidas son especiales, pero también fáciles de manejar.

Ahora que hemos establecido el sistema lineal. Es simple, pero tedioso, así que voy a utilizar su juguete ejemplo donde $H = J = 2$ $(1, j_0) = (1, 2)$ $(h_0, 1) = (2, 1)$ (esto puede básicamente el uso de los mismos cálculos que hice, pero creo que voy a ver cómo generalizar). En este caso no se $3$ posible no salir de las posiciones para cada persona y por lo tanto $9 - 2 = 7$ (para el $2$ sin salir de las habitaciones para satisfacer en) las ecuaciones y las incógnitas. Escrito (y teniendo en cuenta el orden de los argumentos en $P(x_1, y_1, x_2, y_2)$), tenemos:

$$ P(1,1,1,1) = 1 \\ P(2,1,1,1) = 0 \text{ (salida)} \\ P(1,2,1,1) = \frac{1}{4}(P(2,2,2,1) + P(2,2,1,2) + P(1,1,2,1) + P(1,1,1,2)) \\ P(2,2,1,1) = \frac{1}{4}(P(1,2,2,1) + P(1,2,1,2) + P(2,1,2,1) + P(2,1,1,2)) \\ \\ P(1,1,1,2) = 0 \text{ (salida)} \\ P(2,1,1,2) = 0 \text{ (salida)} \\ P(1,2,1,2) = 1 \text{ (incluso si la salida)} \\ P(2,2,1,2) = 0 \text{ (salida)} \\ \\ P(1,1,2,1) = \frac{1}{4}(P(2,1,1,1) + P(2,1,2,2) + P(1,2,1,1) + P(1,2,2,2)) \\ P(2,1,2,1) = 1 \text{ (incluso si la salida)} \\ P(1,2,2,1) = \frac{1}{4}(P(2,2,1,1) + P(2,2,2,2) + P(1,1,1,1) + P(1,1,2,2)) \\ P(2,2,2,1) = \frac{1}{4}(P(1,2,1,1) + P(1,2,2,2) + P(2,1,1,1) + P(2,1,2,2)) \\ \\ P(1,1,2,2) = \frac{1}{4}(P(2,1,1,2) + P(2,1,2,1) + P(1,2,1,2) + P(1,2,2,1)) \\ P(2,1,2,2) = 0 \text{ (salida)} \\ P(1,2,2,2) = \frac{1}{4}(P(2,2,1,2) + P(2,2,2,1) + P(1,1,1,2) + P(1,1,2,1)) \\ P(2,2,2,2) = 1 $$

Después de la sustitución de todos los valores en los siete no trivial ecuaciones, obtenemos:

$$ P(1,2,1,1) = \frac{1}{4}(P(2,2,2,1) + P(1,1,2,1)) \\ P(2,2,1,1) = \frac{1}{4}(2 + P(1,2,2,1)) \\ \\ P(1,1,2,1) = \frac{1}{4}(P(1,2,1,1) + P(1,2,2,2)) \\ P(1,2,2,1) = \frac{1}{4}(2 + P(2,2,1,1) + P(1,1,2,2)) \\ P(2,2,2,1) = \frac{1}{4}(P(1,2,1,1) + P(1,2,2,2)) \\ \\ P(1,1,2,2) = \frac{1}{4}(2 + P(1,2,2,1)) \\ P(1,2,2,2) = \frac{1}{4}(P(2,2,2,1) + P(1,1,2,1)) $$

Para las probabilidades en este orden, este sistema tiene la solución única $\frac{1}{7}(0,5,0,6,0,5,0)$, y el valor de $P(1, j_0, h_0, 1) = P(1,2,2,1) = \frac{6}{7}$ es la respuesta que se obtuvo anteriormente. Para grandes edificios, el sistema acaba de ser más grande.

(Mirando a la solución, nosotros, evidentemente, podría haber eliminado cerca de la mitad de las ecuaciones usando la paridad de consideraciones: en cualquier momento, $x_1 + y_1 + x_2 + y_2 \equiv 1 + j_0 + h_0 + 1 \equiv j_0 + h_0 \text{ (mod } 2)$. Podría ayudar un poco en la solución del sistema.)

Por supuesto, esto no estaría tan elegante como desee, pero eso es todo lo que sé. Tal vez la intención de su amigo para representar cosas mediante $H \times J$ matrices. (Me interesaría saber su respuesta, por cierto).

Answer 2

Con la ayuda de un programa GP, he obtenido la probabilidad de que al $J=2$$j_0=h_0=2$, para$H$$2$$10$. Los primeros valores son :

$$ p_2=\frac{6}{7} (\ {\rm \ se \ ya \ mencionados \ por \ varios \ otros \ personas \ aquí }) $$

$$ p_3=\frac{58925}{79311} $$

$$ p_4=\frac{667042459265}{982993299201} $$

$$ p_5=\frac{1195623797792938901759}{1790700722288716572625} $$

Las fracciones de conseguir más y más complicado, y no veo el punto en la reproducción de todos ellos aquí. Parece que el $(p_H)$ de disminución y converge a un límite alrededor de $0.663$.

Algunos detalles de la programación : la teoría de los procesos estocásticos, todo se reduce al cálculo del núcleo de una $(JH)^2 \times (JH)^2$ matriz (y además $J=2$ en los valores de arriba). El tiempo más largo que el cálculo que he hecho, para$p_{10}$, $400 \times 400$ de la matriz y se lleva el GP de dos minutos para calcular todo.

Answer 3

Para un determinado $H$$J$, no existe un estándar de "fuerza bruta" método para calcular este tipo de probabilidad de que no requiere ningún tipo de inteligencia. En primer lugar, contar cuántas configuraciones hay. Un método es para decir que hay una configuración de uno de los tres tipos:

• La declaración de que la primera persona en la sala de $(a,b)$ y la segunda persona en la sala de $(c,d)$, y que no han cumplido
• La declaración de que las dos personas se han reunido
• La declaración de que una persona ha salido de la construcción

Hay formas de utilizar el menor número de configuraciones, pero estoy con el objetivo de explicar la idea de la manera más simple. También, menos no podría ser mejor.

Supongamos que hay $M$ configuraciones en todos. Podemos escribir una $M \times M$ matriz $A$ con la propiedad de que la $m$-ésima componente del vector $A \mathbf{\hat{e}}_n$ es la probabilidad de que la configuración de $n$ transición para la configuración de $m$ donde $\mathbf{\hat{e}}_n$ es un estándar de base de vectores.

Con esta matriz $A$, es fácil de escribir distintas probabilidades. Por ejemplo, si la configuración #1 es el punto de partida confiruation y configuración #M es la declaración de que las dos personas se han reunido, a continuación, $ \mathbf{\hat{e}}_M^t A^k \mathbf{\hat{e}}_1 $ es la probabilidad de que las dos personas se encuentran en algún momento dentro de $k$ minutos de partida. Tenga en cuenta que por diagonalizing $A$, usted puede conseguir un 'directo' de la fórmula para esta probabilidad.

Para hallar la probabilidad de que cumplan a lo largo del tiempo, usted puede tomar el límite de $k \to \infty$. De hecho, el límite de $\lim_{k \to \infty} A^k$ debe existir, que voy a llamar a $A^\infty$. El vector $A^\infty \mathbf{\hat{e}}_1 $ debe ser realmente el "situación estable" de la distribución. Dado el problema en particular, debe tener sólo dos a cero de los componentes, correspondientes a las posibilidades que he conocido o que uno ha salido de la construcción.