23-随机游走

可交换事件

• 从测度空间 出发。令

  令 为乘积 -代数， 为乘积概率测度。

• 的一个有限置换，是从 到自身的一一映射，并且除了有限多个点之外固定其余所有点。

• 如果事件 在 的任何有限置换下都保持不变，就称 是可置换的。

• 令 为所有可置换事件构成的 -域。

• 它与本课程前面介绍的尾 -代数有关。它更大还是更小？

Hewitt–Savage 零一律

• 如果 独立同分布，并且 ，那么

• 证明思路： 设法证明 与自身独立，也就是说，

  首先使用一个测度论事实：可以用由 生成的 -代数中的集合 逼近 ，使得 与 的对称差具有非常小的概率。把 与 交换后，让 表示 成立这一事件；注意， 与 相互独立。 与 的对称差也很小，所以除去这个很小的误差后， 与自身独立。最后让误差任意小。

Hewitt–Savage 零一律的应用

• 如果 是 中的独立同分布随机变量，那么

  是 上的一个随机游走。

• 定理： 如果 是 上的随机游走，那么下列情形之一以概率 1 发生：

  • 对所有 ，都有 ；
  • ；
  • ；

• 证明思路： Hewitt–Savage 零一律表明， 与 是 中的几乎必然常数。注意，如果 不是几乎必然为常数，而这两个值又不属于 ，那么它们都会依赖于 。

停止时的定义

• 如果对每个 ，事件

  就称 为一个停止时。

• 在金融应用中， 可以是一个人卖出股票的时刻。这一条件表示：在时刻 卖出的决定只取决于截至时刻 的价格，而不取决于尚且未知的未来价格。

停止时的例子

• 设 是独立同分布随机变量，分别以概率 取值 和 。令

• 下列哪些是停止时？

  1. 使 的最小 ；
  2. 使 的最小 ；
  3. 使 的最小 ；
  4. 序列 第 9 次取得数值 17 的时刻 ；
  5. 使 最大的那个 ；
  6. 使 的最大 。

• 答案：前四个是停止时，后两个不是。

关于停止时的定理

• 定理： 设 独立同分布， 是满足 的停止时。

• 在停止时 的条件下，

  的条件概率律与 独立，并且与原序列具有相同的概率律。

• Wald 等式： 设 独立同分布，并且

  如果 是满足 的停止时，那么

• Wald 第二等式： 设 独立同分布，并且

  如果 是满足 的停止时，那么
  

Wald 等式在简单随机游走中的应用

• 设 。在每个时步， 都按照一次公平抛硬币的结果，独立地增加或减少 1。固定 ，并令

  是多少？

• 是多少？

反射原理

• 从 到 、且不穿过水平轴的游走路径有多少条？

• 可以尝试先数那些确实穿过水平轴的游走路径：把它们与从 到 的游走路径建立双射。

投票定理

• 假设在一次选举中，候选人 获得 票，候选人 获得 票。在整个计票过程中， 始终领先的概率是多少？

• 答案：

  可以利用反射原理证明。

反正弦定理

• 关于最后一次到达时刻的定理。

• 关于处于正值状态的时间总量的定理。

随机游走

可交换事件

• 从测度空间 出发。令

  令 为乘积 -代数， 为乘积概率测度。

• 的一个有限置换，是从 到自身的一一映射，并且除了有限多个点之外固定其余所有点。

• 如果事件 在 的任何有限置换下都保持不变，就称 是可置换的。

• 令 为所有可置换事件构成的 -域。

• 它与本课程前面介绍的尾 -代数有关。它更大还是更小？

Hewitt–Savage 零一律

• 如果 独立同分布，并且 ，那么

• 证明思路： 设法证明 与自身独立，也就是说，

  首先使用一个测度论事实：可以用由 生成的 -代数中的集合 逼近 ，使得 与 的对称差具有非常小的概率。把 与 交换后，让 表示 成立这一事件；注意， 与 相互独立。 与 的对称差也很小，所以除去这个很小的误差后， 与自身独立。最后让误差任意小。

Hewitt–Savage 零一律的应用

• 如果 是 中的独立同分布随机变量，那么

  是 上的一个随机游走。

• 定理： 如果 是 上的随机游走，那么下列情形之一以概率 1 发生：

  • 对所有 ，都有 ；
  • ；
  • ；

• 证明思路： Hewitt–Savage 零一律表明， 与 是 中的几乎必然常数。注意，如果 不是几乎必然为常数，而这两个值又不属于 ，那么它们都会依赖于 。

停止时的定义

• 如果对每个 ，事件

  就称 为一个停止时。

• 在金融应用中， 可以是一个人卖出股票的时刻。这一条件表示：在时刻 卖出的决定只取决于截至时刻 的价格，而不取决于尚且未知的未来价格。

停止时的例子

• 设 是独立同分布随机变量，分别以概率 取值 和 。令

• 下列哪些是停止时？

  1. 使 的最小 ；
  2. 使 的最小 ；
  3. 使 的最小 ；
  4. 序列 第 9 次取得数值 17 的时刻 ；
  5. 使 最大的那个 ；
  6. 使 的最大 。

• 答案：前四个是停止时，后两个不是。

关于停止时的定理

• 定理： 设 独立同分布， 是满足 的停止时。

• 在停止时 的条件下，

  的条件概率律与 独立，并且与原序列具有相同的概率律。

• Wald 等式： 设 独立同分布，并且

  如果 是满足 的停止时，那么

• Wald 第二等式： 设 独立同分布，并且

  如果 是满足 的停止时，那么
  

Wald 等式在简单随机游走中的应用

• 设 。在每个时步， 都按照一次公平抛硬币的结果，独立地增加或减少 1。固定 ，并令

  是多少？

• 是多少？

提纲

• 随机游走
• 停止时
• 反正弦律及简单随机游走的其他故事

反射原理

• 从 到 、且不穿过水平轴的游走路径有多少条？

• 可以尝试先数那些确实穿过水平轴的游走路径：把它们与从 到 的游走路径建立双射。

投票定理

• 假设在一次选举中，候选人 获得 票，候选人 获得 票。在整个计票过程中， 始终领先的概率是多少？

• 答案：

  可以利用反射原理证明。

反正弦定理

• 关于最后一次到达时刻的定理。

• 关于处于正值状态的时间总量的定理。