Archive for recursion

Riddle of the lanes

Posted in Books, Kids, R with tags , , , , , on July 13, 2020 by xi'an

An express riddle from the Riddler about reopening pools, where lanes are allowed provided there is no swimmer in the lane or in any of the adjacent lanes. If swimmers pick their lane at random (while they can), what is the average number of occupied lanes?

If there are n lanes and E(n) is the expected number of swimmers, E(n) satisfies a recurrence relation determined by the location of the first swimmer:

E(n)=1+\frac{1}{n}[2E(n-2)+\sum_{i=2}^{n-1}\{E(i-2)+E(n-i-1)\}]

with E(0)=0, E(1)=E(2)=1. The above can be checked with a quick R experiment:

en=0
for(t in 1:T){
   la=rep(u<-0,N)
   while(sum(la)<N){
     i=sample(rep((1:N)[!la],2),1)
     la[max(1,i-1):min(N,i+1)]=1
     u=u+1}
   en=en+u}

the large half now

Posted in R, Statistics with tags , , , on October 28, 2012 by xi'an

The little half puzzle proposed a “dumb’ solution in that players play a minimax strategy. There are 34 starting values less than 100 guaranteeing a sure win to dumb players. If instead the players maximise their choice at each step, the R code looks like this:

solveO=function(n){
if (n&lt;3){ solve=(n==2)}else{
  solve=(!(solveO(n-1)))||(!solveO(ceiling(n/2)))}
solve}

and there are now 66 (=100-34, indeed!) starting values for which the starting player can win.

Incidentally, I typed

&gt; solveO(1113)
Error: evaluation nested too deeply: infinite recursion / options(expressions=)?

which shows R cannot handle heavy recursion without further programming. Testing for the upper limit, I found that the largest acceptable value is 555 (which takes forever to return a value, predicted at more than one hour by a linear regression on the run times till 300…).

Cross validated question

Posted in R, Statistics, University life with tags , , , on February 20, 2012 by xi'an

Another problem generated by X’validated (on which I spent much too much time!): given an unbiased coin that produced M heads in the first M tosses, what is the expected number of additional tosses needed to get N (N>M) consecutive heads?

Continue reading

ultimate R recursion

Posted in Books, R, Statistics, University life with tags , , , , , , on January 31, 2012 by xi'an

One of my students wrote the following code for his R exam, trying to do accept-reject simulation (of a Rayleigh distribution) and constant approximation at the same time:

fAR1=function(n){
 u=runif(n)
 x=rexp(n)
 f=(C*(x)*exp(-2*x^2/3))
 g=dexp(n,1)
 test=(u<f/(3*g))
 y=x[test]
 p=length(y)/n #acceptance probability
 M=1/p
 C=M/3
 hist(y,20,freq=FALSE)
 return(x)
 }

which I find remarkable if alas doomed to fail! I wonder if there exists a (real as opposed to fantasy) computer language where you could introduce constants C and only define them later… (What’s rather sad is that I keep insisting on the fact that accept-reject does not need the constant C to operate. And that I found the same mistake in several of the students’ code. There is a further mistake in the above code when defining g. I also wonder where the 3 came from…)