趣题:随机选取两个无穷大的图,求两者相同的概率

    假设我们俩各自独立地随机选取一个有无穷多个顶点的图(两点之间1/2的概率有边1/2的概率没有边)。那么,我们俩选到相同的图的概率是多少?

    令人难以置信、但想通了之后又异常显然的是,两个图相同的概率为1。并且,我可以精确地告诉你,这个相同的图是什么样子的。考虑这样一个无穷大的图,我们用自然数1, 2, 3, …给所有顶点标号,然后如果y的二进制表达中的右起第x位为1,就在顶点x和顶点y之间连一条线。比如,顶点5就和顶点1、顶点3相连。我可以证明,我们俩都100%地会选取到上述这个图。


    我们先来定义一个东西。我们说一个图是“任意连通”的,如果对于任意两个不相交的有限点集U和V,总能找到一个顶点x,使得x和U里面的所有顶点都相连,但和V里面的任一顶点都不相连。下面我们先证明,随机选取一个无穷大的图,该图满足任意连通性的概率为1;其次我们说明,所有满足任意连通性的图都是同构的。
    为什么一个随机选取的无穷大图具有任意连通性的概率为1呢?我可以反过来说明,一个随机图不满足该性质的概率为0。考虑两个任意的有限点集U和V,假设这两个点集一共有n个点。那么,随便选取一个点x,它和U里所有点都相连,但和V里所有点都不相连的概率显然为1/2^n(因为两点之间是否相连是独立确定的,且概率为1/2)。不管n有多大,1/2^n总是一个不为0的数,但供我选的点有无穷多个。在我第k次选点后还找不到满足条件的点的概率为(1-1/2^n)^k,它是一个最终趋于0的值。
    然后我们来证明,只要两个图都满足这个性质,我一定能为它们的顶点适当编号,使得图A的点x点y之间有边当且仅当图B的点x点y之间有边。这个证明是构造性的。假设我们已经找到了一个图A和图B的同构子图,这个子图有6个顶点,分别标号为1, 2, 3, 4, 5, 6。在图A当中选取下一个未编号的顶点,把它标号为顶点7。假设顶点7和前面6个顶点中的2, 4相连,和1, 3, 5, 6都不相连。由于图B满足任意连通性,因此图B当中必然也存在一个点,它和自己图里的那个2, 4相连,和1, 3, 5, 6都不相连。于是,把图B中的这个新的点编号为顶点7。不断执行该操作,就可以给图里的每个顶点确定一个适当的编号。
    有一个问题是,不断这样操作后,虽然图A里的所有顶点都能找到图B中的对应顶点,但图B中可能还剩有顶点一直未被编号。问题的解决办法也很简单:利用任意连通性找到图B中与图A中的顶点7相对应的点后,立马换成让B选取下一个未编号的顶点并命其为顶点8,让图A利用任意连通性来找它的对应点。如此交替变更图A和图B的角色,就能保证两个图中的每个点都能编上号了。

    那么,为什么我刚才说,我们选出的图都和第二段中描述的那个图相同呢?因为,那个图显然满足任意连通性。

 
来源:http://blogs.warwick.ac.uk/dangoodman/entry/something_completely_ridiculous/

43 条评论

  • iceberg

    相同改成同构比较合适。。

  • pp

    其实仔细想一想确实是“异常显然”。。。
    对于两个n个顶点构成的随机图,两者同构的概率“约等于”1-(1-(1/2)^(n*(n-1)/2))^(n!)。n取无穷大时极限为1

  • 燕仰

    嗯~拜托帮忙把links里的地址改一下,http://www.asyanyang.com/

  • CpyPrefersYou

    楼上 >_<

  • pp

    仔细研究了一下,这个证明似乎是有问题的,简单的讲就是有限个1乘起来还是1但无限个1乘起来就未必是1了。
    从另一个角度考虑,对于两个n个顶点构成的随机图,定义两者同构的概率p(n)。p(n)小于两者边数相同的几率,显然地,后者在n->∞时为0。之前对于p(n)的估计比较粗糙。

  • Zealot

    这个证明的最后一步好像有问题
    你最后一步只证明了包含有限点的“任意连通”图是同构的
    其中使用的是数学归纳法
    但是, 注意数学归纳法只能证明有限集合的命题
    对于无限集 数学归纳法是不适用的

  • Zealot

    最后一步的证明两个“任意连通”图同构是有问题的
    证明过程使用了数学归纳法
    但是数学归纳法只适用于证明有限集的命题
    对于无限集数学归纳法是不适用的

  • Phil

    恩… asyanyang.com 即将成为OI人访问最多的非OI blog了.

  • wuzhengkai

    数学归纳法基于反证法和最小数原理,可以应用于无限集,假设原命题不成立,必然存在最小的n使得p(n)不成立,然后可以将其证伪

  • iceberg

    地基的数学归纳法定义不知从何而来?
    http://zh.wikipedia.org/w/index.php?title=%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95&variant=zh-cn
    这个是一般被认同的数学归纳法的定义。

  • zgg___

    那么,随机选取两个无穷大的方阵,它们相似的概率是不是也是1呢?赫赫,如果是,它们的特征值排序后构成一个什么样的无穷序列呢?(注:可以从简单的情况开始,设方阵中的每个数都是满足正态分布的实数。并且方阵是对称的,好让它的特征值可以排序。赫赫。)

  • Sevenk

    3L……M67MS以前说过什么话……

  • Zealot

    看来高估了这里的水平.我再来解释下,普通的数学归纳法是不适用无限集的
    只有超限归纳法适用于无限集, 超限归纳法是数学归纳法在序数上的扩展

    现在来尝试用超限归纳法证明

    1. 假设任意连通图A拥有α个点时候 图A与构造图同构
    2. 则任意连通图B拥有β=α+1个点的时候 图B与构造图同构
    (α, β为序数)

    两步都有问题.
    步骤1问题: 构造图只构造了顶点数小于ω的图, 所以当α > ω时图A不可能与构造图同构
    步骤2问题: 若要在图A中加入第β个定点, 那么要把α个点分为U,V两个集合, 如果α >= ω, 那么U,V中必然有一个集合拥有无穷个点, 但是原证明中只证明了有限个点连通性(原文:考虑两个任意的有限点集U和V).

    对于α = ω的情况, 无法用数学归纳法证明 也无法用超限归纳法证明
    所以在ZFC集合论中, 楼主的命题对所有图都不成立
    (ZFC集合论包含选择公理, 选择公理等价于良序公理, 所以集合顶点数必然是个良序的, 所以必然是一个序数)

    关于 超限归纳法 序数 ω 的定义 ZFC集合论 选择公理 良序公理 请自行wikipedia

    回10楼: 我不知道你强调”数学归纳法”本身的证明有什么意义
    回12楼: 要懂得尊重别人 多考虑考虑再回复 人家知道啥是数学归纳法

  • 燕仰

    祝贺Blog四周年~~

  • Nova

    数学归纳法显然不适用于无穷的情况,记得大一上数理逻辑的时候老师举的例子,考虑集合{1,2,…,n},n有限的情况下,该集合均有最大的数,n为无穷的时候(虽然不能这么说,但相信大家明白我的意思),就没有了。这个例子或许不太好,不过15楼解释的比较清楚了~

  • iceberg

    @15楼
    首先我当时似乎没有什么态度问题,陈述事实而已。
    你的表述自然是会引起误解的。“不适用于无限集”的说法显然违背数学归纳法的一般理解,而我当然无从猜想你究竟是什么意思。
    另外,我认为这里是可以转化为数学归纳法的叙述形式的,只是表面上不符合而已。

  • 何苦

    15楼可以啊!学中文的不能小觑。你问问数学的学生,是不是每个人都知道超限归纳。

  • 何苦

    不好意思 我浏览器显示出了问题,把15楼和16楼弄混了。

  • pp

    我还是没弄懂哪里使用了数学归纳法

  • wuzhengkai

    @15
    我不明白为什么不能用普通的数学归纳法(原命题基于自然数的啊),请解释下,谢谢。

    对于你步骤二中的问题,原文只是举了有限集为例子说明概率的求法,再求极限后求出无限图任意联通的的概率。

    我水平比较低,才升高中,请多指教

  • sss正和

    我来个简化到极点的例子:
    证明(0, 1)中一个随机实数以概率1与0.1111111111111111111111………….同构。
    首先可证明:随机实数小数点后只有有限个1的概率为0(对应于“任意连通”:)。
    选一个“n点同构子图”0.1…1,得到“n+1点同构子图”0.1…11的概率为1,按数学归纳法原理,证毕。

  • sss正和

    前面的极简例子上下文是:通过改变数字顺序达成一致叫做同构。这是在别的地方讨论时的上下文。

  • sss正和

    顿悟~楼主的证明方法只能证明存在无穷大同构子图,不能证明所有的点都包括进来了,就象我证明随机实数与0.11111……同构的实质一样。

  • sss正和

    还是不准确,更准确表述为:
    楼主的证明方法只能证明以概率1存在无穷大同构子图,不能证明以概率1将所有的点都包括进来了,就象我证明随机实数与0.11111……以概率1同构的实质一样。

  • imsophia

    我是文盲,我不知道啥叫超限归纳,但是我觉得如果一个图边集是空的,另一个有边它们怎么能同构呢……

  • sss正和

    两个随机选取的n点有穷图同构的概率应当是随n的增长而减小直至趋于0的,如果到实无穷图时反而突变为以概率1同构,本身就否定了归纳法在这种情况下的适用性。

  • wuzhengkai

    @24
    选一个“n点同构子图”0.1…1,得到“n+1点同构子图”0.1…11的概率为1,这步如何归纳

  • pp

    首先我承认这个证明我没看懂。下面的文字只是就命题而言

    我认为出现争议的核心原因在于将“相等”应用到无限的时候所导致的矛盾。

    最简单的例子:设把硬币抛阿列夫零次为一次试验,则两次试验中正反面个数分别相同的概率为p。

    1.定义p(n)为把硬币抛n次,正反面个数一样的概率。
    我们可以定义p=p(n)|n->∞。p=0

    2.正面的个数是阿列夫零的概率为1,反面亦然。阿列夫零与阿列夫零相等。从而两个试验的结果相同的概率为1。

    这两种解释在似乎都没错。只是因为命题表达不严密(如何严密化??)所造成互相矛盾的结果。这篇文章应该是采取了后种解释吧。

    不过不知道大家对我前面提出过的“有限个1乘起来还是1;但无限个1乘起来就未必是1了”这一论点有何想法?

  • iceberg

    pp评论的有道理。严格地说,就是这样:
    样本空间为所有的随机图:{A:V(A)=N,E(A)=…}
    定义事件S为{A:∀U,V⊂V(A),∃x,x与U相连而与V分离},而将A的子集对编号为U_i,V_i后令事件S_i为{A:∃x,x与U_i相连而与V_i分离},则显然S=⋂S_i。
    我们的证明只给出了对每一个i,P(S_i)=1
    于是就有两个问题:
    各S_i未必互相独立
    aleph0个1相乘未必为1(概率论中的1都是极限意义上的)

  • sss正和

    [ZT]我现在想到一个证明,但仍有一个尾巴,等着老大的测度论。

    引理:两个可数个顶点的无穷图A、B都可以用自然数将全部顶点无遗漏地标上号。(不证自明吧)

    1、A{0}和B{0}是同构的,tsy所说的找不到归纳起点问题不存在,不过博主一开始就用了6个顶点的起点,是有点迷惑人的。

    2、然后,找到与A{0,1}同构的—假定为—B{0,5}
    3、接下来,从A、B中找出未取出的最小编号点,这里是B{2}
    4、接下来,找出与B{0,2,5}同构的—也是假定为—A{0,1,8}
    5、接下来重复第2步,这次找到的是A{2}
    6、重复第4步,找出与A{0,1,2,8}同构的—假定为—B{0,2,5,9}
    ……

    这样,如果每一步是必然事件而非以概率1找到下一个同构顶点,则A、B的任意顶点N都将在不迟于第2N步被取出,A、B同构被证明。

    可是,如果某一步就是找不到下一个同构顶点,而除此之外的无穷次寻找都能找到,似乎这个测度为零的事件不会破坏以概率1找到下一个顶点的说法。

    如果无穷次寻找中以非0概率发生1次找不到下个顶点的情况,就破坏了A、B同构概率为1的结论,但并不破坏每一步找到下一个同构顶点的概率为1的性质。

  • sss正和

    第3步找到的应是B{1},痴呆了~

  • Zealot

    pp 无限个1相乘 最简单的例子就是e=lim(1+1/n)^n (n->∞)

    sss 引理:两个可数个顶点的无穷图A、B都可以用自然数将全部顶点无遗漏地标上号。(不证自明吧) 这个是错的 存在不可数图的

  • wuzhengkai

    @35
    引理是对的啊,他只针对顶点可数

  • wuzhengkai

    @31、32
    很有道理,原来是证明任意连通性成立时,每次选点不是必然事件,而是概率为1,无限个1相乘未必是1.

    @35
    你那个例子有问题,这里的无限个1相乘未必是1,每个1的极限都要是1,而不是这串1的极限是1

  • windmeup

    用熵的思想去想,无穷的话肯定是均匀的.两个均匀的东西肯定是同构的.所以如果物理定律是一样的话,无数多个宇宙也肯定是同构的,如果他们无限大.

  • cervelo

    数学归纳法只适用于证明有限集的命题
    对于无限集数学归纳法是不适用的

  • qirenrui

    这个证明是错的,顶点个数未必可数

  • qirenrui

    还有,无穷多个概率为零的命题至少有一个成立的概率未必为零
    比如:对于正整数n
    n=1? n=2? … n=k? …

  • qirenrui

    实际上,n顶点图的连边方法有2^n(n-1),这个数远远大于n!
    另外,15L真相

发表评论