求助：一个概率问题

xyh · 发表于 2009-2-19 07:30:44

假设美国有1000万人很想发财，想变成百万富翁，而此时世界首富比尔盖茨心血来潮，要从这1000万人中选10个人，每人发送100万美元。

这样的好事真不错。但是为保证其公平性，我们必须随机的而且是等概的从这1000万人中选取10人。例如，我们的可以给每个人发一个唯一个号码。这样我们就有了1000万个不同的数字。这1000万个数字我也可以存放在电脑中，可以用程序随机的选取。电脑的选取可以保证随机，但是能保证等概吗？

你能否设计出一种可行的方案，保证尽可能的公平，也就是尽可能的让每个人都有相同的被选中的概率？

（可以用电脑程序编写）

我个人认为似乎不可能。不知道这里网友有没有好方法。

把此题延伸一下：一副连号的新扑克牌，你尽最大的可能性洗乱它，使之达到随机性最强（最等概），那么是不是洗的次数越多就越好？

yinyin · 发表于 2009-2-19 08:51:55

现实中是无法做到“绝对”等概率的，但可以做到当前世上几乎无人能够确有把握地（因而令人信服地）指出某个号码比另一个号码出现的概率大。

用电脑来实现您的公平抽奖是最方便的。先将这1000万人按任意方式排号，从０到9999999。利用许多软件里都带有的随机数发生器产生十个在 [0, 1) 区间里均匀分布的具有十进制７位以上有效数字的随机数。尽管它们仅是伪随机数，但能通过现今世上统计学教科书中介绍的任何随机性检验（按最苛刻的常用信度）。取这十个伪随机数的前７位，对号入座就是了。

至于您的延伸，理论上讲，当然是洗的次数越多，“随机性”越高。但洗过三四遍（间中再随机分叠几次）后，再多洗已无实际上的意义了。

idiot94 · 发表于 2009-2-19 12:06:31

斗，里面有许多经过严格检查的均匀的完全相同的硬币，然后斗被拉翻后，这些硬币一起掉到一个光滑的漏斗里面，然后依次落到一个匀速移动的传送带上，这样正反面产生的二进制代码应该是比较好的随机数列了。

xyh · 发表于 2009-2-20 05:44:04

哈哈，果然不出我所料，发此题时，我想应该会有高手出头。

yinyin的回复，我没有完全看懂，回头再花点时间消化消化。我大概了解了一下，可以用电脑程序中可以产生一个随机数字。例如可以在1~100之间随即的选取一个或者一系列数字。这些数字的选取是随机的，但是是不是等概的，我就不清楚了，根据上面yinyin的回复。似乎应该有方法产生等概数字。

在电脑中随即产生数据，我们需要事先提供一个数字，这个数字称作seed(中文如何翻译我不清楚)。有了这个seed，就可以随即的产生一系列数字（你想要在什么范围内就在什么范围内；你想要几个就给你几个）。这些数字是什么样的随机分布方式我不大清楚。但是有一点很有趣，那就是如果你给出相同的seed，那么一定可以产生相同的系列数字。这一点我不大明白，不知道为什么会这样，我想一定是什么地方我没有弄清楚。

关于洗牌问题。是因为我看了一篇关于滚屏抽奖方式是否合理的文章而来。这篇文章部分段落摘录如下，不知道yinyin，idiot94对此有何看法？

***********************

…… 要做到1000个万备选号码被抽中的几率尽可能等概，其实并不是一件容易的事，你当然可以用几行程序就设计一个随机选号程序，但要你证明这么多的备选号被选中的概率相同，恐怕就不容易了……

再往深里说，试举一例，一副连号的新扑克牌，你尽最大的可能性洗乱它，使之达到随机性最强（最等概），那要洗多少次呢？我们的第一感觉是洗得次数越多就越好，但事实并不是这样，早已经有人做过了这样的仿真计算，答案是7次。再洗的话其随机性反而退化了。当然，这个次数与洗法是密切相关的，这个
数字并不重要，重要的是它在技术层面上给滚屏抽号的公平性提出了一个新的问题：假使我们之前设计了一个尽可能随机并公平的抽号程序，在这个基础上，我们再假设两种情况：情况1：程序其实不考虑嘉宾的喊停时间，那个中奖号已经靠那个尽可能随机公平的抽号程序选好了，无论嘉宾何时喊停，都会蹦出那个号。
情况2：程序把嘉宾喊停的时间作为加扰的一个参数，最后被选的号与喊停时间相关。结论是情况1更公平，虽然情况2多了一个加扰参数，但它的随机性反而退化了，就跟那副牌洗了第8次一样。这是密码学中的一个重要问题，有着非常重要的现实意义，在二战期间，德国的密码机令英国很头痛，英国人根本破译不出来，没想到德国为了增加安全性，多加了一个齿轮，结果反而被英国破译出来了，因为多一个齿轮加扰后随机性不增反减了……

idiot94 · 发表于 2009-2-20 08:34:00

我们一个一个来讨论：

1）您关于电脑产生的随机数的问题是这样的: 一般电脑里面使用的随机数发生器都是所谓线性同余法，这个算法很简单，运算次数很少，很经济，而且线性同余产生的伪随机数（注意：yinyin 老师也不断强调计算机的随机数都是伪随机数，这一点很重要，也就是说，这些数列其实不是随机的，正如你观察到的，给定一个种子，你永远会得到同样的数列），具有很好的统计属性，也就是说，它产生的伪随机数列满足很多“真正”随机样本应该满足的统计性质，这些是通过统计测验来验证的。线性同余产生的基本数列是均匀分布的，也就是您说的“等概率的”。一个简单的改进线性同余的种子问题的办法就是用机器时间来把种子“随机化”，这样用户就不会看到同样的结果了。

在工程中，有很多大型的项目需要很强大的伪随机数列，线性同余不能满足其要求了，还有更加高级的伪随机数发生器，但是根本上，他们仍然还是*伪*的，也就是说，他们只是看起来象是随机的而已，当然这是可以理解的，计算机要是有什么计算结果真的是随机的，恐怕也就坏了。关于线性同余法，您可以自己google一下，就可以有很多文献。

2）那么什么是“真正的”随机呢？这个问题，我曾经写过一点东西，贴在文学城的脑瘫里面了，有兴趣的话，可以去看看，我记得题目叫做“什么是概率”，主要是为了介绍现代概率论的来源，前面几节谈了谈关于所谓“物理”随机的想法，不一定对，仅供参考：）。这里顺便说下，我的前面的回答为什么要用猴子，因为即使是想抛硬币这样看起来“随机”的事情，对于一个高手（比如魔术师）来讲，也未必是随机的----事实上，无论是“洗牌”，还是“抛硬币”，魔术师都可以完全控制他们的结果。但是对于一个就是为了拿到香蕉的猴子来说，这种控制的可能性大概就比较小了。

3）对于您提的洗牌的问题，我不明白什么叫做“等概率”的结果？54张牌随便什么排列有什么区别吗？为什么“全部理好”就不是“等概率”的呢？我看不明白您的引文，主要是原作者没有给出什么叫做“等概率”的54张牌的明确定义。而且，这个好像也没有什么“约定俗成”的简单解释。

4）至于抽奖的问题，如果没有主动作弊，那么等概率的随机性是可以保证的。方法很简单，就比如说猴子抛硬币，正反两面的出现概率（完全均匀的硬币）就是相等的。这个就是最基本的0/1，从这个就可以构造出任何离散的随机结构。至于摇滚筒，只要各个数码之间的距离，所占的空间都是相等的，滚筒是很均匀光滑的圆柱，没有主动作弊，那么结果也是等概率的（各个数码被选中的概率相等）。

yinyin · 发表于 2009-2-20 10:27:41

同意94兄的看法，新新所引述的东西似是而非，看来不是出自数学专业人士之手。

（１）文中“随机性”不是一个数学概念。

新新能否找一找原文对“随机性”的确切定义以及相应的量化方法？在我过去的讲课中，从没拿它用来作为概率论中的一术语。人们通常所理解的“随机性”实际上是蕴含在概率分布中的，例如，人们会说”按xx分布随机地抽取...”。倒是另一个术语“熵”，它是用来描写一个离散概率分布的不确定性大小的。给定有限样本空间，其上的均匀分布具有极大熵。

（２）洗牌：似是而非的“再洗的话其随机性反而退化了”这一说法会误导读者。

原文中“使之达到随机性最强（最等概）”意思不明。没说清楚哪些事件的概率相等才叫“等概”。所谓的“仿真计算”，看来只是按某一确定的方式来重新排列那些牌，而非真正的随机洗牌。当然，正象引文中所说，这样必然会得出“这个次数与洗法是密切相关的”结论。下面的简单例子就可看出所谓的“仿真”，其实一点也不仿真。

有一叠四张牌编号依次为１，２，３，４。现按下法来“洗”：先分成左右两叠，（１，２）和（３，４），再按先左后右一一相插，得（１，３，２，４）。这就算“洗”了一次。它们的次序看来是乱了一点。但若按上法再“洗”一次，结果就回到（１，２，３，４）。这大概就是引文中所说的“再洗的话其随机性反而退化了”。

（３）从所说密码机一例，还看不出它跟概率论有什么关系。能否更详细地解释一下？

xyh · 发表于 2009-2-23 23:54:46

这么一解释清楚了很多。另外我把idiot94 在文学城的那篇文章转过来了

。希望 i 兄不要介意。这几天忙无法坐下来认真读，回头有时间了一定好好学学。

只需填入未经注册笔名 · 发表于 2009-2-24 01:36:08

选中我　＝＝＞　公平，　否则不公平

		自动登录	找回密码
密码			立即注册

动态微博

求助：一个概率问题

回复：求助：一个概率问题

大概可以让一个猴子来试试，比如，让它拉动一个连着香蕉的

回复：求助：一个概率问题

嗯，您的引文中间那些话似是而非，好像不是很明白，这样吧，

回复：回复：求助：一个概率问题

谢谢楼上两位高手

简单