来自减压群的一道概率

kuing

老鱼(5755*****) 12:59:22

直接考虑一般情况，设初始数为 $n$，考虑过程中出现 $m$ 的概率。

假设由 $n$ 操作到 $m$ 的过程为 $n\to n_1\to n_2\to\cdots\to n_k\to m$，因为由 $a$ 一次操到 $b$ 的概率为 $1/a$，所以此过程的概率为 $1/(nn_1n_2\cdots n_k)$。

由于 $\{n_1, \ldots, n_k\}$ 可以取遍 $\{n-1,n-2,\cdots,m+1\}$ 的任意子集（包括空集，即一操操到 $m$ 时），所以总的概率为
\begin{align*}
P&=\sum_{\{n_1,\ldots ,n_k\}\subseteq \{n-1,n-2,\ldots ,m+1\}}\frac 1{nn_1n_2\cdots n_k}\\
&=\frac 1n+\sum_{n>i>m}\frac 1{ni}+\sum_{n>i>j>m}\frac 1{nij}+\sum_{n>i>j>k>m}\frac 1{nijk}+\cdots +\frac 1{n(n-1)\cdots (m+1)}\\
&=\frac 1n\left( 1+\frac 1{n-1} \right)\left( 1+\frac 1{n-2} \right)\cdots \left( 1+\frac 1{m+1} \right)\\
&=\frac 1{m+1},
\end{align*}
也就是说结果其实只和经过的数字有关，与初始值无关。

PS、结果如此简单，直觉告诉我极可能存在非常简单的解法。

kuing

有了。

设由 $n$ 开始操作，过程中出现 $m$ 的概率为 $f(n,m)$。

设第一次操作后变成 $k$，这一步的概率为 $1/n$，对于 $n>k>m$ 的，则再由 $k$ 到 $m$，概率为 $f(k,m)$，于是有
\[f(n,m)=\frac1nf(n-1,m)+\frac1nf(n-2,m)+\cdots +\frac1nf(m+1,m)+\frac1n,\]
若记 $f(m,m)=1$，上式即
\[nf(n,m)=f(n-1,m)+f(n-2,m)+\cdots +f(m,m),\]
将 $n$ 变为 $n+1$，即
\[(n+1)f(n+1,m)=f(n,m)+f(n-1,m)+f(n-2,m)+\cdots +f(m,m)
=(n+1)f(n,m),\]
所以
\[f(n+1,m)=f(n,m),\]
因此概率完全由 $m$ 决定，与 $n$ 无关，所以可取 $n=m+1$，即得概率为 $P=1/(m+1)$。

231908

回复 2# kuing
初中的我竟然看懂了！

游客

回复 2# kuing


    应该是条件概率的意思，在“随机数出现在0~m”的条件下，这个随机数正好是m的概率。
比如“依次出现10，8，7，5”这个事件的概率，可以写成为p=(4/10)(1/4)(2/8)(1/2)(6/7)(1/6).
即：每次都把可能出现的随机数都分成两组来考虑。
“10，8，7，5”——（9876）（543210）中选到8；（76）（543210）中选到7；（6）（543210）中选到5。

kuing

回复 4# 游客

soga，我好像理解了……

或者这样讲，规则可以改成，如果操作得到的数 $\leqslant m$ 就停止（因为后面的已经无关重要），这样，只考虑最后一次操作，由某个数操作到 $\leqslant m$，那么就是楼上所讲的：在“随机数出现在0~m”的条件下，这个随机数正好是m的概率。也就是 $1/(m+1)$。

kuing

回复 4# 游客

嗯，你后来补充的我也看懂了，谢谢！

其妙

回复 1# kuing
不过你的也很棒

敬畏数学

这题看得我头有点晕，清醒再看吧。