Thanks Anubhav C for great solution above, which was very helpful for illuminating the problem's solution.
I think using 0.25 as probability (mentioned above by ) can be misleading and incorrect! If we look at the probability #dead_cases/#total_possible_moves the results will be different.
Consider the following code for finding die/surviving cases:
def winLoss_stat(N, steps):
newStats = [[[0, 0, 0] for i in range(N)] for j in range(N)]
if steps==0:
newStats = [[[1, 0, 0] for i in range(N)] for j in range(N)]
return newStats
oldStats = winLoss_stat(N, steps-1)
for i in range(N):
for j in range(N):
for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
indX = i + d[0]
indY = j + d[1]
if indX >=0 and indX < N and indY >= 0 and indY<N:
newStats[i][j][0] += oldStats[indX][indY][0]
newStats[i][j][1] += oldStats[indX][indY][1]
newStats[i][j][2] += oldStats[indX][indY][2]
else:
newStats[i][j][1] += 1
if steps==1:
newStats[i][j][2] = 1
return newStats
(or equivalently, for one step (using dfs - recursive):
class winLoss:
def __init__(self, N):
self.win = 0
self.loss = 0
self.N = N
def winLoss(self, x, y, n):
if x < 0 or y < 0 or x >= self.N or y >= self.N:
self.loss += 1
return
if n == 0:
self.win += 1
return
self.winLoss(x - 1, y, n-1)
self.winLoss(x, y - 1, n-1)
self.winLoss(x+1, y, n-1)
self.winLoss(x, y+1, n-1)
wl = winLoss(n)
wl.winLoss(i, j, n)
for any i,j start point and n (size of square)
)
The winLoss_stat returns three values for starting point at each square i, j:
[numbers of survive cases, numbers of die cases before or at k steps, numbers of death exactly at step k]
The results are as the following for n=4 (4X4), steps=4:
0 1 2 3
0 [58, 24, 12] [93, 34, 18] [93, 34, 18] [58, 24, 12]
1 [93, 34, 18] [150, 46, 28] [150, 46, 28] [93, 34, 18]
2 [93, 34, 18] [150, 46, 28] [150, 46, 28] [93, 34, 18]
3 [58, 24, 12] [93, 34, 18] [93, 34, 18] [58, 24, 12]
This translates to the following probabilities for
1. death before or at k steps:
0 1 2 3
0 0.292683 0.267717 0.267717 0.292683
1 0.267717 0.234694 0.234694 0.267717
2 0.267717 0.234694 0.234694 0.267717
3 0.292683 0.267717 0.267717 0.292683
2. death exactly at k steps:
0 1 2 3
0 0.146341 0.141732 0.141732 0.146341
1 0.141732 0.142857 0.142857 0.141732
2 0.141732 0.142857 0.142857 0.141732
3 0.146341 0.141732 0.141732 0.146341
The results can be verified by looking at the numbers of win-loss from step 1 to 3 for n=3:
winLoss_stat(3, 1)
0 1 2
0 [2, 2, 1] [3, 1, 1] [2, 2, 1]
1 [3, 1, 1] [4, 0, 0] [3, 1, 1]
2 [2, 2, 1] [3, 1, 1] [2, 2, 1]
winLoss_stat(3, 2)
0 1 2
0 [6, 4, 2] [8, 5, 2] [6, 4, 2]
1 [8, 5, 2] [12, 4, 4] [8, 5, 2]
2 [6, 4, 2] [8, 5, 2] [6, 4, 2]
winLoss_stat(3, 3)
0 1 2
0 [16, 12, 4] [24, 13, 8] [16, 12, 4]
1 [24, 13, 8] [32, 20, 8] [24, 13, 8]
2 [16, 12, 4] [24, 13, 8] [16, 12, 4]
"What is the probability that he is dead after he walks n steps on the island?"This doesn't say you have to pick the steps (fair enough, it doesn't say anything about walking randomly either). Also, OP's attempt at the problem seems to indicate simply calculating the probability."random walk on a lattice"is reasonably advanced terminology and we both know questions are often not stated exactly as meant. But arguing any more over assumptions made won't be constructive, OP has to clarify. – Bernhard Barker