Definición del sistema

Ejemplo 1 — Estudiante procrastinador

Se utiliza la matriz de transición del ejemplo del estudiante. El espacio de estados es \(S = \{E,\, P,\, D\}\) donde \(E\) = estudia, \(P\) = procrastina, \(D\) = duerme.

Matriz de transición — Estudiante procrastinador
E P D
E 0.65 0.25 0.1
P 0.35 0.45 0.2
D 0.25 0.15 0.6

Ejemplo 2 — Epidemia en el salón

Modelo SIR simplificado con estados \(S = \{\text{Sano},\, \text{Contagiado},\, \text{Recuperado}\}\). El estado Recuperado es absorbente (\(P_{RR} = 1\)).

Matriz de transición — Epidemia en el salón
S C R
S 0.75 0.25 0.0
C 0.00 0.40 0.6
R 0.00 0.00 1.0

Métodos de cómputo para \(P^n\)

Se implementan cuatro métodos para calcular la matriz de transición en \(n\) pasos:

  1. Multiplicación directa (secuencial): multiplica la matriz por sí misma \(n-1\) veces. Complejidad \(O(n \cdot k^3)\).
  2. Recursión (Chapman-Kolmogorov): construye \(P^{(n+1)} = P^{(n)} P\) de forma secuencial usando la ecuación \(P^{(n+1)}_{ij} = \sum_k P^{(n)}_{ik} P_{kj}\). Complejidad \(O(n \cdot k^3)\), pero mantiene la interpretación probabilística en cada paso.
  3. Exponenciación rápida (binaria): reduce multiplicaciones usando paridad del exponente. Complejidad \(O(\log n \cdot k^3)\).
  4. Diagonalización: descompone \(P = V D V^{-1}\) y eleva los valores propios, \(P^n = V D^n V^{-1}\). Complejidad \(O(k^3)\) tras la descomposición inicial.
# 1. Multiplicación secuencial
pow_seq <- function(P, n) {
  res <- P
  if (n == 1) return(res)
  for (i in 2:n) res <- res %*% P
  return(res)
}

# 2. Recursión (Chapman-Kolmogorov): P^(n+1) = P^(n) * P
pow_rec <- function(P, n) {
  res <- P
  if (n == 1) return(res)
  for (i in 2:n) res <- res %*% P
  return(res)
}

# 3. Exponenciación rápida
pow_fast <- function(P, n) {
  res  <- diag(nrow(P))
  base <- P
  while (n > 0) {
    if (n %% 2 == 1) res <- res %*% base
    base <- base %*% base
    n    <- n %/% 2
  }
  return(res)
}

# 4. Diagonalización
pow_diag <- function(P, n) {
  eig   <- eigen(P)
  V     <- eig$vectors
  V_inv <- solve(V)
  D_n   <- diag((eig$values)^n)
  res   <- V %*% D_n %*% V_inv
  return(Re(res))
}

Resultados computacionales

Potencias \(P^3\) y \(P^{10}\)

Ejemplo 1 — Estudiante

P^3 — Estudiante
E P D
E 0.493 0.2905 0.2165
P 0.456 0.2895 0.2545
D 0.418 0.2525 0.3295
P^10 — Estudiante (largo plazo)
E P D
E 0.4635 0.2806 0.2559
P 0.4634 0.2805 0.2561
D 0.4632 0.2804 0.2564 
## P(3)_{PE} = 0.456  -> 45.6 %

Si hoy el estudiante procrastina, la probabilidad de que en 3 días esté estudiando es 45.6 %.

Ejemplo 2 — Epidemia

P^3 — Epidemia
S C R
S 0.4219 0.2556 0.3225
C 0.0000 0.0640 0.9360
R 0.0000 0.0000 1.0000
P^10 — Epidemia (largo plazo)
S C R
S 0.0563 0.0401 0.9035
C 0.0000 0.0001 0.9999
R 0.0000 0.0000 1.0000 
## P(3)_{CR} = 0.936  -> 93.6 %

Si una persona inicia contagiada, la probabilidad de estar recuperada en 3 días es 93.6 %.

Comparación de tiempos de ejecución

La gráfica en escala logarítmica muestra que la multiplicación directa y la recursión Chapman-Kolmogorov tienen complejidad lineal en \(n\), mientras que la exponenciación rápida y la diagonalización mantienen tiempos constantes y bajos.

Tabla de benchmarking (\(n = 1000\), 500 repeticiones)

Benchmark Ejemplo 1 — Estudiante procrastinador (n = 1000)
Metodo Complejidad Tiempo prom (us) Error max abs IQR (us)
Mult. directa O(n*k^3) 386.48 1.11e-15 34.99
Recursion CK O(n*k^3) 428.11 1.11e-15 33.21
Exp. rapida O(log n * k^3) 11.10 0 (ref.) 0.90
Diagonalizacion O(k^3) 104.78 2.05e-13 7.32
Benchmark Ejemplo 2 — Epidemia en el salon (n = 1000)
Metodo Complejidad Tiempo prom (us) Error max abs IQR (us)
Mult. directa O(n*k^3) 375.23 3.33e-16 5.84
Recursion CK O(n*k^3) 375.86 3.33e-16 7.28
Exp. rapida O(log n * k^3) 10.71 0 (ref.) 0.53
Diagonalizacion O(k^3) 91.28 1.11e-16 6.68

Comportamiento de largo plazo

Distribución estacionaria \(\pi\)

La distribución estacionaria satisface \(\pi P = \pi\) con \(\sum_j \pi_j = 1\). Se obtiene como el vector propio izquierdo asociado al valor propio 1.

## Distribucion estacionaria — Estudiante (E, P, D): 0.4634 0.2805 0.2561
## Distribucion estacionaria — Epidemia   (S, C, R): 0 0 1

Para el Ejemplo 2, dado que Recuperado es absorbente, \(\pi = (0,\, 0,\, 1)\): en el largo plazo todos los individuos terminan recuperados.

Convergencia hacia \(\pi\)

El error tiende a cero rápidamente. Esto indica que, después de suficientes transiciones, la probabilidad de estar en cualquier estado converge a \(\pi\), independientemente del estado inicial.