Línea infinita de personas

Question

Supongamos que tenemos una línea infinita de personas, y cada persona puede moverse hacia adelante o quedarse en el mismo lugar. Se mueven solo un paso a la vez. (Saltan de una posición a la siguiente si esa posición está vacía). Todas las personas se mueven o permanecen quietas simultáneamente.

Además, supongamos que una persona en la posición $x$ se moverá hacia adelante a la posición $x+1$ si las posiciones $x+1, x+2$ y $x-1$ están vacías. Para todas las demás personas, se mueven con una probabilidad $\alpha$.

¿Se puede demostrar que "eventualmente", solo habrá dos regiones, una donde la densidad es alta y otra donde la densidad es baja? (el carril rápido y el carril congestionado)

Una forma de pensar en esto es imaginar que las personas están en un bucle circular finito. (obviamente, entonces no hay personas infinitas en la línea)

EDIT:

Con el propósito de aclaración ya que muchas personas están preocupadas por la configuración inicial, si se asume que es lo suficientemente densa (más del 0,33). Podemos tener cualquier configuración inicial, no debería importar ya que estamos interesados en el comportamiento a largo plazo.

EDIT 2:

La objeción planteada a continuación en los comentarios es determinística. Sin embargo, la pregunta es acerca de lo estocástico, por lo tanto, podemos decir que $\alpha \not = 0$ o $1$.

Ejemplo: Que 1 sea una posición ocupada y un 0 una posición desocupada. Entonces podemos comenzar con

...1110001000...

y luego a continuación tenemos ya sea

...1110000100...

o

...1101000100...

dependiendo de si la persona que avanzó tenía la probabilidad $\alpha$ de avanzar.

EDIT: PROGRAMA EN C++

Programa que escribí. Archivo Quizás tengas que agregar un .exe al final si deseas ejecutarlo en Windows OS.

Mismo programa con colores corregidos y un marco de tiempo mucho más largo. Archivo2

Answer 1

Sospecho que la restricción "si los lugares x+1, x+2 y x-1 están vacíos" vuelve el problema más complejo sin agregar nada relevantemente conceptual.

No afirmo tener una respuesta, pero quiero señalar que el modelo tiene cierto parecido con algunos modelos físicos. En particular, consideremos el gas Tonk (o modelo de "barras duras"). Aquí, tenemos partículas unidimensionales de ancho fijo que se mueven en línea, y solo interactúan a través de colisiones elásticas duras. Una forma de simular estos modelos estadísticos (no su dinámica, sino sus configuraciones promedio) es a través de simulaciones de Montecarlo. En este procedimiento, producimos configuraciones aleatorias por alguna regla que genere un muestreo representativo del conjunto; en el modelo de barras duras, una regla posible sería desplazar las partículas (una a la vez o todas simultáneamente) una distancia aleatoria y "aceptar" la nueva configuración si ninguna partícula se superpone.

Ahora, el modelo presentado aquí tiene (para mí) cierto parecido con una simulación de Montecarlo de un sistema de barras duras con un "desplazamiento" añadido. No estoy seguro de si esa similitud puede ser exactamente determinada, pero sospecho que sí, y también sospecho que no hay una "separación de fases" como parece esperar.

Hice una pequeña simulación aquí (solo navegadores modernos con soporte para canvas: Chrome, Firefox - tal vez IE 9) http://hjg.com.ar/varios/mat/queuesimul.html

Actualización: lo siento, había interpretado mal el modelo. Mis pensamientos (y simulación) corresponden a otro modelo (las personas se mueven si la probabilidad 'a' es que los vecinos hacia adelante están vacíos)

Answer 2

Al haber visto las simulaciones, aquí hay algunas definiciones que pueden ayudar a aclarar el problema. (Aunque no tengo una solución.)

1. Primero, para definir la región libre versus la región atascada, la densidad esperada de cada región debería depender de $\alpha$.

   i. Digamos que empiezas con un solo bloque sólido. Para $\alpha = 0$ no habrá movimiento, por lo que la "región libre" estaría vacía. Pero para $\alpha = 1$, la gente se iría desprendiendo de la parte delantera de la cola, por lo que la región libre esperada debería tener cerca del 50% de densidad. En general, probablemente esperarías que la región libre tuviera una densidad de $\alpha / (\alpha + 1)$.

   ii. Por otro lado, digamos que empiezas con una configuración inicial alternada. Para $\alpha = 0$, esto no lleva a movimiento, y debería considerarse como atascado. Mientras que para $\alpha = 1$, esto lleva a un flujo continuo, y debería considerarse como no atascado.

   Entonces probablemente podamos definir libre y no libre basados en la proporción esperada de personas en movimiento. Digamos que un tramo de $K$ puntos tiene densidad $\delta$. Entonces deberías esperar $(1-\delta)^3K$ individuos que puedan fluir libremente, $[(1-\delta)\delta^2 + 2\delta(1-\delta)^2]K$ individuos que puedan fluir con probabilidad $\alpha$, y $\delta K$ individuos que estén necesariamente atrapados. Entonces la proporción esperada de individuos en movimiento es $$ P(\delta,\alpha) = (1-\delta)^3 + 2\alpha (1-\delta)^2\delta + (1-\delta)\delta^2 \alpha$$ así que quizás podamos definir arbitrariamente una región de flujo libre como aquella con densidad $\delta$ tal que $P(\delta,\alpha) > 2/3$ y una región atascada como aquella con densidad tal que $P(\delta,\alpha) < 1/3$ (los números 1/3 y 2/3 los saqué de la manga). En cualquier caso, dado que $\alpha$ y $\delta$ estarán entre 0 y 1, puedes comprobar que $P(\delta,\alpha)$ es una función decreciente de $\delta. Así que puedes definir $\delta_{max}$ como el límite inferior para la región atascada y $\delta_{min}$ como el límite superior para la región libre.

2. Sin embargo, para calcular $\delta$, necesitarás una ventana de tamaño $K$ sobre la cual calcular. Así que quizás lo que necesitamos hacer es fijar el número inicial de personas como muy grande, digamos $N > 10000$. Luego en cada punto calculamos la densidad de sus vecinos $\delta_K(x)$ como la densidad de las personas en la región $[x-50,x+50]$ (nuevamente, aquí seleccioné $K = 101$ bastante arbitrariamente, simplemente mucho menor que $N$). Entonces puedes definir adecuadamente la densidad cerca de un punto $x.

3. Entonces puedes reformular tu pregunta como preguntando lo siguiente. Dado $K$ mucho mayor que 1 y $N$ mucho mayor que $K$. Deja que tu proceso se ejecute con alguna densidad inicial $\delta_{min} < \Delta < \delta_{max}$ (para que no empieces con algo que ya esté completamente libre o completamente atascado) bajo la probabilidad $\alpha$. En cada punto $x$ calcula $\delta_K(x)$ como se mencionó anteriormente. Tu pregunta entonces trata sobre el número esperado de componentes de $\{x| \delta_K(x) > \delta_{max}\}$ y el número esperado de componentes de $\{x|\delta_K(x) < \delta_{min}\}$, el primero siendo el número de regiones atascadas y el segundo siendo el número de regiones libres.

O, quizás una formulación aún mejor (en lugar de los pasos 2 y 3 anteriores) de la pregunta puede ser la siguiente. Comienza con un número grande $N$ y probabilidad $\alpha$, con una configuración inicial con densidad $\delta_{min} < \Delta < \delta_{max}$. Demuestra o refuta que existe una constante $k$ que depende de $\delta_{max}$, $\delta_{min}$ y $\alpha$, tal que debe existir (con probabilidad 1), después de una evolución durante mucho tiempo, un conjunto contiguo de tamaño al menos $N/k$ en el que la densidad de las personas sea mayor que $\delta_{max}$ y un conjunto contiguo de tamaño al menos $N/k$ en el que la densidad de personas sea menor que $\delta_{min}$.

De esta manera, creo que tendrás un problema bien formulado y abordable matemáticamente. ¡Buena suerte!