一个概率问题

· · 算法·理论

突发奇想，编了一个问题。

引入

如图所示，假设有一个数轴，你初始位于原点，目标位于第 n 个点。你有一个骰子，能产生 1 到 6 之间的一个随机数。每次投骰子，得到的数是多少，你就向右移动多少个单位。求：你经过目标的概率是多少。

我们可以设经过第 n 个点的概率为 f(n)。

经过递推，可以得到：

f(n)=\begin{cases} 1 & n = 0 \\ \sum_{i=0}^{n-1} f(i) \times \frac{1}{6} & 1 \le n \le 6 \\ \sum_{i=n-6}^{n-1} f(i) \times \frac{1}{6} & n \ge 7 \end{cases}

问题

那么问题来了，当 n 趋向于无穷大时，求 f(n) 等于多少？即求 \lim_{n \to \infty} f(n) 的值。

\lim_{n \to \infty} f(n) = \frac{2}{7}

问题拓展

如果骰子能产生 1 到 m 之间的一个随机数，\lim_{n \to \infty} f(n) 将变为多少？

f(n)=\begin{cases} 1 & n = 0 \\ \sum_{i=0}^{n-1} f(i) \times \frac{1}{m} & 1 \le n \le m \\ \sum_{i=n-m}^{n-1} f(i) \times \frac{1}{m} & n \ge m+1 \end{cases} \lim_{n \to \infty}f(n)=\frac{2}{m+1}