François Perron is visiting me for two months from Montréal and, following a discussion about the parallel implementation of MCMC algorithms—to which he also contributed with Yves Atchadé in 2005—, he remarked that a deterministic choice of permutations with the maximal contrast should do better than random or even half-random permutations. Assuming p processors or threads, with p+1 a prime number, his solution is to take element (i,j) of the permutation table as (ij) mod (n+1): here are a few examples
[sourcecode language=”r” gutter=”false”]
> ((1:10)%*%t(1:10))%%11
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 1 2 3 4 5 6 7 8 9 10
[2,] 2 4 6 8 10 1 3 5 7 9
[3,] 3 6 9 1 4 7 10 2 5 8
[4,] 4 8 1 5 9 2 6 10 3 7
[5,] 5 10 4 9 3 8 2 7 1 6
[6,] 6 1 7 2 8 3 9 4 10 5
[7,] 7 3 10 6 2 9 5 1 8 4
[8,] 8 5 2 10 7 4 1 9 6 3
[9,] 9 7 5 3 1 10 8 6 4 2
[10,] 10 9 8 7 6 5 4 3 2 1
> ((1:16)%*%t(1:16))%%17
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,] 1 2 3 4 5 6 7 8 9 10 11
[2,] 2 4 6 8 10 12 14 16 1 3 5
[3,] 3 6 9 12 15 1 4 7 10 13 16
[4,] 4 8 12 16 3 7 11 15 2 6 10
[5,] 5 10 15 3 8 13 1 6 11 16 4
[6,] 6 12 1 7 13 2 8 14 3 9 15
[7,] 7 14 4 11 1 8 15 5 12 2 9
[8,] 8 16 7 15 6 14 5 13 4 12 3
[9,] 9 1 10 2 11 3 12 4 13 5 14
[10,] 10 3 13 6 16 9 2 12 5 15 8
[11,] 11 5 16 10 4 15 9 3 14 8 2
[12,] 12 7 2 14 9 4 16 11 6 1 13
[13,] 13 9 5 1 14 10 6 2 15 11 7
[14,] 14 11 8 5 2 16 13 10 7 4 1
[15,] 15 13 11 9 7 5 3 1 16 14 12
[16,] 16 15 14 13 12 11 10 9 8 7 6
[/sourcecode]
which show that the scheme provides an interestingly diverse repartition of the indices. We certainly have to try this in the revision.
