SSL Minutes

15 Feb 2001
Boytcho

{\decor P}avle will be the Beverage Person for Tuesday next.

{\decor R}achel said something about brownies.


Intro to Ergodic theory

This is a theory which studies measurable dynamical systems. Being measurable means that said systems are probabilistic.

Simple example: Fair Coin

If we throw a coin repeatedly we can talk about the probability of a sequence of events. For instance $P(HHT) = \frac{1}{8}$

Some Markov Chains also exhibit ergodicity. A simple MC is for instance: If it rains today then $P($ it will rain tomorrow $)= \frac{2}{3}$, and if it is sunny today then $P($ it will be sunny tomorrow $)= \frac{2}{3}$.

The above examples have one dimensional time, but that need not necessarily be the case with ergodic systems. We can have two (, three, &c.) dimensions of time. For example see the domino tiling in fig 1.

\includegraphics{2-15-fig1.ps}

Here we use $\leftarrow$ to denote one of four possible states. The system depicted above has some built in restrictions. A $\rightarrow$ state can only be to the left of a $\leftarrow$ square. A $\uparrow$ state can only be under a $\downarrow$ square.

An Interesting Question is: ``How random can a system be with restrictions such as the above?''

Entropy is a measure of randomness.

\includegraphics{2-15-fig2.ps}

The figure above illustrates entropy (denoted traditionally by $H$ for some reason), in the case of a coin. If the coin is biased so that $P(T)\in\{0,1\}$, then there be no randomness, thus $H(P)=0$. If the coin is fair, i.e $P(T) = \frac{1}{2}$ then we have maximum entropy.

If we are taking measurements of a sequence of events (say repeated tossings of a coin) at the rate of one measurement per unit of time, the most randomness we can hope for is 1 bit per unit of time.

Then there was a brief discussion of Independent Identically Distributed events. The author of these notes is not quite certain, how to tie that in with the rest of the discussion, yet it seemed relevant enough to be mentioned.

Another example

of a one dimensional system is the $2\times\infty$ square grid tiled by dominoes. A piece of it is shown in the figure bellow.

\includegraphics{2-15-fig3.ps}

In this case a restriction is that $L$ and $R$ states must be next to each other in the correct order. (There are exactly two tilings that we are neglecting here for their negligably low probability of occurring. Those are the two ``brick-work'' tilings). Here we prefer to use $LR$ for horizontal dominoes as opposed to $HH$, for this makes it a local rule, and makes it easier to verify if a piece of the tiling is correct. It takes a while to check if a long sequence of $H$s is of even length.

\fbox{\parbox{2.5in}{\emph{Notetaker's aside:} The example just described deals with the regular language $\left((V)^*(LR)^*\right)^*$}}

So a question we want to answer is how random can a piece of that strip be?

If we start somewhere on the strip we want to know how likely are we to see $V$ in the next column as opposed to $LR$?

One way to make a random system of this kind is to use a biased coin to decide whether to put down a $V$ or an $LR$. If the bias-ratio is too close to $P(V)=1$ (always $V$) or $P(V)=0$ (always LR), the system will have low entropy. It has higher entropy when the bias is $P(V)=\frac{1}{2}$ (a fair coin), but this is still not the best choice. It turns out that the choice of bias that leads to the highest possible entropy is $\phi$ (aka The Golden Ratio).

There is a close relationship between the Golden Ratio and Fibonacci numbers, namely

\begin{displaymath} \lim_{n\rightarrow\infty}\frac{F(n-1)}{F(n)} = \phi \end{displaymath}

in English: The ratio of two successive Fibonacci numbers approaches $\phi$.

Now we can think back to the first homework for some insight on why this is a good bias for this particular coin. Consider a $2\times n$ piece of the strip. The first column of it can be $V$ or $L$. If it be $V$ we have a $2\times{(n-1)}$ piece to tile, otherwise the untiled part is $2\times(n-2)$. As we have seen the probabilities involved are related to the Fibonacci numbers.

Hal has seen matrices related to a similar system.

In the 2-dimensional case

we can think of covering the plane with dominoes. One simple way to go about that is to divide the plane in $2\times 2$ pieces and use a fair coin to tile each of these pieces. We then have 1 bit of information to each $2\times 2$, therefore $\frac{1}{4}$ bit per square. And we can do much better than that.

If we take a random tiling of a $2n \times 2n$ square with dominoes, the probabilities of what domino covers a square in the inside are very much the same as they are in the $\infty$-plane. We can ask for instance how likely are we to come across three horizontal dominoes, stacked one on top of another in a $2\times 3$. The situations would again be similar on a large $2n \times 2n$ and the entire plane.

If we take however and Aztec Diamond, things go terribly wrong really fast. In the polar regions for instance the probabilities are skewed at places that are much further away from the border than in the simple square case.

In the very center of the Aztec Diamond, we have the max entropy.

We can use the Generalized-Domino-Shuffling ({\goth GDS}) algorithm to find the probability of a stack of three h-dominoes by finding the number of matchings of a graph depicted below.

\includegraphics{2-15-fig4.ps}

If we chose to leave all the edges between the six vertices of interest as to simplify the $\epsilon$ calculations in {\goth GDS}, we would increase the number of matchings by a factor of $3$.

In the Aztec Diamond, the polar regions are 0-entropy regions, whereas the temperate zone is of positive entropy.

If we travel from the center of the Aztec Diamond towards one of the poles, at about $\frac{2}{3}$ of the way the probability of having a ``north'' domino approaches $\frac{3}{4}$.

Another phenomenon that may occur is ``Hole in The Wall''. This is a rectangle of even width, which if it is shaded in standard checkerboard fashion, has the white squares from the leftmost column and the shaded squares from the rightmost column removed. In other words, the sizes of consecutive rows alternate between $2n$ and $2n-2$ and the rows are centered left to right. Such an animal has an unique tiling by dominoes.

The point of this is, that we may achieve the behavior of the sub-arctic region of an Aztec Diamond on a square if we remove the right pieces from the border.

Then we talked about halved Aztec Diamonds, and lattice paths in them, which force tilings.

Then Prof. Propp addressed a question by yours truly having to do with the basic moves on a Diabolo-tilable region. An appropriate illustration of the graph that we would want to match can be seen on p.10 of the {\goth GDS} paper. The graph which consists of octagons and squares. The point is there are TWO basic move in the Diabolo world, one deals with the two matchings of a square, the other with the two matchings on an octagon.

The question was raised as to how to get a text file to fit predetermined line lengths in UNIX, which brings us to The UNIX Command of the Day: fold(1).