The following learning problem arises naturally in various applications: Given a finite sample from a categorical or count time series, can we learn a function of the sample that (nearly) maximizes the probability of correctly guessing the values of a given portion of the data using the values from the remaining parts? Unlike classical approaches in statistical inference, our approach avoids explicitly estimating the conditional probabilities. We propose a non-parametric guessing function with a learning rate independent of the alphabet size. Our analysis focuses on a broad class of time series models that encompasses finite-order Markov chains, some hidden Markov chains, Poisson regression for count processes, and one-dimensional Gibbs measures. We provide a margin condition that controls the rate of convergence for the risk. Additionally, we establish a minimax lower bound for the convergence rate of the risk associated with our guessing problem. This lower bound matches the upper bound achieved by our estimator up to a logarithmic factor, demonstrating its near-optimality.

We consider a stochastic process and a given n-string. We study the shortest possible return time (or shortest return path) of the string over all the realizations of process starting from this string. For a β-mixing process having complete grammar, and for each size n of the strings, we approximate the distribution of this short return (properly re-scaled) by a non-degenerated distribution. Under mild conditions on the β coefficients, we prove the existence of the limit of this distribution to a non-degenerated distribution. We also prove that ergodicity is not enough to guaranty this convergence. Finally, we present a connection between the shortest return and the Shannon entropy, showing that maximum of the re-scaled variables grow as the matching function of Wyner and Ziv.