Promedio de la longitud del más largo del Subsequence palindrómico

Question

Supongamos que existe un conjunto finito $A$ contiene $n$ elementos. Uno puede construir una secuencia de longitud finita:

$$\{a_i\},\ a_i \in A,\ i\in \mathbb N,\ i\le N$$

Esta secuencia contiene $2^N$ subsecuencias de la forma:

$$\{ a_{i_k}\}, k\in \mathbb N,\ k\le M\le N,\ i_k>i_{k-1}$$

Tal subequence es capicúa iff $a_{i_{M+1-k}} = a_{i_k}\ \forall k$. La longitud de los más palindrómicas larga por lo tanto puede ser definido como:

$$M_p\{a_i\} = \max\{|\{a_{i_k}\}|:a_{i_{M+1-k}} = a_{i_k}\ \forall k\}$$

El algoritmo para encontrar $M_p$ es un conocido problema de programación dinámica, pero después de la implementación que me he encontrado un interesante comportamiento. La media proporcional de la longitud de los más palindrómicas larga puede ser escrita como:

$$\pi(N) = \left\langle\frac{M_p\{a_i\}}{N}\right\rangle$$

donde $\left\langle\right\rangle$ denota un promedio sobre todos los $\{a_i\}$ de la longitud de la $N$. En principio, un muestreo aleatorio debe proporcionar una buena aproximación. Numéricamente, parece que $\lim_{N\to\infty}\pi(N)$ converge a una constante que depende sólo de la $n$, el número de elementos de los que la secuencia se construye. Para las secuencias binarias, este límite parece ser $\approx 0.8$, mientras que para $n=10$, parece ser $\approx 0.45$.

El hecho de que el límite converge a una constante distinta de $1$ o $0$ indica que la mayor palíndromo escala linealmente con la longitud de la secuencia, y que los valores calculados parecen ser los números racionales bastante curioso.

Aquí están algunas de las aproximaciones de $\lim_{N\to\infty}\pi_n(N)$, generado por el uso de 256 secuencias aleatorias de longitud 256. $\sigma$ indica que la desviación estándar de la distribución, no en la media de la muestra.

\begin{array}{c|lcr} n & \pi_n(N) & \sigma \\ \hline 2 & 0.80035 & 0.01647 \\ 3 & 0.70724 & 0.01615 \\ 4 & 0.64514 & 0.01544 \\ 5 & 0.59718 & 0.01697 \\ 6 & 0.56046 & 0.01617 \\ 7 & 0.53024 & 0.01627 \\ 8 & 0.50377 & 0.01527 \\ 9 & 0.48380 & 0.01520 \\ 10 & 0.46349 & 0.01489 \end{array}

Me gustaría saber si hay una manera de derivar el comportamiento asintótico de la observada en los resultados numéricos. La complejidad del algoritmo para $M_p$ hace que sea difícil obtener una distribución de probabilidad, y el número racional resultados pista de que puede ser un enfoque más sencillo. El aporte se agradece.

Answer 1

Dos palabras $W_1$ $W_2$ compartir un alfabeto común, vamos a $L(W_1, W_2)$ ser el más largo común subword de $W_1$ $W_2$ (es decir, la palabra más larga que aparece como una subword de ambos $W_1$$W_2$). Definir $$\gamma_n = \lim_{N \rightarrow \infty} \frac{E[L(W_1, W_2)]}{N},$$ donde $W_1$ $W_2$ son dos palabras independientes de la longitud de la $N$ uniformemente elegido a partir de un alfabeto de longitud $n$. Este límite existe porque la más larga de la palabra común es superadditive cuando nos concatenar palabras: Hemos $$L(W_1 X_1, W_2 X_2) \geq L(W_1, W_2) + L(X_1, X_2).$$

Determinar el $\gamma_n$ es desde hace tiempo un problema abierto, y parece probable que $\gamma_n$ es también la limitación de la fracción de los más palíndromo.

Por qué $\gamma_n$ es un límite inferior para $\pi(N)$: Dividir la secuencia en dos mitades iguales. Usted puede construir un palíndromo tomando una palabra común entre la primera mitad y la reversión de la segunda mitad.

Por qué $\gamma_n$ es un límite superior para $\pi(N)$ (NO RIGUROSO). Deje $L_k$ ser la longitud de los más comunes de la secuencia entre el primer $k$ personajes y de la inversión de los últimos $N-k$ personajes de su palabra. El más largo palíndromo puede ser considerado como el máximo de $2L_k$ $k$ $1$ y $n$ ($k$ se corresponde con el punto medio de su palabra).

Por definición, el valor esperado de $L_{N/2}$$\frac{N}{2} \gamma_n$. Además, tenemos una cierta cantidad de concentración: Porque el cambio de un solo carácter en la secuencia se puede cambiar solamente el más largo común de larga por $1$, se sigue de McDiarmid de la Desigualdad (que a su vez proviene de Azuma la martingala de la desigualdad) que $L_n$ casi siempre dentro de $O(\sqrt{N})$ de su expectativa. En particular, es muy poco probable (probabilidad mucho menor que $1/N$) $2L_{N/2}$ al menos $cN$ cualquier $c>\gamma_n$.

Intuitivamente, debería ser incluso menos probable que los $L_k$ a ser inusualmente grande cuando la secuencia se divide de manera desigual. Si esto fuera cierto, entonces lo que quería iba a seguir a partir de la unión vinculados. No veo una manera obvia para mostrar que si.

Wikipedia tiene muy pocas referencias sobre el problema de la determinación de $\gamma_k$ en su artículo sobre la Chvátal–Sankoff constantes