## Hamiltonian tails

Posted in Books, Kids, R, Statistics, University life with tags , , , , , , on July 17, 2018 by xi'an

“We demonstrate HMC’s sensitivity to these parameters by sampling from a bivariate Gaussian with correlation coefficient 0.99. We consider three settings (ε,L) = {(0.16; 40); (0.16; 50); (0.15; 50)}” Ziyu Wang, Shakir Mohamed, and Nando De Freitas. 2013

In an experiment with my PhD student Changye Wu (who wrote all R codes used below), we looked back at a strange feature in an 2013 ICML paper by Wang, Mohamed, and De Freitas. Namely, a rather poor performance of an Hamiltonian Monte Carlo (leapfrog) algorithm on a two-dimensional strongly correlated Gaussian target, for very specific values of the parameters (ε,L) of the algorithm.

The Gaussian target associated with this sample stands right in the middle of the two clouds, as identified by Wang et al. And the leapfrog integration path for (ε,L)=(0.15,50)

keeps jumping between the two ridges (or tails) , with no stop in the middle. Changing ever so slightly (ε,L) to (ε,L)=(0.16,40) does not modify the path very much

but the HMC output is quite different since the cloud then sits right on top of the target

with no clear explanation except for a sort of periodicity in the leapfrog sequence associated with the velocity generated at the start of the code. Looking at the Hamiltonian values for (ε,L)=(0.15,50)

and for (ε,L)=(0.16,40)

does not help, except to point at a sequence located far in the tails of this Hamiltonian, surprisingly varying when supposed to be constant. At first, we thought the large value of ε was to blame but much smaller values still return poor convergence performances. As below for (ε,L)=(0.01,450)

## a thread to bin them all [puzzle]

Posted in Books, Kids, R, Travel with tags , , , , , , , , on July 9, 2018 by xi'an

The most recent riddle on the Riddler consists in finding the shorter sequence of digits (in 0,1,..,9) such that all 10⁴ numbers between 0 (or 0000) and 9,999 can be found as a group of consecutive four digits. This sequence is obviously longer than 10⁴+3, but how long? On my trip to Brittany last weekend, I wrote an R code first constructing the sequence at random by picking with high preference the next digit among those producing a new four-digit number

```tenz=10^(0:3)
wn2dg=function(dz) 1+sum(dz*tenz)

seqz=rep(0,10^4)
snak=wndz=sample(0:9,4,rep=TRUE)
seqz[wn2dg(wndz)]=1
while (min(seqz)==0){
wndz[1:3]=wndz[-1];wndz[4]=0
wndz[4]=sample(0:9,1,prob=.01+.99*(seqz[wn2dg(wndz)+0:9]==0))
snak=c(snak,wndz[4])
sek=wn2dg(wndz)
seqz[sek]=seqz[sek]+1}
```

which usually returns a value above 75,000. I then looked through the sequence to eliminate useless replicas

```for (i in sample(4:(length(snak)-5))){
if ((seqz[wn2dg(snak[(i-3):i])]>1)
&(seqz[wn2dg(snak[(i-2):(i+1)])]>1)
&(seqz[wn2dg(snak[(i-1):(i+2)])]>1)
&(seqz[wn2dg(snak[i:(i+3)])]>1)){
seqz[wn2dg(snak[(i-3):i])]=seqz[wn2dg(snak[(i-3):i])]-1
seqz[wn2dg(snak[(i-2):(i+1)])]=seqz[wn2dg(snak[(i-2):(i+1)])]-1
seqz[wn2dg(snak[(i-1):(i+2)])]=seqz[wn2dg(snak[(i-1):(i+2)])]-1
seqz[wn2dg(snak[i:(i+3)])]=seqz[wn2dg(snak[i:(i+3)])]-1
snak=snak[-i]
seqz[wn2dg(snak[(i-3):i])]=seqz[wn2dg(snak[(i-3):i])]+1
seqz[wn2dg(snak[(i-2):(i+1)])]=seqz[wn2dg(snak[(i-2):(i+1)])]+1
seqz[wn2dg(snak[(i-1):(i+2)])]=seqz[wn2dg(snak[(i-1):(i+2)])]+1}}
```

until none is found. A first attempt produced 12,911 terms in the sequence. A second one 12,913. A third one 12,871. Rather consistent figures but not concentrated enough to believe in achieving a true minimum. An overnight run produced 12,779 as the lowest value. Checking the answer the week after, it appears that 10⁴+3 is the correct answer!

Posted in Kids, R with tags , , , on July 6, 2018 by xi'an

Another quick riddle from the riddler: solve the equation

EXMREEK + EHKREKK = ?K?H?X?E

which involves every digit between 0 and 9. While the puzzle can be unravelled by considering first E and K, which must be equal to 6 and 3, a simple R code also leads to the conclusion

```isok <- function(a,b){
s=as.numeric(unlist(strsplit(as.character(sum(10^(6:0)*a)+
sum(10^(6:0)*b)),"")))
if (length(s)==7){ goal=FALSE}else{
goal=(length(unique(c(a,b,s)))==10)&(a[2]==s[6])&
(s[8]==a[6])&(s[2]==a[7])&(b[2]==s[4])}
return(goal)}

pasok <- function(T=1e3){
for (t in 1:T){
a[1]=a[5]=a[6]=6;a[7]=3
digs=sample(c(0:2,4,5,7:9),4)
a[2:4]=digs[1:3] b[1]=a[1];b[2]=digs[4];
b[3]=a[7];b[4]=a[4];b[5]=a[1];b[6:7]=a[7]
if (isok(a=a,b=b))
print(rbind(a,b))}}

> pasok()
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
a    6    2    4    7    6    6    3
b    6    8    3    7    6    3    3
```

which sum is 13085296.

## maximal spacing around order statistics [#2]

Posted in Books, R, Statistics, University life with tags , , , , , , , , on June 8, 2018 by xi'an

The proposed solution of the riddle from the Riddler discussed here a few weeks ago is rather approximative, in that the distribution of

$\Delta_n=\max_i\,\min_j\,|X_{i}-X_{j}|$

when the n-sample is made of iid Normal variates is (a) replaced with the distribution of one arbitrary minimum and (b) the distribution of the minimum is based on an assumption of independence between the absolute differences. Which does not hold, as shown by the above correlation matrix (plotted via corrplot) for N=11 and 10⁴ simulations. One could think that this correlation decreases with N, but it remains essentially 0.2 for larger values of N. (On the other hand, the minima are essentially independent.)

## Le Monde puzzle [#1051]

Posted in Books, Kids, R with tags , , , , , , on May 18, 2018 by xi'an

A combinatoric Le Monde mathematical puzzle of limited size:
When the only allowed move is to switch two balls from adjacent boxes, what is the minimal number of moves to return all balls in the above picture to their respective boxes? Same question with six boxes and 12 balls.

The question is rather interesting to code as I decided to use recursion (as usual!) but wanted to gain time by storing the number of steps needed by any configuration to reach its ordered recombination. Meaning I had to update an external vector within the recursive function for each new configuration I met. With help from Julien Stoehr, who presented me with the following code, a simplification of a common R function

```v.assign <- function (i,value,...) {
temp <- get(i, pos = 1)
temp[...] <- value
assign(i, temp, pos = 1)}
```

which assigns one or several entries to the external vector i. I thus used this trick in the following R code, where cosz is a vector of size 5¹⁰, much larger than the less than 10! values I need but easier to code. While n≤5.

```n=5;tn=2*n
baz=n^(0:(tn-1))
cosz=rep(-1,n^tn)
swee <- function(balz){
indz <- sum((balz-1)*baz)
if (cosz[indz]==-1){
if (min(diff(balz))==0){ #ordered
v.assign("cosz",indz,value=1)}else{
val <- n^tn
for (i in 2:n)
for (j in (2*i-1):(2*i))
for (k in (2*i-3):(2*i-2)){
calz <- balz
calz[k] <- balz[j];calz[j] 0)
val <- min(val,1+swee(calz))}
v.assign("cosz",indz,value=val)
}}
return(cosz[indz])}
```

which returns 2 for n=2, 6 for n=3, 11 for n=4, 15 for n=5. In the case n=6, I need a much better coding of the permutations of interest. Which is akin to ranking all words within a dictionary with letters (1,1,…,6,6). After some thinking (!) and searching, I came up with a new version, defining

```parclass=rep(2,n)
rankum=function(confg){
n=length(confg);permdex=1
for (i in 1:(n-1)){
x=confg[i]
if (x>1){
for (j in 1:(x-1)){
if(parclass[j]>0){
parclass[j]=parclass[j]-1
permdex=permdex+ritpermz(n-i,parclass)
parclass[j]=parclass[j]+1}}}
parclass[x]=parclass[x]-1}
return(permdex)}

ritpermz=function(n,parclass){
return(factorial(n)/prod(factorial(parclass)))}
```

for finding the index of a given permutation, between 1 and (2n)!/2!..2!, and then calling the initial swee(p) with this modified allocation. The R code was still running when I posted this entry… and six days later, it returned the answer of 23.

## Le Monde puzzle [#1045]

Posted in Books, Kids with tags , , , , , , on May 13, 2018 by xi'an

An minor arithmetic Le Monde mathematical puzzle:

Take a sequence of 16  integers with 4 digits each, separated by 2,  such that it contains a perfect square and its sum is a perfect cube. What are the possible squares and cubes?

The question is dead easy to code in R

```for (x in as.integer(1e3:(1e4-16))){
if (max(round(sqrt(x+2*(0:15)))^2==x+2*(0:15))==1) {
b=sqrt((x+2*(0:15))[round(sqrt(x+2*(0:15)))^2==x+2*(0:15)])
if ((round((2*x+30)^(1/3)))^3==(2*x+30))
print(c(x,b,(16*(x+15))^(1/3)))}}
```

and return the following solutions:

```[1] 1357   37   28
[1] 5309   73   44
```

Nothing that exciting…!

## the riddle of the stands

Posted in Books, Kids, R with tags , , , , , on May 11, 2018 by xi'an

The simple riddle of last week on The Riddler, about the minimum number of urinals needed for n men to pee if the occupation rule is to stay as far as possible from anyone there and never to stand next to another man,  is quickly solved by an R code:

```ocupee=function(M){
ok=rep(0,M)
ok[1]=ok[M]=1
ok[trunc((1+M/2))]=1
while (max(diff((1:M)[ok!=0])>2)){
i=order(-diff((1:M)[ok!=0]))[1]
ok[(1:M)[ok!=0][i]+trunc((diff((1:M)[ok!=0])[i]/2))]=1
}
return(sum(ok>0))
}
```

with maximal occupation illustrated by the graph below:

Meaning that the efficiency of the positioning scheme is not optimal when following the sequential positioning, requiring $N+2^{\lceil log_2(N-1) \rceil}$ urinals. Rather than one out of two, requiring 2N-1 urinals. What is most funny in this simple exercise is the connection exposed in the Riddler with an Xkcd blag written a few years go about the topic.