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

[J-F Garnier]

During my search for another (better) solution, I considered counting the different paths and attempting to deduce the probability from the path tree. For the case 5 rows/4 steps, I found the same numbers of paths as Peter, with 16 paths ending at the bottom row over a total of 144. And here I was puzzled because the probability 16/144=0.111111... is significantly different from Valentin's hint 23/288=0.07986... confirmed by the results of Fernando's program or mine.

So to remove any doubt, I attempted to use the Monte-Carlo statistical approach to confirm the probability in this particular case, since 5 rows/4 steps is still manageable in this way.
Here is my program:

 10 OPTION BASE 0
 20 DIM G(15,6)
 30 ! the nodes are coded from P=1 to 15:
 40 !        1
 50 !       2 3
 60 !      4 5 6
 70 !     7 8 9 10
 80 !   11 12 13 14 15
 90 ! matrix G(,) codes the graph:
100 ! G(P,0) codes the number of neighbours of node P
110 ! G(P,1..6) code the neighbouring nodes, up to 6
120 ! the zeros are just fillers.
130 DATA 0,0,0,0,0,0,0
140 DATA 2,2,3,0,0,0,0
150 DATA 4,1,3,4,5,0,0
160 DATA 4,1,2,5,6,0,0
170 DATA 4,2,5,7,8,0,0
180 DATA 6,2,3,4,6,8,9
190 DATA 4,3,5,9,10,0,0
200 DATA 4,4,8,11,12,0,0
210 DATA 6,4,5,7,9,12,13
220 DATA 6,5,6,8,10,13,14
230 DATA 4,6,9,14,15,0,0
240 DATA 2,7,12,0,0,0,0
250 DATA 4,7,8,11,13,0,0
260 DATA 4,8,9,12,14,0,0
270 DATA 4,9,10,13,15,0,0
280 DATA 2,10,14,0,0,0,0
290 READ G(,)
300 !
310 K=0
320 M=10000 ! number of trials
330 FOR I=1 TO M
340   P=1 ! start at node 1
350   FOR J=1 TO 4
360      N=G(P,0) ! number of neightbours
370      X=INT(RND*N+1) ! select one randomly 1..N
380      P=G(P,X) ! move to this node
390   NEXT J
400   IF P>=11 THEN K=K+1 ! count if at last row
410 NEXT I
430 DISP K/M

and the result is ... indeed around 0.08 and not 0.11, confirming the value 23/288 given by Valentin and the validity of the published programs above :-)

Now, I think I understood why 16/144 is NOT the probability of ending in the last row: there are indeed 16 paths over 144 that end in the last row, but all paths are not equally probable, we can't just do 16/144.
However, I thought that my little program was worth to be published here.

J-F