Tiempo para llegar a un estado final en un aleatorio dinámico (sistema de respuesta conocida, prueba desconocido)

Question

Considere la posibilidad de un sistema dinámico con espacio de estado $2^n$ representa como una secuencia de $n$ negro o blanco, caracteres, tales como $BWBB\ldots WB$.

En cada paso, se elige una al azar par $(i,j)$ $i<j$ y copia de la $i$-th color en el $j$-ésima posición. Por ejemplo, si el estado es $BWW$ y elegimos $(1,3)$, entonces el siguiente estado es el $BWB$.

Comenzando con un estado inicial $BWW\ldots W$, vamos a llegar a un estado final $BB\ldots B$ en tiempo finito con una probabilidad de $1$ (debido a que cualquier segmento inicial de los negros persiste para siempre).

¿Cuál es el tiempo de espera para llegar a este estado final $BB\ldots B$?

Baja dimensiones de análisis muestra que la respuesta es exactamente $(n-1)^2$ siempre $n>2$; este fue el "verificado" a a $n=13$ o así. Pero no podemos encontrar una prueba de esta conjetura, ni siquiera muestran que la respuesta es un número entero. Uno espera que, si la respuesta es fácil, también debe haber una primaria de la prueba.

---

He probado varios tipos de inducción. Por ejemplo, traté de usar la inducción para calcular el tiempo de espera para alcanzar el estado $BB\ldots B*$ donde $*$ es algo, y la reducción de la conjetura inicial a una reclamación de que el tiempo de espera de $BB\ldots B*$ $BB\ldots BB$es exactamente $1$. Pero no sé cómo demostrar que es $1$.

Answer 1

Esta es ahora una respuesta completa.

Resulta que Markus se haga todo junto : con esta particular partida de configuración, el número de bolas negras es una cadena de Markov, y en cualquier punto en el tiempo, la distribución de la secuencia es uniforme acondicionado en el número de bolas negras en el espacio de secuencias de partida con una bola negra.

---

Deje $\Omega$ el conjunto de secuencias de $0$ $1$ de la longitud de la $n$ comenzando con $1$.

Para mostrar que el número de bolas negras es una cadena de Markov es suficiente para demostrar que si se nos da una secuencia aleatoria en $\Omega$ distribuido de manera uniforme, condicionado a que el número de bolas negras y aplicar un paso del proceso, entonces todavía podemos obtener una secuencia distribuidos de manera uniforme, condicionado a que el número de bolas negras.

Más formalmente, vamos a $\Omega' = \{1 \ldots n\}$ ser el posible número de bolas negras y $f : \Omega \to \Omega'$ ser el recuento de mapa.
Deje $F,F'$ ser el libre espacios vectoriales sobre la base $\Omega$ $\Omega'$ respectivamente.
Su proceso es descrito por una lineal endormorphism $T : F \to F$, e $f$ induce lineal mapa de $f : F \to F'$.
Deje $g : F' \to F$ ser el mapa enviar a $1.[k]$$k \in \Omega'$$\frac 1{|f^{-1}(k)|} \sum_{f^{-1}(k)} 1.[\omega]$.

Obviamente tendremos que $f \circ g = id_{F'}$.
Si podemos demostrar que la imagen de $g$ es estable por $T$, entonces hay un mapa de $T' : F' \to F'$ tal que $T \circ g = g \circ T'$.
Luego nos vamos (voy a omitir las composiciones a partir de ahora)
$gfTgf = gf(Tg)f = gf(gT')f = g(fg)T'f = gT'f = Tgf$.

Por inducción se sigue que $T^ngf = (Tgf)^n$ $fT^ngf = (fTg)^nf = T'^n f$

Dado que sólo estamos interesados en el comportamiento de $fT^n(V)$ para el primer vector de $V = 1.[10\ldots0] \in F$, y porque tenemos $gfV=V$, estamos interesados en el comportamiento de $fT^n(V) = fT^ngf(V) = T'^n f(V) = T'^n(1.[1])$.

Es decir, $T'$ es la matriz de transición de una cadena de Markov en $\Omega'$ y queremos saber cuál es el tiempo de espera para obtener de$1$$n$.

---

Intuitivamente, si usted interpretar $gf$ como un proceso que de forma aleatoria permutes la $n-1$ derecha bolas, esto nos dice que los dos procesos
"randomize ; aplicar el paso ; randomize" y "randomize ; aplicar el paso" son equivalentes.

Entonces para cualquier $k$, el proceso de "inicializar ; randomize ;( aplicar el paso ; randomize) x $k$" es equivalente al proceso de "inicializar ; randomize ; aplicar el paso x $k$".

Y desde la configuración inicial es ya aleatorizado, "inicializar ; randomize" es equivalente a "inicializar".

Por lo tanto, el proceso original es equivalente a "inicializar ; randomize ; (aplicar el paso ; randomize) x $k$", donde el número de bolas negras es , obviamente, una cadena de Markov

---

Ahora voy a mostrar que la imagen de $g$.es estable por $T$. Deje $N = n(n-1)/2$ el número de pares de $(i,j)$$1 \le i < j \le n$.

Para probar esto básicamente para contar las cosas. El "sorprendente" es que para obtener una secuencia en particular como resultado de una no trivial copiar mover, el número de maneras de obtener que no dependen del orden de las bolas Si desea obtener una secuencia de con $4$ mediante la copia de un $1$ a una $0$, usted tiene que elegir entre dos $1$ , a continuación, reemplace la derecha con un $0$.

Aunque usted consigue algunas secuencias de entrada más veces que otros, ya que todos ellos son equiprobables, el resultado de la probabilidad para cada secuencia de salida no depende del orden de las bolas.

Por el contrario, algunas entradas tienen una tendencia a aumentar la suma, y algunos otros tienen una tendencia a disminuir la suma, pero en realidad, cuando se suma cada permutación de las entradas, se hará algo uniforme dentro de cada clase de equivalencia.

---

Para calcular los $T(g(k))$, considere la posibilidad de una secuencia aleatoria que tiene suma $k$ y se distribuye de forma homogénea, de manera que cada secuencia de suma $k$ probabilidad de $1/\binom {k-1}{n-1}$ a la de entrada.

Para cada posible secuencia de salida de suma $k$, tener en cuenta cuántas veces se puede llegar a ella.
Para conseguir una secuencia de suma $k$ usted necesita hacer un movimiento que no hace nada, y para cada secuencia de salida hay $k(k-1)/2+(n-k)(n-k-1)/2$ movimientos que hacerlo, de manera que cada secuencia de suma $k$ se alcanza en total con una probabilidad de $(k(k-1)+(n-k)(n-k-1))/(2N \binom {k-1}{n-1})$, esto es $ (k(k-1)+(n-k)(n-k-1))/2N \;.g(k)$.

Ahora considere la posibilidad de la salida de secuencias de suma $k+1$ (si $k<n$). Para conseguir una secuencia de suma $k+1$ usted necesita una copia de un $1$ a una $0$.
Para cada resultado, ha $k$ secuencias de suma $k$ que lo puede producir, uno que se produce en uno de los casos, el siguiente en dos casos, y así sucesivamente. Ya que cada secuencia de suma $k$ es igualmente probables, cada secuencia de salida se puede llegar con igual probabilidad $k(k+1)/(2N \binom {k-1}{n-1})$, por ello la suma de todo esto es $k(k+1)\binom {k}{n-1}/(2N\binom {k-1}{n-1})\;. g(k+1) = (k+1)(n-k)/2N \;. g(k+1)$

Por último, considere la posibilidad de la salida de secuencias de suma $k-1$ (si $k>0$) Para conseguir una secuencia de suma $k-1$ usted necesita una copia de un $0$ a una $1$.
Para cada resultado, ha $n-k$ secuencias de suma $k$ que lo puede producir, uno que se produce en uno de los casos, el siguiente en dos casos, y así sucesivamente. Ya que cada secuencia de suma $k$ es igualmente probables, cada secuencia de salida se puede llegar con igual probabilidad $(n-k)(n-k+1)/(2N \binom {k-1}{n-1})$, por ello la suma de todo esto es $(n-k)(n-k+1)\binom {k-2}{n-1}/(2N\binom {k-1}{n-1}) \;. g(k-1) = (n-k)(k-1)/2N \;. g(k-1)$

Y $k(k-1)+(n-k)(n-k-1) + (k+1)(n-k) + (n-k)(k-1) = n(k-1)+(n-k)n = n^2-n = 2N$, por lo que los tres términos de la suma a $1$ según sea necesario.

---

Por último, podemos utilizar el hecho de que las secuencias están distribuidos de manera uniforme, condicionado a que el número de bolas negras para demostrar que $E[T_n - T_{n-1}] = 1$.

Considerar en cada momento, las probabilidades de que vamos a partir de una secuencia particular con $n-1$ $1$s a la secuencia final con $n$ $1$s.

En todos los tiempos, el $n-1$ secuencias con suma $n-1$ son igualmente probables (decir $p_t$), luego de una cuenta simple argumento dice que la secuencia final viene de $1\ldots10$ con una probabilidad de $(n-1)p_t/N = 2p_t/n$ y se trata de uno de los $n-2$ otras secuencias con una probabilidad de $(1+2+\ldots+n-2)p_t/N = (n-2)(n-1)p_t/2N = (n-2)p_t/n$.

Resumiendo los eventos para cada tiempo de $t$, la probabilidad de que el último paso viene de $1\ldots10$$2/n$, lo que significa que $P(T_{n-1} < T_n) = 2/n$,$P(T_{n-1} = T_n) = (n-2)/n$.

Pero si $T_{n-1} < T_n$, entonces el tiempo de espera para el último paso es $N/(n-1) = n/2$ (porque estamos estancados en $1\ldots10$ hasta que nos trasladamos a $1\ldots 11$, lo cual ocurre con probabilidad de $2/n$)

Por lo tanto $E[T_n - T_{n-1}] = 2/n \times n/2 + 0 \times (n-2)/2 = 1$.

---

Usted puede probar fácilmente que @leonbloy de la conjetura a partir de la observación de que $P(T_{n} > T_{n-1}) = 2/n$.

Si se puede ocultar la última $n-k$ bolas, entonces lo que vemos es una mezcla de un mismo proceso, en la primera $k$ bolas y los pasos que copia uno de visible bolas a uno de los ocultos bolas, y así los pasos que no visiblemente hacer nada. Por lo tanto, aunque puede ver una ralentizado el proceso, esto no influye en las probabilidades de $P(T_{k-1} > T_{k}) = 2/k$.

A partir de entonces, es fácil obtener el tiempo de espera entre cada paso, porque si tenemos la igualdad, a continuación,$T_{k-1} - T_{k} = 0$,
y si no, a cada paso entre ellos tiene una probabilidad de $(k-1)/N$ de colorante de la $k$th bola negra, y se lleva $N/(k-1)$ pasos.
Finalmente, se espera que los diferencia es $N/(k-1) \times 2/k = n(n-1)/k(k-1)$.

Answer 2

@leonbloy señaló una observación interesante:

Relacionados con la conjetura (apoyado por simulaciones) : Vamos a $T_i$ ser el incremento en la cantidad de pasos que toma el color de la primera $i$ posiciones de la secuencia sobre y por encima del número de pasos que da el color de la primera $i-1$ carácter. Entonces $$ E(T_i)=\frac{\binom{n}{2}}{\binom{i}{2}} = \frac{n(n-1)}{i(i-1)} $$ Esto concuerda con el resultado original $E(T_2+T_3 + \cdots T_n)=(n-1)^2$ y su conjetura $E(T_n)=1$.

Voy a intentar "demostrar", pero depende de la otra conjetura (también apoyado por la simulación). Esto puede ser sólo una forma de reescritura de @leonbloy del conjeture, pero quizás es más fácil de probar.

Vamos a hacer una especie de pseudo inducción. Podemos probar que es verdadera directamente por $T_2$ donde nuestra secuencia es $BW...W$. La única manera de que el color del segundo personaje es recoger el par $(1,2)$ a que la probabilidad de $1/{n \choose 2}$. Entonces tenemos el siguiente conjunto:

$$ E(T_2) = 1 + \frac{1}{\binom{n}{2}}\cdot 0 \ + \left(1-\frac{1}{\binom{n}{2}}\right)E(T_2) \\ E(T_2) = \binom{n}{2} = \frac{\binom{n}{2}}{\binom{2}{2}} $$

i.e. we must draw one pair and there is a $1/{n \elegir 2}$ we are done and a $1 - 1/{n \elegir 2}$ chance we are back where we started.

Now consider a character sequence where the first $k$ characters have been colored in and the rest are unknown i.e. we have $B\ldots B*$. We will prove the expected number of steps to color the first $k+1$ characters, $E(T_{k+1})$, should be:

$$E(T_{k+1}) = \frac{\binom{n}{2}}{\binom{k+1}{2}} = \frac{n(n-1)}{k(k+1)}$$

To do so we need some more information about the sequence besides the fact that the first $k$ characters are colored. In partiuclar, if we can differentiate the cases where the $k+1^{th}$ character happened to have been colored or not in the process of coloring the first $k$ colors, we can calculate $E(T_{k+1})$. Let $p_k$ be the probability that the $k+1^{th}$ character is already colored. Then we have a $p_k$ probability that our sequence looks like $B\ldots BB*$ i.e. it already has the first $k+1$ characters colored and a $1 - p_k$ probability that it looks like $B\ldots BW*$ i.e. the $k+1^{th}$ character is white (W) and thus we need to calculate the expected number of steps to paint it black. Let us use $W_k$ to denote the number of steps needed to color the $k+1^{th}$ character of the sequence $B\ldots BW*$ black. Then:

$$ E(T_{k+1}) = p_k \cdot 0 + (1 - p_k)E(W_k) = (1 - p_k)E(W_k) $$

We can easily calculate $W_k$. The pairs we can draw that will color the $k+1^{th}$ character are of the form $(i,k+1)$ where $i \in [1,k]$. Thus we have $k$ possible pairs that will paint the desired character giving a probability of $k / \binom{n}{2}$. Thus:

$$ E(W_k) = 1 + \frac{k}{\binom{n}{2}}\cdot 0 \ + \left(1-\frac{k}{\binom{n}{2}}\right)E(W_k) \\ E(W_k) = \frac{\binom{n}{2}}{k} = \frac{n(n-1)}{2k} $$

Thus substituting this back, we get:

$$ E(T_{k+1}) = (1 - p_k)\frac{n(n-1)}{2k} $$

Aquí es donde nos quedamos atascados y la necesidad de la conjetura.

Conjetura (verificado por simulación): Después de seguir una serie de pasos hasta la primera $k$ caracteres de la secuencia son de color, la probabilidad, $p_k$, $k+1^{th}$ personaje ya es de color está dado por: $$ p_k = \frac{k-1}{k+1} $$ La evidencia proporcionada en la parte inferior de la respuesta.

Suponiendo que es cierto, obtenemos:

$$ \begin{align} E(T_{k+1}) &= \left(1 - \frac{k-1}{k+1} \right)\frac{n(n-1)}{2k} \\ &= \frac{2}{k+1}\cdot \frac{n(n-1)}{2k} \\ &= \frac{n(n-1)}{k(k+1)} = \frac{\binom{n}{2}}{\binom{k+1}{2}} \\ \end{align} $$

as required. This would prove op's conjecture since the expected number of steps till completion is given by:

$$ \begin{align} E(T_2 + T_3 + \cdots + T_n) &= \sum_{i=2}^n\frac{n(n-1)}{i(i+1)} \\ &= n(n-1) \cdot \sum_{i=2}^n\frac{1}{i(i+1)} \\ &= n(n-1) \cdot \sum_{i=2}^n\frac{1}{i-1} - \frac{1}{i} \\ &= n(n-1) \cdot \left ( \frac{1}{1} -\frac{1}{2} + \frac{1}{2} -\frac{1}{3} + \frac{1}{3} + \cdots + \frac{1}{n-1} - \frac{1}{n} \right) \\ &= n(n-1) \cdot \left ( \frac{1}{1} - \frac{1}{n} \right) \\ &= n(n-1) \cdot \left (\frac{n-1}{n} \right) \\ &= (n-1)^2 \end{align} $$

---

La evidencia de que la $p_k = \frac{k-1}{k+1}$:

La matriz a continuación es una matriz de $M$ cuando la entrada $i,j$ representa la probabilidad de la $j+1^{th}$ carácter de una secuencia de longitud $i$ ser de color después de la primera $j$ son de color. Como se puede ver, los valores son invariantes de la longitud de la secuencia (las filas). En realidad me encontré con una pruebas más grandes, pero no guardar los resultados. Para esta noche, mi equipo necesita un descanso. Yo podría publicar una muestra más grande mañana.

     1        2        3        4        5        6       7        8       9   
1   0.0  0.00000  0.00000  0.00000  0.00000  0.00000  0.0000  0.00000  0.0000
2   0.0  0.00000  0.00000  0.00000  0.00000  0.00000  0.0000  0.00000  0.0000
3   0.0  0.32890  0.00000  0.00000  0.00000  0.00000  0.0000  0.00000  0.0000
4   0.0  0.33455  0.49570  0.00000  0.00000  0.00000  0.0000  0.00000  0.0000
5   0.0  0.33545  0.49400  0.60520  0.00000  0.00000  0.0000  0.00000  0.0000
6   0.0  0.33605  0.49825  0.59395  0.66200  0.00000  0.0000  0.00000  0.0000
7   0.0  0.33055  0.50465  0.59865  0.67025  0.71760  0.0000  0.00000  0.0000
8   0.0  0.33335  0.50275  0.60105  0.66430  0.71635  0.7476  0.00000  0.0000
9   0.0  0.33005  0.50605  0.60035  0.66255  0.71310  0.7490  0.77605  0.0000
10  0.0  0.33480  0.49800  0.60330  0.66855  0.70855  0.7497  0.77940  0.8023

El programa utilizado para simular los eventos está aquí (python3):

import numpy as np
from pandas import DataFrame

def t_i(n, k, seq=[]):
    if not seq: seq = ['B'] + ['W']*(n - 1)
    assert(k <= len(seq))
    count = 0
    while seq[:k] != ['B']*k:
        i, j = rand_pair(seq)
        seq[j] = seq[i]
        count += 1
    if seq[k] == 'B':
        rem_count = 1
    else:
        rem_count = 0
    return rem_count


def ti_time(n, k, seq=[], iter_n=20000):
    """
    Tries to get probability of k+1-th character being colored
    after coloring the first k characters.
    """
    rem_avg_sum = 0
    count = 0
    for i in range(iter_n):
        rem_count = t_i(n, k, seq)
        rem_avg_sum += rem_count
        count += 1
    return rem_avg_sum/count

def main():
    N_LIM = 7
    arr = np.zeros((N_LIM, N_LIM))
    for n in range(3, N_LIM+1):
        for k in range(2, n):
            arr[n-1][k-1] = ti_time(n, k)
    df = DataFrame(arr)
    df.index += 1
    df.columns += 1
    print(df)
    return df

Answer 3

-esto no es una respuesta, es solo una idea

Supongamos que tenemos $n$ cosas que debemos de color negro. Cada vez que tomamos dos objetos de esta $n$, llamar a uno con menor índice de la "colorista" y el uno con índice mayor que el 'receptor' (el 'colorista' los colores de la 'receptor'). El último objeto nunca puede ser el colorista, sólo recibe. Por lo que podemos ordenar de ignorarlo por ahora, y sólo se concentran en la coloración de la primera $(n-1)$ objetos negro, y la preocupación acerca de la última de una tarde.

Definir $E(n)$ cuando el número de movimientos a color $n$ objetos negro a partir de BWW...WW, y $E'(n-1)$ como el tiempo de espera para el color de la primera $(n-1)$ objetos negro si usted tiene un total de $n$ objetos (ignorando el último objeto).

Cada vez que tomamos dos objetos, nos dicen que el color "fugas" si el receptor es el último objeto. Para encontrar $E'(n-1)$, tenemos que tener $E(n-1)$ nonleaking la coloración de las operaciones y de agregar en las filtraciones. Cada vez que el color, tenemos un $(n-1)/(nC2)$ de probabilidad de fugas. Así tenemos

$$E'(n-1) (\frac{nC2 - (n-1)}{nC2}) = E(n-1)$$

Y entonces, si asumimos (en la esperanza de inducción) que $ E(n-1) = (n-2)^2$, entonces tenemos

$$E'(n-1) = (n-1)^2 -1$$

Después de la coloración de la primera $(n-1)$ objetos negro, tenemos que arreglar el pasado. Observe que las filtraciones "overwrite" cada uno de los otros, en el sentido de que sólo la última fuga de cuenta de qué color es el último objeto termina. Por esta razón, es muy probable que el último objeto ya está en negro en el momento en que realiza la coloración de la primera (n-1) de los objetos. Así, se podría conjeturar que

$$E(n) = E'(n-1) + 1$$

es decir que en promedio tarda de 1 color a color el último objeto. Si esto es cierto, tenemos nuestra relación deseada.

Lo siento si esto es incohesive; estoy en el tren, sólo pensaba poner ideas

Answer 4

No una respuesta

---

Me di cuenta de que Mathematica no es exactamente gratis, así que pensé que iba a compartir también la python3 código que se utiliza para las simulaciones en caso de que sea útil para cualquier persona. Funciona razonablemente rápido para $n < 25$ (python rápido que es :D).

import random
from itertools import permutations

def rand_pair(seq):
    """ 
    Returns random pair of indices from sequence.
    """
    while True:
        i = random.randrange(0, len(seq))
        j = random.randrange(0, len(seq))
        if i != j: break
    return min(i,j), max(i, j)

def model(n, seq=[]):
    """
    Returns the number of steps taken for one run of a sequence
    of length n
    """
    if not seq: seq = ['B'] + ['W']*(n - 1)
    assert(len(seq) == n)
    count = 0
    while seq != ['B']*(n):
        i, j = rand_pair(seq)
        seq[j] = seq[i]
        count += 1
    return count

def exp_time(n, seq=[], iter_n=10000):
    """
    Tries to get expected number of steps for seq of length n
    """
    avg_sum = 0
    count = 0
    for i in range(iter_n):
        avg_sum += model(n, seq[::])
        count += 1
    return avg_sum/count

def main():
    """
    Repeatedly reprompts to generate expected runtime for sequences
    of different lengths.
    """
    while True:
        n = int(input('Enter seq length: '))
        t = exp_time(n)
        # prints float representation to see potential error in rounding
        print('Size: {} - Steps: {} - Float:{}'.format(n, round(t), t)) 


# ==============================================================================
#           Extra stuff for testing transitions between states
# ==============================================================================
def get_perms(l):
    return set(permutations(l[1:]))

def simulate(l, i):
    NUM_TRIALS = 100000
    f_count = b_count = s_count = 0    # front_count, back_count, stay_count
    for _ in range(NUM_TRIALS):
        i,j = rand_pair(l)
        if l[i] == 'B' and l[j] == 'W':
            f_count += 1
        elif l[i] == l[j]:
            s_count += 1
        else:
            b_count += 1
    return (b_count/NUM_TRIALS, s_count/NUM_TRIALS, f_count/NUM_TRIALS)

def transition_prob(i, n):
    curr = ['B']*(i+1) + ['W']*(n-i-1)
    perms = get_perms(curr)
    for l in perms:
        l = ['B'] + list(l)
        b,s,f = simulate(l,n)
        print('{0} ->  {1}, {2}, {3}'.format(l, b,s,f)) 
        input()

Answer 5

Aunque no es útil para demostrar la conjetura, pensé que la gente pueda apreciar el siguiente código de Mathematica para crear secuencias de cadenas de este tipo. (Tengo ninguna queja en cuanto a su eficiencia!)

BWSequence[n_Integer] /; Positive[n] := Module[{}, states = {UnitVector[n, 1]}; While[Not[Equal @@ Last[states]], pair = Sort[RandomInteger[{1, n}, 2]]; If[pair[[1]] != pair[[2]], AppendTo[states, ReplacePart[Last[states], pair[[2]] -> Last[states][[pair[[1]]]]]]];]; ArrayPlot[states\[Transpose], ImageSize -> 1100, Frame -> False]]

El argumento de BWSequence es el número de caracteres en la cadena; la secuencia resultante es visualizado a través de la ArrayPlot, con cadenas secuenciales trazada de izquierda a derecha con cada secuencia organizados de arriba hacia abajo. Una posible salida de BWSequence[15] a continuación se muestra.

Podemos además utilizar esto para probar la conjetura numéricamente. Por ejemplo, podemos generar una colección de tales secuencias y calcular el promedio de la longitud usando el siguiente código:

BWAverage[n_Integer, reps_Integer] /; Positive[n] && Positive[reps] := Module[{}, lengths = {}; Do[BWSequence[n]; AppendTo[lengths, Length[states] - 1], {reps}]; Total[lengths]/reps // N]

Por ejemplo, una posible salida de BWAverage[20,100] es 360.39, lo cual está de acuerdo con la conjetura de valor de $(20-1)^2=361$ a en $0.2\%$.