Fractal structures in Adversarial Prediction
This work addresses the problem of understanding fractal behavior in adversarial settings for researchers in theoretical computer science or game theory, but it appears incremental as it builds on prior suggestions about fractals in financial markets.
The paper tackles the problem of how fractal-like processes emerge in an adversarial prediction game, where an adversary generates a sequence of bits to minimize an algorithm's predictive payoff, and it proves that such fractal distributions arise naturally from the adversary's optimization, with optimal trade-offs between predictability and expected deviation.
Fractals are self-similar recursive structures that have been used in modeling several real world processes. In this work we study how "fractal-like" processes arise in a prediction game where an adversary is generating a sequence of bits and an algorithm is trying to predict them. We will see that under a certain formalization of the predictive payoff for the algorithm it is most optimal for the adversary to produce a fractal-like sequence to minimize the algorithm's ability to predict. Indeed it has been suggested before that financial markets exhibit a fractal-like behavior. We prove that a fractal-like distribution arises naturally out of an optimization from the adversary's perspective. In addition, we give optimal trade-offs between predictability and expected deviation (i.e. sum of bits) for our formalization of predictive payoff. This result is motivated by the observation that several time series data exhibit higher deviations than expected for a completely random walk.