Prawdopodobieństwo śmierci człowieka poruszającego się n krokami w macierzy

Po pierwsze, zacznij od macierzy z prawdopodobieństwem bycia w kwadracie (x, y) w 0 kroku. Zasymulujmy to matrycą 4x4. Zakładając, że facet zaczyna od (1, 2):

After 0 steps:
  0.00%   0.00%   0.00%   0.00%
  0.00%   0.00% 100.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
outside:   0.00%
----
After 1 steps:
  0.00%   0.00%  25.00%   0.00%
  0.00%  25.00%   0.00%  25.00%
  0.00%   0.00%  25.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
outside:   0.00%
----
After 2 steps:
  0.00%  12.50%   0.00%  12.50%
  6.25%   0.00%  25.00%   0.00%
  0.00%  12.50%   0.00%  12.50%
  0.00%   0.00%   6.25%   0.00%
outside:  12.50%
----
After 3 steps:
  4.69%   0.00%  12.50%   0.00%
  0.00%  14.06%   0.00%  12.50%
  4.69%   0.00%  14.06%   0.00%
  0.00%   4.69%   0.00%   4.69%
outside:  28.12%
----
After 4 steps:
  0.00%   7.81%   0.00%   6.25%
  5.86%   0.00%  13.28%   0.00%
  0.00%   9.38%   0.00%   7.81%
  2.34%   0.00%   5.86%   0.00%
outside:  41.41%
----

Oto program Pythona, który oblicza to:

class Table:
    def __init__(self, n, outside=0):
        self.T = [[0]*n for i in xrange(n)]
        self.outside = outside

    def add(self, i, j, value):
        n = len(self.T)
        if 0<=i<n and 0<=j<n:
            self.T[i][j] += value
        else:
            self.outside += value

    def make_next(self):
        n = len(self.T)
        Q = Table(n, self.outside)

        for i in xrange(n):
            for j in xrange(n):
                value = self.T[i][j] / 4.0
                Q.add(i-1, j, value)
                Q.add(i+1, j, value)
                Q.add(i, j-1, value)
                Q.add(i, j+1, value)
        return Q

    def __repr__(self):
        return '\n'.join(' '.join(
                    '{:6.2f}%'.format(item*100) 
                    for item in line)
                    for line in self.T) + \
               '\noutside: {}'.format('{:6.2f}%'.format(self.outside*100))


N = 4
T = Table(N)
T.add(1, 2, 1)

for k in xrange(N+1):
    print 'After {} steps:'.format(k)
    print T
    print '----'

    T = T.make_next()

Jest to bardzo złożony i niuansowy problem -- podejrzewam, że celem ankieterów nie było usłyszenie, jak wymyślisz odpowiedź, ale raczej zobaczyć, jak podchodzisz do problemu.

Problem staje się szachownicą N kwadraty na boku, z pozornie przypadkowym rozmieszczeniem części, która musi poruszać się N spacjami, poruszając się w pozornie przypadkowym kierunku kardynalnym każdego obrotu. Prawdopodobieństwo, że element opuści planszę jest więc związane nie tylko z wielkością deska, ale umieszczenie elementu. Ponieważ każdy ruch poza planszą również liczy się jako opuszczenie planszy, Ścieżka jest zatem istotna również.

Dla siatki 2×2, pionek ma 2/7 prawdopodobieństwa pozostania na planszy (cztery ścieżki pozostają na planszy, czternaście ścieżek ogółem, niezależnie od tego, który z czterech możliwych punktów początkowych).

Dla siatki 3×3, element ma 2/11 prawdopodobieństwo pozostania na planszy (16 ścieżek pozostaje na, 88 wszystkich ścieżek) jeśli zaczyna się na rogu. Jeśli zaczyna się na stronie, ma prawdopodobieństwo 3/11 (24 ścieżki pozostają na). Jeśli zaczyna się w centrum, ma prawdopodobieństwo 9/22 (36 ścieżek pozostaje na). Ponieważ każdy element ma 4/9 prawdopodobieństwa rozpoczęcia w rogu lub na boku, a 1/9 prawdopodobieństwo rozpoczęcia w centrum, jego całkowite prawdopodobieństwo pozostania na planszy jest (2/11 + 3/11) × 4/9 + 9/22 × 1/9 = 0.247.

Siatka 4×4 staje się (oczywiście) jeszcze bardziej skomplikowana, ale być może warto zauważyć, że siatki są zgodne ze wzorem:

2×2:

- - 1 - -
- 2 - 2 -
1 - 2 - 1
- 2 - 2 -
- - 1 - -

3×3:

- - - 1 - - -
- - 3 - 3 - -
- 3 - 9 - 3 -
1 - 9 - 9 - 1
- 3 - 9 - 3 -
- - 3 - 3 - -
- - - 1 - - -

Zacząłem na siatce 4×4, ale nie dzięki. Plac startowy wydaje się mieć 36 ścieżek prowadzących do niego, a ich identyfikacja jest, cóż, żmudna. W każdym przypadku element zaczyna się na środku wzoru i możemy narysować planszę według własnego uznania.

Jest jednak ewidentnie wzorzec i dość krzyczy, że istnieje symetria matematyczna, ale nie mam ani czas ani cierpliwość, aby to wypracować. Każdy biegun ma jedną ścieżkę, następna grupa punktów końcowych ma N ścieżki, a następna grupa wydaje się mieć n² / align = "left" / Podejrzewam, że popełniłem błąd w liczeniu najbardziej wewnętrznego zestawu punktów końcowych dla siatki 4×4, ale jeśli nie, 36 = n (n - 1)², co sugeruje wzór pierścieni.

Podejście powinno opierać się na wzorze probabilistycznym-liczba przypadków korzystnych / całkowita liczba przypadków

Podane współrzędne (x, y) i stopnie-n Całkowita liczba sposobów, w jakie użytkownik może podjąć kroki -
1. Krok - 4 sposoby 2. Krok-4 * 3 (zakładając, że nie może zrobić kroku wstecz) 3. Krok - 4 * 3^2 ... .... ... nth Krok - 4*3^(n-1) Artmetic progresji daje całkowite kroki.

Farovable cases - tj. przekraczanie granic-funkcja rekurencyjna z rekurencją na wszystkich 4 kierunkach i zmiennej incr policz za każdym razem, gdy granica macierzy zostanie przekroczona.

Podziel oba, aby uzyskać odpowiedź.

Dzięki Anubhav C za świetne rozwiązanie powyżej, które było bardzo pomocne w oświetleniu rozwiązania problemu. Myślę, że użycie 0,25 jako prawdopodobieństwa (o którym mowa powyżej ) może być mylące i błędne! Jeśli spojrzymy na prawdopodobieństwo # dead_cases/ # total_possible_moves, wyniki będą różne.

Rozważ następujący kod do znajdowania przypadków śmierci / przetrwania:

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]