一个人在矩阵中移动n步的死亡概率

Question

有一个岛由方阵nxn表示.

岛上的人站在任何给定的坐标(x,y).他可以在岛上向右,向左,向上,向下一步向任何方向移动.如果他走出岛外,他就死了.

将岛表示为(0,0)到(n-1,n-1)(即nxn矩阵)并且人站在给定的坐标(x,y)处.他被允许在岛上移动n步(沿着矩阵).他在岛上走了几步后死亡的可能性是多少？

使用编程技术找到概率的方法应该是什么？

我有一个数学方法,但我不知道它是否正确.这里是:

结果总数为n ^ n.计算可能导致死亡的结果数量:

对于四个方向中的每个方向,检查可以导致他走出矩阵的步数.然后,应用高中概率公式.例如,假设他可以采取的步骤总数为5; (x,y)=(2,1)[索引是基于0的].所以,他需要在北方队采取3个步骤.从岛上掉下来.将它们保持在一组:(NNN)并将其他两个步骤作为4个选项中的任何一个,我们有公式:4*4*3.同样,对于其他3个方向.最后,概率=(计算的死亡结果的总和)/(总结果)

这是一个谷歌面试问题.

Answer 1

TL; DR:递归.(或"数学归纳",如果你是势利的话.)

(在接下来的内容中,"他n在岛上走路后已经死了"被认为是"他在经过不到或等于n步骤后死亡".如果你认为"他在完全n步骤后死亡",答案将是稍微不同.我会在最后简要讨论一下.)

我们有一个NxN矩阵,其中每个单元格中的值表示n如果我们从该单元格开始就会逐步死亡的概率.

考虑0步骤死亡的可能性.显然,这0.0适用于岛内的每个位置,以及岛外的每个位置1.0.

在1步骤中死亡的可能性是多少？您可以以相同的概率移动四个方向.因此,对于每个细胞,您将其四个邻居,找到他们分0步死亡的概率,并将它们平均在一起.(如果邻居在矩阵之外,则考虑它的概率1.0.)

类似地,k从给定细胞k-1开始的步骤中死亡的概率是从其相邻细胞开始的步骤中死亡的概率的平均值.

Python代码:

from itertools import product as prod 

def prob_death(island_size, steps):
    if island_size < 1 or steps < 0: raise ValueError
    new_prob = [[0. for i in range(island_size)] for j in range(island_size)]
    if steps == 0:
        return new_prob
    old_prob = prob_death(island_size, steps - 1)
    directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    for (i, j, direction) in prod(range(island_size), range(island_size), directions):
        neighbor_i = i + direction[0]
        neighbor_j = j + direction[1]
        if neighbor_i >= 0 and neighbor_i < island_size and \
                neighbor_j >= 0 and neighbor_j < island_size:
            prob_death_this_way = old_prob[neighbor_i][neighbor_j]
        else: # neighbor is outside the island 
            prob_death_this_way = 1.
        new_prob[i][j] += 0.25* prob_death_this_way
    return new_prob

现在,让我们稍微测试一下:( mpr这只是一个很好地打印矩阵的功能)

>>> mpr(prob_death(5, 0))
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000

正如预期的那样:如果你在岛内开始,你不能在0步骤死亡.

>>> mpr(prob_death(5,1))
0.500000 0.250000 0.250000 0.250000 0.500000
0.250000 0.000000 0.000000 0.000000 0.250000
0.250000 0.000000 0.000000 0.000000 0.250000
0.250000 0.000000 0.000000 0.000000 0.250000
0.500000 0.250000 0.250000 0.250000 0.500000

这是我们所期望的.如果你从角落单元开始,你有0.5可能在一步中死亡:你的4个邻居中有2个在岛外.如果你从一个边缘开始,只有一个邻居在外面,所以你的死亡概率是0.25.在其他地方,所有邻居都在岛内,因此一步死亡的可能性是0.0.

>>> mpr(prob_death(5, 5))
0.806641 0.666016 0.622070 0.666016 0.806641
0.666016 0.437500 0.349609 0.437500 0.666016
0.622070 0.349609 0.261719 0.349609 0.622070
0.666016 0.437500 0.349609 0.437500 0.666016
0.806641 0.666016 0.622070 0.666016 0.806641

死亡的概率分为5个步骤.我无法验证确切的值,但它看起来是正确的:死角的概率在角落处最高,在边缘处略低,并且向内稳定地减少.

这解决了小于或等于n步骤死亡的问题.

现在,以精确的 n步骤找出死亡的概率:让死亡的概率小于或等于n从开始的步骤开始(x,y)表示P(x,y,n).然后,确切n步骤中死亡的概率是步骤存活的概率,是在n-1步骤中死亡的概率乘以n我们为n-1步骤存活的时间:(1-P(x,y,n-1))*(P(x,y,n) - P(x,y,n-1)).(我对这个公式不太确定;如果我错了,请纠正我.)