蹒跚学步

First Steps

专题: Probability / 概率
难度: L8
来源: OpenQuant

题目详情

一个婴儿正在客厅沙发的帮助下学习走路。宝宝从沙发上开始，在每个给定的时间宝宝都会做出决定。它要么勇敢地向前迈出一步，站在原地不知道该做什么，要么害怕地向后退一步，走向沙发，概率分别为 $0.2$ 、 $0.5$ 和 $0.3$ 。婴儿永远不会走到沙发后面（因此，当婴儿在沙发上时，向前移动的概率为 $0.2$ ，留在沙发上的概率为 $0.8$ ）。

如果你要观察这个婴儿很长一段时间，那么婴儿坐在沙发上的时间比例是多少？

A baby is learning to walk with the assistance of its living room couch. The baby starts at the couch and at each given time the baby will make a decision. It will either take a brave step forward, stand in place not knowing what to do, or fearfully take a step back towards the couch with probabilities $0.2$ , $0.5$ , and $0.3$ respectively. The baby will never go behind the couch (so when at the couch the baby has probability $0.2$ of moving forward and probability $0.8$ of staying at the couch).

If you were to observe this baby for an extremely long amount of time, what proportion of the time would the baby be at the couch?

解析

假设我们创建一个包含状态 $S_0, S_1, ...S_n$ 的状态图，其中 $S_n$ 表示婴儿在距离沙发几步的状态 $n$ 处花费的时间。使用我们的决策矩阵 $\tiny{\begin{bmatrix} 0.2 \\ 0.5 \\ 0.3 \end{bmatrix}}$ ，我们可以绘制婴儿的状态图。在先前状态下位于 $S_0$ 并静止不动或从 $S_1$ 移回沙发后，婴儿将位于沙发或 $S_0$ 处。因此， $S_0 = 0.8S_0 + 0.3S_1$ 同样，我们得到： $S_1 = 0.2S_0 + 0.5S_1 + 0.3S_2 \newline S_2 = 0.2S_1 + 0.5S_2 + 0.3S_3 \newline S_3 = 0.2S_2 + 0.5S_3 + 0.3S_4 \newline \vdots\\ S_n = 0.2S_{n-1} + 0.5S_{n} + 0.3S_{n+1}$ 通过简化这些方程，我们可以识别出一种模式： $S_0 = 0.8S_0 + 0.3S_1 \longrightarrow S_0 = 1.5S_1$ 将 $1.5S_1$ 代入 $S_1$ 方程，我们得到： $S_1 = 0.2(1.5S_1) + 0.5S_1 + 0.3S_2 \longrightarrow S_1 = 1.5S_2$ 显然，所有后续状态方程都可以重写为 $S_n = 1.5S_{n+1}$ 这告诉我们，与 $S_n$ 相比，婴儿在 $S_{n+1}$ 上花费的时间与 $\frac23$ 一样多。我们知道所有这些状态之和必须为一并且具有公共比例 $\frac23$ 。我们可以创建无限几何和： $S_0 + \frac23S_0 + \frac49S_0 + \dots + (\frac23)^nS_0 = 1$ 将总和乘以 $\frac32$ 我们得到： $\frac52S_0 + \frac23S_0 + \frac49S_0 \dots + (\frac23)^{n-1}S_0 = \frac32$ 用第二个方程减去第一个方程得到： $\frac32S_0 = \frac12 \longrightarrow S_0 = \boxed{\frac13}$ 因此，宝宝在沙发上的时间大约为 $\frac13$ 。

import random

#logs state baby has traveled to
state_log = [0]

num_transitions = 10_000
for i in range(num_transitions):

    #modeling random walk using random variable t
    t = random.randint(1,10)

    if t <= 2:
        state_log.append(state_log[-1] + 1)
    elif t <= 7:
        state_log.append(state_log[-1])
    else:
        state_log.append(max(state_log[-1] - 1, 0))

#Expecting value close to 1/3
print((state_log.count(0)-1)/len(state_log))

Original Explanation

Suppose we create a state diagram with states $S_0, S_1, ...S_n$ where $S_n$ represents the time a baby spends at the state $n$ steps from the couch. Using our decision matrix $\tiny{\begin{bmatrix} 0.2 \\ 0.5 \\ 0.3 \end{bmatrix}}$ , we can map the state diagram of the baby. The baby will be at the couch, or $S_0$ , after being at the $S_0$ in the previous state and standing still or moving back towards the couch from $S_1$ . Thus,

S_0 = 0.8S_0 + 0.3S_1

Similarly, we get:

S_1 = 0.2S_0 + 0.5S_1 + 0.3S_2 \newline S_2 = 0.2S_1 + 0.5S_2 + 0.3S_3 \newline S_3 = 0.2S_2 + 0.5S_3 + 0.3S_4 \newline \vdots\\ S_n = 0.2S_{n-1} + 0.5S_{n} + 0.3S_{n+1}

By simplifying these equations, we can identify a pattern: $S_0 = 0.8S_0 + 0.3S_1 \longrightarrow S_0 = 1.5S_1$

Substituting in $1.5S_1$ into our $S_1$ equation we get: $S_1 = 0.2(1.5S_1) + 0.5S_1 + 0.3S_2 \longrightarrow S_1 = 1.5S_2$

It is evident that all subsequent state equations can be re-written as $S_n = 1.5S_{n+1}$ What that tells us is the baby will spend $\frac23$ as much time in $S_{n+1}$ compared to $S_n$ . We know that all these states must sum to one and have common ration $\frac23$ . We can create the infinite geometric sum:

S_0 + \frac23S_0 + \frac49S_0 + \dots + (\frac23)^nS_0 = 1

Upon multiplying the sum by $\frac32$ we get: $\frac52S_0 + \frac23S_0 + \frac49S_0 \dots + (\frac23)^{n-1}S_0 = \frac32$

Subtracting the first equation from the second gets us: $\frac32S_0 = \frac12 \longrightarrow S_0 = \boxed{\frac13}$

Thus, the baby will be at the couch roughly $\frac13$ of the time.

import random

#logs state baby has traveled to
state_log = [0]

num_transitions = 10_000
for i in range(num_transitions):

    #modeling random walk using random variable t
    t = random.randint(1,10)

    if t <= 2:
        state_log.append(state_log[-1] + 1)
    elif t <= 7:
        state_log.append(state_log[-1])
    else:
        state_log.append(max(state_log[-1] - 1, 0))

#Expecting value close to 1/3
print((state_log.count(0)-1)/len(state_log))