Many physical models undergo phase transitions as some parameter of the system is varied. This phenomenon has bearing on the convergence times for local Markov chains walking among the configurations of the physical system. One of the most basic examples of this phenomenon is the ferromagnetic Ising model on an n x n square lattice region Lambda with mixed boundary conditions. For this spin system, if we fix the spins on the top and bottom sides of the square to be + and the left and right sides to be -, a standard Peierls argument based on energy shows that below some critical temperature t_c, any local Markov chain M requires time exponential in n to mix. Spin glasses are magnetic alloys that generalize the Ising model by specifying the strength of nearest neighbor interactions on the lattice, including whether they are ferromagnetic or antiferromagnetic. Whenever a face of the lattice is bounded by an odd number of edges with ferromagnetic interactions, the face is considered frustrated because the local competing objectives cannot be simultaneously satisfied. We consider spin glasses with exactly four well-separated frustrated faces that are symmetric around the center of the lattice region under 90 degree rotations. We show that local Markov chains require exponential time for all spin glasses in this class. This class includes the ferromagnetic Ising model with mixed boundary conditions described above, where the frustrated faces are on the boundary. The standard Peierls argument breaks down when the frustrated faces are on the interior of Lambda and yields weaker results when they are on the boundary of Lambda but not near the corners. We show that there is a universal temperature T below which M will be slow for all spin glasses with four well-separated frustrated faces. Our argument shows that there is an exponentially small cut indicated by the free energy, carefully exploiting both entropy and energy to establish a small bottleneck in the state space to establish slow mixing.

We address a limitation of video compression standards that affects their coding efficiency. The standard methods use one or two Huffman codes for all DCT run-length events. This implicitly assumes that the statistics of DCT run-length events are nearly stationary, but they are not. There is room for significant improvement in coding efficiency by the use of conditional Huffman codes. We propose to condition the Huffman codes for runlength events on the values of previous events in the block, the quantization parameter, and other information available to the decoder. We give a systematic way of designing optimal sets of Huffman codes, to give the maximum gain in coding efficiency for a given number of codes. We achieve significant improvements in coding efficiency over the standard methods with a reasonable number of codes, in low bit rate compression. Our method is non-adaptive and has little effect on the running time of the encoder or decoder.

We consider a finite random walk on a weighted graph G; we show that the fraction of time spent in a set of vertices A converges to the stationary probability $\pi (A)$ with error probability exponentially small in the length of the random walk and the square of the size of the deviation from $\pi (A)$. The exponential bound is in terms of the expansion of G and improves previous results of [D. Aldous, Probab. Engrg. Inform. Sci., 1 (1987), pp. 33--46], [L. Lovász and M. Simonovits, {\it Random Structures Algorithms}, 4 (1993), pp. 359--412], [M. Ajtai, J. Komlós, and E. Szemerédi, Deterministic simulation of logspace, in Proc. 19th ACM Symp. on Theory of Computing, 1987]. We show that taking the sample average from one trajectory gives a more efficient estimate of $\pi (A)$ than the standard method of generating independent sample points from several trajectories. Using this more efficient sampling method, we improve the algorithms of Jerrum and Sinclair for approximating the number of perfect matchings in a dense graph and for approximating the partition function of a ferromagnetic Ising system, and we give an efficient algorithm to estimate the entropy of a random walk on an unweighted graph.

A hidden Markov chain (hmc) is a finite ergodic Markov chain in which each of the states is labelled 0 or 1. As the Markov chain moves through a random trajectory, the hmc emits a 0 or a 1 at each times step according to the label of the state just entered.

We consider a finite random walk on a weighted graph G; we show that the sample average of visits to a set of vertices A converges to the stationary probability /spl pi/(A) with error probability exponentially small in the length of the random walk and the square of the size of the deviation from /spl pi/(A). The exponential bound is in terms of the expansion of G and improves previous results. We show that the method of taking the sample average from one trajectory is a more efficient estimate of /spl pi/(A) than the standard method of generating independent sample points from several trajectories. Using this more efficient sampling method, we improve the algorithms of Jerrum and Sinclair (1989) for approximating the number of perfect matchings in a dense graph and for approximating the partition function of an Ising system. We also give a fast estimate of the entropy of a random walk on an unweighted graph.>