Esta cuadrícula determina un grafo dirigido: los nodos del grafo son las celdas de la cuadrícula y cuando una celda comparte una arista con otra, se colocan dos aristas dirigidas entre los nodos correspondientes del grafo.
Consideremos un grafo finito cualquiera $\Gamma(\mathscr{V},\mathscr{E})$ con $n$ nodos $\mathscr{V}$ conectados por aristas $\mathscr{E}$ (que son pares ordenados de nodos distintos). El problema supone los números enteros $1,2,\ldots,n$ se han asignado aleatoriamente a los nodos. "Aleatoriamente" significa que todos $n!$ estas correspondencias (uno a uno) son igualmente probables. Como cuestión de notación, dejemos que $\nu(i)$ sea el nodo asociado a un número entero cualquiera $i.$ Dado $i$ y $j,$ calcularemos la probabilidad de que exista una arista entre $\nu(i)$ y $\nu(j).$ Es evidente que esto es lo mismo que la posibilidad de que haya un dirigido borde de $\nu(i)$ a $\nu(j).$
El valor de esta perspectiva abstracta es que simplifica el cálculo porque obliga a centrar nuestra atención en el mínimo de información necesaria.
Sea $d(p)$ es el "grado de salida", o número de nodos, con aristas que comienzan en un nodo arbitrario $p.$ Dado $\nu(i)=p$ (un acontecimiento que obviamente tiene azar $1/n$ de ocurrir), el número de maneras en que el par ordenado $(p,\nu(j))$ puede ser una arista es $d(p).$ Dado que existen $n-1$ nodos restantes a los que $j$ y condicionado a la asignación de $i$ a $p$ todos esos nodos tienen la misma probabilidad, la posibilidad de que se produzca esa conexión es $d(p)/(n-1).$ La posibilidad de que $(p,\nu(j))$ es una arista se obtiene ahora a partir de la ley de probabilidad total sumando sobre todos los nodos posibles $p$ que podrían asociarse al número $i:$
$$\begin{aligned} \Pr((\nu(i),\nu(j)) \in \mathscr{E}) &= \sum_{p\in\mathscr{V}}\Pr((p,\nu(j)) \in \mathscr{E} \mid \nu(i)=p) \Pr(\nu(i)=p)\\ &=\sum_{p\in\mathscr{V}}\frac{d(p)}{n-1}\,\frac{1}{n}\\ &= \frac{1}{(n-1)n} \sum_{p\in\mathscr{V}} d(p). \end{aligned}$$
Cuando, para cada grado posible $d$ hay $n_d$ nodos de grado $d,$ esta suma final se simplifica, dando la fórmula general
$$\Pr(\nu(i)\text{ is connected to }\nu(j)) = \frac{1}{n(n-1)}\,\sum_{d=0}^n d\,n_d.$$
Esto reduce el cálculo a encontrar cuántos nodos de cada grado hay.
Por ejemplo, en un $M\times N$ rejilla con $M\ge 2$ y $N\ge 2,$ hay
-
Cuatro esquinas, cada una conectada a sólo dos vecinos, por lo que $n_2=4.$
-
Dos bordes de $N-2$ células cada uno y dos bordes de $M-2$ células cada una, cada una conectada exactamente a tres vecinas, por lo que $n_3=2(N-2) + 2(M-2).$
-
Una matriz rectangular de $(M-2)(N-2)$ celdas interiores, cada una conectada a cuatro vecinas, por lo que $n_4=(M-2)(N-2).$
Existen $n=MN$ nodos en total. Por lo tanto, la respuesta en este caso es
$$\begin{aligned} \frac{1}{(n-1)n}\sum_{d=0}^n d\,n_d &= \frac{1}{(MN-1)MN} \left(2(4) + 3(2(M+N-4)) + 4(M-2)(N-2)\right)\\ &= \frac{4MN - 2(M+N)}{(MN-1)MN}. \end{aligned}$$
En $M=N$ esto se simplifica a $$\frac{4}{N(N+1)}.$$
La pregunta se responde fijando $i=x$ y $j=x+1$ (señalando que $j$ no existe cuando $i=N^2$ ). Por lo tanto,
En $1\le x\le N^2-1,$ la posibilidad de que $x$ y $x+1$ son adyacentes en el $N\times N$ rejilla es $4/(N(N+1)).$
