one-way random walks

A rather puzzling riddle from The Riddler on an 3×3 directed grid and the probability to get from the North-West to the South-East nodes following the arrows. Puzzling because while the solution could be reasonably computed with an R code like

sucz=0
for(i in 1:2^12){
  path=intToBits(i)[1:12]
  sol=0
  for(j in 1:12)sol=max(sol,
        prod(path[paz[[j]][paz[[j]]>0]]==01)*
        prod(path[-paz[[j]][paz[[j]]<0]]==00))
  sucz=sucz+sol

where paz is the list of the 12 possible paths from North-West to South-East (excluding loops!), leading to a probability of 1135/2¹², I could not find a logical reasoning to reach this number. The paths of length 4, 6, 8 are valid in 2⁸, 2⁶, 2⁴ of the cases, respectively and logically!, but this does not help as they are dependent.

This entry was posted on May 2, 2021 at 12:21 am and is filed under Kids, R, Statistics with tags FiveThirtyEight, R, self-avoiding random walk, The Riddler. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

11 Responses to “one-way random walks”

finnstats Says:
May 8, 2021 at 7:04 pm

Good one…

Reply
Carl Witthoft Says:
May 4, 2021 at 1:06 pm

Remind me NEVER to visit this town!

Reply
gd047 (@gd047) Says:
May 2, 2021 at 11:54 am

Could you give us the paz list, so we can replicate your solution?

Reply
- xi'an Says:
  May 2, 2021 at 12:21 pm
  
  Of course, here it is!
```
paz=list(
  a=c(3,8,11,12),b=c(3,6,7,10),d=c(3,6,9,12),
  e=c(1,4,7,10),f=c(1,4,9,12),g=c(1,2,5,10),
  h=c(3,8,11,-9,-4,2,5,10),
  i=c(1,2,5,-7,-6,8,11,12),
  j=c(3,6,-4,2,5,10),k=c(3,8,11,-9,7,10),
  l=c(1,2,5,-7,9,12),m=c(1,4,-6,8,11,12))
```
  Reply
  - gd047 (@gd047) Says:
    May 2, 2021 at 3:04 pm
    
    Thanks, Great piece of R code!
    How would you modify it to get the number of ways that you could also return to the North-West corner (home) ?
  - xi'an Says:
    May 2, 2021 at 5:17 pm
    
    Just as a mere guess: I would look at all pairs of paths…
  - gd047 (@gd047) Says:
    May 3, 2021 at 9:27 am
    
    f() for 1-way solutions, f2() for 2-way
    https://ibb.co/4N3StCJ
  - xi'an Says:
    May 3, 2021 at 10:06 am
    
    Nice solution!
one-way random walks | R-bloggers Says:
May 2, 2021 at 8:12 am

[…] article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here) […]

Reply
Eric Says:
May 2, 2021 at 5:42 am

Wouldn’t the numerator need to be even? I’d expect that every path starting east would have a similar (symmetric) path starting south. So any set of one-way directions that works if you start going east would would have a corresponding set of one-way directions that would work by staring going south. But 1135 isn’t even, so am I missing something?

Reply
- Eric Says:
  May 2, 2021 at 5:52 am
  
  Never mind. I just realized my mistake — a set of one-way directions could work for more than one path. But it only gets counted once. So the number can be odd.
  
  Reply