表示随机变量
指示随机变量(indicator random variable，IRV )是概率分析中非常重要的离散随机变量，用于表示某个事件是否发生。 更具体地说，假设发生事件a，变量IRV取值1，否则取值0。 在数学上，表现如下。
指示随机变量是采用概率分析问题的基本手段。 那么为什么要采用这样的随机变量呢？ 首先，指示随机变量非常简单，对任何概率问题都是可能的，取其随机变量的值也比较简单。
尽管某个事件之间存在关联，但它表现出随机变量的可分解性质，在求解期望值时表现出良好的数学性质。
例如，假设我们扔了n次硬币。 每次扔硬币时，都可能存在两种向上或向下的值。 我们用0和1表示。 他们以等概率出现。 我们要问正面的期待值吗？
投n次硬币，正面朝上的总次数的期望值用x表示。 分解x，假设
发生了表示第I次投硬币，面向正面的事件。 那么，扔了n次硬币的正面朝上的总次数可以表示为：
所以我在计算
在上述中，是指示随机变量，即
引理：给出一个样本空间s和s中的一个事件a进行设置
那么，那么
水平。
随机算法
一般来说，如果某个算法的操作不仅由输入确定，还由随机数生成器生成的数值确定，则称为随机。 在此，输入是未知的数据分布，该数据无法正确建模，只能用一些概率知识进行分析。 另外，在算法执行期间，一些重要步骤由计算机生成的随机数确定，而算法的执行是不确定的。
实际上，所有采样算法都是随机的，包括Metropolis算法和加权采样算法。 具体采样算法的概要请参考本人以前写的文章。 科学传递人：采样方法(Sampling Method )庄兰.智湖.com
分析随机算法的执行时间时，用执行时间的期望值进行测量。 其中，输入值由随机数生成器生成。 随机算法的执行时间称为期望执行时间，这类算法与它们的输入将随机算法区分开来。 一般来说，如果概率分布在算法的输入端上，那么我们讨论平均状况的执行时间； 如果算法本身是随机选择的，我们将考虑其预期执行时间。
比较简单的概率算法伪代码：
高效助手(n )//candidate0isa least-qualifieddummycandidate
for i=1 to n
interview candidate i
ifcandidateiisbetterthancondidatebest
best=i
hire candidate i
该算法的伪代码表明，n名申请者，由于先验知识水平高低未知，输入分布未知。 在代码的第四行中执行是未知的和概率的。 我们用指示随机变量的方法进行了分析算法的平均执行时间。 假说
表示申请者
一旦被雇佣，就会存在指示变量
另外，如果用x表示我们雇佣新人的次数。 因此期待值
现在的问题是如何决定申请人I被雇佣的概率。 分析：如果申请人I已被雇佣，则该申请人将优于所有以前的i-1申请人。 但是，我们的顺序是随机的，不知道申请者的顺序。 此时，整体来说，所有申请者在没有事前信息的情况下被雇佣的概率是
.因此，
也就是说，尽管我们面试了n个人，但实际上我们只平均雇佣
个人。 加上雇佣每个人的成本
总雇佣平均费用为
.这个结论假设申请者是随机排列的，这里的成本也就是平均情况下的成本。
现在我们要接触另一个随机算法。 算法本身会做出随机选择。 这与以前的算法不同，后者是在运行中确定的。 代码如下。
randomized-hireassistant(n ) )。
randomlypermutethelistofcandidates
best=0
for i=1 to n
interview candidate i
ifcandidateiisbetterthancondidatebest
best=i
hire candidate i
很明显，上述随机算法和以前的算法只写了第一行
，也就是随机的打乱应聘者的序列。由于算法本身会做出随机的选择，因此算法期望的运行时间仍然为.
很多随机算法是通过对给定的输入变换排列以使输入随机化。通常情况下存在两种方案：为数组的每个元素A[i] 赋予一个随机的优先级P[i]，然后依据优先级对数组A进行排序。那么每个元素优先级的产生必须是随机的，且是唯一的。构造算法：
PERMUTE-BY-SORTING(A)
n = A.length
let P[1...n] be a new array
for i=1 to n
P[i]=RANDOM(1,n**3)
sort A, using P as sort keys
这里
主要是为了保证P数组里面的优先级唯一。那么一个自然的问题是：当
为多大时，每个优先级元素都唯一。也就是，所有元素都唯一的概率至少是
. 算法第5行需要的事件复杂度为
证明：令
表示
互不相同的事件。因此
表示
互不相同的事件。
还可以表示在
的基础上
与
之一不相同的事件。那么
为什么上述方案能够产生均匀随机序列？或者说，产生均匀随机序列的充分必要条件是什么？
证明：我们从考虑每个元素
分配到第i个最小优先级的特殊排列开始，并说明这个排列正好发生的概率是
。对
, 设
代表元素
分配到第i个最小优先级的事件。对所有的i, 事件
发生的概率，即是
解释：对于第1个元素，其分配到第1个最小优先级的概率为1/n. 依次，第二个元素分配到第二最小优先级的概率为
。要保证唯一不重复。因此类推，所有n个元素都能分配到属于自己的优先级元素的概率为
.
2. 另外一种产生均匀随机序列的方案是：原址排列给定数组。过程RANDOMIZE-IN-PLACE在O(n)时间内完成。算法如下：
RANDOMIZE-IN-PLACE(A)
n = A.length
for i=1 to n
swap A[i] with A[RANDOM(i,n)]
代码第3行表示：交换A[i]与A[i]之后的n-i+1个元素。证明该算法能够生成均匀随机序列。
在2~3行for循环的第i次迭代以前，对每个可能的(i-1)排列，子数组A[1..i-1]包含这个(i-1)排列的概率是
。 采用循环不等式进行说明：
初始化：考虑正好在第一次循环迭代以前的情况，此时i=1. 由循环不变式可知，对每个可能的0排列，子数组A[1..0]包含这个0排列的概率是
子数组A[1..0]是一个空的子数组，并且0排列也没有元素。因而，A[1..0]包含任何0排列的概率是1. 在第一次1循环迭代以前循环不等式成立。
保持：我们假设在第i次迭代以前，每种可能的(i-1)排列出现在子数组A[1..i-1]中的概率是
。在第i次迭代以后，每种可能的i排列出现在子数组A[1..i]中的概率是
. 下一次迭代i累加后，还将保持这个循环不等式。如何证明？
设
表示前(i-1)次迭代已经在A[1..i-1]中构造了特殊(i-1)排列的事件。设
表示第i次迭代在位置A[i]放置
的事件。E1发生的概率是
，在E1的条件下E2发生的概率是
. 那么，E1和E2同时发生的概率为
最终阶段：当i=n+1时，子数组A[1..n]是一个给定n排列的概率为
因此RANDOMIZE-IN-PLACE能够产生一个均匀随机序列。
首先我们从概率分析的角度得出平均情况下的雇佣次数，然后采用随机算法进行设计，设计的随机算法只要能够产生均匀随机序列，即可保证算法的期望成本与平均情况下雇佣次数相同。随机算法通常是解决一个问题最简单，最有效的方法。