Archive for recursion

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<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

> 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…)

Follow

Get every new post delivered to your Inbox.

Join 634 other followers