Records, drift, and the longest increasing subsequence of biased Gaussian random walks

Este artículo investiga numéricamente la subsecuencia creciente más larga (LIS) de paseos aleatorios gaussianos sesgados, revelando que, mientras que el caso simétrico exhibe un régimen de crecimiento de $\sqrt{n}\log{n}$, la introducción de una deriva positiva hace que la longitud media de la LIS transicione a un crecimiento lineal que se alinea cada vez más con el recuento de récords a medida que aumenta la deriva.

Lo esencial

Imagina que estás observando a una persona ebria caminando por una calle larga y recta. Esto es un paseo aleatorio. Cada paso que dan es un poco aleatorio: a veces avanzan, a veces retroceden.

Durante décadas, los científicos han estudiado qué sucede si esta persona tiene la misma probabilidad de avanzar o retroceder (un paseo simétrico). Descubrieron que la secuencia más larga de pasos donde la persona solo subió (nunca bajando) crece lentamente, como la raíz cuadrada del total de pasos dados.

Pero, ¿qué pasa si la persona tiene una ligera tendencia a inclinarse hacia adelante? ¿Qué pasa si está ligeramente sesgada para caminar cuesta arriba? Este artículo explora exactamente ese escenario.

Aquí está la historia de los hallazgos, desglosada en conceptos simples:

1. La Configuración: El Ebrio Sesgado

Los investigadores simularon a un caminante que da pasos basados en una distribución "Gaussiana" (curva de campana), pero con un giro: el caminante tiene un sesgo positivo.

• El Caso Simétrico (50/50): Si el caminante está perfectamente equilibrado, el camino cuesta arriba más largo crece lentamente.
• El Caso Sesgado (Incluso un poco): Si el caminante tiene incluso ligeramente más probabilidad de avanzar que de retroceder, las reglas cambian completamente.

2. El Gran Descubrimiento: La Explosión "Lineal"

El hallazgo más sorprendente se refiere a la velocidad a la que crece el camino cuesta arriba más largo.

• En el mundo equilibrado: El camino crece lentamente (como $\sqrt{n}$).
• En el mundo sesgado: En cuanto hay cualquier sesgo hacia la dirección forward, el camino cuesta arriba más largo comienza a crecer repentinamente de forma lineal.

La Analogía: Imagina que el caminante está escalando una montaña.

• Si el viento está en calma (simétrico), podrían deambular subiendo y bajando, y la subida continua más alta que logran es relativamente corta en comparación con el tiempo total que pasan caminando.
• Si hay incluso una brisa suave que los empuja hacia adelante (sesgo), dejan de deambular sin rumbo. Comienzan a escalar con constancia. La longitud de su subida continua se vuelve directamente proporcional a cuánto tiempo caminan. Si caminan el doble de tiempo, escalan el doble de alto.

El artículo encontró que para cualquier sesgo mayor que cero, este crecimiento lineal ocurre inmediatamente. El "exponente" (la potencia que describe el crecimiento) salta de aproximadamente 0.5 a exactamente 1.

3. El "Esqueleto" del Paseo: Récords

Para entender por qué sucede esto, los autores examinaron los Récords.

• Un Récord es un momento en que el caminante alcanza un punto más alto que nunca antes había alcanzado.
• En un paseo equilibrado, los récords son raros.
• En un paseo sesgado, los récords ocurren constantemente, formando un "esqueleto" o una columna vertebral del paseo.

Los investigadores descubrieron que la Subsecuencia Creciente Más Larga (LIS) —el camino cuesta arriba más largo— esencialmente solo sigue este "esqueleto de récords".

• Con alto sesgo: El caminante está tan decidido a subir que casi cada paso es un récord. El camino cuesta arriba más largo es casi idéntico a la lista de todos sus mejores marcas personales.
• Con bajo sesgo: El caminante aún sigue principalmente los récords, pero ocasionalmente toma una pequeña "desviación" (una fluctuación) para insertar un paso extra entre dos récords.

4. La "Brecha" entre Récords y el Camino

El artículo mide la diferencia entre el número de Récords y la longitud del Camino Más Largo.

• La Brecha: Esto representa los pasos "extra" que da el caminante que no son récords personales pero que aún encajan en la cadena cuesta arriba.
• La Forma de la Brecha: Esta brecha es pequeña cuando el sesgo es diminuto (porque el paseo sigue siendo caótico) y pequeña cuando el sesgo es enorme (porque el caminante está tan decidido que cada paso es un récord).
• El Pico: La brecha es más grande en un sesgo "medio" (alrededor de un 60% de probabilidad de avanzar). Aquí, el caminante está lo suficientemente decidido para escalar con constancia, pero aún lo suficientemente inestable para encontrar pasos "ocultos" extra entre los hitos principales.

5. El "Punto de Inflexión" (El Límite Singular)

La parte más delicada de la investigación es lo que sucede justo en el borde, donde el sesgo es casi cero (50.1% vs 49.9%).

• El artículo muestra que la transición de "crecimiento lento" a "crecimiento lineal" es singular. No es un deslizamiento suave; es un acantilado.
• A medida que el sesgo se vuelve más y más pequeño, la longitud del camino no solo se reduce linealmente; se reduce más lento que lo lineal. Es como si el camino se negara a desaparecer por completo hasta que el sesgo alcanza cero absoluto.
• Los autores no pudieron encontrar una fórmula matemática simple para exactamente cómo se reduce en esta zona diminuta, pero demostraron que se comporta de manera diferente a lo que cualquiera esperaba.

6. La Forma de los Datos: De "Extraño" a "Normal"

Finalmente, el artículo examinó la distribución de estos caminos (si ejecutaran la simulación 10,000 veces, ¿cómo se verían los resultados?).

• Paseo Equilibrado (50/50): Los resultados están "sesgados" y tienen "colas pesadas". Es como una distribución log-normal. La mayoría de los caminos son cortos, pero ocasionalmente obtienes uno sorprendentemente largo. Es impredecible y "extraño".
• Paseo Sesgado (Incluso ligeramente): Los resultados se ajustan a una Gaussiana (Curva de Campana). Los caminos se vuelven muy predecibles y "normales". Cuanto más sesgas el paseo, más los resultados se parecen a una curva de campana estándar.

Resumen

Este artículo nos dice que en el mundo de los paseos aleatorios, incluso un poco de dirección lo cambia todo.

• Antes: Un caminante equilibrado deambula, y sus mejores ascensos son cortos e impredecibles.
• Después: Un caminante sesgado marcha hacia adelante. Sus mejores ascensos crecen de manera constante y lineal con el tiempo, siguiendo un "esqueleto" predecible de récords personales.
• La Transición: En el momento en que introduces un sesgo, las reglas del juego cambian instantáneamente, pasando de un mundo caótico de crecimiento lento a un mundo estable de crecimiento lineal.

Resumen técnico

Resumen Técnico: Récords, Deriva y la Subsecuencia Creciente Más Larga de Caminatas Aleatorias Gaussianas Sesgadas

Enunciado del Problema
El problema de la Subsecuencia Creciente Más Larga (LIS), estudiado tradicionalmente para permutaciones aleatorias y caminatas aleatorias simétricas de media cero, ha establecido leyes de escalado rigurosas donde la longitud esperada de la LIS crece como $\sqrt{n \log n}$ (para varianza finita) o $n^\theta$ (para incrementos de cola pesada). Sin embargo, el comportamiento de la LIS para caminatas aleatorias sesgadas —específicamente aquellas con una deriva positiva— permaneció inexplorado. Las caminatas sesgadas modelan series temporales con tendencias direccionales, donde la LIS sondea estructuras monótonas en secuencias correlacionadas y no estacionarias. Este artículo investiga la LIS de caminatas aleatorias gaussianas con varianza unitaria y una deriva media positiva $\mu_p$, parametrizada por $p = P(\xi > 0) \ge 1/2$. La pregunta central es cómo la introducción de incluso una pequeña asimetría altera el escalado asintótico y las propiedades distribucionales de la LIS en comparación con el caso simétrico.

Metodología
El estudio emplea un enfoque numérico utilizando el algoritmo de ordenamiento por paciencia para calcular la longitud de la LIS ($L_n$) para caminatas aleatorias gaussianas sesgadas.

• Modelo: La caminata se define por $X_k = \mu_p k + W_k$, donde $W_k$ es una caminata aleatoria gaussiana centrada con varianza unitaria, y $\mu_p = \Phi^{-1}(p)$ es la deriva determinada por el parámetro de sesgo $p$.
• Observables: Para cada realización, los autores miden:
  1. La longitud de la LIS $L_n(p)$.
  2. El conteo de récords $R_n(p)$ (el número de veces que la caminata establece un nuevo máximo).
  3. La superposición $R^{LIS}_n(p)$ (el número de tiempos de récord incluidos en una LIS recuperada).
• Protocolo de Simulación: Los autores generaron 10,000 realizaciones independientes para longitudes de caminata $n$ que van desde $10^4$ hasta $10^7$ y parámetros de sesgo $p \in [0.5, 0.999]$. Se prestó especial atención a la región cercana al punto simétrico $p=1/2$ y al límite casi determinista $p \to 1$.
• Análisis: El estudio analiza exponentes efectivos, coeficientes lineales, ratios diagnósticos (por ejemplo, $R^{LIS}_n/L_n$) y la forma distribucional de $L_n$ mediante gráficos cuantil-cuantil y pruebas estadísticas (Kolmogorov–Smirnov, asimetría, curtosis).

Contribuciones y Resultados Clave

1. Transición a Escalado Lineal:
   Contrario al caso simétrico ($p=1/2$), donde $E[L_n] \sim \sqrt{n \log n}$, los autores encuentran que para cualquier $p > 1/2$ fijo, la longitud media de la LIS crece linealmente con $n$:
   $$\langle L_n(p) \rangle \sim a(p)n$$
   El exponente efectivo $\theta(p)$ converge rápidamente a 1 para todo $p > 1/2$. El objeto relevante de estudio se desplaza del exponente al coeficiente $a(p)$, que aumenta suavemente desde $0$ en $p=1/2$ hasta $1$ a medida que $p \to 1$.

2. Estadísticas de Récords y el "Esqueleto de Récords":
   El artículo establece que la LIS en el régimen sesgado está cada vez más alineada con el "esqueleto de récords" (la secuencia de tiempos de récord).

   • El conteo medio de récords también crece linealmente: $\langle R_n(p) \rangle \sim \lambda(p)n$.
   • El coeficiente $\lambda(p)$ se explica cuantitativamente mediante la fórmula de Spitzer para la época media de la escalera ascendente (Ecuación 24), un resultado conocido para caminatas sesgadas.
   • A medida que $p \to 1$, la proporción de elementos de la LIS que son récords ($R^{LIS}_n/L_n$) y la proporción de récords utilizados en la LIS ($R^{LIS}_n/R_n$) ambas se aproximan a la unidad, indicando que la LIS se vuelve asintóticamente idéntica al esqueleto de récords.

3. El Exceso de Fluctuación ($a(p) - \lambda(p)$):
   Un hallazgo clave es la brecha no nula entre el coeficiente de la LIS $a(p)$ y el coeficiente de récords $\lambda(p)$. Esta diferencia, $a(p) - \lambda(p)$, representa la contribución de fluctuaciones no récord (excursiones locales de la caminata centrada $W_k$ entre récords) a la LIS.

   • La brecha es no monótona, anulándose en $p=1/2$ y $p \to 1$, y alcanzando un máximo de $\approx 0.1$ cerca de $p \approx 0.6$ ($\mu_p \approx 0.25$).
   • Esto indica que incluso en el régimen lineal, la LIS no es puramente un proceso de récords; incorpora una fracción significativa de pasos no récord, particularmente en derivas moderadas.

4. Transición Distribucional:
   La distribución empírica de la longitud de la LIS experimenta una transición aguda en el punto singular $p=1/2$:

   • En $p=1/2$: La distribución está sesgada a la derecha y tiene colas pesadas, consistente con una aproximación lognormal (como se observa en caminatas simétricas).
   • Para $p > 1/2$: La distribución de $L_n$ estandarizada es consistente con fluctuaciones gaussianas, apoyando una imagen de límite central para la estructura extensa tipo suma de la LIS en el régimen lineal.

5. El Límite Singular en $p=1/2$:
   El punto simétrico es un límite singular del régimen lineal.

   • La densidad de récords escala como $\lambda(\mu_p) \sim 1.39 \mu_p$ para pequeña deriva.
   • El coeficiente de la LIS $a(\mu_p)$ se anula más lentamente que linealmente. La razón $a(\mu_p)/\mu_p$ aumenta a medida que $\mu_p \to 0$.
   • El exceso de fluctuación $a(\mu_p) - \lambda(\mu_p)$ no sigue una sola ley de potencias en el rango muestreado; las pendientes locales log-log varían, sugiriendo un comportamiento complejo de capa límite que no es capturado por estimaciones ingenuas de excursiones inter-récords.

Significado y Alcance
El artículo proporciona la primera caracterización numérica de la LIS para caminatas aleatorias sesgadas, demostrando que cualquier deriva positiva altera fundamentalmente el escalado de sublineal ($\sqrt{n \log n}$) a lineal ($n$). El estudio identifica el esqueleto de récords como la estructura dominante en el régimen sesgado, pero cuantifica la contribución persistente de las fluctuaciones no récord.

Los autores declaran explícitamente que, aunque el coeficiente de récords $\lambda(p)$ es conocido analíticamente mediante la identidad de Spitzer, no existe actualmente una expresión de forma cerrada para el coeficiente de la LIS $a(p)$. El principal problema abierto identificado es la derivación de $a(p)$, lo cual requiere conciliar la estructura de renovación del esqueleto de récords con las restricciones de monotonía global que gobiernan la interpolación entre récords. El artículo concluye modestamente, señalando que la forma asintótica precisa del comportamiento de pequeña deriva permanece sin resolver y que los resultados son específicos para incrementos gaussianos de varianza finita, dejando los casos de varianza infinita (como la caminata sesgada de Cauchy) para futuras investigaciones.