课件浅谈概率.pptx

浅谈概率DP彭天翼

上课大纲1.什么是概率2.什么是期望3.OI的概率题

什么是概率概率空间事件

概率是一个函数

定义定义一个概率空间Ω，有元素w1,w2,w3...,wn事件A为空间上的一个子集在Ω上定义概率函数P，它的定义域包括Ω的元素与Ω的子集满足：1.0=P(wi)=12.若A={u1,u2,u3,...,um}，则P(A)=P(u1)+P(u2)+P(u3)...+P(um)3.P(Ω)=1

举例掷骰(tou)子

举例小明想要使用“装备强化卷轴”把一个“工地手套”强化11次，右图是每一次强化的成功率。问：在这个过程，概率空间是什么？事件是什么？概率函数是什么？

概率空间下的基本公式1.1-P(A)=P(Ω-A)：例如，在11次强化中，装备消失的概率是？2.P(A1∪A2)=P(A1)+P(A2)-P(A1∩A2)推论：若A1∩A2=?，则P(A1∪A2)=P(A1)+P(A2)

概率空间下的基本公式3.AB同时发生的概率=B发生的概率*在B发生下A发生的概率P(AB)=P(B)*P(A|B)=P(A)*P(B|A)

Practice问：一座别墅在过去的20年里一共发生过2次被盗，别墅的主人有一条狗，狗平均每周晚上叫3次，在盗贼入侵时狗叫的概率被估计为0.9，问题是：在狗叫的时候发生入侵的概率是多少？

PracticeA=狗叫B=盗贼入侵P(A)=每周3次P(B)=每10年1次P(A|B)=0.9P(B|A)=(P(A|B)*P(B))/P(A)≈0.0006

Doyoureallythinkyouknowprobabilityverymuch?你掷了100次硬币，每次都是正面朝上！于是，问题来了。Question1:你再掷一次，这回硬币正面朝上的概率是？Question2:你此时应不应该去买彩票？Question3:我花2元钱买你的1元钱硬币，你会愿意么？

两羊一车现在有一个小游戏，你知道有三扇门后面分别关着两只羊和一辆车。你选定了一扇门【直觉告诉你，这扇门后面有车】主持人看了看另外两扇门，选择了其中有羊的那扇门打开，还剩下两扇门，现在的你有如下几种决策：1.仍然相信直觉告诉你的那扇门2.选择另外一扇门3.求助现场观众

什么是期望

什么是期望掷一枚硬币，正面朝上奖励100元钱，正面朝下罚99元钱抛1次，期望得到多少钱？

定义随机变量X：是定义在概率空间上的一个函数X(wi)-k期望：定义在一个随机变量X上，写作：E[X]=ΣP(wi)*X(wi)

理解期望是一种加权平均数我有0.3的概率考100分，有0.7的概率考0分，那么平均情况下我能得多少分呢？

应用每张“装备强化卷轴”的价格为10万冒险币，未经强化的“工地手套”价格为1元冒险币，强化11次的“工地手套”价格应该为多少？

期望的可加性E[X+Y]=E[X]+E[Y]比如：抛硬币游戏中，改成投100次，期望能得到的收益是？

例题1给定一个图，给点随机地染红色或者蓝色。统计两端颜色不一样的边的期望条数

例题2N个节点的有根树，每次随机删除一棵子树，问期望多少次删完。

例题3在一个n个点,m条边的有向图中，问从1号点出发，走到m号点的期望步数？n=100

例题4饮料等概率有N种不同的瓶盖，在你买下饮料前你不能知道这瓶饮料瓶盖的种类，你希望集齐K种不同的瓶盖，问期望要买多少瓶饮料。1=K=N=10^8题目来源:SRM400CollectingBonuses

f[x]表示已经取到x种颜色，离取到k种颜色还差多少步？f[x]=1+x/n*f[x]+(n-x)/n*f[x+1]f[x]=n/(n-x)+f[x+1]f[k]=0

例题5两人在长为n的数轴上轮流掷d面骰子前进，初始位置是x和y，x先手。两人一直往右走，如果一步超过n就往回走（然后继续往右）走到n胜。问先手胜率n=5000,内存限制32M题目来源:SRM465Div1

首先,两个人是不相干的.可以想象最后可能进入一个无限的过程…也就是两个人都在n-d~n内.问题分为两部分计算

对于无限部分.在n-d~n内,先手胜率是 求极限,得d/(2*d-1).

对于1-n-d-1部分由于每轮至少右移1格,所以结果n-d轮之后肯定会到这个区间内.问题转化成求前n-d轮的胜率.引入辅助变量g(i,j)表示i轮到j概率.g(i,j)可以用部分和+滚动dp求,设f(i)表示经过i轮到n的概率,同理g(i)表示后手胜率.则f(i)=g(i,n).

设pa表示前n-d轮的先手胜率,pn表示n-d轮未结束的概率.则