  Loosely speaking, the Shannon entropy rate is used to gauge a stochastic
process' intrinsic randomness; the statistical complexity gives the cost of
predicting the process. We calculate, for the first time, the entropy rate and
statistical complexity of stochastic processes generated by finite unifilar
hidden semi-Markov models---memoryful, state-dependent versions of renewal
processes. Calculating these quantities requires introducing novel mathematical
objects ({\epsilon}-machines of hidden semi-Markov processes) and new
information-theoretic methods to stochastic processes.
