El camino más corto en el primer paso de percolación

Question

Considere la posibilidad de un cuadrado plano de cuadrícula. (Los vértices son par de puntos en el plano con coordenadas enteras y dos vértices son adyacentes si están de acuerdo en una coordenada y se diferencian por uno en el otro.)

Dar a cada borde de una longitud de uno con una probabilidad de un medio de longitud y dos con una probabilidad de un medio.

Considere la posibilidad de un camino más corto entre el origen y el vértice $(n,0)$.

Muestran que, con probabilidad de que tiende a uno como $$ n tiende a infinito de la ruta más corta será que no contienen el "centro del borde" en el eje x entre el origen y $(n,0)$. (Es decir, la arista entre los vértices $(\lfloor\frac{n}{2}\rfloor,0)$ y $(\lfloor\frac{n}{2}\rfloor+1,0)$.)

---

Esta pregunta está en la categoría de "falta un lexema". En realidad no es una de pleno derecho, abrir problema, sino una declaración de lo que parece correcto que necesitaba era un poco de papel y se resistió a la prueba. Por supuesto, algunas de esas "lemas" llegar a ser muy difícil, pero a veces tal vez un simple argumento era simplemente se perdió. El papel relevante de es con Itai Benjamini y Oded Schramm: Primer Paso de Percolación Ha Sublinear Distancia de la Varianza

---

Mientras que MO ha elegido a aceptar una respuesta, y hubo algunas buenas sugerencias, el problema sigue abierto.

Answer 1

Gil: Este es un tipo de problema que yo sé poco acerca de lo que aquí estoy pensando en voz alta acerca de los problemas que parecen naturales para preguntar acerca de esta situación. Es difícil creer que la gente no piensa acerca de estas preguntas y tal vez les respondió. ¿Dónde puedo encontrar más información?

Escribir usted está interesado en un "cuadrado planar rejilla". Así que me tomé esto significa que usted estaba pensando acerca de los puntos de un cuadrado de la cuadrícula gráfico" con lx1 plazas como la de las células que va de (0,0) a (n,n) y donde los pesos que iban a ser asignados a los bordes de tamaño 1 o 2.

Las rutas de acceso que están hablando de la necesidad de no ser limitada a moverse hacia arriba y a la derecha, pero podría ser interesante contrastar el comportamiento general de los caminos más cortos con los que se mueven hacia arriba y a la derecha. También parece ser de interés para ver lo que sucede si uno selecciona la mitad de los bordes al azar y se les hace toda la longitud 1 de bordes y hace que todos los demás de longitud 2. Ya que hay 4n bordes esto significa 2n 1 y 2n 2. Además, Si insistimos en que los caminos se mueven hacia arriba y a la derecha, todas las rutas de acceso tienen la longitud 2n, por lo que "muy menor" caminos " consistiría sólo en 1.

En ambas opciones de configuración:

una. ¿Cuál es la probabilidad de que hay un camino más corto a (n,n), que consta de todos los 1?

b. ¿Qué se puede decir sobre el valor esperado de la longitud de una ruta más corta a (n, n)? ¿Qué se puede decir acerca del número esperado de las rutas de este valor?

c. Cuando uno insiste en que cada una de las dos longitudes de aparecer con la misma frecuencia de cuántas maneras diferentes puede suceder? (También se puede preguntar cuántos de estos son diferentes a la simetría de la "gente de color" gráfico, el tratamiento de las longitudes de dos colores.) Se puede contar, en el caso general también, pero los de arriba y a la derecha caso parece más interesante aquí.

Answer 2

Gil, como usted dice, este es uno de esos típicos FPP problemas que parece obvio, pero es difícil de probar. Lo has probado ya? Sería útil saber de algunos ingenuos intentos que no funciona.

Aquí están mis pensamientos:

Reclamo: No existe la no-aleatorio de $\lambda$ que, con probabilidad uno, para la gran n, todos los caminos más cortos entre $0$ y $(n,0)$ cumplir $\lambda n + o(n)$ bordes. (este es un LLN-tipo de teorema de manera que no debería ser difícil de probar; por ejemplo, a través de la energía de entropía de métodos, ya que su tiempo paso distribuciones están delimitadas)

Por lo tanto se puede considerar que la probabilidad de espacio $\Omega_n$ que consta de todas las rutas entre $0$ y $(n,0)$ que cumplan $\lambda n + o(n)$ bordes. Un camino más corto es una variable aleatoria $X_n$ en este espacio con una cierta distribución de probabilidad.

Reclamo: existe $\sigma$ tales que $|\Omega_n| \approx \sigma^n$. (debe ser fácil: $\log|\Omega_n|$ es, probablemente, subadditive)

Deje que $\Omega_n'$ ser el subespacio de las rutas que cumplen con el borde medio, por lo que $|\Omega_n'| \approx \sigma^{n/2} + \sigma^{n/2}$.

Supongamos que existe $p > 0$ tal que el camino más corto entre $0$ y $(n,0)$ reúne el centro del borde con una probabilidad de al menos $p$. (*)

Aquí es la parte en la que estoy luchando por cuantificar. Intuitivamente, la distribución de $X_n$ debe ser manchado suavemente sobre $\Omega_n$. Ciertamente, la media es una línea horizontal del segmento, pero incluso los caminos que veer bastante lejos no son razonables. Sin embargo, si (*) se mantiene, con una probabilidad de al menos $p$, $X_n$ se concentra en la mucho menor subespacio $\Omega_n'$. Este parece mal.

Quizás todo lo que he hecho es traducir una "obvio" que la declaración de la otra. Esperamos que esto les ayude un poco. Buena suerte!

Answer 3

Gil, gracias por chocar con este post. Creo que tengo una idea nueva para usted, pero no es una prueba todavía. Deje que $\gamma_n$ ser reducir a un mínimo la geodésica entre $(-n,0)$ y $(n,0)$, y dejar que $\gamma^{\pm}_n$ ser reducir a un mínimo la geodésica entre $(\pm n, 0)$ y el origen.

Denotamos por $d(\gamma_n)$ la máxima distancia Euclidiana desde la línea geodésica $\gamma_n$ a la trayectoria en línea recta entre $(-n,0)$ y $(n,0)$, y definir $d(\gamma^\pm_n)$ mismo para $\gamma^\pm_n$. Por la definición de la transversal de la fluctuación de exponente $\xi$, $d(\gamma^\pm_n)$ escalas como $n^\xi$ y $d(\gamma_n)$ escalas como $(2n)^\xi$.

Desde $\tfrac 1 2$ es menor que el crítico de probabilidad para la orientada a la fianza de percolación en dos dimensiones $\aprox .633$, un teorema de Licea-Newman-Piza se aplica y hay un riguroso límite inferior $$\xi \ge 1/3$$ para el modelo. (cf. Teorema 4.3 en Howard - Modelos de Primer Paso de Percolación)

Suponga que $\gamma_n = \gamma^-_n \cup \gamma^+_n$ (es decir, de la línea geodésica $\gamma_n$ reúne el origen), por lo que $$2^\xi n^\xi \aprox d(\gamma_n) = \max\{d(\gamma^-_n), d(\gamma^+_n)\} \approx n^\xi $$ lo que sugiere una contradicción desde $2^\xi > 1$ por el límite inferior $\xi \ge 1/3$.

He aquí por qué no funciona. El exponente $\xi$ es, precisamente, se define como la potencia mínima de $n$ que la siguiente:se $$\lim_{n\to\infty} \mathbb P\left[d(\gamma^\pm_n) \le n^\xi \right] = 1 \qquad \mathrm{y} \qquad \lim_{n\to\infty} \mathbb P\left[d(\gamma_n) \le (2n)^\xi \right] = 1.$$ Desde el $\aprox$ síntomas anteriores son realmente las desigualdades, no hay ninguna contradicción por encima.

Answer 4

Si el límite de geodesics desde $0$ a $(n,0)$ existe casi seguramente, esta pregunta es respondida por mostrar que esta limitación geodésica no es un doblemente infinita geodésica (bigeodesic). Bajo el supuesto de que el límite de la forma límite es diferenciable, Jack Hanson y puedo demostrar que este límite existe y no es un bigeodesic. Por lo tanto, podemos demostrar que si el límite de la forma es diferenciable, entonces $\mathbb{P}(0 \text{ es en la línea geodésica de }(-n,0) \text{ a }(n,0)) \to 0$.

Es parte de una declaración más general. Supongamos que el límite de la forma límite es diferenciable en dirección $\theta$, $S_\theta$ el sector de los ángulos correspondientes a los puntos de contacto de límite de la forma con el único apoyo de la línea en la dirección $\theta$, y asumir que el límite es diferenciable en los puntos extremos de este sector. A continuación, para cada dirección $\theta$, casi seguramente, si $(x_n)$ es una secuencia de puntos indicado en $S_\theta$, entonces para cada $x$, lo finito geodesics de $x$ $x_n$ tienen un límite y que está dirigido en $S_\theta$. Además, todos los infinitos geodesics en este sector se unen, y no hay bigeodesics con un extremo que se indica en este sector. Esto implica que los relacionados con la desordenada ferroimán no tiene el estado del suelo par con interfaz dirigida en $S_\theta$.

Answer 5

Hablando de intentos ingenuos, pensé que tal vez una solución simple a lo largo de estas líneas podría ser encontrado, pero no pude:

Me indican por $p_k(n,2r)$ la probabilidad de que una ruta más corta desde el origen al $(n,2r)$ contiene el segmento $(\lfloor \frac{n}{2}\rfloor,k)$ $(\lfloor \frac{n}{2}\rfloor +1,k)$. Una simple observación es que $p_k(n,2)=p_k(n,0)$ (considerar que refleja la ruta de acceso en la línea $y=k$ en la región de $x > \lfloor \frac{n}{2}\rfloor$). La idea es mostrar que $p_k(n,2)$ es cercano a los $p_0(n,0)$ para los pequeños $k$. Uno puede hacer esto tal vez considerando una nueva cuadrícula rectangular se extendió por $(1,\frac{2k}{n})$ y $(-\frac{2k}{n},1)$ (con la adecuada borde de la distribución del peso) y tratando de encontrar la nueva $p_0'(n,0)$, que debe ser una buena aproximación de $p_k(n,2)$.

Ahora si se puede encontrar una lenta disminución de la función $f$, de modo que $p_k(n,2)\aprox f(p_0(n,0))$ en el intervalo, digamos $|k|\le \sqrt{n}$, entonces $$1=\sum_{k=-\infty}^{\infty}p_k(n,0)=\sum_{k=-\infty}^{\infty}p_k(n,2)\approx \int_{-\sqrt{n}}^{\sqrt{n}}f(p)dp \geq c\sqrt{n}p_0(n,0)$$ constantes $c$. Si $\lim_{n\to \infty}p_0(n,0)>0$, a continuación, la desigualdad anterior es obviamente falso por lo suficientemente grande como $n$.

ETA: me doy cuenta de que este enfoque funciona si hemos sido capaces de demostrar que $$\liminf_{n\to \infty} p_{0}(n,0)=\liminf_{n\to \infty} p_k(n,0)$$ para cualquier fijo de $k$.