## riddle on a circle

**T**he Riddler’s riddle this week provides another opportunity to resort to brute-force simulated annealing!

Given a Markov chain defined on the torus {1,2,…,100} with only moves a drift to the right (modulo 100) and a uniformely random jump, find the optimal transition matrix to reach 42 in a minimum (average) number of moves.

Which I coded in my plane to Seattle, under the assumption that there is nothing to do when the chain is already in 42. And the reasoning that there is not gain (on average) in keeping the choice between right shift and random jump random.

dure=min(c(41:0,99:42),50) temp=.01 for (t in 1:1e6){ i=sample((1:100)[-42],1) dura=1+mean(dure) if (temp*log(runif(1))<dure[i]-dura) dure[i]=dura if(temp*log(runif(1))<dure[i]-(dura<-1+dure[i*(i<100)+1])) dure[i]=dura temp=temp/(1+.1e-4*(runif(1)>.99))}

In all instances, the solution is to move at random for any position but those between 29 and 41, for an average 13.64286 number of steps to reach 42. (For values outside the range 29-42.)

December 22, 2019 at 9:59 am

[…] by data_admin [This 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 […]

December 22, 2019 at 8:13 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) […]