# How many states in a movement HMM?
# https://tidyecology.com/posts/choosing-hmm-state-number/
#
# The R code of this Tidy Ecology tutorial, chunk by chunk, in the order of the post.
# Run it top to bottom in a fresh R session. Code the post shows but does not run
# is commented out. The prose, and the numbers it quotes, are in the post itself.
# Post last modified: 2026-10-08

## ---- setup ----
library(ggplot2)
library(dplyr)
library(tidyr)

pal <- list(ink = "#16241d", body = "#2c3a31", forest = "#275139", label = "#46604a",
            sage = "#93a87f", paper = "#f5f4ee", line = "#dad9ca", faint = "#5d6b61")
st3 <- c("#cda23f", "#b5534e", "#275139")
theme_te <- function(base_size = 12) {
  theme_minimal(base_size = base_size) +
    theme(plot.background = element_rect(fill = pal$paper, colour = NA),
          panel.background = element_rect(fill = pal$paper, colour = NA),
          panel.grid.major = element_line(colour = pal$line, linewidth = 0.3),
          panel.grid.minor = element_blank(),
          axis.text = element_text(colour = pal$faint), axis.title = element_text(colour = pal$body),
          plot.title = element_text(colour = pal$ink, face = "bold"),
          plot.subtitle = element_text(colour = pal$label),
          strip.text = element_text(colour = pal$ink, face = "bold"),
          legend.text = element_text(colour = pal$body), legend.position = "top")
}

dvm <- function(theta, mu, kappa) exp(kappa * cos(theta - mu)) / (2 * pi * besselI(kappa, 0))
rvm <- function(n, mu, kappa) {
  mu <- rep(mu, length.out = n); kappa <- rep(kappa, length.out = n); out <- numeric(n)
  for (i in 1:n) {
    k <- kappa[i]; a <- 1 + sqrt(1 + 4 * k^2); b <- (a - sqrt(2 * a)) / (2 * k); r <- (1 + b^2) / (2 * b)
    repeat {
      u1 <- runif(1); u2 <- runif(1); u3 <- runif(1)
      z <- cos(pi * u1); f <- (1 + r * z) / (r + z); cc <- k * (r - f)
      if (cc * (2 - cc) - u2 > 0 || log(cc / u2) + 1 - cc >= 0) { out[i] <- sign(u3 - 0.5) * acos(f) + mu[i]; break }
    }
  }
  ((out + pi) %% (2 * pi)) - pi
}
mkGamma <- function(eta, N) {
  G <- diag(N); if (N == 1) return(G); idx <- 1
  for (i in 1:N) { e <- numeric(N)
    for (j in setdiff(1:N, i)) { e[j] <- eta[idx]; idx <- idx + 1 }
    num <- exp(e); G[i, ] <- num / sum(num) }
  G
}
w2n_gen <- function(w, N) {
  ntr <- N * (N - 1); eta <- if (ntr > 0) w[1:ntr] else numeric(0); rest <- w[(ntr + 1):length(w)]
  list(Gamma = mkGamma(eta, N), shape = exp(rest[1:N]),
       scale = exp(rest[(N + 1):(2 * N)]), kappa = exp(rest[(2 * N + 1):(3 * N)]))
}
statdist <- function(G) { N <- nrow(G); if (N == 1) return(1); solve(t(diag(N) - G + 1), rep(1, N)) }
allprobs_gen <- function(p, step, turn, N) {
  Tn <- length(step); ap <- matrix(1, Tn, N)
  for (j in 1:N) ap[, j] <- dgamma(step, shape = p$shape[j], scale = p$scale[j]) *
    ifelse(is.na(turn), 1, dvm(turn, 0, p$kappa[j]))
  ap
}
nll_gen <- function(w, step, turn, N) {
  p <- w2n_gen(w, N); Tn <- length(step); ap <- allprobs_gen(p, step, turn, N)
  if (any(!is.finite(ap))) return(1e10)
  if (N == 1) return(-sum(log(pmax(ap[, 1], 1e-300))))
  delta <- tryCatch(statdist(p$Gamma), error = function(e) rep(1 / N, N))
  foo <- delta * ap[1, ]; s <- sum(foo); if (s <= 0) return(1e10); ls <- log(s); foo <- foo / s
  for (t in 2:Tn) { foo <- (foo %*% p$Gamma) * ap[t, ]; s <- sum(foo); if (s <= 0) return(1e10); ls <- ls + log(s); foo <- foo / s }
  -ls
}
npar_hmm <- function(N) N * (N - 1) + 3 * N
emis_start <- function(step, N) {
  qs <- quantile(step, probs = seq(0, 1, length.out = N + 1)); sh <- sc <- ka <- numeric(N)
  for (j in 1:N) { grp <- step[step >= qs[j] & step <= qs[j + 1]]
    m <- mean(grp); v <- var(grp); sh[j] <- max(m^2 / v, 0.3); sc[j] <- v / m; ka[j] <- 1 }
  c(log(sh), log(sc), log(ka))
}

## ---- simulate ----
Gamma_true <- matrix(c(0.90, 0.10, 0.15, 0.85), 2, 2, byrow = TRUE)
shape_true <- c(2, 4); scale_true <- c(20, 50); kappa_true <- c(0.7, 3.0); Tn <- 500
delta_true <- solve(t(diag(2) - Gamma_true + 1), rep(1, 2))
set.seed(4517)
S <- integer(Tn); S[1] <- sample(1:2, 1, prob = delta_true)
for (t in 2:Tn) S[t] <- sample(1:2, 1, prob = Gamma_true[S[t - 1], ])
step <- rgamma(Tn, shape = shape_true[S], scale = scale_true[S])
phi <- rvm(Tn, 0, kappa_true[S]); turn <- phi; turn[1] <- NA   # same RNG stream as the foundation post

## ---- fit ----
min_sd <- 5   # metres: a state with a smaller step-length sd has collapsed onto a handful of steps
proper <- function(w, N) { p <- w2n_gen(w, N); all(sqrt(p$shape) * p$scale >= min_sd) }
# best proper four-state fit from a separate, much longer search with widely scattered starts
# (working scale, as read by w2n_gen); the jittered starts rarely reach its basin
w4_stored <- c(-3.85, -4.60, -2.28, -2.40, 0.63, -28.07, 36.29, 37.44, 37.40, -1.82, -3.70, -25.59,
               0.57, 3.59, 5.33, 1.22, 3.21, 1.57, 0.21, 4.08, -0.45, 2.90, 1.07, 1.04)
multistart <- function(N, nstart, seed, nm_maxit = 1500, extra = list()) {
  set.seed(seed); vals <- numeric(0); ok <- logical(0); stored <- logical(0); bestf <- NULL
  for (s in 1:(nstart + length(extra))) {
    jit <- if (s == 1) 0 else 0.7
    w0 <- if (s > nstart) extra[[s - nstart]] else
      c(if (N > 1) rep(-1.5, N * (N - 1)) + rnorm(N * (N - 1), 0, jit) else numeric(0),
        emis_start(step, N) + rnorm(3 * N, 0, jit))
    f <- try(optim(w0, nll_gen, step = step, turn = turn, N = N, method = "Nelder-Mead",
                   control = list(maxit = nm_maxit, reltol = 1e-11)), silent = TRUE)
    if (inherits(f, "try-error")) next
    fp <- try(optim(f$par, nll_gen, step = step, turn = turn, N = N, method = "BFGS",
                    control = list(maxit = 200, reltol = 1e-12)), silent = TRUE)
    if (!inherits(fp, "try-error") && fp$value < f$value) f <- fp
    vals <- c(vals, f$value); ok <- c(ok, proper(f$par, N)); stored <- c(stored, s > nstart)
    if (proper(f$par, N) && (is.null(bestf) || f$value < bestf$value)) bestf <- f
  }
  list(vals = vals, ok = ok, stored = stored, fit = bestf)
}
plan <- list(c(N = 1, ns = 3, sd = 511), c(N = 2, ns = 5, sd = 512),
             c(N = 3, ns = 40, sd = 513), c(N = 4, ns = 30, sd = 514))
tab <- data.frame(); fits <- list(); ls3 <- NULL
for (pl in plan) {
  m <- multistart(pl["N"], pl["ns"], pl["sd"], extra = if (pl["N"] == 4) list(w4_stored) else list())
  f <- m$fit; N <- pl["N"]; k <- npar_hmm(N)
  fits[[N]] <- f; if (N == 3) ls3 <- m$vals
  if (N == 4) { n4jit <- sum(!m$stored); jit4 <- min(m$vals[!m$stored & m$ok]) }
  tab <- rbind(tab, data.frame(states = N, npar = k, logLik = round(-f$value, 2),
                               AIC = round(2 * f$value + 2 * k, 2),
                               BIC = round(2 * f$value + k * log(Tn), 2), conv = f$convergence))
}
tab$dAIC <- round(tab$AIC - min(tab$AIC), 2); tab$dBIC <- round(tab$BIC - min(tab$BIC), 2)

## ---- table ----
knitr::kable(tab, align = "r", row.names = FALSE, caption = "Movement HMMs with one to four states; each row is the best fit with no collapsed state.")

## ---- fig-ic ----
lng <- tab %>% select(states, AIC, BIC) %>% pivot_longer(-states, names_to = "criterion", values_to = "value")
best <- data.frame(criterion = c("AIC", "BIC"),
                   states = c(tab$states[which.min(tab$AIC)], tab$states[which.min(tab$BIC)]),
                   value = c(min(tab$AIC), min(tab$BIC)))
ggplot(lng, aes(states, value, colour = criterion)) +
  geom_line(linewidth = 0.8) + geom_point(size = 2.4) +
  geom_point(data = best, shape = 21, size = 4.5, stroke = 1.1, fill = NA) +
  scale_colour_manual(values = c(AIC = "#275139", BIC = "#b5534e"), name = NULL) +
  scale_x_continuous(breaks = 1:4) +
  labs(title = "Model selection across state numbers",
       subtitle = "Open circles mark the lowest point of each criterion",
       x = "Number of states", y = "Information criterion") + theme_te()

## ---- inspect ----
p2 <- w2n_gen(fits[[2]]$par, 2); m2 <- p2$shape * p2$scale; o2 <- order(m2)
p3 <- w2n_gen(fits[[3]]$par, 3); m3 <- p3$shape * p3$scale; o3 <- order(m3)

## ---- fig-split ----
gx <- seq(0, 620, length.out = 400)
dl2 <- statdist(p2$Gamma); dl3 <- statdist(p3$Gamma)
lab2 <- c("State 1", "State 2"); lab3 <- c("State 1", "State 2", "State 3")
c2 <- do.call(rbind, lapply(seq_along(o2), function(k) { j <- o2[k]
  data.frame(x = gx, dens = dl2[j] * dgamma(gx, p2$shape[j], scale = p2$scale[j]), state = lab2[k], model = "Two states") }))
c3 <- do.call(rbind, lapply(seq_along(o3), function(k) { j <- o3[k]
  data.frame(x = gx, dens = dl3[j] * dgamma(gx, p3$shape[j], scale = p3$scale[j]), state = lab3[k], model = "Three states") }))
cc <- rbind(c2, c3); cc$model <- factor(cc$model, levels = c("Two states", "Three states"))
hh <- rbind(data.frame(step = step, model = "Two states"), data.frame(step = step, model = "Three states"))
hh$model <- factor(hh$model, levels = c("Two states", "Three states"))
ggplot() +
  geom_histogram(data = hh, aes(step, after_stat(density)), bins = 45, fill = pal$sage, alpha = 0.3) +
  geom_line(data = cc, aes(x, dens, colour = state), linewidth = 0.9) +
  facet_wrap(~model) + scale_colour_manual(values = st3, name = NULL) +
  labs(title = "Fitted step-length densities, two states and three",
       subtitle = "The same histogram of steps under each model",
       x = "Step length (m)", y = "Density") + theme_te()
