线性的期望gydF4y2Ba
期望的线性性是gydF4y2Ba期望值gydF4y2Ba的和等于它们各自期望值的和,不管它们是否独立。gydF4y2Ba
随机变量的期望值实质上是可能结果的加权平均值。我们通常对随机变量和的期望值感兴趣。例如,假设我们在玩一个游戏,我们取两个六面骰子掷出的数字之和:gydF4y2Ba
用我们的基本方法计算滚动总和的期望值是很繁琐的。相反,我们提出以下论点:gydF4y2Ba每个骰子的期望值是gydF4y2Ba ,两次掷骰子都是gydF4y2Ba独立事件gydF4y2Ba,那么它们的和的期望值应该是gydF4y2Ba ."
这是真的——这些期望值增加了。但还有更多!期望的线性特性特别强大因为它告诉我们gydF4y2Ba即使随机变量是相关的,我们也可以用这种方式添加期望值gydF4y2Ba.gydF4y2Ba
让我们仔细思考一下,因为它可能是相当反直觉的!举个例子,这意味着本周末降雨量的期望值恰好是周六降雨量的期望值加上周日降雨量的期望值,尽管我们确实如此gydF4y2Ba不gydF4y2Ba我们认为周六的降雨量与周日的降雨量无关(例如,周六下大雨会增加周日下雨的可能性)。gydF4y2Ba
在这一页上,我们推导出期望值的性质。我们将解决一些基本的问题,然后深入到先进的技术,使我们能够解决许多组合学问题,范围从合理的直接到相当具有挑战性。最后,我们将探索在其他学科领域的应用,如计算机科学和几何。gydF4y2Ba
内容gydF4y2Ba
定义和证明gydF4y2Ba
首先,让我们清楚地说明期望值函数的线性特性(通常简称为“期望的线性”):gydF4y2Ba
为随机变量gydF4y2Ba 而且gydF4y2Ba (可能因人而异),gydF4y2Ba
更一般地说,对于随机变量gydF4y2Ba 和常量gydF4y2Ba
我们将显式地证明这个定理gydF4y2Ba离散随机变量gydF4y2Ba 而且gydF4y2Ba .根据期望值的基本定义,gydF4y2Ba
这个结果可以推广为gydF4y2Ba 变量使用感应。gydF4y2Ba
注意,在这个证明中我们从未使用过任何独立性的性质,因此期望的线性对所有随机变量都成立!gydF4y2Ba
为gydF4y2Ba连续随机变量gydF4y2Ba,证明本质上是一样的,只是求和被积分代替了。此外,可以很容易地将两个随机变量的证明扩展到更一般的情况gydF4y2Ba期望值属性gydF4y2Ba.gydF4y2Ba
希望从上面的证明中,我们能清楚地知道为什么这个性质成立,不管随机变量是否独立。这是期望线性的关键概念之一,所以如果不明显,一定要再做一次证明。gydF4y2Ba
基本的例子gydF4y2Ba
在我们跳到解决问题的技巧之前,让我们看看如何直接应用期望的线性。考虑在介绍中给出的例子:在一个游戏中滚动两个六面骰子。我们已经讨论了如何求和的期望值gydF4y2Ba 由于每个骰子的期望值为gydF4y2Ba
然而,记住期望线性最重要的区别之一是它可以被应用于gydF4y2Ba依赖gydF4y2Ba随机变量。让我们以骰子为例:gydF4y2Ba
如果掷骰子的数字之和是gydF4y2Ba 摇出的数字的乘积是gydF4y2Ba 计算gydF4y2Ba
我们知道gydF4y2Ba 因为摇出的两个数字是独立的,我们有gydF4y2Ba 因此,尽管事实是gydF4y2Ba 而且gydF4y2Ba 显然是相关的,期望的线性告诉我们gydF4y2Ba
你可以在下面的问题中直接应用期望的线性:gydF4y2Ba
现在我们已经看到了期望线性的一些直接应用,让我们进入一些解决问题的技巧!gydF4y2Ba
介绍解决问题的gydF4y2Ba
有趣的是,在解决问题时,期望值的线性最常见的用法之一是,它可以被应用于寻找单个随机变量的期望值。你可能会想,等等,我怎么把一个随机变量和的工具应用到单个随机变量上呢gydF4y2Ba
在期望线性最有用的情况下,通常不明显应该应用它。相反,我们必须使用解决问题的技巧将单个随机变量重新框定为其他随机变量的和。gydF4y2Ba
首先,让我们注意两个重要的迹象,它们提醒我们,在解决给定期望值问题时,我们可能能够应用期望的线性:gydF4y2Ba
- 以加权平均值计算期望值是困难的/混乱的,因为每个单独结果的概率很难计算。gydF4y2Ba
- 考虑的随机变量可以写成一些更简单的随机变量的和。gydF4y2Ba
让我们看一个例子:gydF4y2Ba
卡罗琳将抛10枚均匀硬币。如果她翻转gydF4y2Ba 正面,她将得到$gydF4y2Ba .她支付的预期价值是多少?gydF4y2Ba
我们把卡洛琳的支出记为$gydF4y2Ba .我们的第一反应是找出gydF4y2Ba 然后进行加权平均,但计算这些概率并进行期望值求和很快就会变得很糟糕——这是我们考虑利用期望线性的第一个迹象!我们该如何表达gydF4y2Ba 是简单随机变量的和吗?gydF4y2Ba我们注意到得到$gydF4y2Ba 为gydF4y2Ba 正面等于她得到了$gydF4y2Ba 对于每个人头,我们可以把她的总支付看作是每一枚硬币($gydF4y2Ba 头)。因此,如果我们让gydF4y2Ba 如果gydF4y2Ba 硬币是正面和gydF4y2Ba 如果是反面,那么我们可以把卡洛琳的支出写成gydF4y2Ba
的期望值gydF4y2Ba ,我们现在只需要找到的期望值gydF4y2Ba .就像这样,我们的问题看起来像一个期望线性问题!gydF4y2Ba
当然,因为每个硬币都有正面的概率gydF4y2Ba ,gydF4y2Ba 对所有gydF4y2Ba .因此,gydF4y2Ba
所以卡洛琳的预期收益是美元gydF4y2Ba .gydF4y2Ba
正如您所看到的,期望的线性可以极大地简化期望值计算所需的计算!注意我们是如何利用期望值计算看起来很混乱的事实来考虑调用期望的线性性,然后我们巧妙地将随机变量(Caroline的支出)写成简单随机变量的和。试试下面的问题来测试你的技能:gydF4y2Ba
在上面的例子和问题中,我们将期望的线性应用于独立随机变量的和。这很好,但请记住期望线性最强大的方面之一是它适用于相互依赖的随机变量!我们来做一个例题我们有一个和gydF4y2Ba依赖gydF4y2Ba随机变量。gydF4y2Ba
数字gydF4y2Ba 而且gydF4y2Ba 被随机排列成两个两位数,gydF4y2Ba 而且gydF4y2Ba 例如,我们可以gydF4y2Ba 而且gydF4y2Ba 的期望值是多少gydF4y2Ba
我们的第一反应是寻找gydF4y2Ba 而且gydF4y2Ba 简单地乘以它们。然而,请记住,gydF4y2Ba 只有当随机变量独立时才成立gydF4y2Ba.很明显,gydF4y2Ba 而且gydF4y2Ba 是gydF4y2Ba不gydF4y2Ba独立,因为每个数字只能使用一次;例如,如果gydF4y2Ba 那我们就知道了gydF4y2Ba 只能是24或42岁。这激励我们试着把我们的问题变成某种求和。gydF4y2Ba因为我们最简单的变量是单个数字,我们被启发将乘积写成gydF4y2Ba
然而,很明显,这些形式的任何产品的期望值gydF4y2Ba 是一样的,因为有对称性之间gydF4y2Ba 我们可以计算gydF4y2Ba
因此,通过期望的线性,gydF4y2Ba
现在我们已经有了基本的想法,让我们转向一些更复杂的解决问题的技巧。gydF4y2Ba
使用指标变量gydF4y2Ba
在本节中,我们将继续探索允许我们这样做的技术gydF4y2Ba解决组合问题gydF4y2Ba利用线性的期望,引出了一种新的工具称为gydF4y2Ba指标变量gydF4y2Ba.特别是,当考虑的随机变量为gydF4y2Ba计数gydF4y2Ba简单事件发生的次数。gydF4y2Ba
在这类问题中,考虑的随机变量可以写成其他随机变量的和的事实将不像前一节中那样明显。但是有了我们到目前为止所建立的工具,我们很快就能解决这些问题!gydF4y2Ba
让我们从一个例子开始,帮助激发一些关于将随机变量写成简单随机变量和的聪明方法的想法:gydF4y2Ba
一个盒子里有一个黄色的球,一个橙色的球,一个绿色的球和一个蓝色的球。比利从盒子里随机选择了4个球(有替换)。比利选择的不同颜色的球的数目的期望值是多少?gydF4y2Ba
我们想求出比利选择的不同颜色的数目的期望值。我们可以直接计算比利选择的概率gydF4y2Ba 不同的颜色,但这有点乱(如果有很多超过4个球会更困难)。这是我们的线索,看看线性的期望是否可能有帮助!gydF4y2Ba现在,我们需要考虑如何将比利选择的不同颜色的数量写成其他随机变量的和。首先,假设比利的四个选择如下:gydF4y2Ba
你如何确定比利选择的不同颜色的数量?好的,看上图,比利选择了橙色、绿色和蓝色的球,但他没有选择黄色的球,所以这是三种不同的颜色。如果你在想,“是的,当然,我已经知道怎么数数了!”gydF4y2Ba
因为我们的随机变量只是计算有多少种颜色被选中,我们可以把它看作是四个随机变量的和:每种颜色一个,如果颜色被选中则等于1,如果没有,则等于0。因此,在上面的例子中,橙色、绿色和蓝色随机变量为1,而黄色随机变量为0。把这些加起来,总共有3个不同颜色的球被选中。gydF4y2Ba
此外,这四个随机变量的期望都很容易计算。事实上,利用期望值的基本定义,我们可以看到它的期望值简单地等于颜色被选中的概率。使用gydF4y2Ba赠送的概率gydF4y2Ba技术上,我们发现任意颜色(比如黄色)被选中的概率是gydF4y2Ba
最后,根据期望的线性性,比利选择的不同颜色的球的数目的期望值为gydF4y2Ba
让我们回顾一下这个例子,看看我们使用了哪些重要的思想:gydF4y2Ba
- 期望的线性帮助我们以非常简单的方式计算一个看似复杂的期望值(虽然使用了聪明的洞察力-但这些将成为第二天性的更多的练习)!gydF4y2Ba
- 期望的线性性让我们不用担心考虑的是因变量的和。显然,这些变量是相关的:例如,如果其中三个为0,那么第四个必须为1(因为必须选择至少一种颜色)。然而,正如我们在本页的开头所证明的那样,期望的线性对所有随机变量都成立,不管其独立性如何。gydF4y2Ba
- 因为我们的随机变量gydF4y2Ba数gydF4y2Ba有些东西(例如不同颜色的球的数量),我们可以把它写成随机变量的和,表明哪些东西应该被计数(例如,每种颜色都用1表示)。gydF4y2Ba
看一下最后一点,这实际上让人想起我们如何解决之前卡罗琳抛硬币的例子我们通过对随机变量求和来计算她抛的正面的次数,对于每一枚硬币,它是否为正面。事实上,对于这样的随机变量,有一个正式的术语:gydF4y2Ba
一个gydF4y2Ba指示器随机变量gydF4y2Ba在一个事件gydF4y2Ba ,通常表示为gydF4y2Ba 随机变量是什么gydF4y2Ba 如果gydF4y2Ba 发生,如果为0gydF4y2Ba 不发生。根据期望值的定义,gydF4y2Ba
这些指标变量对于解决期望线性的问题非常有帮助,特别是当计算它们的期望(即事件发生的概率)很简单的时候。使用这个想法,你就可以着手解决一个问题,而这个问题本来根本不可能以简单、干净的方式解决。gydF4y2Ba
综上所述,在下列情况下,使用指示变量的期望线性通常是有用的gydF4y2Ba
- 一个问题看起来可以用期望的线性性来解决;gydF4y2Ba
- 没有一种明显的方法可以将考虑中的随机变量写成简单随机变量的和;gydF4y2Ba
- 考虑中的随机变量是计算固定数量的简单事件的发生次数。gydF4y2Ba
使用状态gydF4y2Ba
在本节中,我们将介绍一种应用期望线性的技术,当所考虑的随机变量衡量完成某种过程所需的时间或步骤数时。如果这听起来有点模糊,让我们考虑以下简单的例子来介绍流程中的“状态”的概念:gydF4y2Ba
艾利森有一枚非均匀硬币,正面朝上的概率很高gydF4y2Ba 她抛硬币直到抛出一个正面的次数的期望值是多少?gydF4y2Ba
乍一看,我们的随机变量确实是在计算简单的事件,所以指标变量似乎是有帮助的。我们只需要数一下抛掷反面的次数,每次抛掷都是有概率的反面gydF4y2Ba 但是有一个大问题!我们不知道总共有多少次抛硬币;事实上,这几乎正是提出的问题。gydF4y2Ba相反,我们从“完成一个过程”的角度来考虑这个问题,在这个过程中有多个状态。这里的状态很简单:我们要么还没有抛出正面(我们称其为状态0),要么已经抛出正面(我们称其为状态1)。gydF4y2Ba
现在,让gydF4y2Ba 表示完成过程所需的预期次数(抛第一个正面),假定我们处于状态gydF4y2Ba 应该很清楚gydF4y2Ba 因为状态1意味着我们抛了一个正面,所以这个过程已经完成。另一方面,一旦我们在状态0中翻转,我们将保持在状态0的概率gydF4y2Ba 我们会以概率移动到状态1gydF4y2Ba 因此,考虑状态0第一次翻转后的状态,我们有gydF4y2Ba
所以gydF4y2Ba 给gydF4y2Ba
备注:gydF4y2Ba这是求a的期望值的一种方法gydF4y2Ba伯努利分布gydF4y2Ba.gydF4y2Ba
让我们来看一个使用状态的更复杂的例子,在这个例子中我们将能够直接应用我们刚刚导出的结果!gydF4y2Ba
在SlurpeeShack上的每一次购买,你都会收到右图所示的一块随机拼图。gydF4y2Ba
一旦你收集到所有12块,你就可以免费得到一杯思乐冰!gydF4y2Ba
为了收集到所有12件物品,你需要购买的数量的期望值是多少?gydF4y2Ba
这里,状态表示有多少不同的息票。让gydF4y2Ba 表示我们需要购买的数量,以获得gydF4y2Ba 不同的息票,所以考虑的随机变量是gydF4y2Ba一旦你有了gydF4y2Ba 不同的优惠券,在任何给定的购买中得到一个新的概率是gydF4y2Ba 正如在前面的例子中得到的,所需购买的预期数量将为gydF4y2Ba 因此,通过期望的线性,gydF4y2Ba
奖金:gydF4y2Ba这是一个著名的问题,通常被称为gydF4y2Ba优惠券收集器的问题gydF4y2Ba.一般来说,对gydF4y2Ba 优惠券的期望值为购买的次数gydF4y2Ba 在哪里gydF4y2Ba 是gydF4y2Ba 谐波数。用微积分可以证明,对于大gydF4y2Ba 期望值大概是gydF4y2Ba
正如我们所看到的,当我们可以将随机变量写成其他随机变量的和时,状态的方法是有用的,这些随机变量度量从一个状态到下一个状态所需的时间/步骤。如果你正在寻找一个额外的挑战,试试下面这个问题,它的状态甚至不那么明显:gydF4y2Ba
应用程序gydF4y2Ba
我们已经学过如何利用期望的线性来解决一些组合问题。然而,期望值的线性也有许多现实世界和跨学科的应用,在本节中我们将探讨其中的一些。gydF4y2Ba
让我们从考虑彩票开始。gydF4y2Ba
有一个抽奖比赛,参与者支付1美元,从整数1到50中选择5个不同的数字。如果有人猜对了5个数字,彩票公司将提供250万美元的奖金(如果有多个正确的参与者,奖金将在所有中奖者中平分)。gydF4y2Ba
我们知道从gydF4y2Ba组合gydF4y2Ba有gydF4y2Ba 可能的选择。但是那里等候gydF4y2Ba鸽子洞原理gydF4y2Ba,这意味着如果我们得到一组gydF4y2Ba 每个人都要提交一张不同的彩票,我们肯定会从彩票公司赚到钱!gydF4y2Ba
虽然这是事实,但彩票公司知道,参与者通常没有资源以这种方式协调。相反,他们可能认为每个人都可能随机选择他们的数字。如果是这样的话gydF4y2Ba 人们参加抽奖gydF4y2Ba 可能的选项,某个参与者获胜的概率是多少?gydF4y2Ba
让gydF4y2Ba 是彩票组合事件上的一个指示变量gydF4y2Ba 是gydF4y2Ba不gydF4y2Ba由任何参与者选择。因为每个人的选择都是随机的,gydF4y2Ba
对所有gydF4y2Ba 根据期望的线性性,未选择组合个数的期望值为gydF4y2Ba
由于获胜的组合是随机选择的,gydF4y2Ba
例如,在我们有2,118,760个选项和2,118,760名参与者的彩票中,有人中奖的概率约为63%。gydF4y2Ba
奖金:gydF4y2Ba当…gydF4y2Ba 可能的选择的数量,变得非常大?如果参与者的数量增加,这将如何影响彩票公司需要如何适应?提示:结果涉及到一个著名的gydF4y2Ba数列的极限gydF4y2Ba与常数相关gydF4y2Ba 此外,阅读这gydF4y2Ba回答gydF4y2Ba为了更深层次的洞察gydF4y2Ba 和组合。gydF4y2Ba
看到我们如何能够应用我们的技能与线性的期望,发现一个关于现实彩票的有趣事实,这是非常酷的!让我们转向一个非常不同的味道:一个著名的gydF4y2Ba几何概率gydF4y2Ba的问题。gydF4y2Ba
假设一根长度为1的针被扔到地板上,地板上的木条间距为1个单位。针落在两块木板上的概率是多少?gydF4y2Ba
这个问题的传统解决方法是使用微积分,但我们将展示如何用期望的线性来解决它!gydF4y2Ba
首先,我们认为针穿过木条的预期次数与长度成正比gydF4y2Ba 的针。假设这根针是由gydF4y2Ba 等长的线性片,让gydF4y2Ba 的指示变量gydF4y2Ba 穿过两条木条的木板。那么,根据期望的线性关系,总杂交的期望数为gydF4y2Ba
保持这些小碎片的长度不变,我们可以看到,预期的次数与针的长度成正比(不可否认,这有点像手摇,但直觉应该是清楚的)。gydF4y2Ba
因此,作为长度的函数gydF4y2Ba 预期的穿越次数是gydF4y2Ba 为一个常数gydF4y2Ba 但是,考虑一个直径为1的圆(周长)gydF4y2Ba );以1的概率,这个圆恰好与两个木条相交。因此,gydF4y2Ba 所以gydF4y2Ba 如果你对圆的概念感到不舒服,可以考虑将一堆非常非常小的线性片段组合在一起来近似圆。gydF4y2Ba
对于任何一根针(如我们的针),只要它最多能穿过一个木十字,gydF4y2Ba 实际上是指针穿过两条木板的指示变量,所以期望值恰好是发生这种情况的概率。因此,与长度为1的针交叉的概率很简单gydF4y2Ba
奖金:gydF4y2Ba你能想想如何利用这个结果来估计的价值吗gydF4y2Ba 通过一个gydF4y2Ba蒙特卡罗gydF4y2Ba模拟?gydF4y2Ba
以下是一些可以用期望线性来处理的其他例子:gydF4y2Ba
关于随机图中期望值的许多问题都可以用期望的线性来回答。例如,假设有一组gydF4y2Ba 潜在的朋友,每一对人成为朋友都有可能gydF4y2Ba .“三胞胎朋友”的数量的期望值是多少,例如三个人组成的团体,他们都是共同的朋友?gydF4y2Ba
注意这里有gydF4y2Ba 这样的三元组,每一个三元组都是有概率的朋友三元组gydF4y2Ba 如果我们让gydF4y2Ba 的指示变量gydF4y2Ba 三胞胎是朋友三胞胎,那么朋友三胞胎的期望数量是gydF4y2Ba
如果gydF4y2Ba 人们在一个房间里,假设一年有365天,那么不同生日的预期数目是多少?这和什么有关系gydF4y2Ba生日悖论gydF4y2Ba问题吗?gydF4y2Ba
这与彩票的例子非常相似。看看你能不能解决这个问题!gydF4y2Ba
在计算机科学中,随机化gydF4y2Ba快速排序算法gydF4y2Ba有预期的运行时gydF4y2Ba 期望的线性如何让我们证明这一点?gydF4y2Ba
(想为这个示例编写一个解决方案吗?编辑这个wiki !)gydF4y2Ba