Tempering Monte Carlo

Counting the number of magic squares of order 6 exactly, is much more complicated than those of order 4 and 5, which were discussed in Magic Squares and Algorithms for Finance.

Similar arguments to those given there show that by rotation, reflection and simultaneous intersection of rows and columns, you can obtain 192 magic squares from one arrangement of magic rows, columns and diagonals.

For the last several years, my private working horse computer (with an i7 processor) has been calculating about a trillion (10^12) magic squares of order 6, and the end is not near at all. Is there a different way to count or to estimate the number of magic squares of order 6?

An example of a 6x6 magic square: All numbers in the diagonals are (here) between 13 and 24.

Already in 1998, K. Pinn and C. Wieczerkowski (Institute for Theoretical Physics, Münster, at that time) published their paper Number of Magic Squares From Parallel Tempering Monte Carlo.

For a configuration C (a permutation of the numbers 1 thru 36), they define the "energy" E(C) to be the sum of squared residuals of row sums, colmun sums and diagonal sums compared to the magic constant 111 (for the squares of order 6). Therefore, if a configuration is magic, then its energy is 0, otherwise it is strictly positive (and greater than 2, to be more specific.)

For a positive beta, we can (at least theoretically) calculate exp ( - beta E(C)) and sum over all configurations C. With beta going to infinity, this sum converges to the number of magic squares (counting each rotation or reflection separately).

The art, and it really is art in my eyes, is now twofold:
(1) Replace the sum over all configurations by a clever Monte Carlo simulation, which becomes increasingly difficult (larger standard deviations) for larger beta, and
(2) increase the number beta to obtain better accuracy.

Details can be found in their paper.

Their estimate for the number of magic squares of order 6 is  (0.17745 ± 0.00016) × 10^20 with a 99% significance.

Two of the techniques they use are extremely relevant for finance.
(1) Of course, Monte Carlo simulation and accuracy estimates are essential in valuation of derivative products.
(2) The tempering (increasing the beta) is a technique which is also essential in simulated annealing, a method from global optimization.