Probabilidad de encontrar una secuencia de enteros en un espacio bidimensional

Question

Supongamos que tengo una matriz, de tamaño $m\times m$ para cualquier valor impar de $m \geq 3 $ , rellenado con números enteros seleccionados aleatoriamente, donde cada número entero está limitado a entre 1 y $c$ , para $c \geq 2$ . ¿Cuál es la probabilidad de que encuentre una secuencia específica de enteros, de longitud $k$ ¿Empezando por el centro? Además, digamos que $m/2> k$ para evitar tener que lidiar con los límites. La única restricción adicional es que una secuencia no puede utilizar el mismo elemento de la matriz más de una vez, por considerar la siguiente matriz:

$ M= \left[ {\begin{array}{ccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 2 & \color{pink}3 & 1 & 2 & 1\\ 1& \color{pink}3 & \color{blue}4 & \color{blue}4 & 2 & 2& 1 \\ 1 &1 & 2 & \color{red}3 & \color{pink}3 & 3 & 1\\ 1 &4 & 3 & 2 & 1 & 4 & 1\\ 1 & 2 & 1 & 4 & 2 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array} } \right]. $

Digamos que en $M$ partimos del centro (R4,C4) = $\color{red} 3$ buscando la secuencia $\color{red}3,\color{blue}4,\color{pink}3$ . En este caso hay un total de 4 secuencias posibles, porque no podemos contar el centro más de una vez para una secuencia dada.

Primero encontré la probabilidad para el caso 1D. En el caso 1D, la probabilidad viene dada por $P( c, k) = 1 - (1 - \frac{1}{c^K})$ . Esto es sólo a partir de una posición (no sobre todas las posiciones posibles).

Para el caso 2D, empezaré en el centro de la matriz. Para un $3\times3$ matriz, el centro es (R2, C2). La extensión hacia fuera del centro en una dirección (ya sea S, SW, W, NW, N, NE, E o SE) es equivalente al caso 1D, por lo que podemos obtener la probabilidad incluyendo un factor de 8 para tener en cuenta un total de todas las direcciones posibles. Así, para el caso de mi $3\times 3$ matriz, creo que la probabilidad viene dada por: $P(c, 2) = 8\cdot(1- (1-\frac{1}{c^2}) )$ .

Ahora estoy luchando por extender esto para una matriz que tiene un tamaño $5\times 5$ para una secuencia que tiene una longitud $k=3$ . Utilizando una simulación de Monte Carlo con $10^9$ ensayos, calculo el $P(c=12, k=3) \approx 0.066805$ pero utilizando $8\cdot(1- (1-\frac{1}{12^3}) )=0.0046$ . Sospecho que tendré que encontrar un factor adicional que dependa de cómo crece el número de caminos posibles para las secuencias más grandes. Mi intuición me dice que eso debería escalar como $8, 16-1, 32-2, ...$ pero estoy atascado.

Answer 1

Intuitivamente su idea de la probabilidad en el $3 \times 3$ La matriz puede parecer correcta, esencialmente tienes 8 caminos unidimensionales por lo que parece que puedes multiplicar la probabilidad por 8 para tener la nueva probabilidad. Sin embargo, esto es incorrecto y es una de las razones por las que la probabilidad es difícil, no siempre sigue la intuición.

Para ver un ejemplo de por qué su fórmula es errónea, considere $P(c=2,k=2)$ . Según su cálculo, la probabilidad es $8\left( 1 - \left(1 - \frac{1}{2^2} \right) \right) = 2$ . Las probabilidades no pueden ser más de una, pero su fórmula devolvió $2$ ¡! Considere otro caso, $P(c=4,k=2$ ), su probabilidad calculada es $.5$ que interpretado es: el 50% de las veces genero un $3 \times 3$ tendrá la secuencia que desees dada tu restricción de empezar por el medio. Sin embargo, esto no puede ser cierto porque el nodo central sólo tiene un $\frac{1}{c}$ de ser el valor correcto, por lo que la probabilidad no debe ser mayor que $\frac{1}{4}$ .

La pregunta que me parece que se hace es: Dada una $3\times3$ matriz, ¿cuál es la probabilidad de encontrar Al menos un camino correcto. No te importa especialmente si hay $2,3$ o $4$ caminos, sólo quieres la existencia. Esto significa que en realidad deberías sumar todas las probabilidades:

$$ P(\text{1 path exists}) + P(\text{2 paths exist}) + \cdots + P(\text{8 paths exist}) $$ para encontrar la probabilidad real. Afortunadamente podemos aprovechar el complemento que dice que esta probabilidad es equivalente a $1 - P(\text{0 paths exist}).$

Sólo hay dos formas de que nuestro camino no exista cuando $k=2$ :

1. El nodo central es incorrecto, lo que ocurre con probabilidad $1 - \frac{1}{c}$ .
2. El nodo central es correcto, y los 8 nodos que rodean el centro son incorrectos. Esto ocurre con la probabilidad $\left(\frac{1}{c} \right) \left( 1 - \frac{1}{c}\right)^8$ .

Esto significa que $P(\text{0 paths exist}) = \left[1 - \frac{1}{c}\right] + \left(\frac{1}{c} \right) \left( 1 - \frac{1}{c}\right)^8$ Así que sabemos que $$ P(\text{at least 1 path exists}) = 1 - \left[1 - \frac{1}{c}\right] -\left(\frac{1}{c} \right) \left( 1 - \frac{1}{c}\right)^8 \\ = \frac{1}{c} - \left(\frac{1}{c} \right) \left( 1 - \frac{1}{c}\right)^8 \\ = \frac{1}{c}\left(1 - \left(1 - \frac{1}{c} \right)^8 \right). $$

Por lo tanto, la fórmula para el $3\times3$ matriz es $P(c,k) = \frac{1}{c}\left(1 - \left(1 - \frac{1}{c} \right)^8 \right)$ .

Otra derivación, y quizás con la que te sientas más cómodo, es tratar las 8 celdas alrededor del centro como una distribución Binomial que tiene $n$ dibuja con $\frac{1}{c}$ como su probabilidad, y la ecuación que es la probabilidad de que el nodo central sea correcto, multiplicada por la probabilidad de al menos un éxito.

Lamentablemente no he podido extender este caso al $5\times5$ porque no veo ninguna extensión obvia para el número de caminos que tenemos disponibles en el tercer elemento de la secuencia.

• En el paso 1, se garantiza que sólo tenemos un nodo a considerar, el centro.
• En el paso 2, se garantiza que sólo tenemos 8 nodos a considerar, cada elemento rodeando el centro.
• En el paso 3, tenemos $Y$ nodos, que depende tanto del número de nodos en el paso 2 que fueron correctos, como de DONDE están posicionados esos nodos.

Para ilustrar lo que quiero decir en el paso 3, considere una alteración de su ejemplo original del $5\times5$ matriz (antes de su edición) en su pregunta:

$ M= \left[ {\begin{array}{ccccc} 1 & \color{green}2 & \color{green}3 & 1 & 2 \\ \color{pink}3 & \color{blue}4_1 & \color{blue}4_2 & 2 & 2 \\ 1 & \color{green}2 & \color{red}3 & \color{pink}3 & 3 \\ 4 & 3 & 2 & 1 & 4 \\ 2 & 1 & 4 & 2 & 1 \\ \end{array} } \right]. $

$\color{blue}4_1$ tiene $7$ posibles opciones, $3$ de los cuales son compartidos por $\color{blue}4_2$ (resaltado en verde), por lo que al buscar el siguiente elemento de la secuencia, tenemos $9$ si el elemento no es $4$ entre $\color{blue}4_1$ y $\color{blue}4_2$ .

Pero ahora haz este cambio, moviendo $\color{blue}4_2$ a la esquina inferior derecha:

$ M= \left[ {\begin{array}{ccccc} 1 & 2 & \color{pink}3 & 1 & 2 \\ \color{pink}3 & \color{blue}4_1 & 1 & 2 & 2 \\ 1 & 2 & \color{red}3 & \color{pink}3 & 3 \\ 4 & 3 & 2 & \color{blue}4_2 & 4 \\ 2 & 1 & 4 & 2 & 1 \\ \end{array} } \right]. $

En esta variante, no se comparten nodos entre $\color{blue}4_1$ y $\color{blue}4_2$ por lo que hay $14$ células que tienen la posibilidad de satisfacer la última secuencia, por lo que el número y la posición del número afectan a la probabilidad.

A pesar de que cada paso no es independiente del anterior, he comprobado que $$ P(c,k) = \frac{1}{c}\left(1 - \left(1-\frac{1}{c}\right)^8 \right)^{k-1} $$ es una aproximación decente a la probabilidad (probada mediante un método de MonteCarlo).

Aquí está mi código python para simular la probabilidad:

import numpy as np
def matrix(m,c,k_vals):
    """ Returns 1 if k_vals is found in the Matrix generated.
    Note that values can not be re-used

    """
    # np.random.randint excludes the top value, so it draws ints from 1 to c
    M = np.random.randint(1,c+1, size=(m,m))
    center = m // 2

    if M[center,center] != k_vals[0]:
        # The center value is not the first digit, return false
        return 0
    visited = set()
    stack = [(center,center,1)]
    # path is only collected for verifying a path during debugging
    path = [(center, center)]

    # Terminates if stack is ever empty
    while stack:
        currentx, currenty, depth = stack.pop()
        path = path[:depth-1] + [ (currentx, currenty) ]
        visited.add((currentx, currenty))
        # When the depth of our node is the length of the sequence, we have found a path
        if depth == len(k_vals):
            return 1

        for dx in [-1,0,1]:
            for dy in [-1,0,1]:
                if (currentx + dx) < 0 or (currentx + dx) >= m or (currenty + dy) < 0 or (currenty + dy) >= m:
                    # This value is out of bounds, skip it.
                    continue
                if (currentx + dx,currenty + dy) not in visited and M[currentx + dx, currenty + dy] == k_vals[depth]:
                    # We have not seen this node before, and its value is the next element we are looking for
                    if (currentx + dx, currenty + dy) not in visited and (depth + 1) <= len(k_vals):
                        stack.append((currentx + dx, currenty + dy, depth + 1))

    # If we finished the while loop then we did not find a path
    return 0

vals = []
N = 10**5
m = 3
c = 10
k_vals = [3,4]
for _ in range(N):
    vals.append(matrix(m,c,k_vals))
print("MC estimated Probability:",sum(vals)/len(vals))
print("3x3 Analytic Probability:",  1/c*(1 - (1-1/c)**8 ))
print("MxM Estimated Probability with k < m/2", 1/c*(1 - (1-1/c)**8 )**(len(k_vals)-1))

Creo que encontrar una probabilidad analítica para cualquier cosa mayor que el $3\times3$ va a resultar muy difícil