^{1,a)}

### Abstract

Hamilton paths, or Hamiltonian paths, are walks on a lattice which visit each site exactly once. They have been proposed as models of globular proteins and of compact polymers. A previously published algorithm [Mansfield, Macromolecules27, 5924 (1994)] for sampling Hamilton paths on simple square and simple cubic lattices is tested for bias and for efficiency. Because the algorithm is a Metropolis Monte Carlo technique obviously satisfying detailed balance, we need only demonstrate ergodicity to ensure unbiased sampling. Two different tests for ergodicity (exact enumeration on small lattices, nonexhaustive enumeration on larger lattices) demonstrate ergodicity unequivocally for small lattices and provide strong support for ergodicity on larger lattices. Two other sampling algorithms [Ramakrishnan *et al.*, J. Chem. Phys.103, 7592 (1995); Lua *et al.*, Polymer45, 717 (2004)] are both known to produce biases on both and lattices, but it is shown here that the current algorithm gives unbiased sampling on these same lattices. Successive Hamilton paths are strongly correlated, so that many iterations are required between statistically independent samples. Rules for estimating the number of iterations needed to dissipate these correlations are given. However, the iteration time is so fast that the efficiency is still very good except on extremely large lattices. For example, even on lattices of total size we are able to generate tens of thousands of uncorrelated Hamilton paths per hour of CPU time.

These computations were performed using the High Performance Computing Facility at Stevens Institute of Technology.

I. INTRODUCTION

II. GENERATION OF LATTICE HAMILTON PATHS

III. ERGODICITY TESTS

A. Small lattices

B. Larger lattices

IV. PERFORMANCE STATISTICS

V. SAMPLING STATISTICS

VI. SUMMARY

### Key Topics

- Parity
- 9.0
- Rotational correlation time
- 5.0
- Annealing
- 3.0
- Classical ensemble theory
- 3.0
- Correlation functions
- 3.0

## Figures

(a) A Hamilton path on a lattice and its associated list, in which sites are specified by their coordinates. The head of the path is site with coordinates . One of the nearest neighbors of is the site . A new path may be generated from the old one by reversing the order of the half-list lying above . (b) Another possible outcome occurs if we select the tail, , and its neighbor . Then we reverse the half-list lying below . After each maneuver, only a single edge has moved, but the end of the walk has jumped to a new lattice site.

(a) A Hamilton path on a lattice and its associated list, in which sites are specified by their coordinates. The head of the path is site with coordinates . One of the nearest neighbors of is the site . A new path may be generated from the old one by reversing the order of the half-list lying above . (b) Another possible outcome occurs if we select the tail, , and its neighbor . Then we reverse the half-list lying below . After each maneuver, only a single edge has moved, but the end of the walk has jumped to a new lattice site.

Correlation “time” as a function of lattice size, or number of iterations needed to remove correlations between successive samples on lattices.

Correlation “time” as a function of lattice size, or number of iterations needed to remove correlations between successive samples on lattices.

Correlation time in “real-time” units, or number of CPU seconds (on a Pentium III processor) needed to remove correlations between successive samples on lattices.

Correlation time in “real-time” units, or number of CPU seconds (on a Pentium III processor) needed to remove correlations between successive samples on lattices.

The three unique conformations of Hamilton paths on the lattice.

The three unique conformations of Hamilton paths on the lattice.

The quantity is the number of conformations on the lattice that appear times in samples. The symbols are results for the current algorithm, the solid curve is Eq. (1), the expected distribution assuming unbiased sampling.

The quantity is the number of conformations on the lattice that appear times in samples. The symbols are results for the current algorithm, the solid curve is Eq. (1), the expected distribution assuming unbiased sampling.

## Tables

The current algorithm has been shown to be rigorously ergodic, by exhaustive enumeration, on all the following lattices. represents the total number of unique Hamilton paths, counting any path and its reverse only once.

The current algorithm has been shown to be rigorously ergodic, by exhaustive enumeration, on all the following lattices. represents the total number of unique Hamilton paths, counting any path and its reverse only once.

Performance statistics for the procedure on lattices of total size using a Pentium III processor. is defined as the CPU or real time required to complete iterations. is the correlation “time,” or a measure of the number of iterations needed to dissipate correlations between successive samples. is defined as the CPU or real time required to complete iterations.

Performance statistics for the procedure on lattices of total size using a Pentium III processor. is defined as the CPU or real time required to complete iterations. is the correlation “time,” or a measure of the number of iterations needed to dissipate correlations between successive samples. is defined as the CPU or real time required to complete iterations.

Distributions of the different conformations obtained by three different sampling techniques. Rows one and two are taken from Ref. 10. Only the current algorithm samples the three conformations uniformly.

Distributions of the different conformations obtained by three different sampling techniques. Rows one and two are taken from Ref. 10. Only the current algorithm samples the three conformations uniformly.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content