这个学期上了Prof. Sheldon Ross的<Elements of Stochastic Processes>，总算是把本科阶段时曾经粗浅地接触过、但是现在早已忘掉绝大部分的概率论知识给重新捡起来了。自我感觉概率论的水平有不小的提高，于是决定趁热打铁整理一下笔记，写下这篇小文章。

随机变量是一座桥梁，它的一端是这个世界上的各种或复杂或简单的随机现象(不确定性是这个世界的本质之一)，另一端是包括代数计算在内的各种数学工具。对于随机现象，我们可以定义一个随机变量，针对每一种可能出现的结果，我们都可以给这个随机变量赋予一个取值，这样一来，我们就能够运用数学的力量来对这个世界的随机性进行分析。很多时候，我们关心的是平均值，我们有下面四种方法来计算随机变量的期望值(均值)：

(1)式是随机变量期望值的定义式。由于使用这一公式需要知道该随机变量的概率质量函数——当你已知其概率质量函数时，你可以求出包括期望、方差等在内的所有统计值——而在复杂的现实世界中我们很难得到一个变量的分布表达式（甚至很多时候连求出均值都显得困难），因此该式使用相对较少。

(2)式表明，当一个随机变量可以表示成若干个随机变量之和的形式时，它的期望即为这些变量的期望之和。当一个随机事件可以拆解成具有先后顺序的子事件时，这一表达式很有效。

(3)式是计算期望值最常用的式子，实际上，「条件于(conditioning on )」是概率论体系中最为核心的技术之一。在分析现实世界的随机现象时，如果你能够获取额外的信息，这便意味着一些本是未知且随机的元素不再随机，而是成为了确定性因素，这将影响你原本的分析计算结果。

(4)式又叫条件恒等式(Conditioning Identity)，是同时应用了(1)(3)两式得到的，根据求随机变量函数值的期望值的公式，我们有

注意到是随机变量的函数值(仍旧是一个随机变量)，它表示，当变量取不同的值(这是随机事件)时，变量的期望值(这是一个数值)也随之变化，这正是随机变量的定义(由某一随机现象得到某一对应的数值)，因此，是一个随机变量。

下面我们通过一些例子来展示这四个式子的运用。

一系列相互独立的试验，每次试验成功的概率都是，用随机变量表示出现第一次成功试验时所需要的试验次数，其概率质量函数为。这样的一个随机变量服从几何分布。

使用(1)式来计算其期望值如下(在第二行运用了求导与求和运算次序的可交换性)

使用(2)式，设随机变量为第一次实验过后仍需要几次实验才能出现第一次成功，即。因此，，该式表示第一次试验就成功了，所以不再需要额外的试验；，该式表示前n次试验都失败了，在第次试验时才终于成功。于是有：

使用(3)式，定义随机变量，当首次试验成功时取值1，失败时则取值0。条件于来计算的期望值如下：

如果我们定义随机变量如下，，那么按照(4)式对变量求期望便能求出。对比(3)式的求解过程，我们可以看到(4)式本质上是在运用(3)式。

现在我们同时运用(2)(3)来计算方差。

注意到，仅考虑时，变量是不服从几何分布的，但是在引入「第一次实验失败了」这个条件后，在得知这个原本未知的信息之后，随机变量 成为了一个服从几何分布的随机变量，其参数和完全相同，所以有和。

下面我们考虑一个以几何分布为基础的问题。现在变量不再表示出现第一次成功试验时所需要的试验次数，而表示连续出现k次成功试验时所需要的试验次数。试求变量的期望。

要想最大化条件期望这一工具的威力，我们要找到合适的变量来作为条件。现定义变量为出现第一次失败时所需要的试验次数，这个变量将帮助我们轻松求出的期望值。

以为例，独立随机试验的设定在于，哪怕你已经连续9次成功，你也不能确定下一次就会成功。不管在连续9次成功之后失败了，还是在连续3次成功之后失败了，得到的结果都是一样的，同样是回到了游戏的起点，同样是需要从头再来。所以我们有：

利用(3)式来求其期望值：

接着我们进一步拓展。几何分布的试验只有两种结果，即成功与失败。现在我们对其推广，假设每次独立随机试验都会有m种可能结果，每种结果出现的概率都是，用随机变量表示任意一种结果连续出现k次所需要的试验次数。试求的期望值。

这又是一道初看很棘手，但使用条件期望就能轻松解决的问题。用表示任意一种结果连续出现次所需要的的试验次数，那么有

对(8)式两边求期望：

在(7)式中，令则有；在(8)式中，令，则有。这两个结果是一致的，之所以差了个倍数2，是因为在后一题里，任意一种结果出现k次就行，而在前一题里，需要特定某个结果出现k次才行。

快速排序是一种常用的排序算法，随机从数列中选出一个数字，数列中剩余的所有数字和它进行比较，比它小的落入到左侧的子数列中，比它大的落入到右侧的子数列中，然后对这两个子数列分别进行同样的操作，重复下去，直到每个子数列只有1个或2个数字为止。最后我们将得到一个从左到右依照从小到大排列好的数列。这是典型的分治法应用，将一个复杂的大问题不断地拆解成容易解决的小问题。

为了分析这一算法，我们先定义一些必要的变量。用表示完成对一个数列的排序所需要进行的大小比较的次数；用表示对一个长度为n的数列进行排序平均需要进行多少次大小比较；用表示第一个随机选取的数字在全体n个数字中的排名，如果，那么有个数字比这个数小，落入它的左侧，有个数字比它大，落入它的右侧。根据条件期望我们得到：

两边同时乘以后我们便能得到的一般表示式：

由此可知，快速排序算法是平均复杂度为的排序算法。

有n个人在一个房间里聚会，每个人头戴一顶帽子，现在大家都把帽子放到房间中心的一个箱子里，每个人依次上前去随机抽取帽子，如果他刚好抽到了他自己的那顶帽子，我们说此时产生了一个匹配(match)。用随机变量表示产生了多少个匹配。试求(a)的期望值；(b)的概率质量函数。

对于 (a)问，利用(2)式可以轻松求出，令，其中表示第i个人是否成功地拿到了自己的那顶帽子。

,该式表示第一个人没有拿走属于第二个人的帽子，然后第二个人顺利地拿到了他的那顶帽子。于是有：

这一结果意味着，不管房间里有多少个人，平均而言只有一个人可以拿到属于他的那顶帽子。

对于(b)问，为了求出，我们需要先求出，虽然这一项指的是所有人都没有拿到自己的那一顶帽子，但是不能简单地用链式法则来求解：

上式是错误的计算方法，对于「第一个人没有拿到他的帽子」这个事件，需要分类成「第一个人拿到了第二个人的帽子」和「第一个人拿到了既不属于他也不属于第二个人的帽子」这两个子事件，然后你才能去研究第二个人的匹配情况。

我们需要借助条件概率来求解，用表示事件「产生匹配的数量为零」，用表示事件「第一个人拿到了他的那顶帽子」，用表示事件「第一个人没有拿到他的那顶帽子」，用变量表示「n个人中没有产生匹配」的概率。则有：

若第一个人没有选走他帽子，则他的帽子留在了剩余的n-1顶帽子中，成为了「多余的帽子」(因为这顶帽子没有被他的主人取走)，而他所拿走的那顶帽子的主人则成了「多余的人」(因为他没有机会取走他自己的帽子了)。现在我们来研究一下事件。这一事件分为两个子事件：

• 剩余n-1个人里没有产生匹配，并且多余的人拿走了那顶多余的帽子，将此称为事件A
• 剩余n-1个人里没有产生匹配，并且多余的人没拿走那顶多余的帽子，将此称为事件B

,把多余的帽子看做归属于多余的人，这样一来，第一个人走后，剩下的n-1个人都还有机会拿到自己的那顶帽子。

现在我们可以求出了，将所有人分成两队(一共有种分法)，一队有k个人，他们中的每个人都拿到了自己的帽子；另一队有n-k个人，每个人都没有拿到自己的帽子。

有了概率质量函数之后，我们可以用期望的定义式即(1)式来验证(a)问的结果：

利用可以化简这一结果：

结果与(a)问的答案一致。下面我们拓展原问题，现在规定，在第一轮里拿到了自己帽子的人离开房间，剩下的人把拿错的帽子放回箱子里，继续随机抽取，重复进行下去直到所有的人都拿回自己的帽子为止。用变量表示需要经过多少轮才能让所有人都拿回帽子。试求的期望。

从(a)题的结果我们知道，不管房间里有多少人，平均而言，一轮中只有一个人能够拿回自己的帽子，于是我们直观猜测。现在我们用数学归纳法来证明这个结论。

用表示当房间里有n个人时需要经过多少轮才能使所有人拿到自己的帽子，有；用变量表示第一轮里有多少人拿到了自己的帽子(即匹配的数量)。显然，成立，现在我们假设有，可以得到：

在一个教室里坐着n个学生，假设每个人在任意一天出生的概率相同，都为，那么这n个学生中，有两个人在同一天过生日的概率是多少？

用表示事件「至少有两个人在同一天出生」，用表示事件「没有人的生日相同」，由于这两个事件互补，所以有。我们从着手，因为它比的计算要简单得多。事件意味着，第一人在某一天出生了，第二个人的生日与他不同；第三个人的生日既和第一个人不同，也和第二个人不同；第四个人的生日和前面三个人的生日都不相同，以此类推，第n个人的生日和前n-1个人的生日都不相同。所以有：

当n=23时，；当n=57时，。这意味着，只需要有23个人，就有超过一半的几率出现两个人同一天过生日(对于概率论不熟悉的人可能会猜测至少需要157人)；只需要57个人，就能使这一概率值高达99%。以人数为横轴，概率值为纵轴，绘图如下：

这个问题有各种版本的场景描述(最初的场景是要从众多的候选者中选出综合能力最好的那个秘书)，而我个人倾向于这样来描述：在你生日这天，你的n个好朋友排成一队给你送红包，但在这n份红包中你只能接受一份。每次拿到红包后，你可以拆开红包来查看面额大小，如果满意，你选择接受这一红包，游戏结束；如果不满意，你拒绝这份红包(事后不能反悔)，然后去拆下一份红包。这个问题的目标是拿到面额最大的那个红包，它的难点在于，每一份红包的面额大小都是纯粹随机的，不管你已经见过多少份红包，下一份红包对于你而言仍旧是完全未知的(虽然见过的红包越多，对于面额的相对大小的判断越准确)。

直观上来看，n越大，红包数量越多，拿到最大的那一份红包就越困难。用数学的语言来说就是，表示事件「拿到最大的红包」，有。但是，下面我们将看到，在采用适当的策略之后，是一个恒定不变的常数，与n的大小无关。

这样的策略称为k-policy，它的做法是，不管最开始的k个红包面额如何，都不要接受，在这之后，如果遇到一个比前k个面额都大的红包，就接受它，如果一直没有遇到比前k个面额大的红包，那么就接受最后一个红包(即第n个)。下面我们来求这种策略下的. 用随机变量表示最大红包所在的位置，. 则有：

好好品味一下时的这个表达式，如果前个红包中最大的那个在前k个位置里，就能确保在此之后、在最大的红包之前，不会有红包被选走。

考虑关于x的函数，对其进行求导。

这一结论是反直觉的(大概这就是概率论的魅力所在)，它表明，不管有多少份红包，我们拿到最大的那个红包的概率都是个常数，并且这个概率还不小(接近四成了)。