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

Question

我是一名生物学家，正在申请一份工作，需要解决这个问题。这是一份开卷考试，可以使用互联网和任何其他资源，以下是问题 - 我不知道如何解决它，并希望得到指导。我的直觉在下面。

背景

你的邻居是一个有两只奶牛Clarabelle和Bernadette的农民。每头奶牛都有自己的正方形围栏，边长为11米（见第一张图）。农民计划离开镇子出门旅行，打算把奶牛留在它们各自的圈里，这些圈子里开始时完全填满草。奶牛在圆心开始移动，并会慢慢地绕着围栏吃草。它们移动非常缓慢，每走一步就会停下来吃草或休息。如果将笼子分成1米的正方形，奶牛每次可以沿任意方向移动一个正方形（就像国王在棋盘上移动一样），如第二张图所示。

每次移动后，奶牛会在新的方块中花20分钟吃草，如果有草的话。一旦一个正方形中的草被吃完，就永远没有了。如果奶牛移动到一个已经吃过草的方块上，那么她将在那个方块休息20分钟。无论是休息还是吃草，20分钟后，奶牛都会移动到另一个方块。如果一头奶牛处于靠近围栏的方块旁边，它永远不会朝着围栏的方向移动。奶牛从不在同一个正方形里连续停留 - 它们总是在休息或吃草后移动到另一个方块。第一张图展示了围栏在一些小时后可能看起来的样子，棕色斑点表示已经吃草的方块。

第一只奶牛Clarabelle在移动时没有方向偏好。她随时都有同等的可能性朝任何方向移动。让p是她向某个方向移动的概率，如下面的第一张图所示。

第二头奶牛Bernadette更喜欢移动到有草的方格。如下图所示，与已经吃过的空间相比，她移动到有草的空间的概率要高出两倍。

问题

• 如果农民在48小时后回来，您预计Clarabelle会吃掉围栏里百分之多少的草？
• 您认为Bernadette需要多长时间才能吃掉她围栏里50%的草？
• 假设两头奶牛中的任何一头24小时没有吃到任何草，它就会死亡。哪头奶牛预计可以生存更长时间？

我的直觉

这似乎是通过一个二维网格进行随机游走的建模。例如，我可以计算在给定时间后位于特定节点的概率。但我不确定如何考虑奶牛在行走时覆盖的区域。如果您有任何见解，请告诉我。

编辑：这里的最终目标是让我编写某种程序。这不是纯数学问题，因此帖子发布在此处。

- mission1983

---

我投票关闭此问题，因为它似乎是关于数学的，没有特定的编程方面（请尝试http://math.stackexchange.com）。 - Oliver Charlesworth

实际上，这是一个算法问题 - 最终目的是编写一个程序来计算概率。这怎么会是离题的呢？ - mission1983

好的，但现在的问题是弄清楚数学，对吗？ - Oliver Charlesworth

@OliverCharlesworth，一个模拟过程并汇总统计数据的计算机程序，就像Lior建议的那样，我认为它直接涉及计算机编程。当你仅仅因为你认为问题只涉及数学而关闭问题时，这样的创造性解决方案就没有机会出现。（一般来说，我认为SO是关于对编程感兴趣的人——他们通常也对数学感兴趣——而不是关于编程与数学的区别。） - גלעד ברקן

@OliverCharlesworth 在SO上引起人们兴趣的问题可能是一个不断发展的对话，可能会或可能不会涉及“具体的编程角度”。当你关闭它时，你切断了SO用户社区之间的创造性过程 - 这些人从编程、数学和其他领域中汲取灵感。既然SO上的人显然对此感兴趣，为什么要关闭它呢？ - גלעד ברקן

Answer 1

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

如果您使用基于蒙特卡罗方法的模拟过程，可以通过对多个试验结果求平均值轻松找到答案。

我认为这是您应该做的事情，除非另有指示。

- Lior Kogan

Answer 2

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

1. 从一个网格开始，除了在单元格（6,6）上为1以外，其余都为0，这是时间t = 0的概率网格。 2. 在时间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（48小时）。

如果你想知道一个细胞已被吃掉的概率，那么它就是简单的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算法有点复杂，因为你的是概率性的，所以每个相邻单元格都有两个项。

一旦你拥有所有这些概率，你就可以轻松找到你想要的。

- Holt

---

这可能适用于计算Clarabelle在某个时间和地点的概率，实际上是在计算马尔可夫链的转移矩阵（参见这个有趣分析中的后半部分，讲述了一个简单游戏）。这对Bernadette不起作用，因为她的移动将取决于先前的历史。我认为你关于已经被吃掉的单元格的公式是错误的，因为它可以变成多个。应该像这样：pe(x,y,t) = (1 - p(x,y,t)) * pe(x,y,t-1) + p(x,y,t)。 - Bas Swinckels

此外，你的解决方案可能不被称为“动态规划”，而更多地被称为计算“马尔可夫链”，但无论如何你的答案都不错。 - Bas Swinckels

是的，可能就是这样，需要区分在时间t吃饭和已经在之前的步骤中吃过了。我仍然相信这通常不被称为DP解决方案，因为你通常是基于更小的子问题来解决问题（类似但仍然不同于分治），并且通常使用记忆化来加速计算。并非每个迭代方案都是DP... - Bas Swinckels

@BasSwinckels 是的，回过头来看，你可能是对的，这不是DP（我编程的方式让我想到了DP，但这不是）。 - Holt

感谢大家的答案和评论。这真的很有帮助。 - mission1983