go forth and X [or the reverse]

The New Year Riddle is about optimisation: starting with a single machine, between delivering one unit per machine – hour and delivering one new machine per machine every six days, what is the maximal number of units produced over 100 days?

Comparing the amounts produced by k machines after 6log₂(k) days used to multiply the machines showed that 2¹⁵ -1 additional machines were first produced, to generate 7864320 items over the remaining 10 days. Which did not really require an R implementation (although I checked that intermediate solutions where only some of the machines were producing new machines were sub-optimal).

foliage to the max

An easy riddle from The Riddler that did not even require coding! Given that a tree changes colours at a random time A distributed according to a Uniform distribution (over (0,1)) and that it sheds its leave at a random time B distributed according to a Uniform distribution (over (A,1)), what is the time when a maximal number of trees show their new colour?

Which means optimising in t the probability that A<t<B. Which is equal to -(1-t)log(1-t) and maximal for t=1-e⁻¹, resulting in a (maximal) fraction of e⁻¹ of the trees holding to their new colour at that time.

Bertrand’s tartine

A riddle from The Riddler on cutting a square (toast) into two parts and keeping at least 25% of the surface on each part while avoiding Bertrand’s paradox. By defining the random cut as generated by two uniform draws over the periphery of the square. Meaning that ¼ of the draws are on the same side, ½ on adjacent sides and again ¼ on opposite sides. Meaning one has to compute

P(UV>½)= ½(1-log(2))

and

P(½(U+V)∈(¼,¾))= ¾

Resulting in a probability of 0.2642 (checked by simulation)

fast track & slow lane

A riddle from the Riddler where N cars going at random (iid) speeds drive a road with a slow and a fast lane, each car choosing the fast lane iff any of the cars ahead in the slow lane is slowerthan them. With the question of the average number of car convoys.

If there were one single lane, the problem would be to determine how many times a smaller realisation and it has been solved in a much older Riddler. Namely

In the two-lane system, the slow one only gathers cars with speeds lowest than the current speed, i.e. a decreasing sequence of speeds, creating single car convoys.  The fast lane thus captures cars that are above the current minimum in the sequence, which, as it converges to the global minimum at some points, means that all following cars are found in the fast lane. i thought this would bring the number of convoys close to twice the above logarithmic sum (which sealed my destiny during an entrance oral exam 40 years ago!), but there are actually more of them for N large enough , which may be due to the possibility of the slow lane to capture more moderate speed cars in the beginning… The above compares the number of convoys for one lane (in red) and two (in gold), as well as the remarkable fit when regressing these numbers against log(N).

Here is the R code I used for that simulation

convoy=function(N,T=1e5){
  for(t in 1:T){
    speed=runif(N)
    slow=fast=NULL
    slow=speed[1]
    for(i in 2:N){
      if(speed[i]<min(slow))slow=c(slow,speed[i]) 
      else fast=c(fast,speed[i])} 
    F=F+length(slow) 
    if(length(fast)>0)F=F+1+sum(fast[-1]<cummin(fast)[-length(fast)])}
  return(F/T)}

the Kelly criterion and then some

The Kelly criterion is a way to optimise an unlimited sequence of bets under the following circumstances: a probability p of winning each bet, a loss of a fraction a of the sum bet, a gain of a fraction b of the sum bet, and a fraction f of the current fortune as the sum bet. Then

is the fraction optimising the growth

Here is a rendering of the empirical probability of reaching 250 before ruin, when starting with a fortune of 100, when a=1, p=0.3 and f and b vary (on a small grid). With on top Kelly’s solutions, meaning that they achieve a high probability of avoiding ruin. Until they cannot.

The Ridder is asking for a variant of this betting scheme, when the probability p to win the bet is proportional to 1/(1+b), namely .9/(1+b). In that case, the probabilities of reaching 250 (using the same R code as above) before ruin are approximated as followswith a maximal probability that does not exceed 0.36, the probability to win in one go, betting 100 with a goal of 250. It thus may be that the optimal choice, probabilitiwise is that one. Note that in that case, whatever the value of b, the Kelly criterion returns a negative fraction. Actually, the solution posted by the Riddler the week after is slightly above, 0.3686 or 1−(3/5)^9/10. Which I never reached by the sequential bet of a fixed fraction of the current fortune, eps. when not accounting for the fact that aiming at 250 rather than a smaller target was removing a .9 factor.