醉虫漫步记(2019年)

来见见虫子拉里。拉里和他的朋友们在酒吧里畅饮了一个美妙的夜晚。

唉，拉里喝得有点太醉了，所以当他和他的朋友喝完酒后，他就醉醺醺地走(呃，爬)回家了。

拉里和他的朋友们住在一条一维的路上。拉里喝醉了，他随意地走回家。每一步，概率为0.5，他将向右行走，概率为0.5，他将改为向左行走。此外，每一步都独立于它之前和之后的一步，并且所有步的长度都是恒定的。

哦，顺便说一句，拉里是酒吧的老板，而且住在里面，他喝得烂醉，忘了酒吧是他的家。…。无论如何，问题仍然是，拉里最终会回家吗？

拉里的步行回家是一个典型的一维随机行走的概率，在一维。我们可以将拉里的道路建模为一行中的所有数字，酒吧(以及拉里的家)在数字0上。每一步都是等概率的左或右行走，每一步都是相互独立的。向右走相当于在拉里的位置上加1，向左走相当于减1。

假设，在不丧失一般性的情况下，Larry在他的第一步就向右走到1(如果他向左走，证明仍然是一样的)。我们现在要问的问题是，拉里在回家之前升到2的概率有多大(如果有的话)？

这很容易回答，如果他先到0，他在1之后向左转，否则他向右转到2，所以概率等于0.5，因为这是向左转的概率。

现在我们问一个类似的问题，拉里在去4点之前回家的概率是多少？要到4才能到0，拉里必须通过2，所以他需要在0之前到2。如前所述，概率为0.5。他数到2以后，情况看起来是这样的：

现在，他在得到0之前从2到4的概率是多少。请注意，0和4与2的距离相等。此外，Larry的行走没有优先考虑任何一个方向(左或右)。因此，如果我们交换0和4，则根本不会影响概率(对于每一种达到4的方式，都有一种相同概率达到0的方式，反之亦然)。因此，通过对称，拉里有相等的机会(各0.5)先到0和先到4。

把这些放在一起，拉里要在0之前达到4，他必须在0之前达到2，在0之前从2到4。每个步骤都有0.5的概率，因此由于这些步骤是独立的，因此发生这种情况的概率为0.5*0.5=0.25。

现在我们在归纳法中重复这个过程。也就是说，对于每个n，我们证明了Larry在0之前到达2n的概率是(0.5)n。实际上，假设我们已经证明了n=k，现在我们想证明n=k+1。因此，和前面一样，Larry要想在0之前到达2k+1，他必须首先在0之前到达2k。根据我们的假设，概率为(0.5)k。

当他到达2k时，注意到Larry正好在0和2k+1之间，所以像以前一样，通过对称，Larry在到达0之前从这里到达2k+1的概率是0.5。因此，Larry在0之前到达2k+1的概率是(0.5)k+1。我们用归纳法证明了这一点(因为我们已经讨论了基本情况n=1)。

对于那些不熟悉归纳法的人来说，可以认为这是一种多米诺骨牌效应。我们证明了n=1的论点，如果该论点对n=k成立，那么它对n=k+1也成立。因此，它对n=1成立意味着它对n=2成立，n=2对n=3成立，依此类推。

现在我们注意到我们以前忽略的以下重要事实。拉里最终会逃脱任何有限的间隔。也就是说，对于每一对整数m<；k，如果Larry在m和k之间，他最终会逃离m和k之间的区间，也就是说，他要么到了k的右边，要么到了m的左边。

以下是如何证明这一点的草图。当停留在区间内时，Larry在每一步都可以在随后的k-m步中向右走k-m步，概率为(0.5)k-m。由于区间的长度是k-m，这将把Larry带到k的右侧，从而超出区间。这种情况发生的概率很低，但却是一个非零常数。因此，有了足够的时间，拉里将向右走k-m步，并走出中场休息(如果他还没有这样做的话)。

现在我们可以完成校样了。让我们看看Larry再也不回家的事件(在他先向右迈出一步的情况下，正如前面所述的另一种情况类似)。如前所述，Larry将逃脱任何有限的间隔，特别是对于任何正整数n，0和2n之间的间隔。在Larry没有回家的事件中，他必须通过2n逃脱该间隔，因为0是他的家

但是他会在到达0之前到达2n，正如我们通过归纳法证明的那样，概率是(0.5)n。因此，对于每个正整数n，Larry永远不回家的概率小于(0.5)n。让n到无穷远，(0.5)n接近于0，因此Larry永远不回家的概率一定小于0，因此是零。因此，拉里很有可能会回家，所以他几乎肯定会回家。

下面是我们证明的一个有趣的结果。假设拉里永远不会停止漫步，即使他回到家。事实证明，这意味着拉里最终会无限次地到达队伍中的任何一点，无论他从哪里开始(几乎是肯定的)。

要了解原因，请注意，在Larry第一次返回到0之后，他实际上会重新开始他的行走。由于步数是独立的，因此他返回到0的方式对他未来的行走没有任何影响。因此，在第一次返回到0之后，他将重新开始行走，因此几乎可以肯定再次返回到0。类似地，在那之后，他几乎肯定会再次返回到0，一次又一次，一次又一次，以此类推。因此，几乎可以肯定的是，他会在无限多的步数中处于0。

现在，设k是数字行上的整数。从0开始，如果拉里向左走|k|步或向右走|k|步(取决于k的符号)，他将到达k。这有(0.5)|k|发生的恒定概率。这可以是非常低的，但仍然是积极的。因此，由于拉里无限次访问0，在其中一次访问中，他最终将完成这些|k|步骤，并达到k.q.e.d。

(与以前类似，我们可以证明Larry将无限次返回k)。

顺便说一句，拉里和IS的朋友们可以去酒吧聊天等等，是因为他们是超智能的变种蠕虫。现在他们来找血了。

在2059年的人虫大战中，拉里和他的朋友们是蠕虫坦克营的一员，袭击了戈壁沙漠的多个地点。按照传统，拉里和他的朋友们一起玩，一起喝酒。不幸的是，他们也酒后驾车(坦克)。

他们醉醺醺地把坦克开出基地，然后进行一次二维的随机漫步。在每一步，他们以相等的概率向前、向后、向左或向右行驶，每一步的概率都是0.25，每一步的长度都是相同的(戈壁沙漠也是无限的平原，由于某种原因完全被剥夺了)。

从数学上讲，我们可以使用晶格Z^2(整数的平方)对其进行建模。也就是说，坐标晶格(x，y)，其中x和y是整数。随机游走从(0，0)(Larry的军事基数)开始，每一步都是：

每一步都以0.25的概率发生，每一步都独立于其他步骤。

我们现在问的问题和以前一样。拉里和他的朋友最终会回到基地吗？

也许我们可以用我们已经证明的关于一维随机游动的东西。如果我们只看x坐标，那么在每一步，它要么以0.25的概率增加1，以0.25的概率减少1，要么以0.5的概率保持不变(当坦克在y轴上移动时)，当然所有的步骤都是独立的。这有点类似于以前的一维随机漫游，只是在每一步都有机会停留在原地。然而，不难看出与之前相同的结果，即x坐标最终将返回到0。

类似地，我们可以证明y坐标最终将返回到0。事实上，由于我们所展示的一维随机游动，这意味着x坐标将无限次为0，y坐标也是如此。

可悲的是，我们现在被困住了。尽管x坐标和y坐标都将无限多次为0，但这并不意味着它们最终都将同时为0，这意味着返回到(0，0)。

因此，也许因为那次尝试失败了，拉里不幸的不会总是回到他的基地。毕竟，在某种意义上，二维平面比它前面的那条线“大”，所以在那里更容易迷路。然而，事实证明，拉里和他的团队确实会回到(0，0)。这里的证据太多了，所以我会在这篇文章的末尾加上一个证据。

所以拉里和他的蠕虫同伴成功地征服了地球，消灭了人类。现在他们准备离开地球，探索外太空，成为太空文明。

拉里和他的伙伴们被选为探索太空的第一批蠕虫。不幸的是，他们又喝醉了。和以前一样，拉里的旅程是一次随机漫步(呃，太空旅行)。在每一步中，他们的宇宙飞船上下、右、左、向前或向后移动的概率都是相等的(如果你把外层空间看作一个3D空间，对这些方向的含义有一个清晰的概念)，他们的宇宙飞船每一步都会向上、向下、向右、向左、向前或向后移动。

我们可以再次将其数学建模为3D随机漫游。宇宙飞船的每个位置都是Z^3格中的一个矢量(x，y，z)，其中x，y和z是整数。宇宙飞船从(0，0，0)开始，在每一步，宇宙飞船都以相等的概率沿着一个基本方向行进。

问题还是和以前一样。拉里的宇宙飞船最终会返回地球吗？一种可能的方法是再次尝试使用我们已经知道的关于一维和二维随机行走的知识。但和以前一样，这一尝试遗憾的是没有任何结果。但是看起来他还是会像以前一样返回地球，对不对？

事实证明，答案出人意料地是否定的。以正概率，拉里的宇宙飞船永远不会返回地球，它与地球的距离将接近无穷远，拉里将永远在太空中徘徊。

同样，证据过于密集，不能包含在这里，所以我为下面感兴趣的人提供了一个指向它的链接。也许并不令人惊讶的是，在高于3维的随机游动中，游动的概率也是正的，它将不会返回原点。

对我个人来说，这个例子是真正让我了解概率的事情之一。从直觉上看，二维行走有时似乎不会回到原点，但令人惊讶的是，它确实以1的概率返回。然后，在看到二维行走回到原点之后，你的直觉告诉你，它在三维情况下也是成立的。但同样，直觉是错误的，事实证明，三维和更高维度的行走可能不会回到原点。当我在第一节概率课的第一节课上看到这一点时，我感到震惊。

我将以一个问题结束这篇帖子。回到一维随机游走，我们知道它几乎肯定会回到原点。但这平均要走多少步呢？