3N+1猜想的Markov链模型.doc

3N+1猜想的Markov链模型赵国1基金项目:西南民族大学青年项目资助作者简介：赵国（1979）， 男，硕士，主要研究方向为密码学 王辉2(1.西南民族大学计算机科学与技术学院,成都 610041；2.四川省彭州一中，成都 611930)（E-mail:）摘 要:3N+1猜想是世界著名数学难题。本文研究了相应的3N+1函数迭代过程的Markov链模型，并通过统计试验确定了相应的一步转移概率，由此得到该Markov链的极限分布与数值计算结果相符。关键词:3N+1猜想；3N+1函数；伪随机性；Markov链;转移概率中图法分类号: O156文献标识码: A 1 引言 3N1猜想考虑的是如下定义的3N1函数的迭代行为即若为偶数，则除以2；若为奇数，则乘3加1。大量的数值计算表明，每个自然数经3N1函数经反复迭代后最终总得到1，然后进入循环。事实上，Oliveira e Silva验证了对所有，都存在相应满足。例如，当时，经次迭代，迭代过程中最大值达到9232，最后仍然得到1，相应的迭代过程如下(图1)图 1 27的迭代轨迹因此，人们猜想：对任意自然数，都存在相应使得，这就是著名的3N1猜想1。3N1猜想具有大数学家Hilbert所说的优秀数学问题的特征：描述的简洁性以及明显的不可解困难性，因此吸引了大量的研究。从耶鲁大学教授到普通中学生，从理论数学家的纸上演算到计算机科学家的网上分布式验证，对此问题的研究可谓方兴未艾。从启发式论证2（Heuristic Argument）到统计模型3（Stochastic Model），所有结果都预示3N1猜想是对的，但却给不出一般性的证明，至今未获得突破性进展，它仍是一个世界性的数学难题。3N1函数的一个吸引人的性质是其迭代过程中的伪随机行为，这种伪随机性被认为是解决3N1猜想的困难所在。但是在积极的一面，Cloney4建议用3N1函数作为伪随机数发生器。2 Markov链模型 3N1函数迭代的动态行为引发了大量的研究，这是一种表现出某种伪随机性的确定过程5。这种伪随机性观点促使人们建立统计模型去刻画3N1函数的性质，例如随机行走模型3，3N+1树模型6。接下来，我们建立3N1函数迭代过程中奇偶分布的Markov模型7，用以预测3N1函数迭代过程中奇数与偶数出现的概率。2.1 概率转移矩阵首先注意到，在3N1函数中，每一次奇变换后随即而来的一定是一次偶变换，因为如果n是奇数的话，3n+1一定是偶数；而每一次偶变换后随即而来的却不一定是一次奇变换。J. Lagarias改进了这个启发式（Heuristic）论证。他指出，如果把奇变换后再作偶变换考虑在一起，那么这样得到的奇偶分布结果可以看作是真的“很随机”。所以从启发式观点，3N1猜想的实质可以简单概括为:奇数变偶数,偶数变奇数,最后必为1。但是就算再有实验证据来表明它是对的，启发性论证也只能让人对猜想的正确性更充满信心。它不能代替真正的数学证明。为方便研究，我们需要3N1函数迭代过程中关于奇偶分布的Parity序列的概念。由定义，给定初值的相应Parity序列为由下面的公式确定的向量即若3N1函数迭代过程中取值为奇数，则相应；若取值为偶数，则相应。例如，当时，相应的Parity序列为为长度为111的01伪随机串。注意到每一次奇变换后随即而来的一定是一次偶变换，所以1后面一定是0，但是每一次偶变换后随即而来的却不一定是一次奇变换，所以0后面未必是1。 但是，3N1函数迭代过程是一种确定性过程，也就是说，它遵从如下的演变规则：当的值已知时，的奇偶性只与的取值有关，而与前步迭代的取值无关。通俗地说，就是在已经知道“现在”的条件下，3N1函数迭代过程的“将来”不依赖于“过去。所以，3N1函数迭代过程中01的分布是一个Markov链，而且还是齐次的。下面求相应的一步转移概率。 设3N1函数迭代过程中偶数变奇数的概率为 ，即Parity序列中0后面是1的概率为。同时注意到Parity序列中1后面一定是0，可得3N1函数迭代过程的一步转移概率矩阵为 在实际中，一步转移概率可通过统计确定。以为例，其相应Parity序列所确定的Markov链中，01状态转移的情况是：29次，：40次。因此，偶数变奇数的一步转移概率可用下面频率近似考虑到3N1函数的伪随机性，对的所有自然数计算相应偶数变奇数的概率并求平均值得由大数定律知，该值可作为Parity序列中0后面是1的概率。由此可得相应的一步转移概率矩阵为2.2 极限分布在3N1猜想研究中，人们关心的是3N1函数迭代过程中奇数和偶数各自出现的次数，或者等价地，相应的Parity序列中01各自出现的比率。对应于，相应的Markov过程，这等价于要求出该Markov链的极限分布。由著名的ChapmanKolmogorov方程【7】，对齐次Markov链而言，步转移概率矩阵是一步转移概率矩阵的次方，即由著名的遍历性定理【7】，可知相应的极限分布为上述极限分布的意义是：在3N1 函数迭代过程中，偶数出现的概率为0.6685，奇数出现的概率为0.3315，二者之比，与大量数值计算结果吻合。 例如，当时，其相应Parity序列中0的个数为70，1的个数为41，二者之比0.5857。从该例同时也可以看出，3N1函数的伪随机性使得有关预测变得十分困难。实际上，对的所有自然数，分别计算相应的Parity序列中0与1的个数之比是极不规则的（图2）。图 2 parity向量中1与0的比率致谢： 感谢余柏林赠送参考文献8，使得本文得以顺利完成。参考文献： 1 J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 1985,92 (),3-23.2 R. E. Crandall, On the”3x+1 problem, Math. Comp., 1978, 32 (), 1281-1292.3 J. C. Lagarias and A. Weiss, The 3x + 1 problem: Two stochastic models, Ann. Applied Prob., 1992, 2 (), 229-261.4 T. Cloney, C. E. Goles, and G. Y. Vichniac, The 3x + 1 Problem: a Quasi-Cellular Automaton, Complex Systems, 1987, 1 (), 349360.5 J. C. Lagarias, How random are 3x + 1 function iterates? in: The Mathematician and Pied Puzzler: A Collection in Tribute to Martin Gardner, A. K. Peters, Ltd.: Natick, Mass. 1999, 253266.6 D. Applegate and J. C. Lagarias, Density bounds for the 3x + 1 problem I. Tree-search method, Math. Comp., 1995, 64 (), 411-426. 7 盛骤，谢式千，潘承毅，概率论与数理统计（第三版），高等教育出版社，2001。8 邬家邦. 世界难题3 N + 1 猜想. 长沙:湖南大学出版社,2001.Markov Chain Model of the 3N+1 ConjectureZHAO Guo1 WANG Hui2（1. College of Computer Science and Technology, Southwest University for Nationalities , Chengdu 610041;2. Pengzhou No. 1 middle school of Sichuan Province, Chengdu 611930）Abstract: The 3N+1 conjecture combines simplicity of statement with apparent intractability. In this paper we propose using the Markov Chain to model the average behavior of the 3N+1 function iteration and determining the transition probability by statistical testing method. The pre