南京大学：《计算机问题求解》课程教学资源（课件讲稿）概率分析与随机算法

Hiring-Assistant算法的平均情况分析 涉及的随机变量： ·Hiring操作执行次数：X; 事件“第个候选人被雇用”的indicator:X,; X=X1+X2+…+Xn E[X]= (by equation (5.2)) n EXM (by linearity of expectation) i=1 n 1/i (by equation(5.3)) E[X]=1/i i=1 为什么？ Inn +0(1)(by equation(A.7))

Hiring-Assistant算法的平均情况分析 涉及的随机变量： • Hiring操作执行次数：X ； • 事件“第i个候选人被雇用”的indicator：Xi ; 为什么？

让随机“更随机” I have two nickels and two quarters in my left pocket and four dimes in my right pocket.Suppose I flip a penny and take two ns from my left pocket if the penny comes up heads and two coins from my right pocket if it comes up tails.Assuming Iam equally likely to choose any coin in my pocket at any time,what is the expected amount of money that I draw from my pocket?

让随机“更随机

条件期望值 a将penny也纳入：HNQ,HQN,HQQ,HNN,and TDD 0(6)+0()+0(位)+0（日）+20（付）=25 ■引入条件期望值：E(XIF)=∑xP(X=x川F) i=】 这里n=2;P(F)=P(F2)=0.5 ·X的期望值；E(X)=∑E(XIF)P(F) .EX=(30+20)/2=25 i=1 。若F=Heaa:(x1-30G+306)+s08+1d8)-30 口若F=“Tai”：F(XE）)=2.0①=20

条件期望值  将penny也纳入：  引入条件期望值：  X的期望值；  若F=“Head”：  若F=“Tail”： 30 6 1 10 6 1 50 3 1 30 3 1 ( | ) 30                             E X F  E(X | F)  201  20 这里n=2；P(F1 )=P(F2 )=0.5  E(X) = (30+20)/2 = 25