Fractal Structures in Adversarial Prediction
Pages 75 - 84
Abstract
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 [FP98, Man05]. 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.
References
[1]
J. Abernethy, R.M. Frongillo, and A. Wibisono. Minimax option pricing meets black-scholes in the limit. In Proceedings of the 44th symposium on Theory of Computing, pages 1029--1040. ACM, 2012.
[2]
E. Bayraktar, H.V. Poor, and K.R. Sircar. Estimating the fractal dimension of the s&p 500 index using wavelet analysis. International Journal of Theoretical and Applied Finance, 7(05):615--643, 2004.
[3]
F. Black and M. Scholes. The pricing of options and corporate liabilities. The journal of political economy, pages 637--654, 1973.
[4]
B.O. Bradley and M.S. Taqqu. Financial risk and heavy tails. Handbook of Heavy-Tailed Distributions in Finance, pages 35--103, 2003.
[5]
T. Cover. Behaviour of sequential predictors of binary sequences. Transactions of the Fourth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes, 1965.
[6]
P. DeMarzo, I. Kremer, and Y. Mansour. Online trading algorithms and robust option pricing. 2006.
[7]
P. Davy, A. Sornette, and D. Sornette. Some consequences of a proposed fractal nature of continental faulting. Nature, 348(6296):56--58, 1990.
[8]
Kenneth Falconer. Front matter. Fractal Geometry: Mathematical Foundations and Applications, Second Edition, pages i--xxvii.
[9]
A.J. Frost and R.R. Prechter. Elliott wave principle: key to market behavior. Bookworld Services, 1998.
[10]
G. Gripenberg and I. Norros. On the prediction of fractional brownian motion. Journal of Applied Probability, pages 400--410, 1996.
[11]
N. Littlestone and M.K. Warmuth. The weighted majority algorithm. FOCS, 1989.
[12]
B. Mandelbrot. Fractals and Chaos: the Mandelbrot set and beyond, volume 3. Springer, 2004.
[13]
B.B. Mandelbrot. The inescapable need for fractal tools in finance. Annals of Finance, 1(2):193--195, 2005.
[14]
B.B. Mandelbrot, D.E. Passoja, and A.J. Paullay. Fractal character of fracture surfaces of metals. 1984.
[15]
B.B. Mandelbrot and J.W. Van Ness. Fractional brownian motions, fractional noises and applications. SIAM review, 10(4):422--437, 1968.
[16]
J. Nolan. Stable distributions: models for heavy-tailed data. Birkhauser, 2003.
[17]
I. Norros. On the use of fractional brownian motion in the theory of connectionless networks. Selected Areas in Communications, IEEE Journal on, 13(6):953--962, 1995.
[18]
D. Nualart Rodón. Fractional brownian motion: stochastic calculus and applications. In Proceedings oh the International Congress of Mathematicians: Madrid, August 22--30, 2006: invited lectures, pages 1541--1562, 2006.
[19]
Rina Panigrahy and Preyas Popat. Fractal structures in adversarial prediction. CoRR, abs/1304.7576, 2013.
[20]
S.T. Rachev, C. Menn, F.J. Fabozzi, et al. Fat-tailed and skewed asset return distributions: Implications for risk management, portfolio selection, and option pricing, volume 139. Wiley, 2005.
[21]
L.C.G. Rogers. Arbitrage with fractional brownian motion. Mathematical Finance, 7(1):95--105, 2002.
[22]
G. Shafer and V. Vovk. Probability and finance: it's only a game!, volume 373. Wiley-Interscience.
[23]
T. Sottinen and E. Valkeila. On arbitrage and replication in the fractional black-scholes pricing model. Statistics & Decisions/International mathematical Journal for stochastic methods and models, 21(2/2003):93--108, 2003.
[24]
J. Voit. The statistical mechanics of financial markets. Springer, 2005.
Index Terms
- Fractal Structures in Adversarial Prediction
Recommendations
A comparison of fractal dimension estimators based on multiple surface generation algorithms
Fractal geometry has been actively researched in a variety of disciplines. The essential concept of fractal analysis is fractal dimension. It is easy to compute the fractal dimension of truly self-similar objects. Difficulties arise, however, when we ...
Application of chaos and fractal models to water quality time series prediction
This paper established a global chaos model to predict water quality time series that comprised a small amount of data, and the reducing-dimension chaos method was put forward to improve calculation of the global chaos method. Furthermore, sectioned ...
Adversarial Attacks on Deep Neural Networks for Time Series Prediction
ICICSE 2021: 2021 10th International Conference on Internet Computing for Science and EngineeringTime series data is widespread in real-world scenarios. To recover and infer missing information in practical domains, such as stock price monitoring, electricity load forecasting, traffic flows analysis, climate trend prediction, etc., the problem of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2015 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 January 2015
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ITCS'15
Sponsor:
Acceptance Rates
ITCS '15 Paper Acceptance Rate 45 of 159 submissions, 28%;
Overall Acceptance Rate 172 of 513 submissions, 34%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 88Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in