这会是什么结果呢？

zgg___

在matrix67的blog上，看到了一个问题：“随机选取两个无穷大的图，求两者相同的概率” 见 http://www.matrix67.com/blog/archives/2168 所对应的出处为 http://blogs.warwick.ac.uk/dango ... pletely_ridiculous/ 文章的结论是：两者是同构的几率为1。 于是我就联想啦，赫赫。 随机选取两个无穷大的方阵，它们相似的概率是不是也是1呢？ 赫赫，如果是，它们的特征值排序后构成一个什么样的无穷序列呢？ （注：可以从简单的情况开始，设方阵中的每个数都是满足正态分布的实数。并且方阵是对称的，好让它的特征值可以排序。赫赫。） 貌似结论是“神奇的”。大家对这个无穷序列能有一些数值上的支持么？

mathe

这个说法有问题了. 这里牵涉到概率的定义问题. 严格数学意义上概率的定义是满足可列可加性. 也就是任意取可列个(有限或同自然数一一对应的数目)互不相交的事件集合${A_i}$ 那么至少一个事件发生的概率就是所有事件发生的概率的和. 这个是概率的可列可加性. 但是对于一些总数目为可列情况的问题,比如这里的问题,我们就很难定义一个满足可列可加性的概率.也就是对于这一类问题,虽然我们每一步淘汰的都是0概率事件,但是淘汰了无限次以后,可能淘汰的就不是0概率事件了.(也就是可能将所有的解都淘汰了). 比如我们考虑自然数集合.那么任意选择一个自然数的子集A,A中包含数字1的概率是多大呢? 显然我们直接考虑这个数字1是否被包含,那么可以得出是1/2的结论. 但是如果我们枚举A中每个元素是否等于1,那么这个概率都是0,如果我们一一枚举A中所有的元素,就会得到A中含有1的概率是0. 而上面文章中的方法也类似,它等于依次枚举集合A和集合B中的各个元素,每次都判断给定A中的一个元素,必然能找到B中相匹配的元素的概率为1(不匹配情况概率为0,那种情况的B被淘汰了).所以这个方法同上面依次枚举A中每个元素是否为1的方法类似,不一定可以得到正确的答案. 不过虽然如此,方法还是很有意思

shshsh_0510

如果是Matrix67的结论，还敢和他争辩一下，但仔细一看，他是引大牛Cameron的结论，就只有再仔细的学习了。 研究的人总喜欢用一些独特的方式来表达，这个问题我举个俗些的类比更容易理解（但不知是否恰当） 两个随机无理数，表为无限小数，截取一个中的任意一段数字，几乎总可以另一个中的某个位置找到这段数字。 我想意思是差不多的。 至于zgg兄的联想，我想和这个差别很大，相似的概率应该是0

mathe

没必要迷信大牛.而且我觉得他这里提出这个问题玩笑的因素居多 牵涉到可列状态数目的情况,定义概率本身是有问题,通常只能通过一些特别的方法. 而这个题目本身就是有问题的 比如说,我们会说随机选择一个整数是偶数的概率是1/2,实际上我们是这样认为的;限定整数再某个有限的范围[-N,N],在这个范围内随机选择一个整数,然后让N趋向无穷,这样得出的概率是我们通常说的概率. 而对于上面无限图的情况,我们同样可以用这种方法去查看:那么拥有N个点的图,有$2^{{N(N-1)}/2}$个(根据任何两个点之间是否有边.而对于每个图,同它同构的最多$N!$个(置换不同的点),所以我们得出这两个图同构的概率不超过${N!-1}/{2^{{N(N-1)}/2}}$,让N趋向无穷,得到概率为0.

zgg___

恩，或许mathe说的是。 这个问题提得是有不严密的地方，比如说，我们可以讨论命题：“随机选取两个无穷大的图，那么它们的节点数相同的概率是1么？” 这个问题等价于“随机选取两个无穷大的数，它们一样么？” 因为节点数相同是同构的必要条件，所以问题就陷入了某种“哲学困境”了。 而这个领域我们并不想过早的涉及。 然而我想，（赫赫，转折了。） 这个命题是基于某种“现象”的。比如说：我们穷举具有N个节点的所有图，从这些图中随机抽取两个图，可以计算出它俩恰好同构的几率。随着N变大，这个几率趋近于1。如果这种现象存在，那么就存在对其合理的解释。（或许“穷举具有N个节点的所有图”的句子改为“穷举具小于等于N个节点的所有图”之后，并不影响结论。） 为什么我会联想起矩阵的呢？因为这样可以出数。赫赫。 比如说：我们取一个N*N的方阵，其中的每个数都从-1到1间平均选取，然后计算所有特征值的模的算术平均值。大家可以试一试，可以得到一个N的数列。但是这样只是相当于计算期望值，并不那么high。 然而图的同构带来矩阵的相似。 比如说：我们穷举具有N个节点的所有图，列出所有图的连接矩阵，（基本相当于穷举了所有的0、1对称矩阵，）按照前面的观点，随机抽取两个矩阵，可以计算出它俩恰好相似的几率。随着N变大，这个几率趋近于1。如果这种现象存在，这时意味着这些矩阵对应着唯一的一个实数序列，它的两头都是无穷，但是中间会是离散的实数。这个序列并不是某种平均值。因此，我只是觉得这个序列会比较有趣。 上面的说法我也不是很确定，于是和大家讨论，或是先寻求一些数值上的支持。

zgg___

"我们穷举具有N个节点的所有图，从这些图中随机抽取两个图，可以计算出它俩恰好同构的几率。随着N变大，这个几率趋近于1。" 看来的确是有问题。随着N变大，这个几率趋近于0。

shshsh_0510

不会吧，讨论成这个结果了。