[期望] 看完一维随机游走想到的题目

题目：

一开始在数轴0位置，有P概率往右走，Q概率往左走，问第一次到达位置n的期望步数

特别的，在0位置有100%几率到达1。(有点像装备强化的事件，或者排位上分？)

思路：

用模拟与数学推导分别算一次结果对拍

假设P=0.75  程序模拟10000000次的均值如下（大数定理，但肯定有误差）

n	ans
1	1
2	2.6662
3	4.55596
4	6.51928

设E(x)为从x开始，第一次到n的期望步数，答案就是E(0)

方程为  

解释就是有P的概率状态转移至x+1  Q概率转移至x-1  花费为1步

在1的时候有P概率转移到2花费为1，Q的概率转移到1（0下一步肯定是1），花费为2步

开始推导：

设E(x)-E(x+1)=Ax

注意到A1=E1-E2

注意到En=0，那么E1=Ax的前n-1项和 1<=x<=n-1

对An进行求和得到Sn如下

代入P=0.75,Q=0.25

而我们想要的的

n	ans	数学公式
1	1	1
2	2.6662	5/3+1     =2.666666
3	4.55596	32/9+1   =4.555555
4	6.51928	149/27+1=6.51852

因此验证此公式是正确的

 

注意：以上公式是P!=Q的时候成立

当P=Q=1/2时可得E(0)=n^2