数轴整点上的随机游走问题

· · 算法·理论

现有 n=0，0\le p\le 1。每次有 p 的概率 n\to n+1，否则 n\to n-1，求 n 最终达到过 1 的概率。

令概率为 x。有 p 的可能直接到 1，也有 1-p 的概率到 -1，然后 -1 到 0，再 0 到 1。那么有 x=p+(1-p)x^2，因式分解有 (x-1)(px-x+p)=0，即 x=1 或 x=\dfrac{p}{1-p}。这时候就遇到了一个问题：该舍弃哪个呢？

考虑回到期望原本的定义。那么有 x=\sum\limits_{i=0}^{+\infty}C_ip^{i+1}(1-p)^i，其中枚举的是 2i+1 步走到 1，C_i 表示 Catalan 数。提取后得到 x=p\sum\limits_{i=0}^{+\infty}C_i(p-p^2)^i。后半部分不就是 Catalan 数的生成函数吗？答案就是 x=p\cdot\dfrac{1-\sqrt{1-4(p-p^2)}}{2(p-p^2)}=\dfrac{1-|1-2p|}{2-2p}=\begin{cases}\dfrac{p}{1-p}&0\le p\le\dfrac{1}{2}\\1&\dfrac12<p\le1\end{cases}。

等下，生成函数你咋直接代值的？实际上推理过程可以照搬（u=1+(p-p^2)u^2,u=\sum\limits_{i=0}^{+\infty}C_i(p-p^2)^i）。等下，这不还是要舍根吗？还有你证敛散性了吗？实际上，令 y=p-p^2，我们只要证明，0\le y\le \dfrac{1}{4} 时，A=\sum\limits_{i=0}^{+\infty}C_iy^i\le2 即可，因为不难证明两解一个不超过 2，一个不小于 2。欲证上式，只需证 y=\dfrac{1}{4} 的极端情形即可。因为 y=\dfrac14 时，两根均为 2，因此只需证其收敛性即可。A=\sum\limits_{i=0}^{+\infty}\dfrac{1}{i+1}\dfrac{(2i)\cdot(2i-1)\cdot(2i-2)\cdot(2i-3)\cdots\cdot2\cdot1}{\cdot(2i)\cdot(2i)\cdot(2i-2)\cdot\cdots\cdot4\cdot2\cdot2}\le\sum\limits_{i=0}^{\infty}\dfrac{1}{(i+1)\sqrt{2i+1}}\le1+\zeta(1.5)。根据积分判别法它显然收敛。\square。