6 votos

Trayectoria coloreada en una cuadrícula coloreada aleatoriamente

Un amigo mío me hizo esta pregunta hace un tiempo y no pude encontrar ninguna respuesta adecuada para ella. Agradecería cualquier comentario o ayuda.

Si se colorea cada casilla de la unidad con el blanco/negro de un $m \times n$ de acuerdo con el resultado de un lanzamiento de moneda H/T (con probabilidades $p$ o $1-p,$ resp.) ¿cuál sería la probabilidad de que existiera un camino que uniera los dos lados opuestos del tablero? (Las casillas de un camino deben tener todas el mismo color, y sólo las casillas con un borde común pueden hacer un camino).

3voto

JGab Puntos 525

Existe una teoría muy rica que aborda este problema, desarrollada principalmente por físicos estadísticos durante la segunda mitad del siglo XX $^\text{th}$ siglo, conocido como _teoría de la percolación_ .

La principal clase de problemas de los que se ocupa esta teoría puede enunciarse así:

Supongamos un entramado formado por muchos sitios etiquetados e interconectados en un orden determinado. Dado que cada sitio está ocupado independientemente con probabilidad independiente $P$ ¿Cuáles son las propiedades estadísticas de grupos conectados ?

Las agrupaciones conectadas se definen como conjuntos de sitios ocupados a los que se puede llegar siguiendo los caminos permitidos por la red.

Ejemplo de entramados:

Percolación 1-D

Este tipo de celosía consiste en una serie infinita de sitios en la línea.

$$...-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ- ...$$ Y después de una realización del experimento, con decir $P=0.3$ .

$$...-\circ-\bullet-\circ-\bullet-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\circ-\bullet-\bullet-\circ-\circ- ...$$

Donde utilicé el $\bullet$ para representar los lugares ocupados (probabilidad $P$ ), y $\circ$ para lugares desocupados $(1-P)$ .

Obsérvese que a menudo se suponen límites periódicos para simplificar el tratamiento matemático.

Percolación en árboles de Cayley (red de Bethe)

credit: wikipedia

Cada sitio tiene exactamente $z$ vecinos en este tipo de entramado. Lo anterior es el árbol de Cayley para $z=3$

Algunas definiciones:

  • Permítanme definir el concepto de clúster de expansión : Para una retícula finita, se define un cluster spanning como un cluster que toca los límites opuestos de la retícula.

  • También tendremos que definir el distribución del tamaño de los grupos . Esto se explica por sí mismo: es la distribución del tamaño de los clusters, donde el tamaño de un cluster se define como el número de sitios ocupados conectados (disjuntos de otros clusters). Utilizaré la notación $n(s;P)$ .

Una primera respuesta

Los 2 entramados anteriores son susceptibles de una solución analítica exacta porque un caminante sobre dicha malla no puede volver a hacer un bucle . Partiendo de esta observación, podemos ver fácilmente que para una red 1-d de $L$ sitios, la probabilidad de que exista una ruta de cluster spanning es $P^L$ . Para el entramado de Bethe, la cuestión ya no es tan clara porque hay que especificar cómo se corta.

Esto ilustra lo difícil que es el problema. Digamos que no hay más sitio en la imagen anterior. Tenemos que calcular todo explícitamente . El camino posible podría consistir en ir del nivel 3 al nivel 2 y volver al nivel 3 inmediatamente. También se podría bajar hasta el nivel 1 y hacer una copia de seguridad, o pasar por el nodo central. El problema ya está en cierto modo mal definido.

Sin embargo, podemos hacer algunas afirmaciones estadísticas para los tamaños grandes.

Por ejemplo (y de ahí deriva el nombre), se ha observado que por encima de algún umbral crítico $P_c$ , a componente gigante aparece. Es decir, un cúmulo que ocupa una fracción finita de una red infinita. En la línea, $P_C$ es igual a 1, obviamente. Pero en el árbol de Cayley, es igual a $(z-1)^{-1}$ . La probabilidad de que un sitio determinado forme parte del clúster gigante es entonces $$p_\infty=p\left[1-\left[1-2\frac{p(z-1)-1}{p(z-1)(z-2)}\right]^z\right]$$

También podemos estudiar la distribución del tamaño de las agrupaciones, tal y como se ha definido anteriormente. En la línea, se encuentra que es $$n(s;P)=p^s(1-p)^2$$ ya que cada grupo finito debe estar delimitado por 2 sitios ocupados.

Ahora, para su pregunta:

Celosía 2-D

\begin{align} \begin{matrix} \circ&-&\circ&-&\circ&-&\bullet&-&\circ&-&\circ\\ |& & | & & | & & | & & | & & |\\ \circ&-&\circ&-&\circ&-&\bullet&-&\circ&-&\circ\\ |& & | & & | & & | & & | & & |\\ \bullet&-&\circ&-&\bullet&-&\bullet&-&\circ&-&\circ\\ |& & | & & | & & | & & | & & |\\ \circ&-&\circ&-&\circ&-&\bullet&-&\circ&-&\circ\\ |& & | & & | & & | & & | & & |\\ \circ&-&\circ&-&\circ&-&\bullet&-&\circ&-&\bullet\\ |& & | & & | & & | & & | & & |\\ \circ&-&\circ&-&\circ&-&\bullet&-&\circ&-&\circ \end{matrix} \end{align} Probablemente, a estas alturas, ya se puede adivinar que la solución exacta sólo se obtendrá mediante la enumeración para tamaños finitos. Además, como los bucles son ahora posibles Incluso el tratamiento estadístico se vuelve peligroso.

Permítanme hacer un ejemplo, y vamos a tratar de calcular la distribución $n(s;P)$ en 2D.

Digamos que puede calcular $g(s,t)$ el número de agrupaciones de tamaños $s$ con perímetro $t$ . (El perímetro es el número de sitios adyacentes no ocupados, en las cuatro direcciones: por ejemplo, el grupo más a la izquierda en la figura anterior tiene $t=3$ vecinos). Entonces la distribución vendrá dada por

$$n(s;P)=\sum_{t=1}^\infty g(s,t)(1-P)^t P^s$$

Hasta aquí todo bien. El problema es que no hay una forma conocida de calcular $g(s,t)$ metódicamente. Además, la enumeración es tediosa, y la última vez que lo comprobé, se había tabulado hasta $s\sim 50$ que es algo menos que el infinito ;).

Aquí es donde entra en juego su pregunta. Si la respuesta a su problema se conociera por general tamaños, entonces este problema tan importante también tendría una solución . Pero no es el caso (hasta ahora, tal vez MSE pueda resolverlo?!).

Más información

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X