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

如果s是长度为n的序列，那么：（3）K（s）≤ n+O（log（n））在等式3中，O（log（n））仅取决于使用的通用语言。这个属性来自这样一个事实，即所有有限字符串至少可以由程序“print（s）”生成，其长度接近于s的大小。请注意，大多数n位字符串（只要n足够大）的科尔莫戈罗夫复杂度K（s）接近于n。K（s）<<n意味着存在一个程序P，它可以生成s，并且比s短得多。在这种情况下，据说P在s或s中发现了结构规律性。相反，定义1.4。如果对于由S表示的有限二进制字符串：Cn K（S） n）≥ N- CWS在这里 n表示自然数集合n中S和C的前n位为常数，然后定义为“随机字符串”。由Martin-L¨of（1966）提出，由Chaitin（1987）重新制定，并在Downey和Hirschfeldt（2010）中审查的随机弦定义，与任何概率概念无关，仅依赖于S的结构性质，通常与计算机科学中的“有效性”概念有关（例如，见Velupillai（2004））。大多数现代编程语言都是通用的（例如C、Java、R、Lisp）。根据定义1.4，从随机字符串的第一个数字可以得到的最佳压缩率是byrate=n- K（S） n） n=CnAs n→ ∞, 速度→ 换句话说，随机字符串是不可压缩的。与直觉相反，可压缩弦相对较少。

例如，在所有n个数字串中，那些验证K（s）<n的数字串的比例- 10不超过1/1000。为了说明可压缩性和规则性之间的关系，让我们考虑两个可压缩（规则）字符串：a:01101110010111011110001001010111110111100001100101111111111110000110010100111010110101B:11111 001111001100111111111111111011011010101110111111111111111101101101110第一个字符串，称为Champernowne序列（即第2页的字符串C），它是用一个非常简单的算术规则生成的：它是以2为基数的自然数的并置。a首百万位数的最佳压缩率高于99%（c.f.附录B），这表明a可以通过短程序打印。第二个字符串独立于随机律（借助物理过程）得出，以2/3的概率传递“1”，以1/3的概率传递“0”。生成b的计算机程序可能比它短得多。事实上，经典工具可以获得b上的压缩率，计算如下：（4）- 1/3对数（1/3）- 2/3log（2/3）=91，8%虽然b来自随机律，但其可压缩性仍然与统计猜想完全一致：由定义大于0的1组成，b不应被视为标准随机游动的致病因素。面对罕见事件，算法和统计方法也给出了类似的结论。让cdenote生成一个100位的字符串，该字符串仅由0组成。要推断c是否由tossinga硬币生成，可以做两种猜测：1。根据可计算性理论，c具有相对可忽略的Kolmogorov复杂性，并且不可能是抛硬币过程的结果。2.

从统计学的角度来看，通过投掷硬币获得100个连续“正面”（或“反面”）的概率不超过7.889e- 31，c可能不是这种程序的结果。然而，尽管前面有两个论点，c可能总是由tossinga coin生成的，因为即使概率为零，也会发生罕见的事件。这种现象经常被金融从业者称为“黑天鹅”。观测K（s）<n的概率-20小于1/1000000。附录A中提供了这一结果的证明。这种压缩率与b的香农熵有关。在大多数编程语言中，c可以很容易地用短命令生成。在本节中，通过比较Kolmogorov复杂度与统计框架在随机性方面的考虑，介绍了Kolmogorov复杂度。前一个概念的两个性质——不变性定理和有界性定理——在这篇理论导言中得到了强调，因为它们使olmogorov复杂性成为给定序列和随机序列之间距离的良好指示器。基于这一理论发展，我们将在以下章节中展示如何在实证数据分析中使用Kolmogorovcomplexity。1.2. 价格序列的Kolmogorov复杂性：一个基本例子在理论上介绍了Kolmogorov复杂性之后，我们用下面的例子来说明如何在某些序列的复杂外观后面搜索结构规律。这个例子是用图1中绘制的模拟价格序列开发的。图1：模拟序列模拟序列的前14个值为：e1，t=1000102810441015998101710481079111010901058108911171100，。。。e1中一个明显的规律是，所有价格似乎都集中在1000美元左右。

我们可以通过方程e2，t=pt，来“消除”这种规律性- pt-1.这个过程传递以下顺序：e2，t=28,16，-29，-17,19,31,31,31，-20，-32,31,28，-17，-17。。。由于阳性序列更容易转化为碱基2，e2的每个元素加上32，即：e3，t=60,48,3,15,51,63,63,63,12,0,63,60,15,15，。。。然后，e3用6位二进制数编码：e4，t=11110011000000001100111111111111111111111111110000000011111111110000111001111，。。。不带逗号e4，t字节：e=111100110000000011001111111110011111111111111111100000000111111。。。可压缩吗？换句话说，在前面的转换之后，在ea中仍然存在结构吗？在回答这些问题之前，我们必须注意到，eis的二进制表达式比e的二进制表达式要短。我们的第一次转换实际上通过利用e的顺序、集中方面对应于第一次压缩。如果e不可压缩，我们的“规则性擦除过程”（此后，REP）将达到最后阶段。然而，事实并非如此。在e中，还有另一个结构可以描述如下：如果（2n- 1） 第四项是1（分别为0），第二项也是如此。通过利用这种规律性，ECA可以被压缩成只携带e的每秒钟一个元素的e:e=1101000010111101111111101000011101011011。。。在REP的这一步，我们有一个不可压缩（随机）的字符串吗？再一次，情况并非如此。eis实际上是由一个伪随机发生器产生的，从理论上讲，它可以被简化为它的种子！因此，eis原则上是可压缩的。

然而，应该承认，考虑到压缩工具的可用范围，这种最终压缩在实践中几乎是不可行的。这个基本的例子强调了三个重要的规律是如何隐藏在e1，t的复杂表象背后的，以及这些结构是如何通过一个简单的确定过程来揭示的。在接下来的几节中，借助经典压缩算法，我们将展示如何在模拟（c.f.第3节）和真实金融时间序列（c.f.第4节）上实现REP。特别是，我们强调REP可以用来发现大多数统计测试无法检测到的规律性。在具体示例之前，我们首先提出一些方法上的考虑2.2。本文的重点是展示如何使用无损压缩算法来测量数字字符串的随机性水平。这需要一系列特殊的转换。Initialdata必须经历两个连续的操作：离散化和REP。为了集中讨论压缩和正则性之间的关系，在最后一节中，我们用一个具体的例子展示了REP如何揭示整数字符串中的结构。然而，为了将后一种方法应用于现实世界的数据，离散化是必要的，因为财务回报通常被认为是实数，而计算机工具只能处理离散的数据。因此，人们可以质疑这种离散化对金融序列随机性的影响。为了回答这个问题，我们介绍了无损离散化的原理。E需要前14个价格的56位小数，而eonly需要30位小数。当然，我们必须将“1000”存储在eto的某个地方，以便跟踪第一个价格。

在基数2中测量，从4×56=224位到4×30=120位的Eturn长度，因为从0到9的每个十进制数字都至少用4位编码。（i） 集中价格值，（ii）二进制数字的特殊结构和（iii）伪随机发生器。我们将使用附录C.2.1中给出的名为Hu Off man、RLE和Paq8o8的算法。无损离散化原则在本节中，我们提出了一种通用方法来估计对数价格序列的Kolmogorov复杂性，这是人们在现实金融市场中可以观察到的。如第1.2节所述，第一个“压缩”包括将对数价格序列转换为回报。这种金融研究人员所熟悉的操作实际上提供了不必要的精确性：例如，没有人会对财务回报的18位小数感兴趣。因此，在不丢失敏感信息的情况下，可以将实数序列与每个整数关联一定范围的实际收益，从而将其转换为整数。我们还假设用于离散化的整数属于N的子集，其长度可以任意固定为2的幂。整数的总数应为2的幂，因为这允许在无偏差的情况下，以基数2对离散化结果进行编码。一旦以二进制为基础编写，财务报表就会变成一个由0和1组成的序列，这非常适合压缩工具。在介绍了离散化的主要思想之后，关于后一种方法必须讨论三点：1。

为什么不直接压缩基数为10的实际回报率？如果价格变化以10为基数编码，并直接写入文本文件进行压缩，序列中的每个十进制数字将系统地占用8位（一个字节）。由于十进制数字的定义从0到9不等，用8位编码会导致存储空间的最佳占用：在=256的可能性中，只会使用10个不同的字节。因此，即使在随机字符串上，由于次优编码，也会观察到虚假压缩。显然，这种压缩在金融系列研究中并不重要，而二进制编码系统对于在金融中引入科尔莫戈罗夫复杂性是必要的。2.将实数创新转化为整数时是否存在信息丢失？显然，在将同一个整数（例如“134”）附加到两个相近的变量（例如“1,25%”和“1,26%”）上时，我们会降低初始数据的精度。然而，如上所述，离散化过程中使用的整数范围可以从[0,255]、[0,511]、··、[0,2n]中选择- 1] 要获得“正确”的精度水平：既不是非常精确，也不是非常不准确。数字摄影也遵循这一原则：在选择正确的顶点粒度时，我们储存相关信息，忽略一些不重要的细节或变化。按照这个原则，要保留每个返回值的第四位小数，需要使用0到8192之间的整数。我们在这里使用对数价格（pt）的原因是，金融回报（rt）通常被定义为连续复合回报，即rt=ln（pt）- ln（pt）-1） 例如，像这样固定的整数子集可以是从0到255或从-128对+127。每个字节可以代表2=256个1和0的不同组合。

因此，我们可以在一个文本文件中获得256个不同的答案。低（已用字节）/（可能字节）速率。3.如果每个报税表用一个单字节编码，离散化的金融序列可以转换为ASCII字符。无损压缩算法（如Hu Off man、RLE和Paq8O8）可用于搜索相应文本文件中的模式。2.2. 代表：模式检测的增量程序如第1.1节所示，捕获金融动态的通用方法要求识别构成εt的潜在随机过程（例如，i.i.d.高斯随机创新）。在介绍金融领域的科尔莫戈罗夫复杂性时，我们想考虑，除了有据可查的程式化事实外，是否有可能或不可能找到隐藏在财务回报中更微妙的其他结构。换句话说，我们试图在更明显的规律出现时，找到新的、更模糊的规律。如果直接对返回序列使用压缩方法，算法将只捕获数据中的“主体结构”，并可能忽略较弱（但现有）的模式。为了公开这些信息，我们建议一个迭代过程，一步一步地从数据中删除大部分证据结构。由此产生的系列将接受未知结构的压缩试验。由于这一过程，即使财务回报见证了明显的模式，如程式化事实，压缩算法也可以始终专注于未知结构，因为一旦删除，识别模式将不再与未知结构混合，任何进一步的压缩都可能与新模式的存在有关。为了解释REP的压缩结果，我们区分了3种情况：1。原始序列（用s表示）被简化为一个完全确定的过程，压缩工具实际上可以检测到这个过程。在这种情况下，s是一个常规序列。2.s被简化为一个不可压缩的“心脏”。

在本例中，s是一个随机字符串。3.s有一个决定论内核，但后者太复杂，在实践中无法被压缩工具利用。在这种情况下，s应被视为随机的。例如，它是由像“R”这样的编程语言生成的普通序列的情况。REP的第一步是确定分布规律，并提供编程语言spseudo-random生成器生成的序列。这个生成器是一个完美的决定论算法，是一个可检测且可擦除的结构。然而，据我们所知，没有任何压缩算法探索这种结构。因此，在实践中，从“R”中的统一定律得出的二元级数被认为是“完全随机的”，尽管从理论角度来看并非如此。实际上，给定一个有限的时间序列，不可能确定它是一个规则的还是随机的。至少有两个参数支持这一点：这意味着实数返回是用0到255之间的整数离散的。R开发核心团队（2005）1。由于统计推测基于样本而非总体，因此Kolmogorov复杂性是用有限字符串估计的。因此，没有人能以某种方式判断某个有限字符串是否是随机字符串的一部分。2.附加在s上的函数，其Kolmogorov复杂度的真实值不能用计算机计算。换句话说，除了在一些非常罕见的情况下，人们永远无法确定给定的程序P是s的最短表达式。因此，压缩工具只估计Kolmogorov复杂度，它们都不应被视为最终解决方案，可以检测有限序列中的所有可能规律。

这一结论与G¨odel不可判定性密切相关。从这个意义上讲，压缩算法与统计测试有着相同的不足：这两种方法都无法传递特定的语句。尽管如此，由于统计测试对金融研究做出了不可估量的贡献，压缩算法也可以成为收益序列中模式检测的强大工具。为了说明这一点，我们将在下一节中比较有关数字序列结构检测的算法和统计方法。3.算法和统计方法之间的不等价在本节中，我们用模拟数据说明如何使用压缩算法搜索规则结构。在这些插图中，对统计和算法工具进行了比较，以展示一些模式如何被标准统计测试忽略，但被压缩工具识别。更准确地说，通过模拟数据，我们将显示：1。统计和算法方法在随机字符串上的表现，2。一些统计上看不见的结构是如何被算法工具检测出来的，3。压缩试验也有实际的局限性。3.1. 图1：不可压缩随机性在本节中，我们用统计语言“R”模拟了一系列32000个i.i.d.N（0，1）返回，并分别用统计测试和压缩算法检查模拟数据。我们发现压缩算法不能压缩随机字符串，有时甚至会增加初始数据的长度。模拟系列与“连续财务回报”非常相似，可用于生成一个人工“价格序列”。