  Predicting the near-future delay with accuracy for trains is momentous for
railway operations and passengers' traveling experience. This work aims to
design prediction models for train delays based on Netherlands Railway data. We
first develop a chi-square test to show that the delay evolution over stations
follows a first-order Markov chain. We then propose a delay prediction model
based on non-homogeneous Markov chains. To deal with the sparsity of the
transition matrices of the Markov chains, we propose a novel matrix recovery
approach that relies on Gaussian kernel density estimation. Our numerical tests
show that this recovery approach outperforms other heuristic approaches in
prediction accuracy. The Markov chain model we propose also shows to be better
than other widely-used time series models with respect to both interpretability
and prediction accuracy. Moreover, our proposed model does not require a
complicated training process, which is capable of handling large-scale
forecasting problems.
