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

[Fernando del Rey]

Here’s the raw code to get quick results using Emu71/Win, with no attemps to optimize execution speed or to minimize memory usage. I have ideas for how to do both, but I wanted just to test the algorithm and get quick results.

The idea of the algorith is simple. Wherever the man starts, in our case at position (1,1) in the grid, he has a certain probability to move to the adjacent cells.

If the man is located at any if the 3 corner cells of the grid, he has a 1/2 probability to move to any of their two adjacent cells.

If he is located in a border cell, he has a 1/4 probability to move to each of the 4 adjacent cells.

If he is located at any of the remaining inner cells, he has a 1/6 probability to move to each of its 6 adjacent cells.

The program calculates a probability matrix after each step (matrix B) from the results of the probability matrix resulting from the previous step (matrix A).

After some trivial initilization (lines 10 to 50), the program iterates M times (M number of steps) in the big loop ranging from lines 60 to 240.

Line 70 copies matrix B to A and clears matrix B to start the calculation of a new probability matrix at each step.

Lines of code 80, 90 and 100 calculate the probability propagation of the corner cells.

Lines 120 and 130 calculate the probability propagation of the left border cells. Lines 140 and 150 calculate the propagation of the right border cells. Lines 160 and 170 calculate the propagation of the lower border cells.

Lines 190 to 230 calculate the probability propagation of the inner cells.

Finally, to obtain the probabilty of the man finishing at the lower line of the grid, we just need to add the probabilities of all cells in the lower line of the grid (line 250).

If we would like to know the probability of the man finishing at any other location of the grid after M steps, we just need to look at the final probability map in matrix B.

Also, if we want to know what happens if the man starts at an (X,Y) location different from the upper corner, we just need to change line 50 to B(X,Y)=1.

Please note the the program listing is a manual transcription from the code in Emu71/Win. I have tried to be careful to avoid any errors, but I cannot be 100% sure. I don’t know how a to do a copy/paste of the program code in Emu71/Win. If anyone could guide me how to do it, I’d be most grateful.

In a physical 71B, this program will take about 108 minutes to resolve the 30/60 case. As mentioned earlier, it can surely be optimized for speed, but I was looking for simplicity and code clarity just to test the algorithm, not speed or memory usage optimization.

You may have noticed that I am a complete newbe with the 71B. I had to do a quick read of the manual to be able to produce this code as I have practically no experience with the 71B. But I must admit it has been real fun!

Here's the code:

10 DESTROY ALL @ OPTION BASE 1 @ STD
20 INPUT “Grid Size? “;N
30 INPUT “# Steps? “;M
40 REAL A(N,N), B(N,N), F
50 B(1,1)=1
60 FOR K=1 TO M
70 FOR I=1 TO N @ FOR J=1 TO I @ A(I,J)=B(I,J) @ B(I,J)=0 @ NEXT J @ NEXT I
80 F=A(1,1)/2 @ B(2,1)=F @ B(2,2)=F
90 F=A(N,1)/2 @ B(N-1,1)=F @ B(N,2)=F
100 F=A(N,N)/2 @ B(N-1,N-1)=F @ B(N,N-1)=F
110 FOR I=2 TO N-1
120 F=A(I,1)/4 @ B(I-1,1)=B(I-1,1)+F
130 B(I,2)=B(I,2)+F @ B(I+1,1)=B(I+1,1)+F @ B(I+1,2)=B(I+1,2)+F
140 F=A(I,I)/4 @ B(I-1,I-1)=B(I-1,I-1)+F
150 B(I,I-1)=B(I,I-1)+F @ B(I+1,I)=B(I+1,I)+F @ B(I+1,I+1)=B(I+1,I+1)+F
160 F=A(N,I)/4 @ B(N,I-1)=B(N,I-1)+F
170 B(N-1,I-1)=B(N-1,I-1)+F @ B(N-1,I)=B(N-1,I)+F @ B(N,I+1)=B(N,I+1)+F
180 NEXT I
190 FOR I=3 TO N-1 @ FOR J=2 TO I-1
200 F=A(I,J)/6 @ B(I-1,J-1)=B(I-1,J-1)+F @ B(I-1,J)=B(I-1,J)+F
210 B(I,J-1)=B(I,J-1)+F @ B(I,J+1)=B(I,J+1)+F
220 B(I+1,J)=B(I+1,J)+F @ B(I+1,J+1)=B(I+1,J+1)+F
230 NEXT J @ NEXT I
240 NEXT K
250 F=0 @ FOR I=1 TO N @ F=F+B(N,I) @ NEXT I @ DISP “Pr.=”;F