概率DP

浅谈概率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.0006Doyoureallythinkyouknowprobabilityverymuch?你掷了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题目来源:SRM400CollectingBonusesf[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轮未结束的概率.则本题答案就为pA+pN*d/(2*d-1)涉及到无限的概率问题,先求极限情况,然后解决有限的情况.重在设计状态表示.谢谢大家