Archive for random walk

clair obscur #3 [jatp]

Posted in pictures, Travel with tags , , , , , , , on February 17, 2022 by xi'an

clair obscur #2 [jatp]

Posted in pictures, Travel with tags , , , , , , , , , on February 16, 2022 by xi'an

triple ruin

Posted in Books, Kids, pictures, R, Statistics, Wines with tags , , , , , , , , , , on December 28, 2021 by xi'an

An almost straightforward riddle from The Riddler involving a triple gambler’s ruin: Dawn competes against three players Alessandra, Berenike, and Chinue, with probabilities of winning one round ¾, ½, and ¼, respectively, until the cumulated score reaches ±15, ±30, and ±45, for the first, second, and third games. What is Dawn’s optimal sequence of adversaries?

First, a brute force R simulation shows that the optimal ordering is to play the three adversaries first weakest, third strongest and middle fair:

ord=function(p){
  z=2*(runif(1)<p[1])-1
  while(abs(z)<15)z=z+2*(runif(1)<p[1])-1
  y=2*(runif(1)<p[2])-1
  while(abs(z+y)<30)y=y+2*(runif(1)<p[2])-1
  x=2*(runif(1)<p[3])-1
  while(abs(z+y+x)<45)x=x+2*(runif(1)<p[3])-1 
  return(x+y+z>0)}
mcord=function(p,T=1e2){
  for(t in 1:T)F=F+ord(p)
  return(F/T)}
comp=function(T=1e2){
  return(c(mcord(c(.5,.55,.45),t),
    #mcord(c(.5,.45,.55),t),#1-above
    mcord(c(.55,.5,.45),t),
    #mcord(c(.45,.5,.55),t),#1-above
    mcord(c(.55,.45,.5),t)
    #mcord(c(.45,.55,.5),t)))#1-above
    ))}

where I used probabilities closer to ½ to avoid estimated probabilities equal to one.

> comp(1e3)
[1] 0.051 0.038 0.183

(and I eliminated the three other probabilities by sheer symmetry). Second, checking in Feller’s bible (Vol. 1, XIV.3) for the gambler’s ruin probability, a simple comparison of the six orderings confirms this simulation.

coupling, donkeys, coins & fish meet in Paris

Posted in Statistics with tags , , , , , , , , , , , , , , , , , , , , , , on March 22, 2021 by xi'an

around the table

Posted in Books, pictures, R, Statistics with tags , , , , , , , , , , on December 2, 2020 by xi'an

Monty Python and the Holy Grail: the round table in CamelotThe Riddler has a variant on the classical (discrete) random walk around a circle where every state (but the starting point) has the same probability 1/(n-1) to be visited last. Surprising result that stems almost immediately from the property that, leaving from 0, state a is visited couterclockwise before state b>a is visited clockwise is b/a+b. The variant includes (or seems to include) the starting state 0 as counting for the last visit (as a return to the origin). In that case, all n states, including the origin, but the two neighbours of 0, 1, and n-1, have the same probability to be last. This can also be seen on an R code that approximates (inner loop) the probability that a given state is last visited and record how often this probability is largest (outer loop):

w=0*(1:N)#frequency of most likely last
for(t in 1:1e6){
 o=0*w#probabilities of being last
 for(v in 1:1e6)#sample order of visits
   o[i]=o[i<-1+unique(cumsum(sample(c(-1,1),300,rep=T))%%N)[N]]+1
 w[j]=w[j<-order(o)[N]]+1}

However, upon (jogging) reflection, the double loop is a waste of energy and

o=0*(1:N)
for(v in 1:1e8)
   o[i]=o[i<-1+unique(cumsum(sample(c(-1,1),500,rep=T))%%N)[N]]+1

should be enough to check that all n positions but both neighbours have the same probability of being last visited. Removing the remaining loop should be feasible by considering all subchains starting at one of the 0’s, since this is a renewal state, but I cannot fathom how to code it succinctly. A more detailed coverage of the original problem (that is, omitting the starting point) was published the Monday after publication of the riddle on R bloggers, following a blog post by David Robinson on Variance Explained.

R codegolf challenge: is there a way to shorten the above R for loop in a single line command?!

%d bloggers like this: