Serie geométrica

Nivel FundamentalDificultad ★★★★★Concepto⌖ Ver en el mapa

¿Qué es?

$\sum_{k\ge0} r^k = \frac{1}{1 - r}$ si $|r| < 1$ . La serie que todo el mundo sabe sumar en forma cerrada, y la que hay detrás de los arrays dinámicos, las recurrencias de divide y vencerás y las recompensas descontadas del aprendizaje por refuerzo.

Intuición

Multiplica $S = 1 + r + r^2 + \dots$ por $r$ y resta: todo se cancela salvo el 1, así que $S(1 - r) = 1$ . Con $r = 1/2$ : $1 + \frac12 + \frac14 + \dots = 2$ ; el total lo dominan los primeros términos, y por eso el primer nivel de una recursión que divide por dos cuesta tanto como todo el resto.

Fórmulas

$\sum_{k=0}^{n-1} r^k = \frac{1 - r^n}{1 - r}, \qquad \sum_{k=0}^{\infty} r^k = \frac{1}{1 - r}\ \ (|r| < 1)$; $G_t = \sum_{k=0}^{\infty}\gamma^k r_{t+k} \le \frac{r_{\max}}{1 - \gamma}$
retorno descontado en aprendizaje por refuerzo

Ejemplo

Un array dinámico duplica su capacidad cuando se llena. Insertar $n$ elementos copia en total como mucho $1 + 2 + 4 + \dots + n/2 < n$ elementos: $O(1)$ amortizado por inserción. Con factor de crecimiento 1,5 la cota es $\frac{1}{1 - 2/3} = 3$ copias por elemento.

Aplicaciones en informática

Análisis de algoritmos y complejidad★★★★★fundamentalComputación científica y algoritmos
El análisis amortizado de los arrays dinámicos y los casos del teorema maestro son sumas geométricas.
Teoría de colas y rendimiento★★★★★frecuenteOptimización y sistemas
En una cola M/M/1 el número de clientes es geométrico: $P(N = n) = (1 - \rho)\rho^n$ .

Dónde aparece en IA

Aprendizaje por refuerzo★★★★★fundamentalIA y machine learning
Descontar con $\gamma < 1$ convierte el retorno infinito en una serie convergente de tipo geométrico.

¿Dónde se utiliza?

Temas de informática a los que se llega desde aquí, con la cadena de ideas que lleva a ellos:

Qué depende de él

Ejercicios

1IA

Un agente recibe recompensa 1 en cada paso para siempre, con $\gamma = 0{,}99$ . ¿Cuál es el retorno? ¿Cuál es el «horizonte efectivo»?

Solución

$\sum 0{,}99^k = \frac{1}{0{,}01} = 100$ . Las recompensas más allá de unos $\frac{1}{1-\gamma} = 100$ pasos aportan poco: el horizonte efectivo es de unos 100 pasos.