阅微堂 » 科学 http://zhiqiang.org/blog 科学，人文，民主 Sun, 05 Oct 2008 05:03:35 +0000 http://wordpress.org/?v=2.6.2 en 概率论感觉测试 http://zhiqiang.org/blog/posts/test-on-probability.html http://zhiqiang.org/blog/posts/test-on-probability.html#comments Mon, 29 Sep 2008 12:44:56 +0000 zhiqiang http://zhiqiang.org/blog/posts/test-on-probability.html 所有大学生都应该学的两门课程，一是经济学，二是概率论，这两门课分表代表着一种生活中的思维方式。来测试一下你的概率论学得怎么样吧。题目作者: wzz12346@newsmth, 原发Mathematics@newsmth。解答亦来自wangzz。题目顺序和答案经过调整。

如果有题不会的话，就用你的直觉吧，看看最后你的直觉与真实的概率相差有多大。

解答颜色为白色，在每个题目下面，选中即可显示。

  1. 在打桥牌的时候，如果你和对家共持有某门花色的9张牌，则剩余的4张牌怎样分布的概率最大   
          A.  2-2
          B.  3-1
          C.  4-0
    B. 可以简单计算得到这个结果。3-1的概率应该是50%。2-2的概率是37.5%。4-0的概率是12.5%。
      
  2. 如果有3个门，有一个背后有大奖。你选中一个，主持人知道哪个门后面有奖，并且总会打开另外两个中的某个没奖的。现在你有一次换得机会，你应该
          A.  换
          B.  不换
          C.  换不换都一样
    A，三门问题，详细情况见三门问题及相关

  3. 100个球随机的放在100个箱子里，最后空箱子的数量大约是
         A.  0-10
         B.  10-20
         C.  20-30
         D.  30-40
    D. 这个题可以用简单的概率论计算。结论是不管多少个球，c*n个球放到n个箱子里，最后空箱子的个数约为n(1-1/n)^{cn}=ne^{-c}，现在的情况是箱子数和球数一样多，那么就约为100e^{-1}.
     
  4. 打10000副拱猪，总共持有9500-10500个A的概率大约在        
          A.  80%-90% 
          B.  90%-95% 
          C.  95%-99% 
          D.  99%以上
    D. 这个可以用中心极限定理计算。事实上这个题也不需要计算，只是要考察大家的一个感觉，实际上这个概率大于0.99...9，一共有9个9。不过有时候我们打牌仍然觉得牌总是很差。  

  5. 台湾大选，假定马英九最终得到600000票，谢长廷得到400000票，如果一张一张的唱票，则过程中马英九一直领先谢长廷的概率为 
          A.  0.1 
          B.  0.2 
          C.  0.3 
          D.  0.4
  6. 有以下几个国家，每个国家有自己的习俗。问哪个国家长期以后男人的比例最大  
          A.  每个家庭不断的生孩子直到得到第一个男孩为止 
          B.  每个家庭不断的生孩子直到得到第一个女孩为止 
          C.  每个家庭不断的生孩子直到得到一男一女为止 
          D.  以上几个国家最后男女比例基本一样
    D. 我们只需要考察一个家庭最后产生多少男女即可以。用概率的方法可以得到不管哪个方法都是1:1。事实上，我们只是把一个很长的男女的序列按照不同的方式来截断。当然这个序列本上包含多少男女是不变的。我每次都愿意以另外一个例子来说明，那就是如果我们在网上下棋，可以每天下到第一盘输为止或是第一盘赢为止或是有输有赢为止，显然不管怎样，因为你的实力是恒定的，你永远都是你本来应有的胜率。
      
  7. 给一个1到100的排列，与原来位置相同的数字的个数的期望大约是 （如1到5的排列51324 与原来位置只有3是相同的）    
          A.  1
          B.  5
          C.  10
    A. 在第1个位置，这个排列的第1个数字为1的概率为1/100，而期望是可加的，所以总共与原来位置相同的数字的个数的期望应该是1。也就是说不管是多少的数字，平均恰好有一个数与顺序是相同的。 
      
  8. 美国的25分硬币共有50种，上面有50个州的图案，如果我们每次得到的硬币是随机的，则期望大约收集多少可以收集全   
          A.  200
          B.  300
          C.  400
          D.  500
    A. 这是所谓的收集硬币问题。具体解法不是很容易。不过结论是要收集齐n种硬币，需要大约\sum_{i=1}^n\frac{n}{i}=n\log n个。
      
  9. 假设有1000次100m短跑大赛，每次比赛的冠军成绩都在9.7-10之间均匀分布，问期望有多少次比赛打破了之前的纪录   
          A.  7
          B.  10
          C.  15
          D.  32
    A. 假设均匀分布,则最后n次比赛之后这n个成绩形成一个排列。第k次创纪录的概率是这个排列中第k个在前k-1个之前的概率，也即1/k，所以n次比赛大约有1+1/2+1/3+...1/n=\log n次破纪录。
      
  10. 扔10000次硬币，其中最长一次连着正面的次数大约会是多少   
          A.  100
          B.  13
          C.  9
          D.  4
    B.这也是一个特殊的概率问题，叫做Head Runs。答案应该是log_2^n。大约为13。或者大于13是显然的，但不太可能有100。所以必定是选B。
      
  11. 以下那件事情发生的期望时间最短   
          A.  在第0秒，一个物体从原点出发，每一秒以概率1/2向左走，1/2向右走，第一次回到原点的时间
          B.  一只猴子，每秒种随便按键盘上的一个键，第一次打出"Beijing Welcomes You"的时间
          C.  在第0秒，一个物体从原点出发，每一秒以概率1/2向左走，1/2向右走，第一次到达1的时间
    B. A和C两个事件发生的时间的期望都是+inf. 只有B是有限的。A和C说明了等概率的赌博不可能赢钱（如果C是有限的则参加赌大小的游戏总能赢钱了）。而B说明的是另外一条概率上的定理,"What always stands a reasonable chance of happening will almost surely happen, sooner rather than later",也就是说从任何时刻开始，总有一个固定的概率发生的事情(比如一个猴子打出beijing welcomes you, 这个概率可能是 1/26^20左右)，不过这个概率是多少，这件事情早晚能发生。
          
  12. 如果一个物体在3维随机游动，也即每一刻他可以向左，右，上，下，前，后等概率的走，长久来看，则会发生什么情况   
          A.  此物体无穷多次回到原点
          B.  此物体无穷多次回到任何一条坐标轴上，但不会无穷多次回到原点
          C.  此物体不会无穷多次回到任何一条坐标轴上
    B. 1维和2维的随机游动是常返的，也就是说会无穷多次回到起点（但回来的平均时间期望是无穷的），而3维以上的随机游动是非常返的。因此对于2维德某改革坐标，此物体会无穷多次经过，但是不会无穷多次经过原点。对一个完全没有方向感的人，在平面上不会迷路，但在宇宙中是会迷路的。
       
  13. 一支股票，初始价为1，每天的价值变化率独立同分布，且期望为0，不恒为0。则
          A.  股票在任何时刻期望价值为1
          B.  股票以概率1变成0
          C.  A和B都对
          D.  A和B都不对
    C. 也就是说对于很多投机的东西，平均值总是不变的，但是多数人都会倾家荡产。其实仔细想想很有道理，比如说你的股票第一天涨10%。第二天跌10%或是第一天跌10%，第二天涨10%，最后的结果都是跌了1%。所以要保持增长所需要的是远大于0的平均变化率，这个才是一般人难以做到的。
      
  14. 如果一个群体里，每个个体以0.2的概率没有后代，0.6的概率有1个后代，0.2的概率有两个后代，则
          A.  这个群体最后会灭绝 
          B.  这个群体最后将稳定在一个分布，即种群大小在一定范围内震荡 
          C.  这个群体最后将爆炸，人口将到无穷 
          D.  不一定会发生什么
    A. 这是个简单的人口模型。这个可能直觉比较困难，但是这个实际上和上次的一道题是一样的。注意到每一代的期望总是1。因此根据上次的答案，这个群体最后会灭绝。对于这种模型，当每一代的期望小于等于1时，最后的结果都是会灭绝。对于期望大于1的情况，我们也可以很简单的通过解方程得到灭绝的概率。 
     
  15. 当我们考虑一种可能重复发生的事件时，哪种方式更科学   
    A.  按照第一次发生这个事件的时间作为一个起点，考虑从其本身出发之后的性质
          B.  按照最后一次发生这个事件的时间作为一个起点，考虑从其本身出发之后的性质
          C.  以上都可以
          D.  以上都不可以
    A. 这个问题深一些的背景在于Kolmogorov向前向后微分方程。很多人知道向后微分方程更通用，但是并不知道原因。事实上，向后微分方程是基于A的方法对事件进行分解得到的，而向前微分方程是基于B的方法对事件进行分解的。但是有很多重复发生的事情会越发生越频繁，以致没有最后一次发生的事件。但是我们总能找到第一次发生的时间。所以A更科学。 
         
  16. 实验室测试灯泡的寿命，在灯泡不断的换新灯泡。灯泡寿命约为1小时。考察10000小时时亮着的那个灯泡    
          A.  那个灯泡的寿命期望也约为1小时 
          B.  那个灯泡的寿命期望约为其他灯泡的2倍 
          C.  那个灯泡的期望寿命约为其他灯泡的1/2 
          D.  以上说法都不对  

    B. 这个题可能是稍难的。如果具体的算需要一点本科高年级的知识。不过我们仍然可以从直觉得到结果。事实上，当每个灯泡或是我们观测的事物的生命是随机的时候。在时间足够久以后的一点，那个事物的寿命要长于这个事物本身平均的寿命。因为正是因为它寿命长导致我们容易观测到。简单的说，如果灯泡有两种，一种只能坚持1小时，一种能坚持100小时，那我们在后面观测到的99%都可能是100小时那个。所以观测到的平均寿命较长。通常我们认为灯泡的寿命是指数分布的，在这个情况下，答案是2倍。对于一般的分布，甚至有可能平均寿命有限，而观测的那个寿命期望是无限的。这个问题在美国一次监狱调查中被发现，即被调查的囚犯的平均判刑年数要远大于全美平均判刑的年数

相关文章

  • 三门问题及相关
    写篇三门问题的终结版。欢迎补充材料。 三门问题，亦称为蒙特霍问题（英文：Monty Hall problem），最初的表述形式： 参赛者会看见三扇关闭了的门，...
  • 快来测试你的脑年龄
    从+0那看来的。主要测试快速记忆能力。 我第一次29（注意得分越小越好，奇怪的设定），目前个人最好成绩为20。大家来试试看吧，留言留成绩者注意...
  • 杀人的理论分析
    “杀人”，英文名为"Mafia Game"，广泛流传于国内外。上个星期我们在玩的时候被Elchanan Mossel发现，然后他给了一个talk，内容就是杀人的理论分析。 ...
  • Google的疯狂面试题
    有一些是火星题，比如最后一个海盗分金，不太可能还用来作为面试题，估计是被拉过来凑数的。 原文（英文）直接到这里看吧，27floors给出了中文翻...
  • 帽子游戏二
    这个题目听说是MSRA的面试题。 在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参...

© zhiqiang for 阅微堂, 2008. | 链接 | 24 条评论

]]> http://zhiqiang.org/blog/posts/test-on-probability.html/feed 递归算法的复杂度 http://zhiqiang.org/blog/posts/complexity-of-recursive-algorithm.html http://zhiqiang.org/blog/posts/complexity-of-recursive-algorithm.html#comments Sat, 27 Sep 2008 06:26:46 +0000 zhiqiang http://zhiqiang.org/blog/?p=852 递归算法的复杂度通常很难衡量，一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大，如果我们可以保存每次子递归的结果的话，递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。

看一下下面这个算法题目，据称是百度的笔试题：

简述：实现一个函数，对一个正整数n，算得到1需要的最少操作次数：

如果n为偶数，将其处以2；如果n为奇数，可以加1或减1；一直处理下去。

要求：实现函数（实现尽可能高效）int func(unsigned int n)；n为输入，返回最小的运算次数。

我不确定是不是对n的操作次数有一个简单的刻画，尝试着想了一会儿，似乎不太容易想到。但后来发现这个题目本质上不是算法题，而是算法分析题。因为仔细分析可以发现，题目中给的递归构造本身就是非常高效的。

直接按照题目中的操作描述可以写出函数：

int function(unsigned int n) {
  if (n == 1) return 0;
  if (n%2 == 0) return 1 + function(n/2);
  return 1 + min(function((n + 1)/2), function((n - 1)/2));
} 

在递归过程中，每个节点可以引出一条或两条分支，递归深度为\log n，所以总节点数为n级别的，但为何还说此递归本身是非常高效的呢？

理解了动态规划的思想，就很容易理解这里面的问题。因为动态规划本质上就是保存运算结果的递归，虽然递归算法经常会有指数级别的搜索节点，但这些节点往往重复率特别高，当保存每次运算的节点结果后，在重复节点的计算时，就可以直接使用已经保存过的结果，这样就大大提高了速度（每次不仅减少一个节点，而且同时消灭了这个节点后面的所有分支节点）。

在这个问题里是什么情况呢？仔细分析就会发现，在整个搜索数中，第k层的节点只有两种可能性n>>k和n>>k - 1。这意味着整个搜索树事实上只有2\log n个节点。所以这个递归算法本质上的运算复杂度只有O(\log n)。这已经是最优的了。

相关文章

  • 求平方根倒数的算法
    下面这个求$$1/\sqrt{x}$$的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。 float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&x...

© zhiqiang for 阅微堂, 2008. | 链接 | 8 条评论

]]> http://zhiqiang.org/blog/posts/complexity-of-recursive-algorithm.html/feed 一个简单图的三染色算法问题 http://zhiqiang.org/blog/posts/3-color-a-simple-graph.html http://zhiqiang.org/blog/posts/3-color-a-simple-graph.html#comments Thu, 25 Sep 2008 06:57:19 +0000 zhiqiang http://zhiqiang.org/blog/?p=851 注: 这个问题来自China Theory Week 2008的Open Problems Session。

我们知道在数学里证明一个东西的存在性的时候，有时候只证明了“存在性”，而且在证明过程中并没有说明如何找到它，这种证明方法被称为“非构造性证明”。有些流派的数学家对这种证明方法非常不满，具体这里就不详谈了。

这里要说的是，一个玩意儿，即时你知道它总是存在的，它也是可以算出来的，但是不是就一定能够很快的比如在多项式时间之内算出来呢？

Game Theory已经证明了在两人非合作博弈中，纳什均衡总是存在的，但是如何计算它确被证明是PPAD-hard的，一个被猜测不属于P的复杂类。

纳什均衡的计算问题不太好理解，下面介绍一个问题，描述比较简单非常容易理解。它有类似的效果，存在性可在数学上被证明，但如何计算它却不知道，复杂性也未知。

输入：一个3n点的图，顶点构成一个正3n边形，以及它们之间的6n条边。其中3n条为多边形的边，另外3n条边构成n个顶点互不重合的三角形。下图为一个n=3的例子。

输出：这个图的一种三染色方案（给定点染色，使任何有边相连的顶点都不同色）。

相关文章

  • 点染色问题
    继上次的硬币游戏（解答在此）之后，Sariel又出了一个有意思的题目。 给定平面上若干个点。证明总存在一个黑白染色方法，使得对于平面上任何一个...
  • 实数上的可数颜色染色问题
    命题：实数集$$\mathcal{R}$$上的任何一个可数种颜色染色方案，都存在四个不等的同色点$$x, y, z, w$$使得$$x+y=z+w$$。 这个问题是一个月前在Computational C...

© zhiqiang for 阅微堂, 2008. | 链接 | 4 条评论

]]> http://zhiqiang.org/blog/posts/3-color-a-simple-graph.html/feed 求平方根倒数的算法 http://zhiqiang.org/blog/posts/inverse-square-root-algorithm-analysis.html http://zhiqiang.org/blog/posts/inverse-square-root-algorithm-analysis.html#comments Fri, 19 Sep 2008 04:10:28 +0000 zhiqiang http://zhiqiang.org/blog/posts/inverse-square-root-algorithm-analysis.html 下面这个求1/\sqrt{x}的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。

float InvSqrt (float x){
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    y = *(float*)&i;
    y = y*(1.5f - xhalf*y*y);
    return x;
}

我们这里分析一下它的原理（指程序的正确性，而不是解释为何快）。

分析程序之前，我们必须解释一下float数据在计算机里的表示方式。一般而言，一个float数据x共32个bit，和int数据一样。其中前23位为有效数字M_x，后面接着一个8位数据E_x表示指数，最后一位表示符号，由于这里被开方的数总是大于0，所以我们暂不考虑最后一个符号位。此时

x=1.M_x 2^{E_x-127}

如果我们把计算机内的浮点数x看做一个整数I_x，那么

I_x = 2^{23}E_x+M_x

现在开始逐步分析函数。这个函数的主体有四个语句，分别的功能是：

int i = *(int*)&x; 这条语句把x转成i=I_x。

i = 0×5f3759df - (i>>1); 这条语句从I_x计算I_{1/\sqrt{x}}。

y = *(float*)&i; 这条语句将I_{1/\sqrt{x}}转换为1/\sqrt{x}。

y = y*(1.5f - xhalf*y*y); 这时候的y是近似解；此步就是经典的牛顿迭代法。迭代次数越多越准确。

关键是第二步 i = 0×5f3759df - (i>>1); 这条语句从I_x计算I_{1/\sqrt{x}}，原理:

令y=1/\sqrt{x}，用x=(1+m_x)2^{e_x}和y=(1+m_y)2^{e_y}带入之后两边取对数，再利用近似表示\log_2(1+z)\sim z+\delta，算一算就得到

I_y = \frac{2}{3}(127-\delta)2^{23}-I_x/2

若取\delta=0.0450465679168701171875，\frac{2}{3}(127-\delta)2^{23}就是程序里所用的常量0×5f3759df。至于为何选择这个\delta，则应该是曲线拟合实验的结果。

相关文章

  • 递归算法的复杂度
    递归算法的复杂度通常很难衡量，一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大，如果我们可以保存每次子递归的结果的话...
  • 算法百科全书 - Encyclopedia of Algorithms
    Xie Xie推荐了一本今年出版的一本新书，Encyclopedia of Algorithms，全书1200页，涵盖各类有名问题的算法，概率算法，近似算法，量子算法等。 翻了一下，...
  • 有序矩阵的中位数算法
    给定$$n\times n$$的实数矩阵，每行和每列都是递增的，求这$$n^2$$个数的中位数。 使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数...
  • Perfect Shuffle的算法
    珍爱生命，远离政治。我们继续讨论算法。 2008/04/01补充：此算法有重大缺陷。详情请见留言部分。 一年前，我们讨论过一个算法问题，perfect shuffle，...
  • 素数筛法的复杂度
    Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。 所谓素数筛法就是那个求小于n的...

© zhiqiang for 阅微堂, 2008. | 链接 | 15 条评论

]]> http://zhiqiang.org/blog/posts/inverse-square-root-algorithm-analysis.html/feed 高等理论计算机I http://zhiqiang.org/blog/posts/advanced-theoretical-computer-science-i-lectures.html http://zhiqiang.org/blog/posts/advanced-theoretical-computer-science-i-lectures.html#comments Fri, 19 Sep 2008 02:06:48 +0000 zhiqiang http://zhiqiang.org/blog/posts/advanced-theoretical-computer-science-i-lectures.html 姚期智教授给清华大学新入学研究生开的一门课，课程内容

在经典计算复杂性方面：NP完全性，多项式空间复杂性，对数空间复杂性，交互式证明系统，随机复杂性，去随机化，概率检验证明系统，电路复杂性，通信复杂性，判定树复杂性等。在量子计算复杂性方面将包括：量子计算模型，量子电路，量子Fourier变换算法，Shor算法，Grover量子搜索算法，量子纠错码，冯诺依曼墒等。

从这里可以看出理论计算机的一些主要的方向。按照姚先生的说法，这些是做理论的学生，多少都应该知道一点的东西，这样跟别人讨论的时候才不会embarrass。Researcher不应该局限于自己所专注的领域，眼界要开阔; 这也是开这门课的主要原因。

参考教材

[1] Complexity Theory: A Modern Approach, Sanjeev Arora and Boaz Barak.
[2] Quantum Computation and Quantum Information, Michael Nielsen and Isaac Chuang.
[3] Lecture nots: Quantum Computation, instructor Umesh Vazirani

这门课有I，II两个学期。这个学期主要讲量子计算和量子信息的一些东西吧。我恰好跟着写一些关于量子的东西放到这里，当然都是简单介绍性质的，目的是大家看了之后，对一些NC的东西有简单的辨别力，比如新浪科技的这篇瑞士实验显示量子信息传输速度远超光速。

相关文章

© zhiqiang for 阅微堂, 2008. | 链接 | 1条评论

]]> http://zhiqiang.org/blog/posts/advanced-theoretical-computer-science-i-lectures.html/feed