奥兹国会不会有不开心的部落?

机器算法验证 可能性 随机过程
2022-03-11 03:38:47

这是一个学生给我带来的一个有趣的问题。虽然最初的措辞是用枪定期发射的相互歼灭的子弹,但我认为您可能会喜欢更平和的介绍。

在奥兹无限平坦的世界中,黄砖路始于翡翠城的中心,蜿蜒穿过乡村,永无交叉。每天中午,一个精力充沛的年轻雌雄同体 Tribble 从它的原点开始沿着这条道路以统一随机选择的速度滚动,最高可达每天一公里。在整个旅程中,它将以相同的速度滚动,永不停息。但是,如果一个 Tribble 在路上超过另一个,每个人都会立即认出它的灵魂伴侣,然后两个人就会掉到一边(大概是为了繁殖并最终提供更多 Tribbles 回家)。

如您所知,这种交配经常发生,因为任何两个 Tribbles 以完全相同的速度滚动的机会为零。哦,快乐的 Tribbles!但生活能保证对他们所有人都有好处吗?

至少有一个 Tribble 永远持续下去,永远不会超车或被超车的可能性有多大?

1个回答

编辑:我似乎混淆了正概率和概率 1 的概念。这里证明的陈述比我希望的要弱得多。

直观地说,答案是 0。不难证明

任何给定的 Tribble 以正概率最终得到一个配偶。

但我认为这可能不足以暗示,根据芝诺悖论,在正概率下,每个tribble 最终都会得到一个配偶。

这是引用声明的证明。首先,让我们用一个更简单的替代公式代替这个问题,如下所示。有一个堆栈开始为空。计算机从 [0, 1] 中独立且均匀地按顺序绘制随机变量。每次绘制一个值时,堆栈都会更改。

  • 如果堆栈为空,或者堆栈顶部的项目具有更大的值,则添加一个具有新值的新项目。(已创建比最后一个子弹慢的子弹或比最后一个 Tribble 慢的 Tribble。)
  • 否则,顶部项目被删除。(子弹或 Tribbles 相撞。)

(这个公式不包括子弹或 Tribble 的事件比前一个创建的速度更快,然后在它击中前一个之前被销毁,但是这样的事件使堆栈保持不变,所以它没有任何后果。)

我想证明任何给定的项目,具有正概率,最终都会从堆栈中删除。我们可以不失一般性地假设永远不会绘制是现有项目,是它的值。以上的项目数,而它们的值按顺序排列,其中是当前顶部项目的值。如果接下来要绘制的值分别落在区间、区间等直到,则1I0v0kI0v1,v2,,vkvkk+1(vk,1)(vk1,1)(v0,1)I0和它上面的所有项目都将被删除。这个事件的概率是,它是正数的有限乘积,所以它是正数。(1vk)(1vk1)(1v0)