主题：【翻译】概率随机及编程 （一） -- 东方射日

十月底被公司裁员，还算幸运吧，十一月中就拿到一个offer，谁说是contract的，但毕竟是有工作了，而且公司还是一个巨型的软件公司，应该对以后找工作有帮助吧。不过俗话说“骑驴找马”，这不，就继续找看看有没有permanent的职位，同时多找一些算法题做做，题海题海，说实在，还是题海最管用。

这不，找到一个好网站：Topcoder.com，上面有大量的算法的编程题，同时还有一些很不错的文章，推荐给大家看看。同时想自不量力，翻译一些文章给不喜欢（本人就是一个）看英文的人参考参考。对你有帮助呢，那就算我为大家在经济危机中多一条生路做一点自己的微薄贡献（当然鲜花是一定欢迎的）。如果有错误或不妥呢，也请高手不吝赐教，鲜花是一定会有的。

原文的链接在外链出处。看了一下，好像没有提到这些文章的版权问题，就先自作主张认为没有关系吧，如果大家发现有版权问题就请尽快来消息告知。

不过里面的很多例题都是有版权的，我们只能大致描述一下，具体的内容还是请大家注册一个帐号到上面去看吧。相信我，如果你是软件工程师，而且对算法感兴趣，这一定是值得的。

翻译中才发现翻译的困难，有的明明看起来很好理解的，用中文表达的话，还真就有点绕口。雅是不敢求的，不过翻完后，自己又都读了一篇，应该理解是不会有太大的困难吧，只希望“信”上不要有太大的差距。

在上述链接中有很多文章，我不敢保证有时间都翻译出来，有一篇算一篇吧。希望有人也愿意翻译其他一些文章。好吧，就随机地从这篇文章开始吧：

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities

概率随机及编程

作者：supernova

前言

有种说法，生活是概率的学校。概率论让我们的每一天都生活在风险评估中。假设有一个考试，总共有20门可能要考科目，而你只有时间准备其中15门。那么考了两门你都准备过了的科目的可能性是多少？这是我们生活的世界会带给你的一个简单的问题。生活是一个非常复杂的事件链，其中几乎每件事都可以想象成一定的概率。

赌博已经是我们生活的一部分，这其中显而易见牵涉到了概率。虽然赌博的历史可以追溯到史前时代，但是直到17世纪，随着近代数学基础的建立，才开始被研究。这始于一个Chevalier de M（一个经常通过赌博增加财富的贵族）向Blaise Pascal提出的一个简单问题：扔24轮骰子是否可以得到两个6点？

一些编程问题是由现实问题引申来的，通常我们会描述一些状态，并解释一些运行的规则。但你会发现如果这是一个概率相关的问题时，解决的方法就并不那么显而易见。这可能是因为在编程学习、竞赛中，概率经常被忽视而没有作为主要的研究点和考察点。

在采用一些必要的算法解决这类问题前，你必须有一些数学的准备知识。下一章将介绍概率的基本原理。如果你已经在这方面有点经验的话，也许你可以跳到下一章：概率计算。在那以后我们会对随机算法进行简单的讨论，随后列出了一些练习的题目。这最后一章也许是最重要的：练习！关键就是多练习。

基础

解决概率问题很像是在做实验，输出就是一个实验的结果，这包含其他一些不确定的因素。对于一个概率实验所有可能的输出，我们称为采样空间。每种可能的结果在采样空间中占且仅占据一个单位，通常用符号S代表。让我们考察如下实验：

扔骰子一次：

采样空间 S={1,2,3,4,5,6}

抛两个硬币：

采样空间 S=({正，正},{正，反},{反，正},{反，反})

我们定义我们实验一次为一个事件。这样，一个事件就是采样空间S的一个子集。如果我们用E来代表一个事件，那么有E S。如果一个事件仅包含一次采样空间的结果收集，那么我们称为简单事件。对超过一个结果的收集，我们称为复合事件。

事实上我们通常仅对某一特定事件的概率感兴趣，记为P(E)。我们定义P(E)是0到1间的一个实数。0表示这是不可能的事件，而1则表示确定事件。

我们前面说过任何一种结果都是采样空间中的一个单位，那么我们可以有如下公式：

P(E) = |E| / |S|

一种事件发生的概率是该类事件（特定结果发生）的次数除以各种可能事件（各种结果发生）的总次数。要理清事件之间的关系，我们可以应用集合的知识。例如考察扔骰子的实验，我们前面说到这实验的采样空间 S={1,2,3,4,5,6}

现在我们考察如下事件：

事件 A = '点数 > 3' = {4, 5, 6}

事件 B = '点数为奇数' = {1, 3, 5}

事件 C = '点数为7' =

A∪B ='点数大于3或为奇数' = {1, 3, 4, 5, 6}

A∩B ='点数大于3或为奇数' = {5}

A' = '事件A没有发生' = {1, 2, 3}

那么我们有：

P(A∪B) = 5/6

P(A∩B) = 1/6

P(A') = 1 - P(A) = 1 - 1/2 = 1/2

P(C) = 0

解决概率问题的第一步是定出采样空间，然后你就需要确定期望结果的数目。这就是传统的解决办法，但是具体的解决方法是多种多样的。例如在”Quiz Show”（例题都是有版权的，请自己登录网站看）问题中，解决的关键是考虑所有的可能性，这数目并不多。通过简单的分析，我们可以定义一下样本空间

S = { (wager 1 is wrong, wager 2 is wrong, you are wrong),

(wager 1 is wrong, wager 2 is wrong, you are right),

(wager 1 is wrong, wager 2 is right, you are wrong),

(wager 1 is wrong, wager 2 is right, you are right),

(wager 1 is right, wager 2 is wrong, you are wrong),

(wager 1 is right, wager 2 is wrong, you are right),

(wager 1 is right, wager 2 is right, you are wrong),

(wager 1 is right, wager 2 is right, you are right) }

该问题要求你找到你最有可能获胜的下注额，为了计算一定下注额的获胜概率，我们可以分别计算8种情况下各人的最后得分。以下程序可以进行这个计算：

int wager (vector scores, int wager1, int wager2)

{

int best, bet, odds, wage, I, J, K;

best = 0; bet = -1;

for (wage = 0; wage ≤ scores[0]; wage++)

{

odds = 0;

// in 'odds' we keep the number of favorable outcomes

for (I = -1; I ≤ 1; I += 2)

for (J = -1; J ≤ 1; J += 2)

for (K = -1; K ≤ 1; K += 2)

if ( scores[0] + I * wage > scores[1] + J * wager1

&& scores[0] + I * wage > scores[2] + K * wager2) { odds++; }

if (odds > best) { bet = wage ; best = odds; }

// a better wager has been found

}

return bet;

}

另外一个很好的例子是“Pipe Cuts” 。这也可以用类似的方法解决。对这类只有有限可能（且数目不是太大）的情况，我们可以利用这种穷举法计算。

对于一系列独立事件：E1，E2......EN，有两个经常会提到的问题（应该你们也已经遇见过）：

一：所有事件发生的概率是多少？

二：至少一事件发生的概率是多少？

要回答第一个问题，我们可以先考虑第一事件E1发生的概率，如果E1不发生，上述一将永远不会满足。那么我们可以确定必须有E1以P(E1)的概率发生了——即有P(E1)的可能性——我们才需要继续检查下一事件（E2）。而E2发生的概率是P(E2)，接着我们就可以重复这一步骤。正如我们上面说到概率是用0到1间的实数定义的，那么显然我们可以用以下公式计算所有事件发生的概率：

P(all events) = P(E1) * P(E2) * …... * P(EN)

对于第二个问题，更容易的方法是计算任一事件都不发生的概率。（也就是说有反事件发生的概率）我们可以有：

P(at least one event) = 1 - P(E1') *P(E2`)*......* P(EN')

这两个公式非常重要，请在继续下一章前理解他们。

• 【翻译】概率随机及编程 （二）
• 我也不认识