坑爹的网页游戏升级

Buffalo

现在的网页游戏都有各种升级规则，一般是这样：从第$n$级升级需要耗费$C_n$的金币啊，元宝之类的。但是游戏并不保证你升级成功，成功升一级的概率是$p_n$，等级不变的概率是$q_n$，最坑爹的就是还有概率$r_n$降一级，当然$p_n+q_n+r_n=1$。傻鸟们就在那里升升降降被玩得团团转，憋不住的就会被骗走真金白银。
现在来讨论一下这种升级的耗费。把从$m$级升到$n$级需要消耗的金币期望值记为$E(m,n)$，为方便起见规定当$m\ge n$时$E(m,n)=0$，于是有等式$E(i,n)=C_i+p_i E(i+1,n)+q_i E(i,n)+r_i E(i-1,n)$，定义$C'_i=\frac{C_i}{1-q_i}$，$p'_i=\frac{p_i}{1-q_i}$，$r'_i=\frac{r_i}{1-q_i}$，问题就变成带有新参数的没有等级不变选项的简化版，$E(i,n)=C'_i+p'_i E(i+1,n)+r'_i E(i-1,n)$。
这个方程的解$E(1,n)$满足递推式$p_n E(1,n+1)=C_n+E(1,n)+(p_n-1)E(1,n-1)$。
对最简单的情况$C_n=C$，$p_n=p$，可以解得$E(1,n)=C*\frac{2p(1-p)}{(2p-1)^2}[(\frac{1-p}{p})^{n-1}-1]+C\frac{n-1}{2p-1}$。
这个表达式在$n$比较大的时候的行为如下
$p>1/2$，这是最仁慈的运营商，这时候差不多有$E(1,n)~C\frac{n-1}{2p-1}$，虽然花费大点，但还是线性的，可预期的。
$p=1/2$，$E(1,n)=C*(n-1)^2$，这就了不得了，平方增长。
$p<1/2$，$E(1,n)~C*\frac{2p(1-p)}{(2p-1)^2}(\frac{1-p}{p})^{n-1}$，花费指数增长，大部分游戏都属于这类。

严格求解方程$E(i,n)=C_i+p_i E(i+1,n)+r_i E(i-1,n)$也是很有意思的课题，不过对这个问题来说意义不大。

BeerRabbit

MarkovChain。一般化情况其实就是离散Markov过程。