Muestreo típicos racimos entre puntos muy alejados en subcrítico de percolación

Question

He hecho en varias ocasiones se preguntó cómo se puede proceder para muestras grandes subcrítico de Bernoulli bond-clusters de percolación, dicen que en la plaza de la celosía.

Más precisamente, vamos a considerar el entramado $\mathbb{Z}^2$, y abrir cada borde de forma independiente con una probabilidad de $p<p_c=0.5$. Estoy interesado en el caso de que los vértices $(0,0)$ $(N,0)$ están conectados por un camino de bordes abiertos, al $N$ un número grande ("grande", que significa aquí "muchas veces la longitud de correlación").

Es bien conocido (rigurosamente) que esta probabilidad decae exponencialmente rápido con $N$, y una que tiene un montón de información acerca de la geometría del clúster correspondiente (por ejemplo, el clúster correspondiente converge a un puente browniano como $N\to\infty$ bajo difusivo de escala, tiene una máxima de la "anchura" de la orden de $\log N$, etc.).

Pregunta: ¿hay (no demasiado ineficientes) algoritmos que muestra los típicos racimos que contribuyen a este evento?

Edit: googleando un poco, he tropezado con este papel. Todavía tengo que leer (y decidir si es pertinente a mi pregunta). Lo que el autor parece estar haciendo es crecer sus objetos de manera sesgada, lo que ayuda a crear el muy poco probable configuraciones de él después, pero el resultado sería la mal distribución final. Así que él es al mismo tiempo la corrección del sesgo (en una forma todavía no he entendido por el solo hecho de navegar a través del papel). Como un ejemplo, él es el muestreo de 18 discontinuo cruce de clústeres para la crítica de percolación en $\mathbb{Z}^3$ en una caja de tamaño $128\times128\times2000$, un evento de probabilidad de orden $10^{-300}$. Así:

Alternativa pregunta: ¿alguien sabe cómo funciona esto? (También puede simplemente leer el periódico, pero podría ser útil para mí y para los demás si es un buen auto-contenida descripción fue dada aquí por alguien que conozca del tema).

Al parecer, mirando más a fondo, hay un montón de material que pueda ser útil. Parece que las palabras clave aquí son: raros eventos de simulación, la importancia de muestreo, división, etc.

Answer 1

Aquí es el algoritmo tal como yo lo recuerdo. Hay un nombre y una referencia adjuntar a ella, voy a actualizar mi respuesta cuando me encuentro con ellos.

El algoritmo no está limitado por $N$ (no requieren el almacenamiento de la cuadrícula). Cada borde de una red infinita es abierto, cerrado o desconocido. Inicialmente todos los bordes son desconocidos. La idea es crecer conectado a un clúster de forma iterativa, tratando de (generar un número aleatorio a) todos los que aún se desconoce bordes en la categoría de barrio.

Usted necesitará dos estructuras de datos: lista de CLÚSTER para abrir aristas que forman la conexión de un clúster, lista CONOCIDA por todos los bordes que están abiertos o cerrados, pero no desconocido.

1. Comience con ambos CLÚSTER y CONOCIDO poblado por un borde abierto.
2. Construcción de la lista de VECINOS que consta de todos los bordes conectados a los bordes en CLÚSTER.
3. Si no hay ningún desconocido bordes de los VECINOS, a continuación, detener.
4. Para cada uno de los desconocidos borde de los VECINOS: a) lanzar un número aleatorio y determinar si es abierto o cerrado; b) agregar el borde CONOCIDOS; c) si el borde está cerrado, agregar al CLÚSTER.
5. Volver al paso 2.

El algoritmo termina con una probabilidad de si están por debajo del umbral de percolación. Mediante la repetición de un número suficiente de veces, se obtiene una evaluación imparcial y distribución de los grupos conectados. Dependiendo de lo que usted está especialmente interesado, puedes descartar todos "pequeños grupos" o construir en un romper de una vez el clúster lineal tamaño excede $N$.

Answer 2

El ingenuo algoritmo de muestreo acondicionado en el raro caso en cuestión (que los vértices (0,0) y (N,0) están conectados) es bastante ineficiente. La única esperanza que veo para un algoritmo eficiente que proviene de la dualidad de los resultados de la conexión de subcrítica de percolación y supercrítico de percolación. Hay varios dichos resultados (que se aplican en mayor generalidad - a no planas de percolación, para grafos aleatorios, etc.). No sé si hay resultados de este tipo para esta pregunta precisa: a saber, de la ley para el clúster que contiene el (0,0) y (N,0) en subcrítico de percolación acondicionado en ellos está conectado es el mismo (o aproximadamente la misma) para subcrítico de percolación con parámetro p y supercrítica de percolación (es decir de la probabilidad 1-p).