估计股票市场的算法复杂性

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Estimating the Algorithmic Complexity of Stock Markets》
---
作者：
Olivier Brandouy, Jean-Paul Delahaye, Lin Ma
---
最新提交年份：
2015
---
英文摘要：
  Randomness and regularities in Finance are usually treated in probabilistic terms. In this paper, we develop a completely different approach in using a non-probabilistic framework based on the algorithmic information theory initially developed by Kolmogorov (1965). We present some elements of this theory and show why it is particularly relevant to Finance, and potentially to other sub-fields of Economics as well. We develop a generic method to estimate the Kolmogorov complexity of numeric series. This approach is based on an iterative \"regularity erasing procedure\" implemented to use lossless compression algorithms on financial data. Examples are provided with both simulated and real-world financial time series. The contributions of this article are twofold. The first one is methodological : we show that some structural regularities, invisible with classical statistical tests, can be detected by this algorithmic method. The second one consists in illustrations on the daily Dow-Jones Index suggesting that beyond several well-known regularities, hidden structure may in this index remain to be identified.
---
中文摘要：
金融中的随机性和规律性通常用概率的术语来处理。在本文中，我们基于Kolmogorov（1965）最初开发的算法信息理论，开发了一种完全不同的方法来使用非概率框架。我们介绍了这一理论的一些要素，并说明了为什么它与金融特别相关，也可能与经济学的其他子领域相关。我们发展了一种通用的方法来估计数值序列的Kolmogorov复杂性。该方法基于一个迭代的“规则擦除过程”，该过程用于对金融数据使用无损压缩算法。模拟和真实世界的金融时间序列都提供了示例。本文的贡献有两个方面。第一个是方法论：我们证明了一些经典统计检验所看不见的结构规律，可以通过这种算法方法检测出来。第二个是每日道琼斯指数上的插图，表明除了几个众所周知的规律外，该指数中隐藏的结构可能仍有待确定。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--

---
PDF下载：
--> Estimating_the_Algorithmic_Complexity_of_Stock_Markets.pdf (2.63 MB)

2022-5-8 03:07:32 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：股票市场 股票市 复杂性 illustration Quantitative

估计股市的算法复杂性Solivier Brandouy+，Jean-Paul Delahaye，林马*+波尔多大学4号，奥利维尔。brandouy@u-波尔多。fr——里尔大学1，delahaye@lifl.fr*通讯作者，里尔大学1，林。ma@iae.univ-莉莉。金融学中的随机性和规律性通常用概率的术语来处理。在本文中，我们基于科尔莫戈罗夫（1965）最初提出的算法信息理论，开发了一种完全不同的方法来使用非概率框架。我们介绍了这一理论的一些要素，并说明了为什么它与金融特别相关，也可能与经济学的其他子领域相关。我们发展了一种通用的方法来估计数值序列的Kolmogorov复杂性。这种方法基于一种迭代的“规律性擦除程序”，该程序用于对金融数据使用无损压缩算法。模拟财务时间序列和真实财务时间序列都提供了示例。本文的贡献有两个方面。第一个是方法论：我们表明，一些经典统计测试看不见的结构规律，可以通过这种算法方法检测出来。

第二个是每日道琼斯指数上的插图，表明除了几个众所周知的规律外，该指数中的隐藏结构可能仍有待识别。关键词：Kolmogorov复杂性、回报率、效率、压缩Jel:C43、G11 8月17日提交给爱思唯尔的再版，2018Introduction考虑以下由0和1组成的字符串：A:010101010101010101010101010101010101010101010101010101010101010101010101010101101010101101010101101101010101101010101011001001001011011001011011011011011011011011011011011011011011011111000010110110110110110110110110110101010110110101010110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110111001001000011111010101000100001010110100011000100010000101010000100011010001100110001101010E:0011111001001101010000000000111100111111100111001100000010010010010010010111011011011011F:001000110000000011001001010100010111101110001111100110011001101110110010100这些序列中的一些是通过简单的数学程序生成的，其他则不是。有些表现出明显的规律性，而另一些可能只有在复杂的转换之后才能揭示“结构”。其中只有一个是由一系列随机抽取生成的。问题是“如何识别后者”？本文将介绍一种通用的方法来解决区分规则（结构化、有组织）序列和随机序列的问题。虽然这种方法可能有广泛的用途，但在这里，它适用于金融领域的规律性检测。为了说明这一观点，我们提供了使用模拟和真实财务数据的示例。结果表明，这种新方法可以揭示一些经典统计检验无法检测到的结构规律。我们的方法基于安德烈·科尔莫戈罗夫（Andrei Kolmogorov，1965）的开创性工作，他提出了非统计术语中随机序列的定义。

他的定义实际上是最普遍的定义之一，其本身就是基于图灵和戈德尔对所谓的“可计算性理论”或“递归理论”（图灵，1937；戈德尔，1931）的贡献。物理学家利用科尔莫戈罗夫的思想重新定义了熵（Zurek，1989），生物学家利用其对系统发育树进行分类（Cilibrasi和Vitanyi，2005），心理学家利用其来估计随机性控制难度（Griffith和Tenenbaum，2001）。在金融领域，科尔莫格罗夫复杂性经常被用来衡量预测未来回报的可能性。例如，Chen and Tan（1996）或Chen and Tan（1999）使用经济计量模型获得的预测误差平方和估计了股票市场的随机复杂性。Azhar、Badros、Glodjo、Kao和Reif（1994）用不同的压缩技术可以达到的最高成功预测率（SPR）衡量了股市的复杂性。Shmilovici，Kahiri，Ben Gal和Hauser（2003）以及Shmilovici，Kahiri，Ben Gal，随机复杂性的概念是由Rissanen（1986）提出的，用一类概率模型代替通用图灵机定义Kolmogorov复杂性。为了获得这个成功的预测率，作者在每一步都使用压缩算法来预测下一次收益的方向，并计算整个序列的成功预测率。Hauser（2009）使用可变阶马尔可夫模型（VOM，上下文预测压缩工具的变体）预测财务回报的方向。他们发现，从财务数据中获得的SPR与从随机字符串中获得的SPR之间存在显著差异。

为了在这一结果和有效市场假说（EMH）之间建立正式联系，作者还在外汇时间序列上模拟了基于VOM的交易规则，并得出结论，不存在异常交易。利用另一种压缩技术，Silva、Matsu*****a和Giglio（2008）和Giglio、Matsu*****a、Figueiredo、Gleria，Da Silva（2008）根据LZ指数对世界各地的股票市场进行了排名，该指数显示了Lempeland Ziv（1976）提出的压缩算法对财务回报的影响程度。尽管这些先锋作品开拓了人们的视野，但上述文献中有两个主要的局限性可以突显出来：1。从理论角度来看，概率框架和算法框架之间的边界尚未明确确定。算法复杂性的一个优点是，它一次处理一个给定的字符串，而不一定是由给定的随机过程生成的概率字符串的总体。因此，当使用算法复杂性时，不需要概率假设。对成功预测率的估计似乎表明，价格运动遵循一定的分布规律。尽管使用了压缩工具，但这项技术重新引入了概率框架。然后削弱了算法复杂性理论提出的一般非概率框架。2.席尔瓦、松下和吉利奥（2008）和吉利奥、松下、菲盖雷多、格利亚和达席尔瓦（2008）的情况并非如此。然而，这些论文中使用的离散化技术仍有待讨论。实际上，财务回报通常以实数表示，而压缩工具只处理整数。

因此，无论使用何种压缩工具，将实数序列转换为离散数列的离散化过程始终是必要的。为了满足这一要求，Shmilovici、Kahiri、Ben Gal和Hauser（2003年）或Shmilovici、Kahiri、Ben Gal和Hauser（2009年），以及Silva、Matsu*****a和Giglio（2008年）或Giglio、Matsu*****a、Figueiredo、Gleria和Da Silva（2008年）提议将财务回报转化为三个信号：“正”、“负”或“稳定”回报。毫无疑问，这种根本性的变化导致了原始财务系列信息的严重丢失。正如Shmilovici、Kahiri、Ben Gal和Hauser（2009）所说，“VOM模型的主要局限性在于它忽略了预期回报的实际值（Shmilovici、Kahiri、Ben Gal和Hauser，2009）。”例如，连续收益计算为连续价格之间比率的对数：rt=log（pt+1）- 日志（pt）。在金融领域引入算法复杂性可能会产生更广泛的影响。例如，Dionisio、Menezes和Mendes（2007）声称，复杂性的概念可以成为衡量金融风险的一种手段，作为“风险价值”或“标准差”的替代品，这可能对投资组合管理产生普遍影响（参见Groth and Muntermann（2011），了解这种意义上的应用）。鉴于这两点，为价格运动建立一个通用算法框架似乎很有趣。我们提出了一种经验方法，允许使用算法工具处理金融时间序列，避免过度离散化问题。该方法基于Brandouy和Delahaye（2005）的初步调查，其想法是由Ma（2010）在处理现实世界的财务数据方面提出的。

在同一个框架中，Zenil和Delahaye（2011）促进了科尔莫戈罗夫复杂性在金融领域的未来应用。使用算法方法，我们证明了道琼斯工业指数的日收益率具有相对较高的Komogorov复杂性，尤其是在删除了最有记录的程式化事实（2001年）之后。这一结果支持Fama（1970）的有效市场假说，该假说证明了超越市场的可能性。本文组织如下：第一部分正式介绍了科尔莫戈罗夫复杂性，并对这一概念进行了初步说明。第二部分提出了一种估计数值序列Kolmogorov复杂性的通用方法。然后，在第三部分中，我们展示了一些传统统计测试难以检测到的规律性，可以通过压缩算法识别出来。最后一节专门介绍我们的真实金融数据分析技术的兴趣和局限性。在我们正式介绍科尔莫戈罗夫复杂性之前，读者可能对我们最初问题的解决方案感兴趣：“如何在序列A、B、C、D、E和F中识别随机生成的序列？”前四个序列（或字符串）在科尔莫戈罗夫意义上很简单，因为它们可以用以下规则来描述：o显然，A是“01”的40次重复B是所谓的“Thue-Morse”序列（见Allouche和Cosnard（2000）），其迭代生成如下：1。初始数字为0.2。“0”（resp.1）的否定是“1”（resp.0）。要以递归方式生成B，请获取现有数字，并在右侧添加其否定：–步骤1：“0”←“1” => “01”-第2步：“01”←“10” => “0110”-第3步：“0110”←“1001” => “01101001”-第4步：“01101001”←“10010110” => “0110100110010110”– ...o C是以2为基数的自然数的串联：0、1、10、11、100101、110、11、1000。。。。

它被称为“Champernowne（1933）常数”D是通过将π的小数转换成二进制数字而产生的。这些生成规则使得A、B、C和D可以通过相应的算法进行压缩。对于D，常用的压缩工具可能会证明是无效的，但在利用著名常数的生成函数时，编写π压缩算法很容易。E是从一个统一的定律中得出的，该定律以50%的概率给出1或0。最后一个序列（F）对应于1987年10月7日至1987年27月10日收盘时观察到的道琼斯工业指数的日变化，其中“0”表示下跌，“1”表示上涨。我们可以在这里质疑F在多大程度上与前四个字符串相似，以及无损压缩算法可以在多大程度上区分它们。这个问题在本文中起到了抛砖引玉的作用，试图为金融动力学中的随机性提供一种新的考虑。1.规律性、随机性和科尔莫戈罗夫复杂性我们从金融学中对随机性的传统解释开始，以便将其与可计算性理论中的相应解释进行对比。然后，我们明确提出“科尔莫戈罗夫复杂性”的概念，并用模拟数据说明其经验应用。1.1. 概率随机性与算法随机性传统上，金融价格运动被建模（现在仍然建模）为随机游动（见等式1）：（1）pt=pt-1+ε在这个等式中，Pt代表一种特定证券在“t”处的价格，ε是从某一分布规律中得出的随机项。这种随机项通常是由高斯噪声估计的，尽管它不能正确地表示一些典型的事实，例如绝对收益的时间依赖性或波动性的自相关性（参见Mandelbrot and Ness（1968）或Fama（1965））。

波动率模型（例如，参见GARCH模型）考虑了几个程式化事实，而其他一些则很少在金融工程中使用（例如，多尺度定律Calvet和Fisher（2002），收益季节性·）。从这个意义上说，金融工程提出了一个迭代过程，逐步提高金融时间序列模型的质量，无论是在描述还是预测方面。至少从理论的角度来看，这个迭代过程最终应该提供一个完美的确定性模型。如果这最后阶段象征着对价格动态的完美理解，那么这一方向上的每一步都可以被视为我们对金融时间序列知识的进步。如果对后者的理解不完善，迭代过程将在确定性模型之前的某个地方停止。同时，无论我们在这个过程中停留在哪里，最终的统计模型都是长期金融时间序列（数百或数千次观察）的“压缩表达式”（一些符号和参数）。“理解就是压缩”实际上是Kolmogorov complexity（Kolmogorov，1965）的主要思想，其定义正式介绍如下：定义1.1。让我们表示一个由{0，1}中的数字组成的有限二进制字符串。它的Kolmogorovcomplexity K（s）是生成（或打印）s的最短程序P的长度。在这里，P的长度取决于它在所谓的“通用语言”中的二进制表达式。这些过程对应于连续环境中的所谓“布朗运动”。

在本文中，由于现实世界中的金融数据总是离散的，算法工具只处理离散序列，我们的理论发展将处于离散框架中。到目前为止，关于εt序列背后的驱动规律，金融科学界尚未达成共识。广义自回归条件异方差模型，Bollerslev（1986）。很明显，“描述”是工作中比较容易的部分，而预测要复杂得多。由于我们对金融时间序列的理解不完善，目前这根本不可能。通用语言是一种编程语言，人们可以用它编写所有“可计算函数”。“可计算性”作为随机性的一般指标，给定字符串的科尔莫戈罗夫复杂性应该与通用语言的选择相对稳定。这种稳定性表现在以下定理中（参见Kolmogorov（1965）或Li和Vit\'anyi（1997）的完整证明），根据该定理，通用语言的变化总是对字符串的Kolmogorov复杂性有一定的影响。定理1.2。设KL（s）和KL（s）分别表示用两种不同的通用语言L测量的字符串s的Kolmogorov复杂性。KL（s）和KL（s）之间的差异始终是一个常数c，它完全独立于s：（2）C吉隆坡（s）- 吉隆坡（s）|≤ 根据这个不变性定理，在科尔莫戈罗夫复杂度估计中，不需要太注意通用语言的选择，因为它的内在价值（取决于部分）在使用的编程技术方面保持稳定。除了不变性定理之外，科尔莫戈罗夫复杂性的另一个特性，即inKolmogorov（1965年）首次证明的特性，使其成为一个很好的随机性度量：有限字符串的科尔莫戈罗夫复杂性总是取有限值。定理1.3。