Horizon-Independent Inference from Sparse Markov Observations

We study horizon-independent inference: maximum-likelihood estimation of monotone degrading Markov systems from sparse $n$-step observations whose computational cost is independent of the maximum observation horizon $N$. This is a challenging regime: multi-step probabilities are complex functions of the parameters, making likelihood optimization intractable as $N$ grows under standard formulations. We exploit the monotone bidiagonal structure to derive a parameterized diagonalization $\bar{P}(\vec{p})=U(\vec{p})D(\vec{p})V(\vec{p})$ whose factors are closed-form in the $T-1$ unknown stay-probabilities ($T$ is the sink state), enabling each $n$-step entry ${\bar{P}}_{x,y}^n(\vec{p})$ to be evaluated in $O(T)$ time with algebraically exact analytic gradients — reducing total cost from $O(T^{2}N)$ to $O(T^2+TH)$, where $H$ is the number of distinct observed tuples. While the strongest baseline fails beyond $N=500$, BDS scales to $N=100,000$ in single-digit seconds. Synthetic evaluations show below $1\%$ MAPE with a few thousand observations; real-world results confirm interpretable recovery and competitive predictive accuracy.