Indefinitely Oscillating Martingales
This work addresses foundational questions in probability theory and statistical learning, with implications for martingale theory and model selection methods like minimum description length.
The authors constructed a class of nonnegative martingale processes that oscillate indefinitely with high probability, establishing a uniform rate for the number of oscillations that is asymptotically close to the theoretical upper bound. They applied these results to show that the limit of the minimum description length operator may not exist and to bound how often beliefs can change when observing data streams.
We construct a class of nonnegative martingale processes that oscillate indefinitely with high probability. For these processes, we state a uniform rate of the number of oscillations and show that this rate is asymptotically close to the theoretical upper bound. These bounds on probability and expectation of the number of upcrossings are compared to classical bounds from the martingale literature. We discuss two applications. First, our results imply that the limit of the minimum description length operator may not exist. Second, we give bounds on how often one can change one's belief in a given hypothesis when observing a stream of data.