每次随机杀掉一个奇数位的人后的存活概率问题

作者: , 共 2266 字 , 共阅读 0

600 个人站一排,每次随机杀掉一个奇数位的人,几号最安全?

在最前面,为了简单,我们用一个简记符号,其中$ \lceil x\rceil $表示上取整:

$$ \tau_{x} = \lceil \frac{x}{2} \rceil $$

现在我们假设有 $n$ 个人,第$k$ 个人存活到最后的概率为$p(n,k)$。考虑第一个杀死的人的位置,很容易我们就能得到递推式子:

$$ p(n, k) = \frac{\tau_{k-1}}{\tau_n} \times p(n-1,k-1) + \frac{\tau_n-\tau_k}{\tau_n} \times p(n-1, k)$$

到这里之后可以用计算机程序快速算出数值结果。但这里有个奇妙的地方在于,它的符号解也特别简单:

$$ p(n, k) = \frac{\tau_{k-1}}{\tau_{n-1}\tau_n} $$

更直观的看,每个人存活的概率为 0, 1, 1, 2, 2, 3, 3, 这样一直下去,最后再标准化(使得概率总和为 1 )。结果非常优美。

很容易验证上面的结果和递推式。但如果不是提前知道答案,直接从上面的递推式子很难猜到。我们可以换一种方法,注意到下面这个事实:前面的$m$个人的存活(相对)概率分布和后面有多少人没有关系,这样我们只用把最后一个人的存活概率算出来,然后再往前推,就可以获得所有的存活概率。

最后一个人存活概率$p(n) = p(n, n)$有一个简单递推式:

$$ p(2n) = p(2n-1)$$
$$p(2n+1) = \frac{n}{n+1} p(2n)$$

结合$p(1) = p(2) = 1 $,很简单就可以得出:

$$ p(n) = \frac{1}{\tau_n}$$

然后我们算倒数第二个人:

$$ p(n,n-1)=(1-p(n))\times p(n-1) = \frac{\tau_{n-2}}{\tau_{n-1}\tau_n}$$

然后有一个特别好的递归式:

$$ \tau_0 + \tau_2 + \cdots + \tau_{n-1} = \tau_{n-1} \tau_n$$
$$ \tau_{k-1}\tau_k + \tau_k + \tau_{k+1} + \cdots + \tau_{n-1} = \tau_{n-1} \tau_n$$

用上面式子类似地往前推,可以得出:

$$\begin{equation}\begin{split} p(n,k)&=(1-p(n,k+1)-p(n,k+2)-\cdots-p(n,n))\times p(k,k) \\ &= \frac{\tau_{n-1} \tau_n-\tau_k-\tau_{k+1}-\cdots-\tau_{n-1}}{\tau_{n-1} \tau_n} \times\frac{1}{\tau_k} \\ &= \frac{\tau_{k-1}\tau_k}{\tau_{n-1} \tau_n}\times\frac{1}{\tau_k } \\ &= \frac{\tau_{k-1}}{\tau_{n-1}\tau_n} \end{split} \end{equation}$$

Q. E. D.

类似文章:
风险管理 » VaR Primer
VaR 衡量一个投资的收益的分位点,衡量未来在一定概率上的损失情况,但某些时候还不够,比如说卖出一个深度价外期权,它的 VaR 为 0 ,但这不代表它没有风险。这类风险被称为尾部风险,可以用 ES 来衡量。
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
利用线性代数可以给某些问题很精妙的证明,Matrix67 就给出了一个这样的例子,这也让我想起以前看见的另外一个例子,分享如下:
IBM 的 Ponder This 项目每个月会发出一个谜题,这个月的题目是加倍交换数字游戏
相似度: 0.057
这是一个老问题,最近有老同学问起,就在这里提一下吧。
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
相似度: 0.054
$ n$ 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
相似度: 0.053
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
从事部门量化策略开发岗的工作,主要工作职责如下:
周末跟队伍去探洞房山的彩虹洞,位于房山的堂上民俗村。