## 2009 Probability Seminar - 05

- Date: 02/25/2009

University of British Columbia

Estimating the entropy of a Z^d shift of finite type with probabilistic methods

In symbolic dynamics, a Z^d shift of finite type (or SFT) is the set of

all ways to assign elements from a finite alphabet A to all sites of

Z^d, subject to rules about which elements of A are allowed to appear

next to each other. A simple example of an SFT is the Z^d golden mean

shift, which is the set of all ways to assign zeroes and ones to sites

of Z^d such that no two ones are adjacent (for d=2, this example is

also known as the hard square model.) Any Z^d SFT has an associated

topological entropy (or entropy), which is a real number measuring the

exponential growth rate, as n goes to infinity, of the number of

configurations in A^({1,...,n}^d) which satisfy the SFT adjacency

rules. For d=1, the entropy of any SFT is easy to compute: it is always

the log of the largest eigenvalue of an easily defined integer-valued

matrix associated with the SFT; for the golden mean shift, the entropy

is the log of the golden mean. For d>1, the computation is much more

difficult. For instance, there is no known explicit closed form for the

entropy of the Z^2 golden mean shift. And the standard ways to

approximate the entropy of a Z^d SFT appear to converge very slowly.

For the Z^2 golden mean shift, we give a sequence of computable upper

and lower bounds which converge exponentially fast to the entropy.

Empirical data suggested that these particular numbers approach the

entropy some time ago, but it has been an open problem to prove the

convergence. Surprisingly, the methods we use to solve this

combinatorially defined problem come mostly from measure theory and

probability. We use concepts and techniques from the theory of

interacting particle systems, including stochastic domination of

measures and uniqueness of Gibbs states. Some results from percolation

theory are also used to prove the exponential rate of convergence.

3:00pm-4:00pm, WMAX 216