3N+1猜想的Markov链模型

《3N+1猜想的Markov链模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3N+1猜想的Markov链模型赵国1基金项目:西南民族大学青年项目资助作者简介：赵国（1979－），男，硕士，主要研究方向为密码学王辉2(1.西南民族大学计算机科学与技术学院,成都610041；2.四川省彭州一中，成都611930)（E-mail:xuanyuanzhao@yahoo.com.cn）摘要:3N+1猜想是世界著名数学难题。本文研究了相应的3N+1函数迭代过程的Markov链模型，并通过统计试验确定了相应的一步转移概率，由此得到该Markov链的极限分布与数值计算结果相符。关键词:3N+1猜想；3N+1函数；伪随

2、机性；Markov链;转移概率中图法分类号:O156　　　文献标识码:A1引言3N＋1猜想考虑的是如下定义的3N＋1函数的迭代行为即若为偶数，则除以2；若为奇数，则乘3加1。大量的数值计算表明，每个自然数经3N＋1函数经反复迭代后最终总得到1，然后进入循环。事实上，OliveiraeSilva验证了对所有，都存在相应满足。例如，当时，经次迭代，迭代过程中最大值达到9232，最后仍然得到1，相应的迭代过程如下(图1)图127的迭代轨迹因此，人们猜想：对任意自然数，都存在相应使得，这就是著名的3N＋1猜想[1]。3N＋1猜想具有大

3、数学家Hilbert所说的优秀数学问题的特征：描述的简洁性以及明显的不可解困难性，因此吸引了大量的研究。从耶鲁大学教授到普通中学生，从理论数学家的纸上演算到计算机科学家的网上分布式验证，对此问题的研究可谓方兴未艾。从启发式论证[2]（HeuristicArgument）到统计模型[3]（StochasticModel），所有结果都预示3N＋1猜想是对的，但却给不出一般性的证明，至今未获得突破性进展，它仍是一个世界性的数学难题。3N＋1函数的一个吸引人的性质是其迭代过程中的伪随机行为，这种伪随机性被认为是解决3N＋1猜想的困难所

4、在。但是在积极的一面，Cloney[4]建议用3N＋1函数作为伪随机数发生器。2Markov链模型3N＋1函数迭代的动态行为引发了大量的研究，这是一种表现出某种伪随机性的确定过程[5]。这种伪随机性观点促使人们建立统计模型去刻画3N＋1函数的性质，例如随机行走模型[3]，3N+1树模型[6]。接下来，我们建立3N＋1函数迭代过程中奇偶分布的Markov模型[7]，用以预测3N＋1函数迭代过程中奇数与偶数出现的概率。2.1概率转移矩阵首先注意到，在3N＋1函数中，每一次奇变换后随即而来的一定是一次偶变换，因为如果n是奇数的话，3

5、n+1一定是偶数；而每一次偶变换后随即而来的却不一定是一次奇变换。J.Lagarias改进了这个启发式（Heuristic）论证。他指出，如果把奇变换后再作偶变换考虑在一起，那么这样得到的奇偶分布结果可以看作是真的“很随机”。所以从启发式观点，3N＋1猜想的实质可以简单概括为:奇数变偶数,偶数变奇数,最后必为1。但是就算再有实验证据来表明它是对的，启发性论证也只能让人对猜想的正确性更充满信心。它不能代替真正的数学证明。为方便研究，我们需要3N＋1函数迭代过程中关于奇偶分布的Parity序列的概念。由定义，给定初值的相应Pari

6、ty序列为由下面的公式确定的向量即若3N＋1函数迭代过程中取值为奇数，则相应；若取值为偶数，则相应。例如，当时，相应的Parity序列为为长度为111的0－1伪随机串。注意到每一次奇变换后随即而来的一定是一次偶变换，所以1后面一定是0，但是每一次偶变换后随即而来的却不一定是一次奇变换，所以0后面未必是1。但是，3N＋1函数迭代过程是一种确定性过程，也就是说，它遵从如下的演变规则：当的值已知时，的奇偶性只与的取值有关，而与前步迭代的取值无关。通俗地说，就是在已经知道“现在”的条件下，3N＋1函数迭代过程的“将来”不依赖于“过去’

7、。所以，3N＋1函数迭代过程中0－1的分布是一个Markov链，而且还是齐次的。下面求相应的一步转移概率。设3N＋1函数迭代过程中偶数变奇数的概率为，即Parity序列中0后面是1的概率为。同时注意到Parity序列中1后面一定是0，可得3N＋1函数迭代过程的一步转移概率矩阵为在实际中，一步转移概率可通过统计确定。以为例，其相应Parity序列所确定的Markov链中，0－1状态转移的情况是：29次，：40次。因此，偶数变奇数的一步转移概率可用下面频率近似考虑到3N＋1函数的伪随机性，对的所有自然数计算相应偶数变奇数的概率并求

8、平均值得由大数定律知，该值可作为Parity序列中0后面是1的概率。由此可得相应的一步转移概率矩阵为2.2极限分布在3N＋1猜想研究中，人们关心的是3N＋1函数迭代过程中奇数和偶数各自出现的次数，或者等价地，相应的Parity序列中0－1各自出现的比率。对应于，相应的Mark