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

图2给出了数据的一般描述。正如我们在表1、表2和表3中看到的那样，统计测试没有检测到正态分布序列中的任何特定结构。为了检查算法方法的性能，我们在模拟数据上实现了压缩工具。正如上一节所解释的，在使用压缩算法之前，我们应该图2：从标准正态分布模拟的收益序列和与模拟收益对应的价格运动。左上：模拟收益的直方图。中间价：模拟收益产生的价格序列，初始价格为100。底部：模拟收益的时间序列图。表1：模拟返回标准值的单位根检验统计顺序p值ADF-32.7479***31 0.01页-178.52949***16 0.01H：模拟序列有一个单位根。表2：模拟返回序列的自相关检验χ- 方形自由度。p值基线0.1838 1 0.66836.9157 36 0.4264H：模拟序列为i.i.d。。表3:BDS模拟收益测试，m={2,3}ε0.50121.002 1.50352.0047m=2-0.2082-0.2987-0.5232-0.7221p-value 0.8351 0.7651 0.6009 0.4702m=30.8351 0.7651 0.6009 0.4702p-value 0.9503 0.9803 0.9344 0.8600H：模拟系列为i.d。。首先将模拟实数返回值转换为整数（离散化）。换句话说，我们必须为每个返回值关联一个范围从0到255的整数，“0”和“255”分别对应于模拟数据的下限和上限。在这里，0到255之间的每个整数必须代表一个实数范围，而不是“一对一”对应关系。

与每个整数（用e表示）相关的区间大小固定如下：（5）e=（M- m） /256其中m和m代表模拟收益的上下限。假设e的值，我们可以将整个范围[m，m]划分为256个区间，并将每个返回值（用x表示）与满足：（6）x的整数k相关联∈ [m+（k- 1） ×e，m+k×e[换句话说，将256个“e大小”区间按升序排序后，k是包含x的区间的秩。当k从0到255变化时，它应该用8位编码，因为2=256。值得注意的是，在将实数集[m，m]划分为256个相同的子集时，我们将在标准正态分布曲线下获得x轴上的一系列规则界，如图3（a）所示。使用这种离散化方法，我们获得正态分布整数：接近128的值是（a）规则边界（b）相同概率图3：数据离散化：如何设置边界？比接近0或255的频率要高得多。高效的压缩算法将检测这种规律性并压缩离散数据。然而，这种基于正常规律的压缩对财务回报分析没有什么意义。

根据REP的说法，正态分布应该从模拟数据中删除，以展示更多的序列结构。为此，我们提出了第二个离散化过程，该过程将提供均匀分布的积分，而不是正态分布的积分。在第二个过程中，主要思想保持不变：实数返回可以离散化，将整个区间[m，m]离散为256个子集，然后与包含x的子集中的每个返回x关联。在这里，可以选择2的幂，其大小足以保留初始序列中的所有必要信息。这是可能的，因为初始数据的精度有限。然而，这一次，我们将用正态分布的概率面被分成相等部分的方式来确定分离边界，而不是得到大小相等的子集（c.f.图3（b））。更准确地说，我们想要定义257个实数界，用borne（0）、borne（2）和。。。，borne（256），以确保从N（0，1）中提取的每个值在每个间隔[borne（i），borne（i+1）]中具有相同的概率（1/256）。这样定义的子集大小不同：如图3（b）所示，子集越接近于零，它就越小。图3（b）中描述的离散化过程用于模拟收益。离散化收益如图D.9所示。图中的ITH点代表与ITH回报相关的整数。可以注意到，离散化收益的曲线图相对均匀，没有任何特别密集或稀疏的区域（见附录D中的图）。这种快速目视检查证实了离散化收益的均匀分布。当无损压缩算法用于从uniformlydiscretized returns（c.f。

附录D中的图D.10），这些算法工具被证明是有效的（c.f.表4）。表4：压缩测试算法文件大小压缩率32000%Huffman 32502-1.57%Gzip 32073-0.23%PAQ8o8 32118-0.37%解释：离散化的回报似乎是不可压缩的。这个例子清楚地表明，正态分布的回报可以转换成一个均匀分布的整数字符串，其长度完全不可被无损压缩工具缩减。我们可以从这个实验中发现，初始序列的Kolmogorov复杂性接近其长度。根据标准正态律模拟的数据，我们表明统计方法和算法方法在随机字符串上给出了相同的结论。在这两种方法之间的进一步比较中，我们将在一个均匀分布的序列中“隐藏”一些结构，并表明隐藏的规则性可以通过压缩算法检测到，而不是通过统计测试。3.2. 图2：统计上不可检测的结构和压缩算法在本节中，我们对模拟序列的统计方法和算法方法进行了进一步比较。更准确地说，我们不是生成随机字符串，而是生成结构化数据来检查这两种方法在模式检测中的能力。结果表明，离散化收益的曲线图并不总是像这样同质，尤其是当初始数据不是i.i.d.时。。返回序列可以承载多种类型的结构。其中一些很容易通过标准统计测试（例如，自回归过程或条件方差过程）检测到。然而，要将压缩算法与统计测试区分开来，这种规律性并不是最佳选择。在这里，我们想要建立统计上不可检测的规律，这些规律可以通过压缩工具揭示出来。为此，回归序列模拟如下：1。

从统一定律U（0，255）中提取32000个整数，并用文本表示包含这些整数的序列。然后，文本被提交到几个转换，以“隐藏”其随机外观背后统计上无法检测到的规律性。让text表示应与均匀分布的text相区别的有偏序列。text通过更改文本中每个整数的二进制表达式的最后一位（分别为最后3位）从文本中获取。更准确地说，在案例1中，文本在每个术语的最后一位显示0和1之间的交替。在案例2中，文本中的元素在最后3位重复周期000、001、010、011、100、101、110、111。例如，在用8位编码文本中的每个整数时，在案例1中，我们可以得到如下序列：{00000001，00010110，11101001，100001110，10000111，…}这种规律性实际上是一种“奇偶交替”，因为以1结尾的二进制数（分别为0）总是奇数（分别为偶数）。在案例2中，我们可以得到如下序列：{01010000，11101001，011010，011011011，…，11100111，00011000}2。有偏整数序列是我们希望在实数返回离散化后得到的。所以，我们模拟过程的第二步是将文本转换为返回序列。换句话说，我们应该将文本中的每个整数与实数返回相关联。该关联基于上一节中计算的分离界限（第3.1段中描述的c.f.伯恩（0）、伯恩（2）、伯恩（256））。

对于文本中的每个整数，用文本[i]表示，我们附加一个实数，该实数是从统一的lawU（borne（文本[i]）、borne（文本[i]+1]）中独立得出的，让chron表示从该变换中获得的返回序列。通过构造，chron有两个属性：（a）在全球范围内，其术语遵循正常规律；U（0255）表示（b）如果我们用第3.1段中描述的过程离散化时间，得到的整数序列将完全是文本。因此，通过构造，chron是一个正态分布的序列，在离散化后将显示模式。这些结构是否可以通过统计和算法方法检测到？或者只有一种方法可以揭示隐藏的规律？这就是我们希望通过以下测试看到的。模拟收益率绘制在图4中，图4（a）对应于案例1，图4（b）对应于案例2。（a） 案例1（b）案例2图4：具有两个重要结构的模拟回报。在每张图的顶部，我们绘制了从chron获得的初始价格为100的伪价格序列。在底部，我们绘制了模拟的回归时间序列。如表5、6和7所示，统计测试未检测到chron中的任何结构。表5:chroncase 1 case 2测试值的单位根检验统计顺序p值ADF-31.5598***31 0.01 -31.2825***31 0.01页-178.797***16 0.01 -179.9449***16 0.01H:chron有一个单位根。表6:chroncase1 case2χ的自相关检验- 方形自由度。p值χ- 方形-自由度。p-value0。0096 1 0.9219 1.1169 1 0.290629.6655 36 0.7629 45.4802 36 0.1337小时：时间不自相关。经过统计测试后，REP应用于chron。从理论角度来看，案例1中隐藏的规则意味着压缩率为12.5%。该速率的计算方法如下：离散化时钟（实际上是文本）中的每个指针都用8位编码，而其中只有7位是必需的。

实际上，给定“奇偶交替”，文本中每个字节的最后一位是确定的。换句话说，我们可以在每个字节上节省1位。因此，理论压缩表7:BDS计时测试，2.5.5 9 9 9.5 9 9 9 0.9 9 9 9 0.0 0 0.5 5 5 0 0 0.0 0 0.850 0.0 0 0.9056 0.950 0.0 0 0 0.950 0.950 0.9 9 9 9 9 9 9.9 9 9 9 9 9 9 9 9.9 9 9 9 9 9 9 9 9 9 9 9.9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 m=2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.1121 0 0 0.1121 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.1 1 9224 0.9508 0.9732 0.8295H:chron是i.i.d.比率1/8=12.5%。根据相同的原理，我们可以计算情况2下的理论压缩率：3/8=37.5%。表8显示了两种情况下的压缩结果。请注意，实现的压缩率接近理论值，但从未达到其确切值。在使用的三种算法中，P aq8o8提供了理论速率的最佳估计。表8：压缩测试案例1案例2算法文件大小压缩率文件大小压缩大小32000%Huffman 31235 2.39%23079 27.88%Gzip 31322 2.12%23160 27.63%PAQ8o8 28296 11.58%20974 34.46%案例1：文本可压缩的解释。案例2的解释：文本是可压缩的。在这个例子中，我们展示了基本上基于Kolmogorov复杂性的算法方法，有时可以识别模拟数据中统计上不可检测的结构。然而，正如理论部分所提到的，计算所有二进制字符串的真正Kolmogorov复杂度的最终算法并不存在。压缩工具也具有实用性。换句话说，某些结构是可用的压缩工具无法检测到的。我们将在下一节介绍这一点。3.3.

算法方法的实际限制：除了欧拉数和斐波那契数之外，π可能是研究最多的数学数之一。计算π的方法很多。以下两个方程都给出了大量的小数位数：o莱布尼茨-马达瓦尔公式，（7）4×2∞Xn=0(-1） n2n+1o第二个公式：（8）π=r6×（1++++++…+n）π可分3步转化为一个返回序列：1。π的每一个十进制数字都以4位的基数2编码。例如，前4位小数（c.f.1,4,1,5）变为0001,0100,0001,0101。根据这一原理，π的前50000位小数对应于200000位二进制信息。2.然后将从第一步获得的200000位二进制字符串重新组织为字节。例如，前4位小数构成两个连续的字节：0000100、0000101。每个字节对应一个从0到255的整数。这里，π的前两个字节变成了20和21。用π表示重组后的整数序列。3.最后，我们将实数返回与π中的每个整数相关联。为此，我们遵循与上一节相同的原则：对π的每一项，用πt（t）表示∈ [1，25000]），我们将独立于均匀分布U（born（πt），born（πt+1））得出的面积数联系起来。何处出生（i）（i）∈ [0，256]）指从第3.1节中正态分布收益序列的统一离散化中获得的分离界限。在这一步之后，我们得到一个伪返回序列，如图5所示。图5：由π小数生成的伪金融时间序列如表9所示，基于π的收益序列在离散化后是不可压缩的，因为据我们所知，没有压缩算法利用π小数。基于π的模拟是另一个例子，显示了在随机外观后面隐藏模式的可能性。

它还证明了一些理论上可压缩的结构可能被现有的压缩工具忽略。这些结构在理论上是完全可压缩的，但在实践中还没有。为了检查统计工具对π小数的性能，我们进行了与前面插图相同的测试。我们注意到，在表10、11和12中，统计测试不起任何作用。表9：压缩测试：π案例1算法文件大小压缩率12500 100%Huffman 12955-3.64%Gzip 12566-0.528%PAQ8o8 12587-0.70%解释：我们无法压缩基于π的返回序列。比压缩工具更好：它们都不能拒绝暗示缺乏规律性的数据。表10：πTestVal构造的系列的单位根检验。统计顺序p值ADF-23.3799***23.0.01页-110.1364***13 0.01H：基于π的级数有一个单位根。表11：自相关检验χ- 方形自由度。p值2。7339 1 0.09824H：基于π的序列不是自相关的。在本节中，模拟数据用于说明模式检测中压缩工具的性能。这些插图支持了两个主要结果：（1）一些统计上无法检测到的模式可以通过压缩工具进行跟踪。（2） 当前可用的压缩工具无法检测到某些结构。在下一节中，我们将用现实世界的财务回报序列测试算法方法。4.真实金融数据的科尔莫戈罗夫复杂性：以道琼斯工业指数为例。在本节中，我们使用无损压缩算法估计真实金融回报的科尔莫戈罗夫复杂性。为此，我们使用了从1896年2月1日到2005年8月30日观察到的道琼斯每日收盘价的对数差异。本研究中使用的数据是从DataStream中提取的。

我们的样本包含27423个观察结果，如图6所示。在重复之后，我们统一离散实数返回，为压缩测试做好准备。虽然前几节中用于离散模拟数据的分离界限都来自标准正态律，但现实世界的回报不能以同样的方式处理，因为众所周知，财务回报不是正态分布的。实际上，基于π的系列没有一致的12:BDS检验，m={2，3}ε0.5023 1.0046 1.5069 2.0092m=2-0.0895 0.0468 0.0395 0.0129p-value 0.9287 0.9627 0.9685 0.9897m=3-0.4005-0.1755-0.2780-0.3208p-value 0.6888 0.8607 0.7810 0.7483H：基于π的系列是i.d。图6：根据道琼斯每日收盘价构建的系列。左上：对数差异直方图。中间：1896年2月1日至2005年8月30日道琼斯每日收盘价。底部：实数返回的时间序列图。关于财务收益在财务文献中的分布方式。因此，为了离散化道-琼斯日收益率，应根据其经验分布估计分离边界（伯恩（i））。这种估计可以通过3个步骤实现：1。按升序对整个返回序列进行排序，2。将升序序列分成256个大小相等的子集，3。每个返回由包含它的子集的秩表示。用这种三步方法估计borne（i）的优点是，可以对样本进行离散化，而无需对总体的分布规律做出任何假设。图7是离散化的道琼斯每日收益图。图7：统一离散化的道琼斯日报收益率在这张图中，我们可以注意到，统一离散化并不能像正态分布的收益率那样提供完全均匀的图像。有几个地区似乎比其他地区更稀疏。