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

Question

Actualización (17 de enero) : El problema ha sido resuelto por Daniel Ahlberg y Christopher Hoffman. (Gracias a Matt Kahle por informarnos).

---

Consideremos una rejilla plana cuadrada. (Los vértices son pares de puntos del plano con coordenadas enteras y dos vértices son adyacentes si coinciden en una coordenada y difieren en una en la otra).

Dar a cada arista una longitud uno con probabilidad media y una longitud dos con probabilidad media.

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

Demuestre que con probabilidad que tiende a uno como $n$ tiende a infinito el camino más corto será pas contienen el "borde medio" en el eje x entre el origen y el $(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 pertenece a la categoría de "un lema perdido". No se trata realmente de un problema abierto en toda regla, sino más bien de una afirmación que parece correcta que se necesitaba en algún documento y que se resiste a ser demostrada. Por supuesto, algunos de estos "lemas" resultan ser muy difíciles, pero a veces simplemente se ha pasado por alto un argumento sencillo. El artículo en cuestión es

• Itai Benjamini, Gil Kalai y Oded Schramm, La percolación de primer paso tiene una varianza de distancia sublineal , Ann. Probab. 31(4) (2003) pp 1970-1978, doi: 10.1214/aop/1068646373 , arXiv: math/0203262 .

---

Aunque MO ha optado por aceptar una respuesta, y hubo algunas buenas sugerencias, el problema sigue abierto.

Answer 1

Gil: Este es un tipo de problema del que sé poco, así que aquí estoy pensando en voz alta sobre problemas que parecen naturales para preguntar sobre esta situación. Es difícil creer que la gente no haya pensado ya en estas preguntas y quizás las haya respondido. ¿Dónde podría buscar más información?

Escribes que estás interesado en una "cuadrícula plana cuadrada". Así que tomé esto como que estabas pensando en los puntos de un "gráfico de cuadrícula cuadrada" con lx1 cuadrados como las celdas que van de (0,0) a (n,n) y donde se iban a asignar pesos a las aristas de tamaño 1 o 2.

Los caminos de los que hablas no tienen por qué estar limitados a moverse hacia arriba y hacia la derecha, pero podría ser interesante contrastar el comportamiento de los caminos más cortos generales con los que se mueven hacia arriba y hacia la derecha. También parece interesante ver qué pasa si se selecciona la mitad de las aristas al azar y se hace que todas sean de longitud 1 y que todas las demás sean de longitud 2. Como hay 4n aristas esto significa que 2n son de 1 y 2n de 2. Además, si insistimos en que los caminos se mueven hacia arriba y hacia la derecha, dichos caminos tienen todos longitud 2n, por lo que los caminos "más cortos" consistirían sólo en 1's.

En ambos escenarios:

a. ¿Cuál es la probabilidad de que exista un camino más corto a (n,n) formado por todos los 1's?

b. ¿Qué se puede decir sobre el valor esperado de la longitud de un camino más corto a (n, n)? ¿Qué se puede decir sobre el número esperado de caminos de este valor?

c. Si se insiste en que cada una de las dos longitudes aparezca con la misma frecuencia, ¿de cuántas maneras diferentes puede ocurrir esto? (También se puede preguntar cuántas son diferentes hasta la simetría del gráfico "de color", tratando las longitudes como dos colores). Se podría contar también en el caso general, pero el caso de arriba y a la derecha parece más interesante aquí.

Answer 2

Gil, como has dicho, este es uno de esos típicos problemas de FPP que parece obvio pero es difícil de demostrar. ¿Qué has probado ya? Sería útil conocer algunos intentos ingenuos que no hayan funcionado.

Aquí están mis pensamientos:

Afirmación: Existe un sistema no aleatorio $\lambda$ tal que, con probabilidad uno, para n grande, todos los caminos más cortos entre $0$ y $(n,0)$ conozca $\lambda n + o(n)$ bordes. (este es un teorema de tipo LLN, por lo que no debería ser difícil de demostrar; por ejemplo, mediante métodos de energía-entropía, ya que sus distribuciones de tiempo de paso están acotadas)

Así, se puede considerar el espacio de probabilidad $\Omega_n$ que consiste en todas las rutas entre $0$ y $(n,0)$ que cumplen $\lambda n + o(n)$ bordes. Un camino más corto es una variable aleatoria $X_n$ en este espacio con una determinada distribución de probabilidad.

Afirmación: Existe $\sigma$ tal que $|\Omega_n| \approx \sigma^n$ . (debería ser fácil: $\log|\Omega_n|$ es probablemente subaditiva)

Dejemos que $\Omega_n'$ sea el subespacio de caminos que se encuentran con la arista central, de modo 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)$ se encuentra con la arista central con una probabilidad de al menos $p$ . (*)

Esta es la parte que me cuesta cuantificar. Intuitivamente, la distribución de $X_n$ debe extenderse suavemente sobre $\Omega_n$ . Ciertamente, la media es un segmento de línea horizontal, pero incluso las trayectorias que se alejan bastante no son descabelladas. Sin embargo, si (*) se cumple, con probabilidad al menos $p$ , $X_n$ se concentra en el subespacio mucho más pequeño $\Omega_n'$ . Esto parece un error.

Quizá lo único que he hecho es traducir una afirmación "obvia" en otra. Espero que esto ayude un poco. Buena suerte.

Answer 3

Parece que este problema ha sido resuelto recientemente por Ahlberg y Hoffman. https://arxiv.org/abs/1609.02447

Answer 4

Si el límite de las geodésicas de $0$ a $(n,0)$ existe casi con toda seguridad, entonces se responde a esta pregunta demostrando que esta geodésica limitante no es una geodésica doblemente infinita (bigeodésica). Bajo el supuesto de que la frontera de la forma límite es diferenciable, Jack Hanson y yo podemos demostrar que este límite existe y no es una bigeodésica. Por lo tanto, podemos demostrar que si la forma límite es diferenciable, entonces $\mathbb{P}(0 \text{ is in the geodesic from }(-n,0) \text{ to }(n,0)) \to 0$ .

Forma parte de una declaración más general. Supongamos que la frontera de la forma límite es diferenciable en la dirección $\theta$ Llama a $S_\theta$ el sector de ángulos correspondiente a los puntos de contacto de la forma límite con la línea de apoyo única en dirección $\theta$ y supongamos que la frontera es diferenciable en los puntos extremos de este sector. Entonces para cada dirección $\theta$ casi con toda seguridad, si $(x_n)$ es una secuencia de puntos dirigida en $S_\theta$ , entonces para cada $x$ las geodésicas finitas de $x$ a $x_n$ tienen un límite y está dirigido en $S_\theta$ . Además, todas las geodésicas infinitas en este sector coalescen, y no hay bigeodésicas con un extremo dirigido en este sector. Esto implica que el ferromagneto desordenado relacionado no tiene ningún par de estado básico con interfaz dirigida en $S_\theta$ .

Answer 5

Gil, gracias por haber sacado este post. Creo que tengo una nueva idea para ti, pero aún no es una prueba. Deja que $\gamma_n$ sea una geodésica minimizadora entre $(-n,0)$ y $(n,0)$ y que $\gamma^{\pm}_n$ sea una geodésica minimizadora entre $(\pm n, 0)$ y el origen.

Denota por $d(\gamma_n)$ la distancia euclidiana máxima de la geodésica $\gamma_n$ a la trayectoria en línea recta entre $(-n,0)$ y $(n,0)$ y definir $d(\gamma^\pm_n)$ de manera similar para $\gamma^\pm_n$ . Por la definición del exponente de fluctuación transversal $\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 probabilidad crítica para la percolación de enlaces orientados en dos dimensiones $\approx .633$ se aplica un teorema de Licea-Newman-Piza y existe un límite inferior riguroso $$\xi \ge 1/3$$ para su modelo. (véase el teorema 4.3 en Howard - Modelos de percolación de primer paso )

Supongamos que $\gamma_n = \gamma^-_n \cup \gamma^+_n$ (es decir, la geodésica $\gamma_n$ se encuentra con el origen), por lo que $$2^\xi n^\xi \approx d(\gamma_n) = \max\{d(\gamma^-_n), d(\gamma^+_n)\} \approx n^\xi,$$ lo que sugiere una contradicción ya que $2^\xi > 1$ por el límite inferior $\xi \ge 1/3$ .

He aquí por qué no funciona. El exponente $\xi$ se define precisamente como la potencia mínima de $n$ tal que se cumpla lo siguiente: $$\lim_{n\to\infty} \mathbb P\left[d(\gamma^\pm_n) \le n^\xi \right] = 1 \qquad \mathrm{and} \qquad \lim_{n\to\infty} \mathbb P\left[d(\gamma_n) \le (2n)^\xi \right] = 1.$$ Desde el $\approx$ Los signos anteriores son realmente desigualdades, no hay ninguna contradicción en lo anterior.