Random Dyadic Tilings of the Unit Square

Svante Janson, Dana Randall and Joel Spencer

May 16, 2001

Abstract A “dyadic rectangle” is a set of the form R = [a2^{−s}, (a+1)2^{−s}]×[b2^{−t}, (b+1)2^{−t}], where s and t are non-negative integers. A dyadic tiling is a tiling of the unit square with dyadic rectangles. In this paper we study n-tilings which consist of 2^{n} nonoverlapping dyadic rectangles, each of area 2^{−n}, whose union is the unit square. We discuss some of the underlying combinatorial structures, provide some efficient methods for uniformly sampling from the set of n-tilings, and study some limiting properties of random tilings.

1 Introduction

We shall be dealing with tilings of the unit square of a special type. By a dyadic rectangle we mean a set of the form

R = [a2^{−s}, (a + 1)2^{−s}] × [b2^{−t}, (b + 1)2^{−t}]

where s, t are nonnegative integers and a, b are integers with 0 ≤ a < 2^{s} and 0 ≤ b < 2^{t}. An n-tiling of the unit square is a set of 2^{n} dyadic rectangles, each of area 2^{−n}, whose union is the unit square. (Overlap at the edges does not concern us.) Figure 1 gives examples of such n-tilings. We shall often just speak of tilings when the value n is understood. Let T_{n} be the set of all n-tilings.

a.  b.  c.

Figure 1: Examples of dyadic tilings

Definition. A tiling has a vertical cut if the line x = \frac{1}{2} cuts through none of its rectangles. It has a horizontal cut if the line y = \frac{1}{2} cuts through none of its rectangles.

We note that Figure 1a has a vertical cut, Figure 1b has a horizontal cut, and Figure 1c has both a vertical and a horizontal cut. We emphasize that cuts, as opposed to the struts of Section 6.2, must cut the square precisely in half. Cuts play a critical role in the analysis of tilings due to the following result.

Theorem 1.1. Every tiling has either a vertical cut or a horizontal cut. (It may have both.)

Proof. If x = \frac{1}{2} cuts through a rectangle then that rectangle must be of the form R = [0, 1] × I. If also y = \frac{1}{2} cuts through a rectangle then that rectangle must be of the form S = J × [0, 1]. But then S, T overlap in I × J.

Let A_{n} denote the number of n-tilings. The square itself provides the unique 0tiling so that A_{0} = 1. A_{1} = 2 since the square may be split into left and right halves or top and bottom halves. Some effort yields A_{2} = 7, and by the following recursion we obtain A_{3} = 82, A_{4} = 11047, A_{5} = 198860242, A_{6} = 64197955389505447, …. (For convenience we let A_{−1} = 0.)

Theorem 1.2. For n ≥ 1,

A_{n} = 2A_{n−1}^{2} − A_{n−2}^{4}.  (1.1)

Proof. Consider n-tilings with a vertical cut. These consist of n-tilings of [0, \frac{1}{2}] × [0, 1] and [\frac{1}{2}, 1] × [0, 1]. Dilating x → 2x, n-tilings of [0, \frac{1}{2}] × [0, 1] are equivalent to (n − 1)- tilings of the unit square. Dilating x → 2x−1, n-tilings of [\frac{1}{2}, 1]×[0, 1] are equivalent to (n − 1)-tilings of the unit square. Hence there are A_{n−1}^{2} such tilings. Similarly there are A_{n−1}^{2} n-tilings with a horizontal cut. This gives, by Theorem 1.1, all n-tilings but we have overcounted by those n-tilings with both horizontal and vertical cuts. Such tilings consist of n-tilings of each of the four subsquares [0, \frac{1}{2}]×[0, \frac{1}{2}], [\frac{1}{2}, 1]×[0, \frac{1}{2}], [0, \frac{1}{2}]×[\frac{1}{2}, 1], [\frac{1}{2}, 1]×[\frac{1}{2}, 1]. Dilating (x, y) → (2x, 2y), n-tilings of [0, \frac{1}{2}]×[0, \frac{1}{2}] are equivalent to (n−2)- tilings of the unit square, and similarly for the other three subsquares. Hence there are A_{n−2}^{4} n-tilings with both horizontal and vertical cuts.

The recursion of Theorem 1.2 does not admit a closed solution. The asymptotics of A_{n} have been carefully studied in [10], here we note only that

A_{n} ∼ ϕ^{−1}ρ^{2^{n}}  (1.2)

where ρ = 1.84454757 ⋯ (ρ does not appear to have a nice form) and ϕ is the golden ratio ϕ = (1 + \sqrt{5})/2 = 1.6180 · · ·.

Dyadic rectangles were used by the senior author in [7] to analyze the packing of random axis parallel rectangles of arbitrary size. The more precise tilings proved to have a fascinating structure, which motivated our current efforts. Much remains to be studied however, and several open problems are given below.

We give some deterministic results on the set of all n-tilings in Section 2. In Section 3 we define two representations as labeled binary trees, which will play an important role in the sequel.

By a random tiling we mean a uniformly sampled tiling in T_{n}, for some given n; in other words, each tiling is chosen with the same probability 1/A_{n}. In Section 4, we present a method to randomly sample tilings with this uniform distribution. The method is both practically useful if one wants to generate random tilings, and theoretically useful in some of our later proofs. In Section 5 we discuss an alternative method to generate random tilings by running a Markov process; we show that two natural Markov processes are rapidly mixing. In Section 6 we study the asymptotic behavior as n → ∞ of some properties of random tilings.

Problem 1.3. More generally, one may naturally define dyadic boxes in d dimensions and from that, n-tilings. For d ≥ 3, however, Theorem 1.1 fails, as n-tilings do not necessarily have any cuts. The structures of the family of n-tilings and the asymptotics of the number A_{n,d} of such tilings remains completely open. In particular, we do not yet know whether, for d ≥ 3 fixed, the 2^{n}-th root of A_{n,d} approaches infinity.

2 The lattice of tilings

There is a useful height function which lends insight into the set of dyadic tilings. Define the height h(t) of a dyadic 2^{−k} × 2^{−l} rectangle t with area 2^{−n} to be k = n − l, and define the total height H(T) of a tiling T to be the sum of the heights of all rectangles in it. Note that since the height of a single rectangle of area 2^{−n} is one of the numbers {0, …, n},

0 ≤ H(T) ≤ n2^{n},  T ∈ T_{n}.  (2.1)

If T is a tiling and p ∈ [0, 1]^{2}, we let T (p) be the dyadic rectangle in T containing p. (If there are two or more such rectangles in T, which happens only if p lies on their boundaries, we choose for definiteness the one containing points north-east of p. This is not important, and we could avoid this complication completely by considering only irrational p ∈ [0, 1]^{2}.) A tiling T ∈ T_{n} then is completely described by its height function h(T) : [0, 1]^{2} → {0, 1, …, n} defined by h(T)(p) := h(T (p)). Note that

H(T) = 2^{n} ∫_{[0,1]^{2}} h(T)(p) dp.  (2.2)

The height function allows us to define a partial order on the set of n-tilings. Given two tilings T_{1}, T_{2} ∈ T_{n}, we say T_{1} ⪯ T_{2} if h(T_{1}) ≤ h(T_{2}), i.e. if h(T_{1}(p)) ≤ h(T_{2}(p)) for all p ∈ [0, 1]^{2}. With these definitions, we find the following.

Theorem 2.1. The partial order on T_{n} defines a distributive lattice.

Proof. First, there are unique highest and lowest elements in T_{n}. Namely, the highest tiling is the all vertical tiling, consisting of only 2^{−n} × 1 rectangles (which has height function constant n), and the lowest is the all horizontal tiling, consisting of 1 × 2^{−n} rectangles (which has height function constant 0).

Let T_{1} and T_{2} be any two tilings in T_{n}. We define the join

T_{1} ∨ T_{2} = {max(T_{1}(p), T_{2}(p)) : p ∈ [0, 1]^{2}},

where max(T_{1}(p), T_{2}(p)) is the tile with larger height. Similarly, define the meet

T_{1} ∧ T_{2} = {min(T_{1}(p), T_{2}(p)) : p ∈ [0, 1]^{2}},

where min(T_{1}(p), T_{2}(p)) is the tile with smaller height.

We need to argue that the meet and join always yield valid tilings. Consider first T_{1} ∨ T_{2}. Clearly every point in [0, 1]^{2} is covered at least once. Suppose that there exists a point p_{1} which is covered by (the interior of) two tiles t and t′ in T_{1} ∨ T_{2}. Clearly t and t′ have different heights, and further they must come from different tilings. We can assume without loss of generality that t ∈ T_{1}, t′ ∈ T_{2} and that h(t) > h(t′). Recalling that t′ ∈ {max(T_{1}(p), T_{2}(p))}, there must exist an irrational point p_{2} ∈ t′ such that T_{2}(p_{2}) = t′ and h(t′) ≥ h(t′′), where t′′ = T_{1}(p_{2}). Let t = I × J, t′ = I′ × J′ and t′′ = I′′ × J′′. Since p_{1} ∈ t ∩ t′ and h(t) > h(t′), and all intervals are dyadic, we have I ⊃ I′ and J ⊂ J′. Since p_{2} ∈ t′ ∩ t′′ and h(t′) ≥ h(t′′), we have I′ ⊇ I′′ and J′ ⊆ J′′. Consequently, t ≠ t′′ but t∩t′′ = I′′ ×J ≠ ∅, which contradicts the fact that t and t′′ are different tiles in T_{1}. Hence tiles in T_{1} ∨ T_{2} can never intersect. An analogous argument shows that T_{1} ∧ T_{2} is a proper tiling.

Note that the height function satisfies

h(T_{1} ∨ T_{2}) = max(h(T_{1}), h(T_{2})),  (2.3)
h(T_{1} ∧ T_{2}) = min(h(T_{1}), h(T_{2})).  (2.4)

It follows that the height function defines an order-preserving bijection of T_{n} onto a sublattice of the distributive lattice of all functions [0, 1]^{2} → {0, 1, …, n}. Therefore T_{n} also forms a distributive lattice.

Let T̃_{k} denote the special tiling with 2^{−k} × 2^{k−n} rectangles, k = 0, …, n; thus T̃_{k} has height function constant k. As noted above, T̃_{0} is the lowest tiling and T̃_{n} is the highest. Other of these special tilings also have useful properties.

Theorem 2.2. An n-tiling T has a horizontal cut if and only if T ⪯ T̃_{n−1}. It has a vertical cut if and only if T ⪰ T̃_{1}.

Proof. T has a horizontal cut if and only if it contains no 2^{−n} × 1 rectangle, i.e. if and only if h(T)(p) ≤ n − 1 for every p ∈ [0, 1]^{2}. The second part is similar.

Theorem 2.3. Suppose that T_{1}, T_{2} are n-tilings with n ≥ 2. If T_{1} ⪯ T_{2}, T_{1} has a horizontal cut and T_{2} has a vertical cut, then there exists a tiling T_{3} with both vertical and horizontal cuts such that T_{1} ⪯ T_{3} ⪯ T_{2}.

Proof. Define T_{3} = T_{1}∨T̃_{1}. By Theorem 2.2, T̃_{1} ⪯ T_{2}, so T_{1} ⪯ T_{3} ⪯ T_{2}. By Theorem 2.2 again, T_{1} ⪯ T̃_{n−1}, and trivially T̃_{1} ⪯ T̃_{n−1}, so T̃_{1} ⪯ T_{3} ⪯ T̃_{n−1}, which by a final application of Theorem 2.2 completes the proof.

If T is a tiling and R is a dyadic rectangle such that R is a union of tiles in T, we can obtain new tilings by rotating the part of the tiling inside R by a multiple of 90^{∘}. (By ”rotating” a non-square region, we really mean a rotation followed by appropriate dilations in the coordinate directions to make the result fit in the same region again.) Rotations will be important later. Here we are only concerned with the simplest nontrivial case.

We make T_{n} into a directed graph by defining an edge T_{1} → T_{2} if T_{1} and T_{2} can be obtained from each other by rotating a dyadic rectangle of area 2^{n−1}, with T_{1} ≺ T_{2}. In other words, T_{1} → T_{2} if there is a dyadic rectangle R of area 2^{n−1} such that T_{1} and T_{2} coincide outside R, T_{1} contains the two horizontal halves of R, while T_{2} contains the two vertical halves of R. It follows that if T_{1} → T_{2}, then H(T_{2}) = H(T_{1}) + 2.

The following theorem yields a natural connection between this graph structure and the partial order on T_{n}: T_{1} → T_{2} if and only if T_{2} is a minimal successor of T_{1}. It further follows from the theorem that T_{1} → T_{2} if and only if T_{1} ⪯ T_{2} and H(T_{2}) = H(T_{1}) + 2, thus yielding yet another characterization.

Theorem 2.4. Let T_{1}, T_{2} ∈ T_{n}. Then T_{1} ⪯ T_{2} if and only if there exists an oriented path from T_{1} to T_{2} in the directed graph T_{n}. Every such path has length \frac{1}{2}H(T_{2}) − \frac{1}{2}H(T_{1}).

Proof. The existence of such a path whenever T_{1} ⪯ T_{2} is clear for n ≤ 1. For larger n we use induction in n. If T_{1} has a vertical cut, then so has (by Theorem 2.2) T_{2}, and the existence of an oriented path follows from the induction hypothesis by considering the left and right halves of the tilings separately. If both T_{1} and T_{2} have horizontal cuts, we consider similarly the upper and lower halves separately. By Theorem 1.1, the only remaining case is when T_{1} has a horizontal cut and T_{2} a vertical cut. In this case we use Theorem 2.3 and find a tiling T_{3} such that, by the previous cases, there exist paths from T_{1} to T_{3} and from T_{3} to T_{2}; we combine these paths into one. This completes the proof of existence of an oriented path from T_{1} to T_{2} whenever T_{1} ⪯ T_{2}. The converse is immediate.

The final assertion follows because H(T_{2}) = H(T_{1}) + 2 when T_{1} → T_{2}.

Corollary 2.5. The total height H(T) is twice the common length of the oriented paths from the lowest tiling T̃_{0} to T.

Theorem 2.6. Ignoring orientations, T_{n} is a connected graph. The distance between two tilings T_{1} and T_{2} in this graph equals

2^{n−1} ∫_{[0,1]^{2}} |h(T_{1})(p) − h(T_{2})(p)| dp = 2^{n−1}∥h(T_{1}) − h(T_{2})∥_{L^{1}([0,1]^{2})}.

Proof. Combining the oriented paths given by Theorem 2.4 from T_{1} and T_{2} to T_{1} ∨ T_{2}, reversing the latter, we obtain a path from T_{1} to T_{2} of length, using (2.2) and (2.3),

\frac{1}{2}H(T_{1} ∨ T_{2}) − \frac{1}{2}H(T_{1}) + \frac{1}{2}H(T_{1} ∨ T_{2}) − \frac{1}{2}H(T_{2})
= 2^{n−1} ∫_{[0,1]^{2}}(2h(T_{1} ∨ T_{2})(p) − h(T_{1})(p) − h(T_{2})(p)) dp
= 2^{n−1} ∫_{[0,1]^{2}} |h(T_{1})(p) − h(T_{2})(p)| dp.

Conversely, if the distance d(T_{1}, T_{2}) = 1, then T_{1} → T_{2} or T_{2} → T_{1}, and ∥h(T_{1}) − h(T_{2})∥_{L^{1}([0,1]^{2})} = 2^{−n}|H(T_{1}) − H(T_{2})| = 2^{1−n}. By the triangle inequality, we have in general ∥h(T_{1}) − h(T_{2})∥_{L^{1}([0,1]^{2})} ≤ 2^{1−n}d(T_{1}, T_{2}).

Corollary 2.7. The diameter of the undirected graph T_{n} is n2^{n−1}. This distance is attained by the lowest and highest tilings T̃_{0} and T̃_{n}.

It is easily seen that the distance between any other pair of tilings is strictly smaller.

Problem 2.8. Study further properties of T_{n} as a lattice or graph! For example, what is the distribution of the vertex degrees?

3 Tree representations

The existence of cuts promotes a useful representation of dyadic tilings in terms of labeled binary trees. Trees are natural in this context because of the hierarchical relationship of the cuts. The first cut divides the unit square into two halves, each of which can be interpreted as a dyadic tiling in T_{n−1} through dilation. These in turn have cuts, and so forth. The labels on a tree capture whether corresponding cuts are horizontal or vertical.

We will use two different versions of this idea; one (HV -trees) where the labels specify the absolute orientations of the cuts and one (AD-trees) where the labels specify the relative orientations.

Recall that a binary tree is either empty, or consists of a root and two (binary) subtrees attached to the root. We find it convenient to say that the root of a binary tree has height 1. Thus a complete binary tree of height n has 2^{n} − 1 nodes; 2^{k−1} with height k for k = 1, …, n. We also say that the nodes with height k lie on level k. The empty tree has height 0.

3.1 HV -trees

A complete binary tree of height n whose 2^{n} − 1 nodes are labeled H or V defines an n-tiling by the following procedure:

1. If the tree is empty (n = 0) then Exit.

2. If the root is labeled H, make a horizontal cut. If the root is labeled V, make a vertical cut.

3. Continue recursively with the two halves separately, using the left subtree of the root for one half (for definiteness, the lower or left half, say) and the right subtree for the other half.

Conversely, Theorem 1.1 implies that every n-tiling is produced in this way by some labeled complete binary tree. However, the tree is in general not unique, since the unit square (or a subrectangle) may have both a vertical and a horizontal cut; indeed, there are 2^{2^{n}−1} complete binary trees on height n whose nodes are labeled H or V, which is far greater than the number of tilings in T_{n}.

In order to obtain a unique representation by labeled binary trees, we decide to use the label V as often as possible. We make the following definition.

Definition. A complete binary tree whose nodes are labeled H or V is an HV -tree if there is no node labeled H which has two children labeled V.

Let T_{n}^{HV} be the set of HV -trees of height n.

Lemma 3.1. An HV -tree with root labeled H defines a tiling without vertical cut.

Proof. This is trivial for height 0 or 1. For larger trees we use induction. The root has, by the definition of HV -trees, at least one subtree whose root is labeled H, so by induction the lower or upper half of the tiling does not have a vertical cut.

Theorem 3.2. The construction above yields a bijection between T_{n}^{HV} and T_{n}.

Proof. Given a tiling, we create a corresponding HV -tree as follows. If there is a vertical cut in the tiling, label the root V and continue recursively with the left and right halves. If there is no vertical cut, there is by Theorem 1.1 a horizontal cut; we then label the root H and continue recursively with the lower and upper halves.

Note that if the root is labeled H, there is no vertical cut and thus at least one of the two halves produced by the first cut has no vertical cut; consequently, the two children of the root cannot both be labeled V. The same applies to all later stages of the construction, which shows that we have constructed an HV -tree.

Clearly, the tree defines the given tiling. Moreover, it follows from Lemma 3.1 that any two HV -trees defining the same tiling have to have the same root label, and by recursion they have to be identical. Hence each tiling corresponds to a unique HV - tree.

3.2 AD-trees

In the second representation, we use complete binary trees with the labels A (agree) or D (disagree) to indicate whether the cut is parallel or orthogonal to its parent (i.e., the preceding cut). We arbitrarily define the (absent) parent of the first cut to have vertical orientation. We formalize the construction of a tiling given a complete binary tree labeled with A and D as follows.

1. Initialize by defining the parent cut to be the left edge of the unit square.

2. If the tree is empty (n = 0) then Exit.

3. If the root is labeled A, make a cut parallel to the parent cut. If the root is labeled D, make a cut orthogonal to the parent cut.

4. Continue recursively (from Step 2) with the two halves separately, using the two subtrees of the root and in both cases setting the parent cut equal to the cut just made. More precisely, if the root is labeled A, use the left subtree for the half nearest the parent cut, and if the root is labeled D, use the left subtree for the left half, viewed from the parent cut.

The specification in Step 4 of the order of the subtrees is chosen such that changing a single label in the tree corresponds to rotating the corresponding subtiling ±90^{∘}.

Just as for HV -trees, every tiling is defined by some labeled complete binary tree, but the correspondence between labeled trees and tilings is not bijective. More precisely, whenever a node is labeled A and its two children are labeled D, we will get the same tiling if we were to label all three nodes D, followed by appropriate relabelings at the

[figure: A; D; A; D; D; A; D; (; (; (; ); ); )]

Figure 2: The correspondence between dyadic tilings and AD-trees.

descendants of these nodes. We resolve this by only allowing the labeling where all three such nodes are labeled D. We say that any tree with an invalid labeling (i.e. a node labeled A which has two children labeled D) has a badly labeled subtree. This motivates the following definition.

Definition. A complete binary tree whose nodes are labeled A or D is an AD-tree if there is no node labeled A which has two children labeled D.

Let T_{n}^{AD} be the set of AD-trees of height n.

Theorem 3.3. The construction above yields a bijection between T_{n}^{AD} and T_{n}.

Proof. This is very similar to the proof of 3.2. Given a tiling, we can create a unique AD-tree recursively, beginning at the root, by always choosing D when we have a choice. We omit the details.

4 Recursive algorithms for sampling

The recursive formula for the number of tilings of each size suggests a natural method for sampling tilings, or equivalently HV -trees or AD-trees, uniformly. Starting with the unit square, we calculate the probability that there is a horizontal or vertical cut, and then recursively determine probabilities of each cut in the two halves that are formed. Analogously, we can use these probabilities to determine the label of the root of the tree. Each subtree is then labeled so as to avoid introducing badly labeled subtrees. We formalize how to do this in what follows. It turns out to be convenient to use the tree representations.

4.1 Probabilities at the root

We start by introducing some notation which will be useful for determining the relevant probabilities. Let

p_{n} = P(a random tiling in T_{n} has a vertical cut) = \frac{A_{n−1}^{2}}{A_{n}} ,  n ≥ 0.  (4.1)

By symmetry, the probability of a horizontal cut is the same. We have p_{0} = 0, p_{1} = 1/2, p_{2} = 4/7, …. Theorem 1.2 yields, by dividing by A_{n−1}^{2}, the recursion

p_{n} = \frac{1}{2 − p_{n−1}^{2}} ,  n ≥ 1.  (4.2)

It follows easily from (4.2) that p_{n} increases to the smallest positive root of x = 1/(2 − x^{2}), i.e.

p_{n} → ϕ^{−1} = ϕ − 1 = (\sqrt{5} − 1)/2, as n → ∞.

Moreover, using \frac{d}{dx}(2 − x^{2})^{−1} = 2x(2 − x^{2})^{−2} ≤ 2ϕ^{−3} for 0 ≤ x ≤ ϕ^{−1}, it follows by the mean value theorem and induction that

p_{n} = ϕ − 1 + O((ϕ^{3}/2)^{−n}).  (4.3)

4.2 The recursive construction

We will construct a random HV -tree in T_{n}^{HV} with a uniform distribution recursively, beginning by choosing the label of the root. Since there is an obvious bijection between HV -trees and AD-trees, given by relabeling H ↔ A and V ↔ D, the same method can be used to construct uniformly distributed random AD-trees. Any of the bijections in Section 3 then yields a uniform random n-tiling. (An HV -tree and the AD-tree obtained by relabeling correspond to different tilings, so the tilings produced by a particular simulation will depend on whether we use HV -trees and AD-trees, but both constructions yield the same uniform distribution. Similarly, note that the algorithm below is highly non-symmetric in H and V, although we know that the resulting distribution of tilings is invariant under rotation.)

If the root is labeled V, its two subtrees can be any trees in T_{n−1}^{HV}, and we may continue recursively. If the root is labeled H, however, and n ≥ 2, we have the constraint that its two children must not both be labeled V; this introduces a dependency between the subtrees that makes a straight-forward recursion impossible. In order to overcome this difficulty we look ahead, which we formalize as follows.

Definition. The type of a node in a HV -tree is one of the four symbols V, H_{HH}, H_{HV}, H_{V H}, chosen according to the following rules:

1. If the node is labeled V, its type is V.

2. If the node is labeled H and it is not a leaf, its type is H_{xy}, where x and y are the labels of its children.

3. If the node is labeled H and it is a leaf, its type is H_{HH}.

Note that the type of a node determines the label, but not conversely; however, the labeling of the whole tree determines the types, and conversely.

We define the type type(T) of a non-empty HV -tree T to be the type of its root, and define type(∅) = H_{HH}.

Consequently, an HV -tree T ∈ T_{n}^{HV}, n ≥ 1, is described by its type and two trees T_{1}, T_{2} ∈ T_{n−1}^{HV}, with the constraints that

type(T) = H_{HH} ⟹ type(T_{1}), type(T_{2}) ∈ {H_{HH}, H_{HV} , H_{V H}};
type(T) = H_{HV} ⟹ type(T_{1}) ∈ {H_{HH}, H_{HV} , H_{V H}}, type(T_{2}) = V;
type(T) = H_{V H} ⟹ type(T_{1}) = V, type(T_{2}) ∈ {H_{HH}, H_{HV} , H_{V H}}.

(4.4)

Apart from these constraints, T_{1} and T_{2} may be any HV -trees in T_{n−1}^{HV}. This allows, in principle, a recursive generation of all trees in T_{n}^{HV}. (This quickly becomes practically impossible, since |T_{n}^{HV} | grows very quickly. We will turn this recursive generation into a practical procedure for random generation of HV -trees.)

For trees of type V, there are no constraints on T_{1} and T_{2}, so the number of such trees is A_{n−1}^{2}; hence the number of trees of other types is A_{n} − A_{n−1}^{2}. It follows from the rules above that the number of trees in T_{n}^{HV} (n ≥ 1) of the four types are

\begin{aligned}V & : A_{n−1}^{2} = p_{n}A_{n} \\ H_{HH} & : (A_{n−1} − A_{n−2}^{2})^{2} = p_{n}(1 − p_{n−1})^{2}A_{n} \\ H_{HV} & : A_{n−2}^{2}(A_{n−1} − A_{n−2}^{2}) = p_{n}p_{n−1}(1 − p_{n−1})A_{n} \\ H_{V H} & : A_{n−2}^{2}(A_{n−1} − A_{n−2}^{2}) = p_{n}p_{n−1}(1 − p_{n−1})A_{n} \end{aligned}  (4.5)

(Together, these numbers add up, as they should, to 2A_{n−1}^{2} − A_{n−2}^{4} = A_{n}, cf. (1.1) and (4.2).)

4.3 Recursive generation of random tilings

Let τ^{(n)} denote a random type τ ∈ {V, H_{HH}, H_{HV} , H_{V H}} with the distribution given by P(τ^{(n)} = V) = p_{n}, P(τ^{(n)} = H_{HH}) = p_{n}(1 − p_{n−1})^{2}, P(τ^{(n)} = H_{HV}) = P(τ^{(n)} = H_{V H}) = p_{n}p_{n−1}(1 − p_{n−1}). Let further τ_{H}^{(n)} denote τ^{(n)} conditioned on τ^{(n)} ≠ V; thus P(τ_{H}^{(n)} = H_{HH}) = (1 − p_{n−1})/(1 + p_{n−1}), P(τ_{H}^{(n)} = H_{HV}) = P(τ_{H}^{(n)} = H_{V H}) = p_{n−1}/(1 + p_{n−1}).

It follows from (4.5) that τ^{(n)} has the same distribution as the type of a randomly chosen tree in T_{n}^{HV}, and thus τ_{H}^{(n)} has the same distribution as the type of a random tree in T_{n}^{HV} with the root labeled H. The discussion in the preceding section now shows that the following algorithm generates a uniformly distributed random element of T_{n}^{HV}, for any given n ≥ 1.

Algorithm 4.1.

1. Select randomly a type for the root with the distribution τ^{(n)}.

2. Recursively assign types to all other nodes such that if a node of height k, 1 ≤ k < n, is assigned a type τ, then its left and right children get types τ_{1} and τ_{2} selected as follows.

τ = V: Choose τ_{1} and τ_{2}, independently, both with the distribution of τ^{(n−k)}.

τ = H_{HH}: Choose τ_{1} and τ_{2}, independently, both with the distribution of τ_{H}^{(n−k)}.

τ = H_{HV}: Choose τ_{1} with the distribution of τ_{H}^{(n−k)} and let τ_{2} = V.

τ = H_{V H}: Let τ_{1} = V and choose τ_{2} with the distribution of τ_{H}^{(n−k)}.

3. All vertices with type V are labeled V; the others are labeled H.

Next observe that since p_{n} → ϕ^{−1} as n → ∞, it follows that τ^{(n)} →^{d} τ^{(∞)} and τ_{H}^{(n)} →^{d} τ_{H}^{(∞)}, with (using ϕ^{2} = ϕ + 1 repeatedly)

P(τ^{(∞)} = V) = ϕ^{−1} = ϕ − 1,  P(τ_{H}^{(∞)} = V) = 0,
P(τ^{(∞)} = H_{HH}) = ϕ^{−5} = 5ϕ − 8,  P(τ_{H}^{(∞)} = H_{HH}) = ϕ^{−3} = 2ϕ − 3,
P(τ^{(∞)} = H_{HV}) = ϕ^{−4} = 5 − 3ϕ,  P(τ_{H}^{(∞)} = H_{HV}) = ϕ^{−2} = 2 − ϕ,
P(τ^{(∞)} = H_{V H}) = ϕ^{−4} = 5 − 3ϕ,  P(τ_{H}^{(∞)} = H_{V H}) = ϕ^{−2} = 2 − ϕ.

We can use these asymptotic distributions to construct an asymptotic version of Algorithm 4.1.

Algorithm 4.2. This is the same as Algorithm 4.1, but using the distributions τ^{(∞)} and τ_{H}^{(∞)} in Steps 1 and 2.

Consequently, for fixed N and n → ∞, the labels of the top N levels of a (uniform) random tree in T_{n}^{HV} converges (in distribution) to the outcome of Algorithm 4.2 (with n = N).

Remark 4.3. In Algorithms 4.1 and 4.2, we may process the nodes in any order such that a node is visited before its children. One natural choice, easily expressed as a recursive algorithm, is to travel depth-first, beginning with the left child, its left child, and so on.

Another choice is breadth-first, where we assign the types level by level, in order of the heights of the nodes. This version is useful for the arguments in Section 6. Moreover, it means that Algorithm 4.2 not only generates a random HV -tree of any given height; we can also regard Algorithm 4.2 as generating a random infinite HV -tree. The remarks above show that this random infinite tree is the limit in distribution of a (uniform) random tree in T_{n}^{HV}, as n → ∞, in the sense that the distribution of labels on any fixed finite part converges.

Remark 4.4. We have shown that Algorithm 4.1 generates uniformly distributed random HV -trees and thus uniformly distributed random tilings in T_{n}. Evidently, one can also produce random tilings in T_{n} by the following simpler algorithm: Make a vertical or horizontal cut, with probability 1/2 each, and continue recursively in each half n levels (with all choices independent). This method, however, does not give a uniformly distributed tiling when n ≥ 2. For example, the probability of obtaining the all horizontal tiling T̃_{0} is 2^{−(2^{n}−1)} ≪ A_{n}^{−1}. Moreover, a branching process argument similar to the one in Section 6.2, shows that for the random tiling generated by this procedure, P(there is a vertical cut) → 1 as n → ∞, in contrast to (4.1). This simpler method is equivalent to choosing a random labeling of the complete binary tree with H and V (or A and D) uniformly among all 2^{2^{n}−1} possibilities without any restrictions, and constructing the corresponding tiling as in Section 3.

5 Dynamic sampling algorithms

An alternative method for sampling AD-trees and dyadic tilings is by simulating suitable Markov chains. A simple Markov chain on the state space T_{n} starts from any tiling T_{0}.

At each step it chooses a random dyadic rectangle R of any size larger than 2^{−n} and checks whether R has a nontrivial intersection with any of the tiles in the current tiling. If not, then it rotates the part of the tiling that falls within R by 90^{∘} in one of the two directions; otherwise it does nothing. When R has area 2^{−n+1}, this rotation changes exactly two tiles and is very similar to a Markov chain previously studied in the context of domino tilings of the chessboard [12, 11, 13].

It will be useful to interpret tilings in terms of AD-trees. We first define a second, very simple Markov chain on AD-trees and show this is rapidly mixing. Of course this immediately defines a Markov chain on the set of dyadic tilings, but this chain is less natural in this context. Hence, we conclude this section by comparing the mixing rates of the two Markov chains on tilings to show that they both define efficient sampling algorithms.

5.1 A Markov chain on AD-trees

The Markov chain on AD-trees T_{n}^{AD} successively changes the labeling at a single node of the tree, while avoiding badly labeled subtrees. If x ∈ T_{n}^{AD} is a labeled tree, then let x(v) be the label which x assigns to vertex v.

The Markov chain M̃_{n} starts at a fixed starting point x_{0}, say the tree such that x_{0}(v) = D for all nodes v. Given that M̃_{n} is at state x_{t} at time t, it moves to state x_{t+1} as follows: Let V_{n} be the set of the 2^{n} − 1 vertices of the tree. Pick (v, b) ∈ V_{n} × {A, D} uniformly. Next, set x_{t+1}(v) = b if it leads to a valid configuration. For all w ≠ v, x_{t+1}(w) = x_{t}(w). If changing the label at v creates a badly labeled subtree, then we reject the move and remain at the current configuration, so x_{t+1}(v) = x_{t}(v) for all v. The transition probabilities P̃(·, ·) of M̃_{n} are

P̃_{n}(x, y) = \begin{cases}\frac{1}{2|V_{n}|} & if there is a unique node v such that \\ & x(v) ≠ y(v); \\ 1 − ∑_{y′≠x} P̃_{n}(x, y′) & if x = y; \\ 0 & otherwise. \end{cases}

Theorem 2.6 shows that the state space is connected. We prove a stronger lemma which will be useful later. Given any two configurations x, y ∈ T_{n}^{AD}, let us define the distance Φ(x, y) to be the Hamming distance between them. That is, Φ(x, y) is the number of vertices which are assigned different labels.

Lemma 5.1. Let x, y ∈ T_{n}^{AD} be any two configurations. Then there is a sequence of states z_{0}, z_{1}, …, z_{d} such that z_{0} = x, z_{d} = y, d = Φ(x, y) and for all 0 ≤ i < d, Φ(z_{i}, z_{i+1}) = 1.

Proof. Let x and y be two labeled trees at distance d. It suffices to identify z_{1} such that Φ(x, z_{1}) = 1 and Φ(z_{1}, y) = d − 1.

Let U ⊆ V_{n} be the set of d vertices in the tree that are assigned different labels in x and y. Let c ⊆ U be any connected component which contains at least one vertex labeled D in x, if it exists. Let w ∈ c be a vertex farthest from the root which is labeled D. We create z_{1} by letting z_{1}(w) = A and z_{1}(u) = x(u) for all u ≠ w. Notice that z_{1} cannot contain a badly labeled subtree: If w is a leaf in c, then its children must not both be labeled D since their labeling must agree with their labeling in y, which is assumed to be a valid configuration. If w is not a leaf, then it has at least one child in c which is labeled A, and therefore z_{1} is valid as long as x is.

Now suppose that all of the vertices of U are labeled A in x. Relabeling the root of any component D must lead to a valid configuration z_{1}. In this case the only potential conflict would occur if the parent of w is labeled A in both x and y, and the sibling of w is labeled D in x. However, since all vertices in x which need to be relabeled are labeled A, it must be the case that the sibling of w is also labeled D in y. If this were the case then y would have a badly labeled subtree, a contradiction.

Corollary 5.2. The Markov chain M̃_{n} is ergodic and converges to the uniform distribution on T_{n}^{AD}.

5.2 Bounding the mixing rate of M̃_{n}

To bound the mixing rate, or convergence time, of our Markov chain, we will use a simple path coupling argument.

Starting in any given initial state x, we measure the deviation of the distribution P^{t}(x, ·) at time t from the uniform distribution π by the variation distance:

Δ_{x}(t) = \frac{1}{2} ∑_{y∈Ω} |P^{t}(x, y) − π(y)|.

The mixing time of the Markov chain is defined as

τ(ϵ) = max_{x} min{t : Δ_{x}(t′) ≤ ϵ for all t′ ≥ t}.

If τ(ϵ) is polylogarithmic in the size of Ω, for fixed ϵ, then we say that the Markov chain is rapidly mixing. Recall that our state space has size which is doubly exponential in n (see equation (1.2)), so this means that τ(ϵ) is exponential in n. All of our algorithms must have mixing time which is at least 2^{n}, the time it takes to write down a single configuration.

One strategy for bounding τ(ϵ) is to construct a coupling for the Markov chain, i.e., a stochastic process (x_{t}, y_{t})_{t=0}^{∞} on Ω × Ω such that each of the processes x_{t} and y_{t} is a faithful copy of M (given initial states x_{0} = x and y_{0} = y), and if x_{t} = y_{t}, then x_{t+1} = y_{t+1}.

The expected time taken for the processes to meet provides a good bound on the mixing time of M. To state this formally, for initial states x, y set

T_{x,y} = min{t : x_{t} = y_{t} | x_{0} = x, y_{0} = y},

and define the coupling time to be T = max_{x,y} E T^{x,y}. The following result relates the mixing time to the coupling time (see, e.g., [1]):

Theorem 5.3. τ(ϵ) ≤ T e⌈ln ϵ^{−1}⌉.

The method of path coupling simplifies our goal by letting us bound the mixing rate of a Markov chain by considering only a small subset of Ω × Ω. (See [6, 9].) We use the following theorem, obtained by combining Theorems 2.1 and 2.2 in Dyer and Greenhill [9].

Theorem 5.4. Let Φ be an integer valued metric defined on Ω × Ω which takes values in {0, …, B}. Let U be a subset of Ω × Ω such that for all (x, y) ∈ Ω × Ω there exists a path x = z_{0}, z_{1}, …, z_{r} = y between x and y such that (z_{i}, z_{i+1}) ∈ U for 0 ≤ i < r and

∑_{i=0}^{r−1} Φ(z_{i}, z_{i+1}) = Φ(x, y).

Let M be a Markov chain on Ω with transition matrix P. Consider any random function f : Ω → Ω such that P[f(x) = y] = P (x, y) for all x, y ∈ Ω, and define a coupling of the Markov chain by (x_{t}, y_{t}) → (x_{t+1}, y_{t+1}) = (f_{t}(x_{t}), f_{t}(y_{t})), where (f_{t})_{t=0}^{∞} are independent copies of f. Let ΔΦ(x_{t}, y_{t}) = Φ(x_{t+1}, y_{t+1}) − Φ(x_{t}, y_{t}). Suppose that, conditioned on any pair of states x_{t} and y_{t},

(i). E(ΔΦ(x_{t}, y_{t})) ≤ 0 when (x_{t}, y_{t}) ∈ U,

(ii). P[Φ(x_{t+1}, y_{t+1}) ≠ Φ(x_{t}, y_{t})] ≥ α when x_{t} ≠ y_{t}, for some constant α > 0.

Then the mixing time of M satisfies

τ(ϵ) ≤ ⌈\frac{eB^{2}}{α} ⌉⌈ln ϵ^{−1}⌉.

The random function f thus updates all states of the Markov chain simultaneously. This is known as a complete coupling.

To apply this machinery to analyze the Markov chain M̃_{n}, we first need to define the random function f that defines the coupling. We do this by choosing (v, b) ∈ V_{n}×{D, A} uniformly and independently and then for any configuration x defining f(x) by changing x(v) to b, if possible. This defines a simultaneous update of all states, and thus a complete coupling with the correct marginal distributions.

Let U be the pairs of configurations (x, y) such that Φ(x, y) = 1. The following lemma establishes that the expected distance between such a pair is never increasing.

Lemma 5.5. Let x_{t}, y_{t} ∈ T_{n}^{AD} be two configurations such that Φ(x_{t}, y_{t}) = 1. Then the expected change in distance E[ΔΦ(x_{t}, y_{t})] ≤ 0 after one step of the coupled Markov chain.

Proof. Let x_{t}, y_{t} ∈ T_{n}^{AD} such that Φ(x_{t}, y_{t}) = 1 and let w be the vertex where they are labeled differently. Assume without loss of generality that w is labeled D in x_{t}. Suppose we choose (v, b) ∈ V_{n} × {A, D} for our next move. We consider the set of moves that can change the distance between the configurations. Let p(w) be the parent of w, s(w) be the sibling of w, and l(w) and r(w) be the left and right children of w.

1. If v = w, then x_{t+1} = y_{t+1} for any choice of b.

2. If v = p(w), then there is exactly one way that the distance can increase. Namely, x_{t}(p(w)) = D, x_{t}(s(w)) = D and b = A. (This move would increase the distance between configuration because the label on x_{t+1}(p(w)) = x_{t}(p(w)) but y_{t+1}(p(w)) ≠ y_{t}(p(w)).)

3. If v = s(w), then again there is exactly one way for the distance to increase. The can only occur if x_{t}(p(w)) = A, x_{t}(s(w)) = A and b = D.

4. If v = l(w) is the left child of w, then we can increase the distance between configurations only if the x_{t}(l(w)) = A, x_{t}(r(w)) = D and b = D, where r(w) is the right child of w.

5. Likewise, if v = r(w), the distance can increase only if x_{t}(l(w)) = D, x_{t}(r(w)) = A and b = D.

Initially it looks as though there are many more possibilities for increasing the distance than decreasing it. However, we are quite fortunate in that not all of these potentially bad events can be present simultaneously. In particular, the bad events described in the second and third cases cannot occur simultaneously, nor can the last two cases. Hence, there are at most two choices of (v, b) which will increase the distance to 2 and exactly two choices of (v, b) which will decrease the distance to 0. All other moves are neutral. Summarizing this discussion, we find that

E[ΔΦ(x_{t}, y_{t})] ≤ 0,

since all of these moves are equally likely.

This lemma provides the crucial ingredient towards our path coupling argument for bounding the mixing rate of M̃_{n}.

Referring to Theorem 5.4, using α = (2^{n} − 1)^{−1} and Lemma 5.1, we find

Corollary 5.6. The mixing time of the Markov chain M̃_{n} on labeled trees T_{n}^{AD} satisfies τ(ϵ) ≤ 2^{3n}e⌈ln ϵ^{−1}⌉.

5.3 A natural Markov chain on tilings

The Markov chain M̃_{n} defined on AD-trees can be reinterpreted in terms of tilings; at each step one of 2^{n} − 1 possible dyadic rectangles is identified, and if certain conditions are met, the subtiling can be rotated. Our definition of AD-trees restricts both the set of possible rectangles as well as the direction of rotation. For example, if the tiling has both horizontal and vertical cuts (of the unit square), then we may allow the top or bottom half to be rotated in this fashion, but we would not allow the left or right halves to be rotated, nor the whole square.

We rectify this asymmetry by introducing a new Markov chain M_{n}, referred to at the beginning of this section. Two tilings are connected by a single step of the Markov chain if one can be transformed into the other by rotating the part of the tiling contained in some dyadic rectangle in the square.

Let b_{n} be the number of dyadic rectangles (regions) in a unit square with area at least 2^{−n+1}. Since there are (k + 1)2^{k} dyadic rectangles with area exactly 2^{−k} (since there are k +1 choices for the shape and each shape can appear in exactly 2^{k} positions), we find

b_{n} = ∑_{k=0}^{n−1}(k + 1)2^{k} = (n − 1)2^{n} + 1.

This gives the transition probabilities P_{n}(·) of our Markov chain M_{n}:

P_{n}(T_{1}, T_{2}) = \begin{cases}\frac{1}{4b_{n}} & if T_{1} and T_{2} differ by rotating the subtiling \\ & in a dyadic subrectangle by ±90^{∘} or 180^{∘}; \\ 1 − ∑_{T′≠T_{1}} P_{n}(T_{1}, T′) & if T_{1} = T_{2} \\ 0 & otherwise. \end{cases}

It is not hard to see that this Markov chain connects the state space; starting with any tiling, we can always rotate subtilings starting with large dyadic rectangles and continuing with smaller ones until all the cuts are vertical. (Theorem 2.6 shows a stronger statement.) In addition, all transitions (besides self-loops) have equal probability, so detailed balance implies that the Markov chain converges to the uniform distribution. Summarizing this, we find:

Theorem 5.7. The Markov chain M_{n} is ergodic and converges to the uniform distribution over dyadic tilings T_{n}.

5.4 Showing that M_{n} is rapidly mixing

We conclude by showing that M_{n} is rapidly mixing by comparing its mixing rate to that of M̃_{n}, using the comparison method of Diaconis and Saloff-Coste [8]. Here we describe a special case of the comparison theorem which is sufficient for our application.

Let P and P̃ be transition matrices of two reversible Markov chains on state space Ω which have the same stationary distribution π. We would like to express the mixing rate of a Markov chain (P, π, Ω) (for example, M_{n}, the Markov chain on tilings) in terms of the mixing rate of (P̃, π, Ω) (for example, M̃_{n}, the rapidly mixing Markov chain on AD-trees).

To apply the comparison method it is necessary to map each transition of P̃ to a path described by some number of transitions in P. In our application this is trivial since P̃(x, y) ≠ 0 implies that P (x, y) ≠ 0 for every x, y ∈ Ω. Hence we can use the identity map and all of our paths have length 1. Using the formulation of the comparison method as given in [13, Proposition 4] (slightly modified here), we have the following theorem.

Theorem 5.8. Let (P, π, Ω) and (P̃, π, Ω) be two reversible Markov chains such that P̃(x, y) ≠ 0 implies P (x, y) ≠ 0 for all x, y ∈ Ω. Let π_{∗} = min_{x∈Ω} π(x). Then, for 0 < ϵ < 1/2,

τ(ϵ) ≤ 4 ln(1/(ϵπ_{∗}))A max(\frac{τ̃(ϵ)}{ln(1/2ϵ)}, 1),  (5.1)

where

A = max_{x≠y,P̃(x,y)>0} \frac{P̃(x, y)}{P (x, y)}.

To apply this to our Markov chains M_{n} and M̃_{n}, consider any pair of states x ≠ y ∈ Ω such that P̃(x, y) > 0. We find

\frac{P̃(x, y)}{P (x, y)} ≤ \begin{matrix}(2|V_{n}|) & −1 \\ (4b_{n}) & −1 \end{matrix}

= \frac{4((n − 1) 2^{n} + 1)}{2(2^{n} − 1)}

≤ 2n.

In addition, the stationary probability π is uniform over dyadic tilings, so π_{∗}^{−1} ≤ 2^{2^{n}}. Applying these bounds, Theorem 5.8 gives

τ(ϵ) ≤ c(ϵ)n 2^{n} τ̃(ϵ),

for some constant c(ϵ). Hence, by Corollary 5.6,

Corollary 5.9. The Markov chain M_{n} on dyadic tilings T_{n} is rapidly mixing.

Problem 5.10. It is also natural to consider the analogous Markov chain where we only rotate rectangles of area 2^{−n+1}. This is the same as random walk on T_{n} regarded as an undirected graph as in Section 2. Is this Markov chain also rapidly mixing?

6 Random dyadic tilings

We now turn our attention to limiting properties of random tilings such as the expected height of a tiling and the likelihood of long, thin rectangles. As in Section 4.2, we shall make use of the partition of tilings into types according to whether there are vertical or horizontal cuts. We also use the recursive random construction in Section 4.3.

6.1 Total height

Recall the definition of the total height of a tiling from Section 2. We will here study the normalized height function defined by

H̃(T) = 2^{−n}H(T) − n/2,  T ∈ T_{n}.  (6.1)

Recalling equation (2.1), this gives us that −n/2 ≤ H̃(T) ≤ n/2. We let H_{n} and H̃_{n} denote the random variables H(T) and H̃(T) obtained by choosing a random tiling T ∈ T_{n}.

By symmetry (a rotation 90^{∘} transforms H̃(T) to −H̃(T)), H̃_{n} is a symmetric random variable. In particular, E H̃_{n} = 0.

Theorem 6.1. There exists a symmetric random variable H̃_{∞} such that (i). As n → ∞, H̃_{n} →^{d} H̃_{∞}, with convergence of all moments.

(ii). For any real t,

E exp(tH̃_{n}) ≤ exp(\frac{1}{4}ϕ^{4}t^{2}), 1 ≤ n ≤ ∞.

(iii). For any a ≥ 0,

P(H̃_{n} ≥ a) ≤ exp(−ϕ^{−4}a^{2}), 1 ≤ n ≤ ∞.

(iv). The moment generating function ψ(z) = E e^{zH̃_{∞}} is an entire function satisfying the functional equation

ψ(z) = (\sqrt{5} − 1) cosh(z/2)(ψ(z/2))^{2} − (\sqrt{5} − 2)(ψ(z/4))^{4}.  (6.2)

(v). Var H̃_{∞} = E H̃_{∞}^{2} = (6ϕ − 2)/11 = (3\sqrt{5} + 1)/11 = 0.7007458 · · ·.

Remark 6.2. Higher moments of H̃_{∞} may be found recursively by differentiation of (6.2). In particular, E H̃_{∞}^{4} = (71230+7902\sqrt{5})/80465 = 1.10482 · · ·. (All odd moments vanish by symmetry.)

Remark 6.3. This theorem justifies the definition of the normalization H̃_{n}, which at first might appear odd. There are 2^{n} rectangles, each with height in {0, …, n}, so that if the heights were independent the variance would be at most n^{2}2^{n}. Theorem 6.1 shows, in contrast, that Var H_{n} = 2^{2n} Var H̃_{n} ∼ c2^{2n}, with c = Var H̃_{∞} = (3\sqrt{5} + 1)/11, which indicates a very high correlation. Roughly speaking, if an early cut creates long thin rectangles then all of its subrectangles will tend also to be long and thin.

Proof. We use the bijection with HV -trees, and define H(T) for an HV -tree T ∈ T_{n}^{HV} to be the total height of the corresponding tiling. It is easily seen (by induction) that each of the 2^{n−1} paths in the tree from the root to a leaf corresponds to two congruent tiles in the tiling, whose height equals the number of labels V in the path. Let v_{k}(T) denote the number of nodes at level k in the tree T that are labeled V. Since each node at level k lies on the path to 2^{n−k} leaves, we obtain by summing over all paths

H(T) = 2 ∑_{x leaf} (number of V on the path to x) = 2 ∑_{k=1}^{n} 2^{n−k}v_{k}  (6.3)

and thus

H̃(T) = ∑_{k=1}^{n}(2^{1−k}v_{k} − \frac{1}{2}).  (6.4)

We label the HV -tree T by types as in Section 4.2 and define the k-type type_{k}(T) to be the subtree of nodes up to height k, labeled with their types in T (k = 1, …, n). Thus type_{1}(T) is the root and its type, or equivalently just the type of the root, which we already have called the type of the tree, i.e. type_{1}(T) = type(T).

For each n we define a martingale X_{0}^{(n)}, X_{1}^{(n)}, …, X_{n}^{(n)} = H̃_{n} by setting X_{0}^{(n)} = E H̃_{n} = 0 and X_{k}^{(n)} = E(H̃_{n} | type_{k}) for k ≥ 1. In other words, X_{k}^{(n)}(T) is defined as the average of X_{k}^{(n)}(T′) over all HV -trees T′ having the same k-type as T.

Let us first consider X_{1}^{(n)} = E(H̃_{n} | type). If T ∈ T_{n}^{HV} is of type V, and the two subtrees of the root are T_{1}, T_{2} ∈ T_{n−1}^{HV}, then H(T) = H(T_{1}) + H(T_{2}) + 2^{n} by (6.3), or directly by considering the corresponding tilings. Hence

H̃(T) = \frac{1}{2}(H̃(T_{1}) + H̃(T_{2})) + \frac{1}{2},  type(T) = V.  (6.5)

Similarly, if T has type H_{HH}, H_{HV} or H_{V H}, then H(T) = H(T_{1}) + H(T_{2}) and

H̃(T) = \frac{1}{2}(H̃(T_{1}) + H̃(T_{2})) − \frac{1}{2},  type(T) ≠ V.  (6.6)

As discussed in Section 4.2, for trees with type(T) = V, T_{1} and T_{2} may be any trees in T_{n−1}^{HV}, and thus

E(H̃_{n} | type = V) = \frac{1}{2} E H̃_{n−1} + \frac{1}{2} E H̃_{n−1} + \frac{1}{2} = \frac{1}{2},  n ≥ 1.  (6.7)

Combining this with

E(H̃_{n} | type = V) P(type = V) + E(H̃_{n} | type ≠ V) P(type ≠ V) = E H̃_{n} = 0

and P(type = V) = p_{n} by (4.1), we find

E(H̃_{n} | type ≠ V) = −\frac{p_{n}}{2(1 − p_{n})}.  (6.8)

Similarly, it follows from (6.6) and the constraints (4.4), using (6.7) and (6.8), that

E(H̃_{n} | type = H_{HH}) = E(H̃_{n−1} | type ≠ V) − \frac{1}{2}

= −\frac{p_{n−1}}{2(1 − p_{n−1})} − \frac{1}{2} = −\frac{1}{2(1 − p_{n−1})}. (6.9)

and

E(H̃_{n} | type = H_{HV}) = E(H̃_{n} | type = H_{V H})

= \frac{1}{2} E(H̃_{n−1} | type = V) + \frac{1}{2} E(H̃_{n−1} | type ≠ V) − \frac{1}{2}

= −\frac{1}{4(1 − p_{n−1})}.

(6.10)

Consequently, X_{1}^{(n)} − X_{0}^{(n)} = X_{1}^{(n)} is a random variable taking the three values in (6.7), (6.9) and (6.10) with probabilities P(τ^{(n)} = V) = p_{n}, P(τ^{(n)} = H_{HH}) = p_{n}(1 − p_{n−1})^{2} and P(τ^{(n)} = H_{HV}) + P(τ^{(n)} = H_{V H}) = 2p_{n}p_{n−1}(1 − p_{n−1}), respectively, where as in Section 4.3 τ^{(n)} is the type of a random HV -tree in T_{n}^{HV}, cf. (4.5). In particular,

|X_{1}^{(n)}| ≤ \frac{1}{2(1 − p_{n−1})} ≤ \frac{ϕ^{2}}{2} .  (6.11)

For future use we define Y^{(n)} = X_{1}^{(n)}, and let further Y_{H}^{(n)} and Y_{V}^{(n)} denote the random variables obtained by conditioning Y^{(n)} on type ≠ V and type = V, respectively. (Thus, by (6.7), Y_{V}^{(n)} = \frac{1}{2} really is non-random.) Moreover, define Ȳ^{(n)} = Y^{(n)} − E Y^{(n)} = Y^{(n)}, Ȳ_{H}^{(n)} = Y_{H}^{(n)} − E Y_{H}^{(n)} and Ȳ_{V}^{(n)} = Y_{V}^{(n)} − E Y_{V}^{(n)} = 0. By (6.11), a similar calculation for Ȳ_{H}^{(n)} and trivially for Ȳ_{V}^{(n)}, we have the common bound

|Ȳ^{(n)}|, |Ȳ_{H}^{(n)}|, |Ȳ_{V}^{(n)}| ≤ \frac{ϕ^{2}}{2} .  (6.12)

We proceed to studying the martingale differences X_{k+1}^{(n)} − X_{k}^{(n)} for higher k. Let T ∈ T_{n}^{HV} and 1 ≤ k < n. There are 2^{k−1} nodes on level k in T, and each of them carries two subtrees of height n − k. Denoting these 2^{k} subtrees by T_{1}, …, T_{2^{k}} ∈ T_{n−k}^{HV}, we find from (6.4)

H̃(T) = ∑_{i=1}^{k}(2^{1−i}v_{i} − \frac{1}{2}) + 2^{−k} ∑_{j=1}^{2^{k}} H̃(T_{j}).  (6.13)

Now consider all trees with a given k-type τ. The k-type determines v_{1}, …, v_{k}, and it specifies some of the labels on level k + 1, i.e. some of the root labels of the trees T_{j} (the ones attached to a node on level k labeled H); say that τ specifies m_{H} labels H and m_{V} labels V on level k + 1, leaving 2^{k} − m_{H} − m_{V} unspecified. By the recursive construction in Section 4, the trees T_{j} can be any trees with the right root labels, and (6.13) yields

E(H̃(T) | type_{k}(T) = τ) = ∑_{i=1}^{k}(2^{1−i}v_{i} − \frac{1}{2}) + 2^{−k}(m_{H} E(H̃_{n−k} | type ≠ V)

+ m_{V} E(H̃_{n−k} | type = V)), (6.14)

where the conditional expectations on the right hand side are given by (6.7), (6.8).

Now suppose that we extend the k-type τ to a (k + 1)-type τ′ by specifying also the types at level k + 1. In (6.13), this means that we now have specified the types of T_{1}, …, T_{2^{k}}. If τ′ specifies type(T_{j}) = τ_{j}, we thus obtain from (6.13) and (6.14), since the trees T_{j} otherwise are arbitrary trees in T_{n−k}^{HV},

E(H̃(T) | type_{k+1}(T) = τ′) − E(H̃(T) | type_{k}(T) = τ)

= 2^{−k}(∑_{j=1}^{2^{k}} E(H̃_{n−k} | type = τ_{j}) − m_{H} E(H̃_{n−k} | type ≠ V) − m_{V} E(H̃_{n−k} | type = V)).

Using the recursive construction in Section 4.3, the types τ_{j} are assigned independently, given τ, and it follows that conditioned on type_{k}(T) = τ, we have

X_{k+1}^{(n)}(T) − X_{k}^{(n)}(T) = 2^{−k} ∑_{j=1}^{2^{k}} Ȳ_{j},  (6.15)

where Ȳ_{1}, …, Ȳ_{2^{k}} are independent random variables, and each Ȳ_{j} is distributed as one of Ȳ^{(n−k)}, Ȳ_{H}^{(n−k)} and Ȳ_{V}^{(n−k)}. Since every Ȳ_{j} has mean 0 and, by (6.12), variance at most c = ϕ^{4}/4, we obtain

E((X_{k+1}^{(n)} − X_{k}^{(n)})^{2} | type_{k} = τ) = 2^{−2k} ∑_{j=1}^{2^{k}} E(Ȳ_{j})^{2} ≤ c2^{−k}

and thus

E(X_{k+1}^{(n)} − X_{k}^{(n)})^{2} ≤ c2^{−k},  0 ≤ k < n.  (6.16)

Since martingale differences are orthogonal, and H̃_{n} = X_{n}^{(n)}, this yields

E(H̃_{n} − X_{k}^{(n)})^{2} = ∑_{i=k}^{n−1} E(X_{i+1}^{(n)} − X_{i}^{(n)})^{2} ≤ 2c2^{−k},  0 ≤ k < n.  (6.17)

Next let k ≥ 0 be fixed, and let n → ∞. Since then p_{n} → ϕ^{−1}, the conditional expectations in (6.7)–(6.10) converge to some limits, and the right hand side in (6.14) converges to some number X_{k}(τ). Moreover, the k-type of a random tiling T ∈ T_{n}^{HV} is given by the first k levels of Algorithm 4.1, and thus its distribution converges to the distribution of the random k-type τ_{k}^{∞} generated by Algorithm 4.2, see Remark 4.3. Hence, defining X_{k} = X_{k}(τ_{k}^{∞}), X_{k}^{(n)} →^{d} X_{k} as n → ∞, for every fixed k ≥ 0.

Moreover, we may generate all τ_{k}^{∞}, k = 0, 1, … together as the k-types of the random infinite HV -tree constructed in Remark 4.3, and then X_{0}, X_{1}, … becomes a martingale, as is easily seen by construction or by taking the limit of the martingales {X_{k}^{(n)}}. Moreover, by letting n → ∞ in (6.16), we see that

E(X_{k+1} − X_{k})^{2} ≤ c2^{−k}, k ≥ 0,

and hence the martingale {X_{k}} is L^{2}-bounded, whence it converges in L^{2}; thus there exists a random variable H̃_{∞} such that E(H̃_{∞} − X_{k})^{2} → 0 as k → ∞. This, the convergence X_{k}^{(n)} →^{d} X_{k} for every fixed k and the uniform bound (6.17), where the bound 2c2^{−k} tends to 0 as k → ∞, implies that H̃_{n} →^{d} H̃_{∞} by a standard 3ϵ argument [5, Theorem 4.2].

This proves the first claim in (i). Convergence of all moments follows from this when we have shown the uniform bound (ii).

For (ii), we return to the representation (6.15) for given n, k and τ. Using again E Ȳ_{j} = 0 and |Ȳ_{j}| ≤ ϕ^{2}/2, it follows as in e.g. [2, proof of Theorem A.16] that

E exp(tȲ_{j}) ≤ cosh(\frac{1}{2}ϕ^{2}t) ≤ exp(\frac{1}{8}ϕ^{4}t^{2}), j = 1, …, 2^{k},

and thus

E(exp(t(X_{k+1}^{(n)} − X_{k}^{(n)})) | type_{k} = τ)

= E exp(t2^{−k} ∑_{j=1}^{2^{k}} Ȳ_{j}) = ∏_{j=1}^{2^{k}} E exp(t2^{−k}Ȳ_{j})

≤ exp(2^{k} \frac{1}{8}ϕ^{4}(2^{−k}t)^{2}) = exp(2^{−k−3}ϕ^{4}t^{2}).

Consequently, since type_{k} determines X_{k}^{(n)},

E exp(tX_{k+1}^{(n)}) = E(E(exp(t(X_{k+1}^{(n)} − X_{k}^{(n)})) | type_{k}) exp(tX_{k}^{(n)}))
≤ exp(2^{−k−3}ϕ^{4}t^{2}) exp(tX_{k}^{(n)}),

and thus, recalling H̃_{n} = X_{n}^{(n)} and X_{0}^{(n)} = 0,

E exp(tH̃_{n}) ≤ ∏_{k=0}^{n−1} exp(2^{−k−3}ϕ^{4}t^{2}) ≤ exp(2^{−2}ϕ^{4}t^{2}).

This is (ii) for finite n. The estimate for n = ∞ follows by taking the limit as n → ∞ (or by the same argument).

(iii) follows from (ii) by a standard application of Markov’s inequality. (Cf. e.g. [2, Appendix A].)

For (iv), we first observe that (ii) implies that E e^{zH̃_{∞}} exists for every complex z and defines an entire function, and further that E e^{zH̃_{n}} → E e^{zH̃_{∞}} as n → ∞.

In order to show the functional equation (6.2), we return to the argument used to show (1.1). Consider a random tiling in T_{n}^{HV} and let V and H denote the events that there is a vertical or horizontal cut, respectively, and let 1_{V} and 1_{H} denote the corresponding indicator functions. Then, since there is at least one cut by Theorem 1.1,

E e^{zH̃_{n}} = E(e^{zH̃_{n}}1_{V}) + E(e^{zH̃_{n}}1_{H}) − E(e^{zH̃_{n}}1_{V∩H})

= E(e^{zH̃_{n}} | V) P(V) + E(e^{zH̃_{n}} | H) P(H) − E(e^{zH̃_{n}} | V ∩ H) P(V ∩ H). (6.18)

Moreover, using (6.5),

E(e^{zH̃_{n}} | V) = e^{z/2} E(e^{^{\frac{z}{2}} H̃_{n−1}}) E(e^{^{\frac{z}{2}} H̃_{n−1}})

and similarly, or by symmetry,

E(e^{zH̃_{n}} | H) = e^{−z/2} E(e^{^{\frac{z}{2}} H̃_{n−1}}) E(e^{^{\frac{z}{2}} H̃_{n−1}}).

Furthermore, if T ∈ T_{n}^{HV} is a tiling with both vertical and horizontal cuts, it is composed of four (arbitrary) tilings T_{1}, T_{2}, T_{3}, T_{4} ∈ T_{n−2}^{HV}, with H̃(T) = \frac{1}{4} ∑_{1}^{4} H̃(T_{i}), which leads to

E(e^{zH̃_{n}} | V ∩ H) = (E(e^{^{\frac{z}{4}} H̃_{n−2}}))^{4}.

Since P(V) = P(H) = p_{n} → ϕ − 1 = (\sqrt{5} − 1)/2 and thus P(V ∩ H) = 2p_{n} − 1 → 2ϕ − 3 = \sqrt{5} − 2, (6.2) now follows by letting n → ∞ in (6.18).

Finally, differentiating (6.2) twice at z = 0 yields, with σ^{2} = Var H̃_{∞} and using E H̃_{∞} = 0,

σ^{2} = 2(ϕ − 1)\frac{1}{4}(1 + 2σ^{2}) − (2ϕ − 3)\frac{4}{16}σ^{2},

which yields (v) after elementary calculations.

6.2 Spanning rectangles

We call a subrectangle of the unit square is a strut if it spans the unit square vertically. (Hence a dyadic rectangle of area 2^{−n} is a strut if its height as defined in Section 2 is n.) We will study the distribution of S_{n}(T), the number of struts in a random tiling T in T_{n}.

We begin by observing that T has a horizontal cut if and only if there are no struts, i.e. if S_{n}(T) = 0. Hence, by (4.1),

P(S_{n} = 0) = p_{n} → ϕ − 1.

To proceed, we again use HV -trees. As remarked in the proof of Theorem 6.1, a path from the root to a leaf in an HV -tree defines two congruent tiles in the corresponding tiling, and these tiles are struts if and only if all nodes on the path are labeled V. Thus S_{n} equals two times the number of such paths in a random HV -tree.

Theorem 6.4. S_{n}/(\sqrt{5} − 1)^{n} →^{d} Z as n → ∞, for some random variable Z such that:

(i). P(Z = 0) = lim_{n→∞} P(S_{n} = 0) = ϕ − 1.

(ii). E Z = β and Var Z = 2ϕβ^{2}, where β = ∏_{n=1}^{∞}(p_{n}ϕ) = 0.702845 · · ·.

(iii). Besides the pointmass at 0, Z has an absolutely continuous distribution on (0, ∞), with a continuous and strictly positive density.

Proof. For an HV -tree T ∈ T_{n}^{HV} and 1 ≤ k ≤ n, let X_{k}^{(n)}(T) be two times the number of paths from the root of T to a node of height k such that the k nodes on the path all are labeled V. Thus X_{n}^{(n)} = S_{n}. Further, let X_{0}^{(n)} = 1.

It follows from the recursive construction in Section 4.3 that X_{k+1}^{(n)} has the distribution of a sum of X_{k}^{(n)} independent variables Y_{j}^{(n−k)}, where Y_{j}^{(m)} has the distribution

\begin{aligned}P(Y_{j}^{(m)} = 2) & = p_{m}, \\ P(Y_{j}^{(m)} = 0) & = 1 − p_{m}. \end{aligned}  (6.19)

In other words, the random sequence X_{0}^{(n)}, …, X_{n}^{(n)} is an inhomogeneous branching process where the kth generation has the offspring distribution given by Y_{j}^{(n−k)} in (6.19). It follows that

E(X_{k+1}^{(n)} | X_{0}^{(n)}, …, X_{k}^{(n)}) = (E Y_{1}^{(n−k)})X_{k}^{(n)} = 2p_{n−k}X_{k}^{(n)};

hence, defining m_{k}^{(n)} = E X_{k}^{(n)} and W_{k}^{(n)} = X_{k}^{(n)}/m_{k}^{(n)}, we see that W_{0}^{(n)}, …, W_{n}^{(n)} is a martingale and that

m_{k}^{(n)} = E X_{k}^{(n)} = ∏_{i=0}^{k−1} 2p_{n−i} = ∏_{i=n−k+1}^{n} 2p_{i},  0 ≤ k ≤ n.  (6.20)

Moreover, again by the branching process,

E((X_{k+1}^{(n)} − 2p_{n−k}X_{k}^{(n)})^{2} | X_{k}^{(n)}) = Var(Y_{1}^{(n−k)})X_{k}^{(n)} = 4p_{n−k}(1 − p_{n−k})X_{k}^{(n)}

and thus

E(X_{k+1}^{(n)} − 2p_{n−k}X_{k}^{(n)})^{2} = 4p_{n−k}(1 − p_{n−k})m_{k}^{(n)}.

and

E(W_{k+1}^{(n)} − W_{k}^{(n)})^{2} = 4p_{n−k}(1 − p_{n−k})m_{k}^{(n)}/(m_{k+1}^{(n)})^{2} = \frac{1 − p_{n−k}}{p_{n−k}} (m_{k}^{(n)})^{−1}.

Since p_{1} = 1/2 and p_{i} ≥ p_{2} = 4/7 for i ≥ 2, (6.20) implies m_{k}^{(n)} ≥ (8/7)^{k−1}, and thus, for 0 ≤ k ≤ n, since martingale differences are orthogonal and S_{n} = X_{n}^{(n)},

\begin{aligned}E(S_{n}/m_{n}^{(n)} − W_{k}^{(n)})^{2} & = ∑_{i=k}^{n−1} E(W_{i+1}^{(n)} − W_{i}^{(n)})^{2} ≤ ∑_{i=k}^{n−1}(m_{i}^{(n)})^{−1} \\ & ≤ ∑_{i=k}^{n−1}(7/8)^{i−1} ≤ 8(7/8)^{k−1}. \end{aligned}  (6.21)

The variable Y_{j}^{(n−k)} defined by (6.19) evidently converges in distribution, as n → ∞ with fixed k, to a limit variable Y_{j} with

\begin{aligned}P(Y_{j} = 2) & = ϕ − 1, \\ P(Y_{j} = 0) & = 2 − ϕ. \end{aligned}  (6.22)

Consider the standard (Galton–Watson) branching process X_{0}, X_{1}, … with X_{0} = 1 and offspring distribution given by (6.22), and the corresponding expectations m_{k} = (E Y_{1})^{k} = (\sqrt{5} − 1)^{k} and martingale W_{k} = X_{k}/m_{k}. As is well-known [4, Section 1.6] (and easy to prove), this martingale converges, and thus W_{k} → W as k → ∞ for some W.

Moreover, it is obvious that for every fixed k ≥ 0, as n → ∞, we have X_{k}^{(n)} →^{d} X_{k}, m_{k}^{(n)} → m_{k} and thus W_{k}^{(n)} →^{d} W_{k}. Together with the uniform bound (6.21), this implies S_{n}/m_{n}^{(n)} →^{d} W, using again [5, Theorem 4.2]. Furthermore, as n → ∞,

\frac{m_{n}^{(n)}}{(\sqrt{5} − 1)^{n}} = ∏_{i=1}^{n} \frac{2p_{i}}{2ϕ − 2} → ∏_{i=1}^{∞} \frac{p_{i}}{ϕ − 1},

where the infinite product converges because of (4.3). Denoting this product by β, we thus have S_{n}/(\sqrt{5} − 1)^{n} →^{d} βW. The proof is completed by using well-known properties of the limit W, see e.g. [4, Th. I.6.2, Cor. I.12.1] and [3, Sec. 3.6].

We might also consider horizontal struts, which are the tiles with height 0. By symmetry, the same results hold for the number S_{n}^{(0)} of them. Note that, by Theorem 1.1, a tiling in T_{n} (with n ≥ 1) cannot contain both horizontal and vertical struts, so at least one of the numbers S_{n} and S_{n}^{(0)} is always 0.

Problem 6.5. We leave for further study the analysis of the number S_{n}^{(h)} of rectangles of a given height h for 0 < h < n. For h fixed, we expect asymptotic distributions similar in nature to those of S_{n}. The situation is less clear when h ∼ cn with 0 < c < 1. In particular, what is the limiting distribution of the number S_{2n}^{(n)} of squares?

Problem 6.6. Let h_{min}(T) denote the minimum height of all tiles in the tiling T. Then

P(h_{min}(T) = 0) = P(there is a horizontal strut) = 1 − p_{n} → 2 − ϕ.

Does h_{min} have an asymptotic distribution (as seems likely)? What is it? In other words, does P(h_{min}(T) = h) have a limit as n → ∞ for every fixed h ≥ 1, and what is the limit?

Acknowledgement

The main results of this paper were discovered during an excursion to the Zaniemyśl Forest during the Random Graphs conference in Poznań, Poland, August 1999.

References

[1] Aldous, D. Random walks on finite groups and rapidly mixing Markov chains. Séminaire de Probabilités XVII, 1981/82, Springer Lecture Notes in Mathematics 986, pp. 243–297.

[2] Alon, N. and Spencer, J. The Probabilistic Method. 2nd Edition, Wiley, New York, 2000.

[3] Asmussen S. & Hering H. Branching Processes. Birkhäuser, Basel, 1983.

[4] Athreya, K.B. and Ney, P.E. Branching processes. Springer, Berlin, 1972.

[5] Billingsley, P. Convergence of Probability Measures. Wiley, New York, 1968.

[6] Bubley, R. and Dyer, M. Path coupling: A technique for proving rapid mixing in Markov chains. Proc. 38th Annual IEEE Symp. on Foundations of Computer Science 223–231, 1997.

[7] Coffman, E.J, Lueker, G.S., Spencer, J. and Winkler, P. Packing random rectangles. Probability Theory and Related Fields (to appear).

[8] Diaconis, P. and Saloff-Coste, L. Comparison theorems for reversible Markov chains. Ann. Appl. Probability 3:696–730, 1993.

[9] Dyer, M. and Greenhill, C. A more rapidly mixing Markov chain for graph colorings. Random Structures and Algorithms 13:285–317, 1998.

[10] Lagarias, J., Spencer, J. and Vinson, J. Dyadic Equipartitions of the Unit Square. Discrete Mathematics (to appear).

[11] Luby, M., Randall, D. and Sinclair, A. Markov chain algorithms for planar lattice structures. Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS ’95) 150–159, 1995.

[12] Propp, J. and Wilson, D. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms 9:223–252, 1996.

[13] Randall, D. and Tetali, P. Analyzing Glauber dynamics by comparison of Markov chains. J. Mathematical Physics 41:1598–1615, 2000.

Svante Janson, Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden

E-mail address: svante@math.uu.se
Web address: http://www.math.uu.se/~svante/

Dana Randall, College of Computing, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA

E-mail address: randall@math.gatech.edu
Web address: http://www.math.gatech.edu/~randall/

Joel Spencer, Courant Institute, 251 Mercer St., New York, NY 10012, USA

E-mail address: spencer@cs.nyu.edu
Web address: http://www.cs.nyu.edu/cs/faculty/spencer/