前话
很早就想给随机游走类问题做个总结了，以后又想到一题不定期更新。
2024.6.22
题目描述
一维空间内，前进一步，后退一步，原地不同概率均为 \(\cfrac{1}{3}\)，\(0\) 点后退后还是 \(0\) 点。求从 \(0\) 点走到右端点 \(n\) 的期望步数。
解决
套路化记 \(f[i]\) 表示从 \(i\) 走到 \(n\) 的期望。那么有 \(f[i] = \cfrac{f[i]}{3} + \cfrac{f[i - 1]}{3} + \cfrac{f[i + 1]}{3} + 1\)，化简后有 \(f[i] = \cfrac{f[i - 1] + f[i + 1] + 3}{2}\)。特殊地，\(f[0] = f[1] + 3\)。
从后向前递推。
\[f[n] = 0 \]这是边界。
\[f[n - 1] = \cfrac{f[n - 2] + 3}{2} \]代入。
\[\begin{aligned} f[n - 2] &= \cfrac{f[n - 3] + f[n - 1] + 3}{2} \\ &= \cfrac{f[n - 3] + \cfrac{f[n - 2] + 3}{2} + 3}{2} \\ \Rightarrow f[n - 2] &= \cfrac{2f[n - 3] + 9}{3} \end{aligned} \]继续。
\[\begin{aligned} f[n - 3] &= \cfrac{f[n - 4] + f[n - 2] + 3}{2} \\ &= \cfrac{f[n - 4] + \cfrac{2f[n - 3] + 9}{3} + 3}{2} \\ \Rightarrow f[n - 3] &= \cfrac{3f[n - 4] + 18}{4} \end{aligned} \]这么做看不出什么规律，考虑记 \(f[i] = k[i] \cdot f[i - 1] + b[i]\)
有 \(\left\{\begin{matrix} k[n - 1] = \cfrac{1}{2} \\ b[n - 1] = \cfrac{3}{2} \end{matrix}\right.\)。
考虑求递推式：
\[\begin{aligned} f[i] &= \cfrac{f[i - 1] + f[i + 1] + 3}{2} \\ &= \cfrac{f[i - 1] + k[i + 1] \cdot f[i] + b[i + 1] + 3}{2} \\ \Rightarrow f[i] &= \cfrac{f[i - 1] + b[i + 1] + 3}{2 - k[i + 1]} \end{aligned} \]即 \(\left\{\begin{matrix} k[i] = \cfrac{1}{2 - k[i + 1]} \\ b[i] = \cfrac{b[i + 1] + 3}{2 - k[i + 1]} \end{matrix}\right.\)
俩数列？
先来看看 \(k\)
\[\cfrac{1}{2}, \cfrac{2}{3}, \cfrac{3}{4}, \cfrac{4}{5}, \cfrac{5}{6}, \cfrac{6}{7}, \cfrac{7}{8}, \cfrac{8}{9}, \cfrac{9}{10}, \cfrac{10}{11}, \cfrac{11}{12}, \cfrac{12}{13}, \cfrac{13}{14}, \cfrac{14}{15}, \cfrac{15}{16}, \cfrac{16}{17}, \cfrac{17}{18}, \cfrac{18}{19}, \cfrac{19}{20}, \cfrac{20}{21}, \ldots \]似乎 \(k[n - i] = \cfrac{i}{i + 1}\)。
归纳一下？
证明：
对于 \(i = 1\) 成立。假设对于 \(n - (i - 1)\) 成立。则：
\[\begin{aligned} k[n - i] &= \cfrac{1}{2 - k[n - (i - 1)]} \\ &= \cfrac{1}{2 - \cfrac{i - 1}{i}} \\ &= \cfrac{i}{2i - i + 1} \\ &= \cfrac{i}{i + 1} \end{aligned} \]成立，则证毕。
再来看看复杂些的 \(b\)
\[\cfrac{3}{2}, 3, \cfrac{9}{2}, 6, \cfrac{15}{2}, 9, \cfrac{21}{2}, 12, \cfrac{27}{2}, 15, \cfrac{33}{2}, 18, \cfrac{39}{2}, 21, \cfrac{45}{2}, 24, \cfrac{51}{2}, 27, \cfrac{57}{2}, 30, \ldots \]情不自禁地变换一下。
\[\cfrac{3}{2}, \cfrac{6}{2}, \cfrac{9}{2}, \cfrac{12}{2}, \cfrac{15}{2}, \cfrac{18}{2}, \cfrac{21}{2}, \cfrac{24}{2}, \cfrac{27}{2}, \cfrac{30}{2}, \cfrac{33}{2}, \cfrac{36}{2}, \cfrac{39}{2}, \cfrac{42}{2}, \cfrac{45}{2}, \cfrac{48}{2}, \cfrac{51}{2}, \cfrac{54}{2}, \cfrac{57}{2}, \cfrac{60}{2}, \ldots \]哦，似乎 \(b[n - i] = \cfrac{3i}{2}\)，归一下纳。
证明：
对于 \(i = 1\) 成立。假设对于 \(n - (i - 1)\) 成立。则：
\[\begin{aligned} b[n - i] &= \cfrac{b[n - (i - 1)] + 3}{2 - k[n - (i - 1)]} \\ &= \cfrac{\cfrac{3(i - 1)}{2} + 3}{2 - \cfrac{i - 1}{i}} \\ &= \cfrac{3i(i - 1) + 6i}{4i - 2(i - 1)} \\ &= \cfrac{3i^2 + 3i}{2i + 2} \\ &= \cfrac{3i}{2} \end{aligned} \]成立，则证毕。
得出结论
那么回到一开始的问题：
\[\begin{aligned} f[0] &= f[1] + 3 \\ &= k[1] \cdot f[0] + b[1] + 3 \\ &= k[n - (n - 1)] \cdot f[0] + b[n - (n - 1)] + 3 \\ &= \cfrac{n - 1}{n} f[0] + \cfrac{3(n - 1)}{2} + 3 \\ \Rightarrow f[0] &= \cfrac{3}{2}n^2 + \cfrac{3}{2}n \end{aligned} \]当 \(n = 0,1,\ldots\) 时，\(f[0]\) 即答案为：
\[0, 3, 9, 18, 30, 45, 63, 84, 108, 135, 165, 198, 234, 273, 315, 360, 408, 459, 513, 570, \ldots \]发现易证明均为整数。
未完待续
无左边界的上述问题……
标签：begin,end,18,3i,cfrac,随机,思考,游走,aligned From： https://www.cnblogs.com/XuYueming/p/18262702