¿Cuál es la probabilidad de atravesar un $n \times n$ tablero en exactamente $K$ se mueve uniformemente al azar?

Question

En un $n$ -Fila $n$ -Tablero de columnas, queremos mover una pieza desde la casilla de la esquina inferior izquierda hasta la casilla de la esquina superior derecha siguiendo las órdenes de una luz que parpadea en $3$ diferentes colores:

• Cada color representa un movimiento: hacia arriba, hacia la derecha o en diagonal (hacia arriba y hacia la derecha) .
• La probabilidad de que cada uno parpadee es igual.

¿Cuál es la probabilidad de llegar a la casilla de la esquina superior derecha utilizando $K$ movimientos, sabiendo que cuando la pieza llega a una casilla que es imposible hacer $1$ de la $3$ se mueve, ese color deja de parpadear?

Answer 1

La solución se corrigió de acuerdo con las explicaciones de la condición de la tarea contenidas en el leonbloy comentarios .

Resulta muy engorroso, pero para conseguir las fórmulas de cálculo había que tener en cuenta muchos detalles. Por comodidad, suponemos que el tablero tiene el tamaño $ (n + 1) \times (n + 1) $ y las celdas del tablero se denotan por el par de coordenadas $ (u, v), u, v \in \lbrace 0, 1, \dots, n \rbrace. $

En primer lugar, determinamos la probabilidad $ P (u, v, t) $ del desplazamiento de la ficha desde la posición inicial $ (0,0) $ a la posición $ (u, v) $ en $ t $ pasos para $ u, v \le n-1 $ . Sea $ i, j, d $ sea el número de movimientos hacia la derecha, hacia arriba y en diagonal, respectivamente. Evidentemente:

$ i+j+d=t, i+d=u, j+d=v, $

de donde $u+v-t=d, i=u-d=t-v, j=v-d=t-u,$ y $ u \le t, v \le t \le u+v.$

Entonces

(1) $P(u,v,t)=\frac 1 {3^t} C_t^{i}C_{t-i}^j=\frac 1 {3^t} C_t^{v}C_{v}^{t-u},$

donde $ C_t ^ {i}$ es el número de variantes de desplazamiento hacia la derecha, $ C_ {v}^ {t-u}$ es el número de variantes de la subida, $ C_t^{v} C_{v}^{t-u} $ es el número de rutas de longitud $ t $ desde la posición inicial hasta la posición $ (u, v), \frac 1 {3 ^ t} $ es la probabilidad de elegir cada una de estas rutas.

A continuación, determinamos la probabilidad $ P'(n, v, t) $ de la primera salida de la viruta a la frontera $ (n, v) $ en $ t $ pasos. Esta salida es posible con probabilidad $ 1/3 $ de la posición $ (n-1, v)$ y desde la posición $ (n-1, v-1)$ para $ v \ge 1 $ .

Por lo tanto,

$ P'(n,0,t)= \frac 13 P(n-1,0,t-1), $

$ P'(n,v,t)= \frac 13 [P(n-1,v,t-1)+ P(n-1,v-1,t-1) ]$ para $ 1 \le v \le n-1 $ .

Del mismo modo, para la primera salida del chip en la frontera $ (u, n) $ podemos escribir:

$ P'(0, n, t) = \frac 13 P(0, n-1, t-1),$

$ P'(u, n, t) = \frac 13 [P(u, n-1, t-1) + P (u-1 , N-1, t-1)] $ para $ 0 \le u \le n-1. $

Y para la primera salida a la derecha y límites superiores en (n, n):

$ P'(n, n, t) = \frac 13 P(n-1, n-1, t-1). $

Después de la primera salida a cualquier frontera, el movimiento de la ficha se determina con probabilidad 1,

La ficha se moverá desde la posición inicial hasta la posición $ (n, n) $ a través de la primera salida a la frontera en la posición $ (n, v) $ en $ k $ pasos, si a la posición $ (n, v) $ se movió $ t_v = k + v-n $ pasos (de forma similar para las posiciones $ (u, n) $ ), por lo tanto

$ P(n, n, k) = \sum_{v = 0}^{n-1} P'(n, v, t_v) + \sum_{u = 0}^{n-1} P'(u, N, t_u) +\frac 13 P(n-1, n-1, k-1) $ ,

donde $ t_v = k + v-n, t_u = k + u-n. $

Teniendo en cuenta la igualdad de las sumas escritas, podemos escribir

$ P (n, n, k) = 2 \sum_{v = 0}^{n-1} P'(n, v, t_v) + \frac 13 P (n-1, n-1, k-1) =$

$ =\frac 23 P(n-1,0, k-n-1) + \frac 13 P(n-1, n-1, k-1) + 2 \sum_{v = 1}^{n-1} P'(n , v, k + v-n) = $

$ = 2 \frac {J (k = 2n)} {3 ^ {n}} + \frac 13 P(n-1, n-1, k-1) +$

$+ \frac 23\sum_{v = 1}^{n-1} [P(n-1, v, k + v-n-1) + P (n-1, v-1, k + v-n-1)] $

donde $J (\cdot)$ es el indicador de verdad, las probabilidades $P (u, v, t)$ están definidos por (1).

Para comprobar las fórmulas obtenidas, he calculado los valores de probabilidad $ P (n, n, k) $ para $n = 6 $ (tablero 7x7), que para $ k = 6, 7, \dots, 12 $ son iguales: 0,00137, 0,03018, 0,15546, 0,32109, 0,31550, 0,14896, 0,02743. Para mi gran sorpresa, los resultados coinciden plenamente con los de Andrew Woods que se le dio en su respuesta.

Answer 2

Supongamos que estamos ante un $5\times 5$ tablero. Utilizando una recurrencia, en la que en cada paso, cada entrada de la nueva matriz suma las entradas de la antigua matriz a su oeste, suroeste y sur, después de cuatro pasos llegamos a la posición:

$$\begin{array}{rrrrr}1&4&6&4&1\\0&4&12&12&4\\0&0&6&12&6\\0&0&0&4&4\\0&0&0&0&1\end{array}$$

Tenga en cuenta que cada entrada es $\binom4{x,\ y,\ 4-x-y}$ un coeficiente trinomial, donde $x$ y $y$ son las distancias horizontales y verticales de la última columna y la fila superior. También hay que tener en cuenta que toda la matriz suma $81=3^4$ como se esperaba. Así, después de cuatro pasos, la probabilidad de que la pieza haya llegado a la esquina noreste es $\frac1{81}$ .

A partir de este punto, la recurrencia continúa de la misma manera, excepto en la última columna y la fila superior. En la fila superior, las contribuciones del oeste se triplican; en la última columna, las contribuciones del sur se triplican. Así, el siguiente paso produce:

$$\begin{array}{rrrrr}0&7&28&42&36\\0&0&10&30&42\\0&0&0&10&28\\0&0&0&0&7\\0&0&0&0&0\end{array}$$ La suma de esta matriz asciende a $240$ , ya que la posibilidad de que la pieza ya haya llegado a la esquina noreste es $\frac3{243}$ . La entrada en la esquina noreste es ahora $36$ , por lo que la probabilidad de que la pieza llegue allí en el quinto paso es $\frac{36}{243}=\frac4{27}$ .

La matriz sigue siendo simétrica con respecto al eje SO-NE; las entradas fuera de la fila superior y la última columna son ahora de la forma $\binom{4+k}{x+k,\ y+k,\ 4-x-y-k}$ con $k=K-(n-1)$ siendo el número de pasos más allá de $4$ .

La consecuencia es que sólo tenemos que prestar atención a la fila superior, ya que la última columna es la misma y el resto es expresable como coeficientes de trinomios.

En cada nuevo paso, la fila superior pierde su última entrada. Entonces, todas las entradas, excepto la última, se triplican y se les añaden dos coeficientes de trinomio; la última se sextuplica y se le añade un coeficiente de trinomio. Como resultado, parece que para $k>1$ debería haber una fórmula para la probabilidad que se parece más o menos a esto: $$\frac{2(3^k()+3^{k-1}(()+())+3^{k-2}(()+())+\ldots+3(()+()))\ +\ ()}{3^{n-1+k}}$$ en el que cada $()$ representa un coeficiente trinomial.

Resulta que la respuesta es: $$\frac{\tbinom{n+k-2}{k,\ k,\ n-k-2}+6\sum_{i=0}^{k-1}3^i(\tbinom{n-3+k-i}{k,\ k-1-i,\ n-k-2}+\tbinom{n-3+k-i}{k-1,\ k-1-i,\ n-k-1})}{3^{n-1+k}}$$

Durante los primeros $n$ obtenemos los siguientes numeradores: $$\begin{array}{rrrrrrr}1\\1&6\\1&14&30\\1&24&114&144\\1&36&282&764&678\\1&50&570&2480&4630&3156\\1&66&1020&6320&18630&26388&14580\end{array}$$

Por ejemplo, en un $7\times7$ tablero la probabilidad de que el contador llegue a la esquina opuesta en $6,\ 7,\ 8,\ldots$ movimientos es $1/729,\ 66/2187,\ 1020/6561,\ldots$ y el número esperado de movimientos es de aproximadamente $9.4758\ldots$