趣题:均匀分布且和为常数的n个变量

    不知道大家有没有幻想过,数学中是否存在这样一个牛B的问题,发表出来后十几年硬是没有一个人解开;后来某人惊奇地发现,它有一个极其精妙的解答,整个解决过程只需要几句话就能说清楚,但它实在是太巧妙了,这么多年就没有任何人想到。最近我就遇到了这样的事情。3月份UyHiP的题目非常有趣,整个证明几句话就完了,但想到解法的却只有一人。
    题目描述也极其简单。对于哪些n,存在一种生成n个随机变量的算法,使得它们在0和1之间均匀分布,且它们的和是一个常数?更进一步,如果这n个变量中任意k个都相互独立,满足要求的k最大是多少(表示成关于n的函数)?

    当然,这道题目我也没想出来。答案公布前,我思考了很久,最后还是放弃了。显然n是偶数时这样的算法是存在的,例如当n=6时,只需要先独立地选取3个随机变量X_1, X_2, X_3,然后令X_4 = 1 – X_1,X_5 = 1 – X_2,X_6 = 1 – X_3即可。这可以保证6个变量之和总为3,且它们均匀地分布在[0,1]区间里。但是当n是奇数时,满足要求的算法就未必存在了。例如当n=3时,不妨让X_1和X_2随机取,X_3等于1.5 – X_1 – X_2。这种算法似乎很和谐,问题就出在X_3有可能不在0和1之间。那么,重复执行该操作直到返回一个落在[0,1]里的X_3呢?这样的话变量又不是均匀分布的了,这将让变量更容易取到中间去,因为X_1和X_2太小或太大往往算不出合法的X_3(下图是Mathematica模拟的结果)。我试图从“n个变量的和的期望值是n/2”出发,证明和为1.5的3个变量不可能均匀分布在0到1之间。不过,最终还是没有找到突破口。


    在上面n为偶数的情况下,有n/2对不独立的变量。是否有可能每一对变量都互相独立呢?很多人估计想,这怎么可能,既然总和要求相等,各个变量之间必然会相互依赖、相互限制。而事实上,如果这些变量可以由第三方变量同时生成出来,上述矛盾很可能解决。一个经典例子就是,投掷一颗骰子,设结果为d,则变量x = d mod 2,变量y = d mod 3,虽然它们看似“有联系”,但显然它们是独立的,不管x等于多少,y=0、y=1、y=2的几率都是相等的,它的取值与x没有任何关系。从概念上说,有P(x)·P(y) = P(x∩y),这足以说明两者是独立的。巧妙利用这种关系,题目要求很可能达到。
    从题目上看来,不单是变量“两两”独立,即使任意三个变量互相独立、任意四个变量互相独立也是有可能的。我猜想k < n/2,不过也没有能证明到。     今天我看到答案,一下子就傻了……这么简单的解法,两个月了我居然一直没想到。     事实上,我的整个大方向都完全错了。除了n=1显然不行,其它情况下都存在均匀分布且和为常数的随机变量。当n=2时,取随机变量X_1,再令X_2 = 1 - X_1,这两个变量显然符合要求。当n=3时这个办法虽然行不通,但我们有很多别的办法。最巧妙的一种办法就是选取3个三进制小数使得它们同一位上的数各不相同。具体地说,从1开始枚举i,每次把0、1、2三个数字随机分配给X_1, X_2, X_3,作为它们各自小数点后的第i位。三个变量显然都均匀分布在[0,1]上,且它们的和总为1.1111111...,即十进制中的1.5。那么,当n>3时这个办法还管用么?其实我们根本不必考虑这个,因为对于更大的n,我们只需要把变量两个两个分成一组,并分别套用n=2的算法;若最后还剩了3个变量,再套用n=3的算法就是了。这样,对所有n>1的情况我们都给出了一种生成满足要求的变量的算法。
    更令人抓狂的是,对于后一个问题,事实上连k=2都办不到,其证明简单得实在是出人意料。考虑

X_1 + X_2 + X_3 + … + X_n = 常数

    等式右边的方差显然为0。假设变量两两独立,则和的方差就等于方差的和。单个变量的方差为,即1/12。n个变量之和的方差即为n/12。等式两边方差不等,矛盾。

16 条评论

  • qzstar1985

    bd
    orz

  • 严酷的魔王

    看开头我就想到了那个点猜想

  • wuzhengkai

    假设变量两两独立,则和的方差就等于方差的和。
    我也觉得不成立
    这句话没想到,概率没学好

  • a_1=[0,1)
    a_2=[0,1)

    a_n=[0,1)

    s=a_1+a_2+…+a_n

    x_1=a_1/s*c
    x_2=a_2/s*c

    x_n=a_n/s*c

    这样行么?

  • 数学迷

    你好,一个偶然的机会让我看到如下的网页
    http://www.qiji.cn/eprint/abs/3799.html
    费马大定理的证明,我太笨了,看不出他错在哪了,
    楼主数学那么好,是否可以看出此证明的错误来呢?等待你的指点。谢谢。

  • pp

    问题的第二个部分,假如把任意n个改为存在n个?

  • mcv

    确实有上百年都无人能够回答的经典问题:
    是否存在一个不共线的点集,其中任意两点所确定的直线上都存在点集中的其他点。

    最终找到解答时让人大吃一惊,因为实在是太简单了。

  • foreverleer

    楼上的问题纯属脑残……

  • ziyuang

    地壳的问题还要求是有限点集

  • skkd

    我觉得这个有点小问题.如果算法必须是有限步的,那就不可能是均匀分布.当然可以说本来一个真正生成均匀分布的东西就是不存在的,但是至少题目里暗示这样的[0,1]分布是可以获得的.

  • yang_bigarm

    果然是精妙的解答。

    n=3的情况,我一开始想的是在一个圆上均匀地随机取3个点(t1,t2,t3~[0,2Pi],{cos[t],Sin[t]}这样的点),然后做一个内接三角形,3个内角为x,y,z,则3个角之和x+y+z=180.接下来推而广之,到N边形的情况也有内角和为定值的情况。

    但是我用mathematia模拟的结果发现不满足均为分布,衰啊!

  • exp

    地幔 单位圆就行啊

  • 酱油

    对于N>1,都可以如法构造n进制小数啊…. 不用分组了。

  • zy498420

    “…当n=3时这个办法虽然行不通,但我们有很多别的办法。最巧妙的一种办法就是选取3个三进制小数使得它们同一位上的数各不相同。具体地说,从1开始枚举i,每次把0、1、2三个数字随机分配给X_1, X_2, X_3,作为它们各自小数点后的第i位。三个变量显然都均匀分布在[0,1]上…”

    请问3个变量为什么联合均匀分布在3维有限实数空间[0,1]上?明显只能在有理数域的一个子集(是一个商环或者叫剩余环)上联合均匀分布啊,或者说如果每一个数都写成分数形态,分母是3的-i次幂(i是这里的最大精度位数),则分子在伽罗华域(有限域)3的i次幂上均匀分布。

    而且如果这种方法看成是有限精度近似,也只对应于n是质数或者质数的幂才对,因为伽罗华域(有限域)的大小必须是质数或者质数的幂。

  • zy498420

    “…等式右边的方差显然为0。假设变量两两独立,则和的方差就等于方差的和。单个变量的方差为,即1/12。n个变量之和的方差即为n/12。等式两边方差不等,矛盾。…”

    随机变量两两独立,不代表他们n个一起独立(这不是互质的关系)。两个可以加,却不代表更多的变量也可以加起来。

    但是题目中的那个结论好像是正确的,一时半载忘记咋个证明了 抱歉 等我想想

发表评论

6  ×    =  24