Distancia media entre las entradas de la matriz

Question

Dada una $4$ por $4$ matriz, o en general una $n$ por $n$ matriz cuadrada, podemos determinar la distancia euclidiana media (es decir $\sqrt{\Delta x ^2 + \Delta y^2}$ ) entre entradas que no son vecinas?

Dos entradas de la matriz $(x_1,y_1)$ y $(x_2,y_2)$ son vecinos si $\Delta x=\Delta y=1$ o $\Delta x=1$ y $\Delta y=0$ o por último $\Delta x=0$ y $\Delta y=1.$ Esto significa, por ejemplo, que la entrada central $(2,2)$ en un $3$ por $3$ La matriz tiene $8$ vecinos, lo que significa que esta entrada no puede emparejarse con ninguna otra entrada de la matriz para crear un par no vecino. Esto también significa que todas las entradas de una matriz de 2 por 2 (debajo de las coordenadas de la entrada en la matriz se escriben)

\begin {matriz} (1,1) & (1,2) \\ (2,1) & (2,2) \end {matriz}

se consideran vecinos.

Entiendo que la primera parte a resolver es: para un tamaño de matriz dado, ¿cuántos pares de entradas no vecinas hay? Por ejemplo en una $3$ por $3$ matriz, tenemos $16$ combinaciones de entradas que no son vecinas. Obsérvese que nos preocupamos por combinaciones de entradas porque, por ejemplo, el par $(1,3) \& (3,3)$ y el par $(3,3) \& (1,3)$ se consideran indistinguibles, es decir, el intercambio de la posición de una entrada en un par no cuenta como un nuevo par de entradas. Una vez conocido el recuento $C$ de pares no vecinos, entonces podemos asignar con seguridad a cada par una probabilidad $1/C,$ con el fin de resolver el media problema de distancia.

Answer 1

Descargo de responsabilidad. Esto no es en absoluto una respuesta completa y totalmente rigurosa, pero debería ser un buen punto de partida.

---

En primer lugar, a menos que entienda mal lo que está tratando de captar con su definición de vecino ¿No debería ser así? $(x_1,y_1)\neq(x_2,y_2)$ son vecinos si y sólo si ocurre una de las siguientes cosas

1. $\Delta x=\Delta y=1$ ;
2. $\Delta x=1$ y $\Delta y=0$ o
3. $\Delta x=0$ y $\Delta y=1$ .

De lo contrario, $\Delta x+\Delta y=2$ podría permitir $(1,1)$ para ser vecino de $(1,3)$ lo que significaría que en realidad hay $10$ combinaciones de no vecinos en un $3\times 3$ matriz.

---

Si mi comentario anterior es realmente lo que te interesa, entonces el número $C_n$ de posibles combinaciones de entradas de matrices no vecinas en un $n\times n$ matriz es el número de formas de colocar 2 reyes no atacantes en un $n\times n$ tablero que aparentemente viene dada por la fórmula explícita $$C_n=\frac{(n - 1)(n - 2)(n^2 + 3n - 2)}2,\qquad n\in\mathbb N.$$ Tenga en cuenta que esto significa que $C_3=16$ en lugar de $18$ . Esta fórmula se confirma con el siguiente código de MatLab (se puede jugar con el parámetro $N$ para cambiar la dimensión, y la salida $C$ es el número de pares que buscamos).

N=3; % Dimension of matrix

X=zeros(2,N^2); % 2 x N^2 array whose columns represent matrix entries

% The loop below generates all matrix entries
ctr=1;
for(i=1:N)
    for(j=1:N)
        X(1,ctr)=i;
        X(2,ctr)=j;
        ctr=ctr+1;
    end
end

% All possible combinations of two entries
C=nchoosek(N^2,2);

% The loop below goes through all combinations.
% If a combination contains neighbouring entries, we remove one from C.
% After going through all combinations, the number C left is precisely
% the number of non-neighbouring combinations.
for(i=1:N^2)
    for(j=i+1:N^2)
        dx=abs(X(1,i)-X(1,j));
        dy=abs(X(2,i)-X(2,j));
        if((dx==1 && dy==0) || (dx==0 && dy==1) || (dx==1 && dy==1))
            C=C-1;
        end
    end
end
C

---

Sospecho que una buena fórmula exacta para la distancia euclidiana media de un par no vecino uniforme para un $n$ puede no existir. Sin embargo, todavía podría ser posible obtener una respuesta asintótica manejable. En esta línea de pensamiento, mi sospecha es que su variable aleatoria puede ser pensada como una aproximación de dimensión finita de la distancia media entre dos puntos aleatorios de un cuadrado que aparentemente es igual a $$\gamma:=\frac{2+\sqrt{2}+5\log(1+\sqrt{2})}{15}.$$

Más concretamente, podemos representar un $n\times n$ como una rejilla cuadrada dentro del cuadrado de la unidad (véase aquí para un ejemplo con $n=13$ ), donde los lados de los cuadrados más pequeños de la cuadrícula son de tamaño $n^{-1}$ y cada cuadrado más pequeño representa una entrada de la matriz.

Dados dos puntos $z_1=(x_1,y_1)$ y $z_2:=(x_2,y_2)$ muestreado uniformemente del cuadrado de la unidad en $\mathbb R^2$ podemos obtener dos entradas de la matriz seleccionadas al azar mirando cuál de los cuadrados más pequeños $z_1$ y $z_2$ tierra en. Por supuesto, esto no tiene en cuenta su requisito de que las entradas de la matriz sean no vecinas, pero para las $n$ la probabilidad de que dos puntos aleatorios $z_1$ y $z_2$ en $[0,1]^2$ La tierra en las plazas vecinas converge a cero, así que espero que esta aproximación funcione a pesar de todo.

---

Si esta aproximación funciona, entonces podemos esperar que la distancia euclidiana media que se busca, al menos para grandes $n$ es aproximadamente igual a $$n\cdot\gamma= n\cdot \frac{2+\sqrt{2}+5\log(1+\sqrt{2})}{15}.$$

Después de hacer algunas simulaciones en MatLab, parece que esta es una aproximación bastante buena, como se muestra en la siguiente imagen (la línea púrpura es el valor asintótico $n\cdot \gamma$ y el amarillo $+$ son los promedios reales calculados utilizando un código muy similar al que utilicé anteriormente para calcular los valores de $C_n$ ).

Answer 2

Descargo de responsabilidad: Este enfoque es un trabajo en curso, y aún no está claro si conduce a una buena solución. Tendré tiempo de terminarlo mañana, por ahora lo publico para guardar mi progreso y quizás inspirar a alguien más a una solución.

---

La distancia media entre un par de puntos, incluidos los vecinos, es $$\frac12\cdot\frac{1}{\binom{n^2}{2}}\sum_{i,j,k,l}\sqrt{(i-j)^2+(k-l)^2}=\frac{1}{n^2(n^2-1)}\sum_{i,j,k,l}\sqrt{(i-j)^2+(k-l)^2},$$ donde todos los índices van desde $1$ a $n$ . Aquí contamos cada par dos veces, y por lo tanto dividimos el conjunto por $2$ . La contribución de los pares de vecinos es la siguiente: \begin {align*} \text {esquinas}:&&4 \times (2 \times1 +1 \times\sqrt {2}) =&&8+4 \sqrt {2}, \\ \text {lados}:&&4(n-2)(3 \times1 +2 \times\sqrt {2}) =&&4(3+2 \sqrt {2})n-8(3+2 \sqrt {2}), \\ \text {center}:&&(n-2)^2(4 \times1 +4 \times\sqrt {2}) =&&4(1+ \sqrt {2})n^2-16(1+ \sqrt {2})n+16(1+ \sqrt {2}). \end {align*} Así que el número total de pares que hemos contado de más es $$4\times3+(n-2)\times5+(n-2)^2\times8=8n^2-54n+78,$$ y la suma de sus distancias es $$4(1+\sqrt{2})n^2-4(1+2\sqrt{2})n+4\sqrt{2}.$$ Ahora queda por determinar el valor de la suma $$S(n):=\sum_{i,j,k,l}\sqrt{(i-j)^2+(k-l)^2},$$ donde todos los índices van desde $1$ a $n$ . Esto parece lo suficientemente bonito como para que alguien haya escrito alguna idea al respecto antes...