随机游走问题

文章预览

引入 想象一只甲虫在一个弯曲的管子里, 假定管子是无限长的 , 这个小生物无休止的随机游走, 它每次在管子里随机的向前或向后移动一步. 最终它能回到起点的概率是多少？ [1] 这是著名的 “随机游走”(Random Walks)问题 . 最早是于1905年, 由卡尔·皮尔逊提出. 我们先简单来分析一下, 不妨将管子看成是一个整数轴, 甲虫在数轴上随机游走, 从 开始, 每一步都以 的概率移动 (向左)或 (向右). 那么5步以后, 它可能在哪些位置呢？ 若 步中有 步向左, 步向右, 不管先后顺序, 甲虫最终会落在 , 根据组合计数原理, 可知总共有 种方式即 条路径. 具体的是：左右右右右, 右左右右右, 右右左右右, 右右右左右, 右右右右左. 要正式定义甲虫走过的路径, 我们可以采用独立随机变量 , 每一个变量分别有 的概率为 , 或 . 更一般的, 一维随机游走问题可定义如下： 每过一个 ………………………………