在2D网格中随机漫步所覆盖的区域是什么？

Question

我是一名生物学家,申请工作,我需要解决这个问题.这是一个开放的书籍测试,互联网和任何其他资源是公平的游戏.这是一个问题 - 我一直坚持如何处理它,并希望指点.我的直觉被张贴在下面.

背景

你的邻居是一头有两头奶牛的农夫,Clarabelle和Bernadette.每头奶牛都有自己的方形笔,一边是11米(见第一张图).这位农民正前往城外旅游,并计划将奶牛放在各自的围栏中,这些围栏完全被草丛填满.奶牛开始在笔的中心,并将慢慢地围着笔吃草.它们非常缓慢地在笔周围移动,在每一步之后总是停下来吃饭或休息.如果将笔分成1米的正方形,奶牛可以在每一步向任何方向移动一个方格(如棋盘上的国王),如第二张图所示.

每次移动后,如果可以的话,奶牛将在新的广场上吃草20分钟.一旦广场上的草被吃掉,它就永远消失了.如果母牛移动到已经吃过草的广场上,那么母牛将在那个广场上休息20分钟.20分钟后,无论是休息还是进食,奶牛都会移动到另一个广场.如果母牛在栅栏附近的广场上,她将永远不会试图向栅栏方向移动.奶牛不会连续两次停留在同一个广场上 - 它们在休息或进食后总是会移动到另一个广场.第一个图显示了几个小时后笔可能看起来像什么的例子,棕色斑点表示已经放牧的方格.

第一头牛Clarabelle在移动时不喜欢方向.她同样有可能随时向任何方向移动.设p是她向一个方向移动的概率,如下图所示.

第二头母牛伯纳黛特(Bernadette)喜欢走向草坪广场.当她走向一个已经吃过的空间时,她走向有草的空间的可能性是她的两倍,如下图所示.

问题

• 如果农民在48小时后回来,你期望Clarabelle吃掉她笔中有多少百分比的草？
• 你期望伯纳黛特能在她的笔中吃掉50%的草需要多长时间？
• 假设如果任何一头奶牛24小时不吃草,她就会死.预计哪头牛会活得更久？

我的直觉

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

编辑:这里的最终目标是为我编写某种程序.这不是一个纯粹的数学问题,因此这里的帖子.

Answer 1

以下是计算概率的方法（对于 Clarabelle）：

1. 从 的网格开始0，除了单元格上的 1 之外(6, 6)，这是时间 的概率网格t = 0。

2. 在时间，位于单元格上的t + 1概率由下式给出：（总和中有八项）。p(x, y, t + 1)(x, y)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（基本上，这是考虑一个马尔可夫链，其中状态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, ...是概率性的，因此每个相邻单元格都有两项。

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