Growth of the number of distinct places under preferential allocation

Under Polya (Dirichlet-process) allocation with concentration \(M\), the \(i\)-th event lands on a new place with probability \(M/(M+i-1)\), so the expected number of distinct places after \(n\) events is \(M\sum_{i<n} 1/(M+i)\), squeezed between \(M\log((M+n)/M)\) and \(1 + M\log((M+n-1)/M)\) (Research.P7.expectedDistinct_bounds): logarithmic growth. A series of repeat victimisations whose count of distinct addresses grows polynomially is not a concentration-only (Polya) process. The function reports the observed growth curve, the concentration that matches the final count, the proved envelope for that concentration, and a log-log slope of the observed curve as the discriminating diagnostic.

Usage

morie_concentration_distinct_growth(place)

Arguments

place

Vector of place identifiers in event order.

Value

A list with n, distinct (observed count after each event), M_hat (concentration matching the final count), expected (Polya expectation curve at M_hat), lower, upper (the proved envelope), loglog_slope (slope of log distinct on log n over the second half of the series; near 0 for logarithmic growth, near a positive constant for a power law) and theorems.

Examples

set.seed(1)
place <- integer(500); k <- 0
for (i in seq_along(place)) {
  if (runif(1) < 5 / (5 + i - 1)) {
    k <- k + 1
    place[i] <- k
  } else {
    place[i] <- place[sample(i - 1, 1)]
  }
}
g <- morie_concentration_distinct_growth(place)
c(M_hat = g$M_hat, slope = g$loglog_slope)
#>    M_hat    slope 
#> 3.522442 0.104588