[VA] SRC #012a - Then and Now: Probability

[Albert Chan]

(10-13-2022 12:04 PM)Fernando del Rey Wrote:  And you could also consider the symmetry of the solution if the man is starting at cell (1,1), calculating only half of the grid. But then the algorithm would not be valid for a starting position which is not located in the central column of the grid, which is therefore not symmetrical.

If the goal is row probability, symmetric solution can still work.

Say, D is starting distribution, D' is its mirror image, P_i is i-th row probability
Note: sum of probability distribution = 1.0

Symmetry: P_i(D) = P_i(D') = P_i(D + D')

Example, below 3 initial conditions produce same row probability.

A(1,1)=1/2 @ A(3,2)=1/6 @ A(3,1)=1/3 ! asymmetric distribution
A(1,1)=1/2 @ A(3,2)=1/6 @ A(3,3)=1/3 ! mirror image
A(1,1)=1/2 @ A(3,2)=1/6 @ A(3,1)=1/6 @ A(3,3)=1/6 ! symmetric distribution

For row probability, we can transform to symmetric distribution, then process only half the grid.