马尔可夫链中的期望问题
马尔可夫链
，求通项的方法不可行，所以我们需要利用另外一种方法。
我们仍然求从
也就是原概率矩阵的转置矩阵再在对角线上全部减一。
或者可以表示为
\[P' = P^T - I_n\]
而我们最终求解的方程为：
\[P'E = \begin{pmatrix}-1 \\ -1 \\ \vdots \\ -1\end{pmatrix}\]
利用高斯消元即可。
例题
在题解区中全是某种奇怪的 DP 设计。所以这里来讲述一下利用本文中的方法求解的方法。
我们设 \(E_i\) 表示从剩下 \(i\) 个地方没有按下到全部按下的期望步数。
根据题目，我们有：
\[E_i = \frac in E_{i-1} + \frac {n-i}n E_{i+1} + 1\]
并且由于最优限制：
\[i \le k \iff E_i = i\]
所以我们可以轻易的利用高斯消元求解……但是很明显，这是不现实的……考虑这个矩阵是一个稀疏矩阵，而且每一个方程是只与临近对角线的 3 个元素相关，所以我们可以轻易的将空间优化到 \(O(3n)\)。
接下来我们只需要参考 Guass-Jordan 消元法（先从上到下消下三角，再从下到上消上三角）。那么复杂度成功的也被我们降到了 \(O(n)\)。只是常数有点小大……
作者有话说
其实本文讲述的方法存在很大的局限性，尤其的求解的过程，很容易就变成了 \(O(n^3)\)。
不过似乎建模的过程还是蛮简单的？
在求期望的问题中，这不失为一个思考的方向。有些时候，可以通过题目相关的特殊性质进行优化，使得复杂度降低。
可是毒瘤出题人们……还是看每道题的正解吧，或许终将有一天，这个方法可以被一种通法优化到 \(O(n^2)\) 呢？