Subsecuencia alternante más larga

En matemáticas combinatorias , probabilidad e informática , en el problema de la subsecuencia alternada más larga , se busca encontrar una subsecuencia de una secuencia dada en la que los elementos estén en orden alterno y en la que la secuencia sea lo más larga posible.

Formalmente, si${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$es una secuencia de números reales distintos, entonces la subsecuencia${\displaystyle \{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{k}}\}}$es alterna ^{[ 1 ]} (o zigzag o de abajo hacia arriba ) si

${\displaystyle x_{i_{1}}>x_{i_{2}}<x_{i_{3}}>\cdots x_{i_{k}}\qquad {\text{y}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

Similarmente,${\displaystyle \mathbf {x} }$es alternante inverso (o arriba-abajo ) si

${\displaystyle x_{i_{1}}<x_{i_{2}}>x_{i_{3}}<\cdots x_{i_{k}}\qquad {\text{y}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

Nótese que toda secuencia de longitud 1 es a la vez alternante y alternante inversa.

Dejar${\displaystyle {\rm {as}}_{n}(\mathbf {x} )}$denota la longitud (número de términos) de la subsecuencia alternada más larga de${\displaystyle \mathbf {x} }$. Por ejemplo, si consideramos algunas de las permutaciones de los enteros 1, 2, 3, 4, 5, tenemos que

• ${\displaystyle {\rm {as}}_{5}(5,4,3,2,1)=2}$, porque hay subsecuencias alternas de longitud 2, (por ejemplo 5,4 o 5,2 o 3,1), pero no todas las subsecuencias de longitud 3 son alternas;
• ${\displaystyle {\rm {as}}_{5}(1,2,3,4,5)=1}$, porque todas las subsecuencias de longitud 2 no son alternas. (en realidad, son alternas inversas);
• ${\displaystyle {\rm {como}}_{5}(5,1,3,4,2)=4,}$porque 5,1,3,2 y 5,1,4,2 y 5,3,4,2 son todos alternantes, y no hay ninguna subsecuencia alternante con más elementos;
• ${\displaystyle {\rm {como}}_{5}(4,3,5,1,2)=5,}$porque 4,3,5,1,2 es en sí mismo alternante.

En una secuencia de elementos distintos, la subsecuencia de extremos locales (elementos mayores que ambos elementos adyacentes, o menores que ambos elementos adyacentes) forma una secuencia alternante más larga canónica. ^{[ 2 ]} Como consecuencia, la subsecuencia alternante más larga de una secuencia de${\displaystyle n}$Los elementos se pueden encontrar en el tiempo${\displaystyle O(n)}$En secuencias que permiten repeticiones, se puede aplicar el mismo método después de reemplazar cada secuencia de elementos repetidos por una sola copia de ese elemento.

Si${\displaystyle \mathbf {x} }$es una permutación aleatoria de los números enteros${\displaystyle 1,2,\ldots ,n}$y${\displaystyle A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )}$, entonces es posible demostrar ^{[ 3 ] [ 4 ] [ 5 ]} que

${\displaystyle E[A_{n}]={\frac {2n}{3}}+{\frac {1}{6}}\qquad {\text{y}}\qquad \operatorname {Var} [A_{n}]={\frac {8n}{45}}-{\frac {13}{180}}.}$

Además, como${\displaystyle n\rightarrow \infty }$, la variable aleatoria${\displaystyle A_{n}}$, adecuadamente centrada y escalada, converge a una distribución normal estándar .

El problema de la subsecuencia alterna más larga también se ha estudiado en el contexto de algoritmos en línea , en los que los elementos de${\displaystyle \mathbf {x} }$Se presentan de forma virtual, y quien toma las decisiones debe decidir si incluye o excluye cada elemento en el momento en que se presenta por primera vez, sin tener conocimiento de los elementos que se presentarán en el futuro y sin la posibilidad de recordar observaciones previas.

Dada una secuencia${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$de variables aleatorias independientes con distribución continua común${\displaystyle F}$, es posible construir un procedimiento de selección que maximice el número esperado de selecciones alternas. Dichos valores esperados pueden estimarse con precisión y es igual a${\displaystyle (2-{\sqrt {2}})n+O(1)}$. ^{[ 6 ]}

Como${\displaystyle n\rightarrow \infty }$, el número óptimo de selecciones alternas en línea adecuadamente centradas y escaladas converge a una distribución normal. ^{[ 7 ]}

• Permutación alternada
• Patrón de permutación y evitación de patrones
• Conteo de máximos locales y/o mínimos locales en una secuencia dada.
• Pruebas de punto de inflexión para probar la independencia estadística de${\displaystyle n}$observaciones
• Número de carreras alternas
• Subsecuencia creciente más larga
• Subsecuencia común más larga