二维网格中随机游走所覆盖的区域是多少？

Question

我是一名生物学家，正在申请一份工作，我需要解决这个问题。这是一个开卷测试，互联网和任何其他资源都是公平的游戏。这是问题 - 我坚持如何处理它并希望得到指点。我的直觉在下面 posted。

背景

您的邻居是一位农民，有两头奶牛，克拉拉贝尔和伯纳黛特。每头奶牛都有自己的边长为 11m 的方形围栏（见第一张图）。农夫正准备出城旅行，并计划将奶牛留在各自的围栏中，开始时这些围栏里全是草。奶牛从围栏中央开始，慢慢地绕着围栏移动吃草。他们在围栏周围移动非常缓慢，每走一步后总是停下来吃饭或休息。如果把围栏分成1m的方格，奶牛每走一步可以向任意方向移动一个方格（就像棋盘上的王），如图二

每次移动后，如果有空的话，牛会在新方格吃草 20 分钟。广场上的草一旦被吃掉，就永远消失了。如果奶牛移动到一个已经吃完草的方格，那么奶牛将在那个方格中休息 20 分钟。 20 分钟后，无论是休息还是进食，牛都会移动到另一个方格。如果一头牛在栅栏附近的一个方格中，她将永远不会尝试朝栅栏的方向移动。奶牛不会连续两次在同一个方格停留——它们总是在休息或进食后移动到不同的方格。第一个图显示了几个小时后钢笔的外观示例，棕色斑点表示已被擦伤的方块。

第一头母牛 Clarabelle 在移动时没有方向偏好。她在任何时候都同样有可能朝任何方向移动。令p为她朝某个方向移动的概率，如下图第一张图所示。

第二头牛伯纳黛特更喜欢向有草的方块移动。她走向有草的 space 的可能性是她走向已经吃过的 space 的可能性的两倍，如下面第二个图所示。

问题

如果农夫 returns 在 48 小时后，您预计 Clarabelle 吃掉了她围栏中的草的百分比是多少？
您预计 Bernadette 吃掉围栏中 50% 的草需要多长时间？
假设如果其中一头牛 24 小时不吃草，她就会死。哪头牛预计存活时间更长？

我的直觉

这似乎是在对二维网格中的随机游走进行建模。例如，我可以计算出在给定时间后出现在网格中特定节点的概率。但是我不确定如何考虑奶牛走过时所覆盖的区域。非常感谢任何见解。

编辑：我的最终目标是为此编写某种程序。这不是一个纯粹的数学问题，因此这里 post。

Answer 1

这是一种计算概率的方法（对于 Clarabelle）：

从 0 的网格开始，除了 (6, 6) 单元格上的 1，这是时间 t = 0.
的概率网格
在时间 t + 1，出现在单元格 (x, y) 上的概率 p(x, y, t + 1) 由下式给出：p(x, y, t + 1) = p1 * p(x + 1, y, t) + p2 * p(x + 1, y - 1, t) + ...（您有八个术语总和).

请注意，所有 pi 都不等于：概率可以是 1/3（角）、1/5（边）或 1/8（任何其他单元格） ).

您可以通过运行这一步动态更新您的网格 t = 0 到 t = 144 (48h)。

如果你想知道一个单元格已经被吃掉的概率，它只是 1 - Pn 其中 Pn 如果单元格从未被访问过的概率是：

(1 - p(x, y, 0)) * (1 - p(x, y, 1)) * (1 - p(x, y, 2)) * ...

这是一个使用 Python 中的 numpy 计算这些概率的代码（基本上，这是考虑一个 Markov Chain，其中状态 X 是所有单元格 |X| = 121，转移矩阵 T = {T_ij} 其中 T_ij 是从 i 移动到 j 的概率） :

GridSize = 11
TranSize = GridSize * GridSize
T_Matrix = np.zeros((TranSize, TranSize), dtype = float)

for u in range(T_Matrix.shape[0]):
    for v in range(T_Matrix.shape[1]):
        ux, uy = u % GridSize, u // GridSize
        vx, vy = v % GridSize, v // GridSize
        if u == v or abs(ux - vx) > 1 or abs(uy - vy) > 1:
            p = 0
        elif (ux == 0 or ux == 10) and (uy == 0 or uy == 10):
            p = 1/3
        elif ux == 0 or ux == 10 or uy == 10 or uy == 0:
            p = 0.2
        else:
            p = 0.125
        T_Matrix[u, v] = p

pxy = np.zeros((TranSize, ), dtype = float)
pxy[11 * 5 + 5] = 1
eat = 1 - pxy

for _ in range(144):
    pxy = pxy.dot(T_Matrix)
    eat *= (1 - pxy)

print((1 - eat).reshape((GridSize, GridSize)))

Bernadette 的算法稍微复杂一些，因为您的 p1, p2, ... 是概率性的，所以每个相邻单元格都有两个项。

一旦你掌握了所有这些概率，你就可以轻松找到你想要的东西。

Answer 2

有两种方法可以解决此类问题：分析或模拟。

如果您使用 Monte-Carlo based method 来模拟该过程，您可以通过对多次试验的结果进行平均来轻松找到答案。

我假设这是你应该做的，除非你得到其他指导。

二维网格中随机游走所覆盖的区域是多少？

What is the area covered by a Random walk in a 2D grid?

algorithm

random-walk

背景

问题

我的直觉