Paseos Aleatorios de Máxima Entropía en Z: Entornos Aleatorios y No Aleatorios

Información Básica

• ID del Artículo: 2503.15957
• Título: Maximal Entropy Random Walks in Z: Random and non-random environments
• Autores: Thibaut Duboux (Université Bourgogne Europe), Lucas Gerin (École Polytechnique), Yoann Offret (Université Bourgogne Europe)
• Clasificación: math.CO (Matemática Combinatoria), math.PR (Teoría de Probabilidad)
• Fecha de Presentación: 20 de noviembre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2503.15957

Resumen

Los paseos aleatorios de máxima entropía (MERW, por sus siglas en inglés) constituyen un proceso natural en grafos finitos, introducido hace varios años motivado por la física teórica. La construcción del proceso depende de la teoría de Perron-Frobenius de la matriz de adyacencia. La generalización a grafos infinitos resulta considerablemente sutil, y este artículo estudia en detalle el modelo MERW en la red de enteros Z con bucles, abarcando entornos tanto aleatorios como no aleatorios. Mediante representaciones combinatorias explícitas de los vectores propios de Perron-Frobenius correspondientes, los autores logran determinar con precisión el comportamiento asintótico de estos paseos. En particular, se demuestra que casi todos los MERW con bucles en Z poseen velocidad positiva.

Antecedentes de Investigación y Motivación

Contexto del Problema

1. Limitaciones del paseo aleatorio estándar: El paseo aleatorio estándar tradicional es un proceso estocástico fundamental en teoría de probabilidad, física estadística y análisis de redes, cuyas probabilidades de transición están dadas por $p_{i,j} = a_{i,j}/\sum_\ell a_{i,\ell}$. Sin embargo, este paseo no necesariamente maximiza la entropía de las trayectorias.
2. Motivación Física de MERW: MERW surge de la formulación de integrales de camino de la mecánica cuántica, con probabilidades de transición dadas por $p_{i,j} = a_{i,j}\psi_j/(\lambda\psi_i)$, donde $\psi$ es el vector propio positivo correspondiente al radio espectral $\lambda$. Esta construcción hace que MERW maximice la tasa de entropía de las trayectorias en grafos finitos.
3. Desafíos en Grafos Infinitos:
   • En grafos infinitos, la teoría de Perron-Frobenius no se aplica directamente
   • Es necesario distinguir entre casos R-recurrentes y R-transitorios
   • En el caso R-transitorio, el vector propio positivo no es único, existiendo un conjunto convexo de soluciones extremales
4. Vacío de Investigación: Aunque MERW en grafos finitos ha sido ampliamente estudiado, existe una falta de investigación sistemática en grafos infinitos, particularmente en casos con perturbaciones aleatorias.

Importancia de la Investigación

1. Significado Teórico: Conecta probabilidad combinatoria, procesos estocásticos y teoría de localización de Anderson
2. Valor Aplicado: Tiene perspectivas de aplicación en algoritmos de detección de comunidades en redes complejas
3. Contribución Metodológica: Proporciona nuevas herramientas para analizar MERW en grafos infinitos

Contribuciones Principales

El artículo realiza las siguientes contribuciones principales:

1. Representación Explícita de Vectores Propios (Teorema 2.9): Para entornos agradables, se proporciona una descripción combinatoria completamente explícita de dos vectores propios extremales $\psi^+$ y $\psi^-$:\beta_{-1}\cdots\beta_i, & i < 0\\ 1, & i = 0\\ (\beta_0\beta_1\cdots\beta_{i-1})^{-1}, & i > 0 \end{cases}$$ donde $\beta_i$ y $\alpha_i$ pueden expresarse como funciones generatrices o fracciones continuas.
2. Caracterización Completa en Entornos Deterministas (Proposiciones 2.3, 2.5):
   • Se demuestra que la matriz $A$ es R-transitoria
   • Se describe con precisión la monotonía y comportamiento límite de los vectores propios extremales
   • Se prueba que todos los MERW en entornos agradables son transitorios
3. Velocidad Lineal en Entornos Aleatorios (Teorema 3.1): Para entornos aleatorios i.i.d., los MERW extremales poseen velocidad constante positiva: $\lim_{n\to\infty} \frac{X^+_n}{n} = v > 0 \quad \text{(casi seguramente)}$ donde $v = 1/\mathbb{E}_\mu[S]$, con $S$ teniendo una expresión explícita.
4. Análisis de Acoplamiento para MERW No Extremales (Teorema 3.4): Para MERW correspondientes a vectores propios mixtos $\psi^{(\kappa)} = \kappa\psi^+ + (1-\kappa)\psi^-$, se demuestra que bajo la condición $X^{(\kappa)}_n \to +\infty$ también existe velocidad lineal $v$.
5. Cálculos Exactos para Entornos de Bernoulli (Proposición 3.6): Cuando el entorno satisface $P(w_k=M)=p$, se demuestra que: $\lim_{p\to 0} v_{p,M} = \sqrt{1-\frac{4}{(2+M)^2}} > 0$ lo que indica que la velocidad experimenta un salto discontinuo cuando $p\to 0$.
6. Contraste con Entornos Periódicos (Proposición A.1): Se demuestra que en entornos periódicos deterministas, MERW es nulo-recurrente y altamente localizado, formando un contraste marcado con entornos aleatorios.

Explicación Detallada de Métodos

Definición de la Tarea

Entrada:

• Entorno $w = (w_i)_{i\in\mathbb{Z}}$, donde $w_i \geq 0$ es el peso del bucle automático en el vértice $i$
• Matriz de adyacencia $A$ definida como: peso de arista 1 entre vértices adyacentes, peso del bucle automático en vértice $i$ igual a $w_i$

Salida:

• Radio espectral combinatorio $\lambda$
• Vector propio positivo $\lambda$ $\psi$ (satisfaciendo $A\psi = \lambda\psi$)
• Comportamiento asintótico del MERW correspondiente $(X_n)_{n\geq 0}$

Restricciones:

• El entorno es M-agradable: acotado, no idénticamente igual a $M$, y para cualquier $\varepsilon>0$ y $r\geq 0$ existe $i$ tal que $w_i,\ldots,w_{i+r}$ son todos $\geq M-\varepsilon$

Arquitectura del Método Principal

1. Cálculo del Radio Espectral Combinatorio (Lema 2.2)

Se proporciona una prueba de $\lambda = 2+M$ mediante conteo de caminos:

Estrategia de Prueba del Límite Inferior:

• Se considera el número de caminos desde $i$ que retornan a $i$ manteniéndose en o por encima de $i$, denotado $u^{i\circlearrowleft i}_r$
• Se utiliza la función generatriz $H^{[\geq i],w}_{i,i}(z) = \sum_{r\geq 0} d^{0\circlearrowleft 0}_r z^r$
• Mediante descomposición de arcos (arch-decomposition) se obtiene: $H^{[\geq i],w}_{i,i}(z) = \frac{1}{1-(M-\varepsilon)z - z^2H^{[\geq i],w}_{i,i}(z)}$
• Resolviendo se obtiene que la singularidad principal está en $z^* = (2+M-\varepsilon)^{-1}$
• Utilizando el teorema de transferencia se deduce $d^{0\circlearrowleft 0}_r \geq c(2+M-\varepsilon)^r r^{-3/2}$

2. Construcción de Vectores Propios Extremales (Proposición 2.3)

Método de Aproximación por Truncamiento:

• Para $k\leq 0$, se define $\psi^{(k,\varepsilon)}$ satisfaciendo condiciones de frontera: 0, & n\leq k-2\\ \varepsilon, & n=k-1\\ 2\varepsilon, & n=k \end{cases}$$ y satisfaciendo la relación de recurrencia $\psi_{n+1} + w_n\psi_n + \psi_{n-1} = \lambda\psi_n$
• Se ajusta $\varepsilon_k$ de modo que $\psi^{(k,\varepsilon_k)}_0 = 1$
• Mediante argumentos diagonales se obtiene una subsucesión convergente
• Se utiliza estimación de convexidad para probar $\lim_{n\to\infty}\psi^+_n = \infty$

3. Derivación de la Representación Combinatoria (Teorema 2.9)

Pasos Clave:

Se definen las funciones generatrices: $\beta_i = \frac{1}{\lambda}H^{[\leq i],w}_{i,i}\left(\frac{1}{\lambda}\right), \quad \alpha_i = \frac{1}{\lambda}H^{[\geq i],w}_{i,i}\left(\frac{1}{\lambda}\right)$

Mediante descomposición de arcos se obtienen las relaciones de recurrencia: $\beta_i = \frac{1}{\lambda - w_i - \beta_{i-1}}, \quad \alpha_i = \lambda - w_i - \frac{1}{\alpha_{i+1}}$

Esto es equivalente a la expansión en fracción continua: $\alpha_i = \cfrac{1}{\lambda - w_i - \cfrac{1}{\lambda - w_{i+1} - \cfrac{1}{\ddots}}}$

Se verifica que $\psi^+_i = \beta_{-1}\cdots\beta_i$ (cuando $i<0$) efectivamente satisface la ecuación característica.

4. Análisis de Velocidad en Entornos Aleatorios

Identificación de Cadena de Markov:

• Cuando $(w_i)$ es i.i.d., $(\beta_i)_i$ y $(\alpha_{-i})_i$ son cadenas de Markov estacionarias ergódicas
• El MERW extremal es un paseo aleatorio en entorno aleatorio ergódico

Fórmula de Velocidad (Ecuación 3.4): $v = \frac{1}{\mathbb{E}_\mu[S]}, \quad S = \sum_{n\geq 0} P^w_0(X^+_n = 0)$

Prueba de Finitud: Se utiliza el control: $\beta_i \leq 1_{\{w_i\leq M-\delta\}} g_{M-\delta}(\beta_{i-1}) + 1_{\{w_i>M-\delta\}}$

obteniéndose: $\mathbb{E}_\mu[\beta_0\beta^2_{-1}\cdots\beta^2_{-i}] \leq \mathbb{E}_\mu[Z^2_0]^i < 1$

Por lo tanto $\mathbb{E}_\mu[S] < \infty$, garantizando velocidad positiva.

Puntos de Innovación Técnica

1. Método de Función Generatriz de Caminos: Transforma el problema de vectores propios en un problema de conteo de caminos, utilizando herramientas de combinatoria analítica.
2. Técnica de Variables de Riccati: Las relaciones de recurrencia satisfechas por $\alpha_i$ y $\beta_i$ están relacionadas con las variables de Riccati en la teoría de localización de Anderson, estableciendo una conexión entre MERW y operadores de Schrödinger aleatorios.
3. Argumentos de Acoplamiento: Para MERW no extremales, se construye un acoplamiento con MERW extremales, utilizando la finitud del conjunto de "tiempos malos" para probar consistencia de velocidad.
4. Análisis de Frontera de Función Generatriz: Mediante control preciso del comportamiento de la función generatriz en la singularidad principal, se obtienen estimaciones asintóticas del número de caminos.

Configuración Experimental

Parámetros de Simulación Numérica

Aunque el artículo es principalmente teórico, incluye verificación numérica:

1. Figura 1: Simulación de MERW en entorno de Bernoulli
   • Parámetros: $M=20$, $p=0.02$ y $p=0.05$
   • 200 trayectorias independientes, pasos de tiempo $n=600$
   • Verifica que la velocidad $v_{p,M}$ es decreciente en $p$
2. Figura 3: Variación de velocidad $v_{p,M}$ con respecto a $p$
   • Simulación Monte Carlo de la fórmula (3.21)
   • Diferentes valores de $M$: $M=0.1, 1, 10$
   • Verifica el comportamiento asintótico de la Proposición 3.6
3. Figura 4: Variación de velocidad $v_{p,M}$ con respecto a $M$
   • Parámetros: $p=0.3, 0.5, 0.8$
   • Muestra que la velocidad es no monótona en $M$

Verificación Teórica

Cálculos Exactos para Entornos de Bernoulli:

• Utiliza identidades combinatorias relacionadas con números de Motzkin
• Verifica $\lim_{p\to 0} v_{p,M} = \sqrt{1-4/(2+M)^2}$
• Demuestra $v_{p,M} \sim 3(1-p)/(2+M)$ cuando $p\to 1$

Resultados Experimentales

Resultados Principales

1. Entornos Deterministas (Sección 2)

Verificación del Teorema 2.9:

• Proporciona expresiones completamente explícitas para $\psi^+$ y $\psi^-$
• Estimaciones de frontera: $\gamma \leq \alpha_i, \beta_i \leq 1$, donde $\gamma = (\lambda-\sqrt{\lambda^2-4})/2$

Ejemplo Juguete (final de la sección 2.3): Para entorno de función escalón ($w_i=M$ cuando $i\leq 0$, $w_i=0$ cuando $i\geq 1$):