{'fraction_non_alphanumeric': 0.05651031571693156, 'fraction_numerical': 0.018219408192272902, 'mean_word_length': 3.444926611359285, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 100, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
V-Variable Fractals: Fractals with Partial Self Similarity

We establish properties of a new type of fractal which has partial self similarity at all scales. For any collection of iterated functions systems with an associated probability distribution and any positive integer V there is a corresponding class of V-variable fractal sets or measures. These V-variable fractals can be obtained from the points on the attractor of a single deterministic iterated function system. Existence, uniqueness and approximation results are established under average contractive assumptions. We also obtain extensions of some basic results concerning iterated function systems.


Introduction
A V -variable fractal is loosely characterised by the fact that it possesses at most V distinct local patterns at each level of magnification, where the class of patterns depends on the level, see Remark 5.2. Such fractals are useful for modelling purposes and for geometric applications which require random fractals with a controlled degree of strict self similarity at each scale, see [Bar06,Chapter 5].
Standard fractal sets or measures determined by a single iterated function system [IFS] F acting on a metric space X such as R k , can be generated directly by a deterministic process, or alternatively by a Markov chain or "chaos game", acting on X. Now let F be a family of IFSs acting on X together with an associated probability distribution on F . Let V be any positive integer. The corresponding class of V -variable fractal sets or measures from X, and its associated probability distribution, can be generated by a Markov chain or "chaos game" operating not on the state space X but on the state space C(X) V or M(X) V of V -tuples of compact subsets of X or probability measures over X, respectively. See Theorems 6.4 and 6.6, and see Section 8 for a simple example. The Markov chain converges exponentially, and approximations to its steady state attractor can readily be obtained. The projection of the attractor in any of the V coordinate directions gives the class of V -variable fractal sets or measures corresponding to F together with its natural probability distribution in each case. The full attractor contains further information about the correlation structure of subclasses of these V -variable fractals.
The case V = 1 corresponds to homogeneous random fractals. The limit V → ∞ gives standard random fractals, and for this reason the Markov chain for large V provides a fast way of generating classes of standard random fractals together with their probability distributions. Ordinary fractals generated by a single IFS can be seen as special cases of the present construction and this provides new insight into the structure of such fractals, see Remark 9.4. For the connection with other classes of fractals in the literature see Remarks 5.22 and 6.9. We summarise the main notation and results. Let (X, d) be a complete separable metric space. Typically this will be Euclidean space R k with the standard metric. For each λ in some index set Λ let F λ be an IFS acting on (X, d), i.e.  We will require both the cases where Λ is finite and where Λ is infinite. In order to simplify the exposition we assume that there is only a finite number M of functions in each F λ and that M does not depend on λ. Let P be a probability distribution on some σ-algebra of subsets of Λ. The given data is then denoted by Let V be a fixed positive integer.
Suppose first that the family Λ is finite and the functions f λ m are uniformly contractive. The set K V of V -variable fractal subsets of X and the set M V of V -variable fractal measures on X associated to F is then given by Definition 5.1. There are Markov chains acting on the set C(X) V of V -tuples of compact subsets of X and on the set M c (X) V of V -tuples of compactly supported unit mass measures on X, whose stationary distributions project in any of the V coordinate directions to probability distributions K V on K V and M V on M V , respectively. Moreover, these Markov chains are each given by a single deterministic IFS F C V or F Mc V constructed from F and acting on C(X) V or M c (X) V respectively. The IFS's F C V and F Mc V are called superIFS 's. The sets K V and M V , and the probability distributions K V and M V , are called superfractals. See Theorem 6.4; some of these results were first obtained in [BHS05]. The distributions K V and M V have a complicated correlation structure and differ markedly from other notions of random fractal in the literature. See Remarks 5.22 and 9.1. In many situations one needs an infinite family Λ or needs average contractive conditions, see Example 6.8. In this case one works with the set M 1 (X) V of V -tuples of finite first moment unit mass measures on X. The corresponding superIFS F M1 V is pointwise average contractive by Theorem 6.6 and one obtains the existence of a corresponding superfractal distribution M V . There are technical difficulties in establishing these results, see Remarks 3.5, 3.6 and 6.7.
In Section 2 the properties of the the Monge-Kantorovitch and the strong Prokhorov probability metrics are summarised. The strong Prokhorov metric is not widely known in the fractal literature although it is the natural metric to use with uniformly contractive conditions. We include the mass transportation, or equivalently the probabilistic, versions of these metrics, as we need them in Theorems 3.2, 6.4, 6.6 and 7.1. We work with probability metrics on spaces of measures and such metrics are not always separable. So in Section 2 the extensions required to include non separable spaces are noted.
In Section 3, particularly Theorem 3.2 and the following Remarks, we summarise and in some cases extend basic results in the literature concerning IFS's, link the measure theoretic and probabilistic approaches and sketch the proofs. In particular, IFS's with a possibly infinite family of functions and pointwise average contractive conditions are considered. The law of large numbers for the corresponding Markov process starting from an arbitrary point, also known as the convergence theorem for the "chaos game" algorithm, is extended to the case when the IFS acts on a non locally compact state space. This situation typically occurs when the state space is a function space or space of measures, and here it is required for the superIFS F M1 V in Theorem 6.6. The strong Prokhorov metric is used in the case of uniform contractions. We hope Theorem 3.2 will be of independent use.
In Section 4 we summarise some of the basic properties of standard random fractals generated by a family of IFS's.
In Section 5 the representation of V -variable fractals in the space Ω V of tree codes and in the space A ∞ V of addresses is developed, and the connection between the two spaces is discussed. The space Ω V is of the type used for realisations of general random fractals and consists of trees with each node labelled in effect by an IFS, see the comment following Definition 4.1 and see Definition 5.1. The space A ∞ V is of the type used to address points on a single deterministic fractal, and here consists of infinite sequences of V × (M + 1) matrices each of which defines a map from the set of V -tuples of sets or measures to itself, see Definition 5.13. Also see Figures 2 and 4.
In Section 6 the existence, uniqueness and convergence results for V -variable fractals and superfractals are proved, some examples are given, and the connection with graph directed IFSs is discussed. In Section 7 we establish the rate at which the probability distributions K V and M V converge to the corresponding distributions on standard random fractal sets and measures respectively as V → ∞. In Section 8 a simple example of a super IFS and the associated Markov chain is given.
In Section 9 we make some concluding remarks including the relationship with other types of fractals, extensions of the results, and some motivation for the method of construction of V -variable fractals.
The reader may find it easier to begin with Section 4 and refer back to Sections 2 and 3 as needed, particularly in the proofs of Theorems 6.4 and 6.6. An index of notation is provided at the end of the paper.
This work was partially supported by the Australian Research Council and carried out at the Australian National University.

Preliminaries
Throughout the paper (X, d) denotes a complete separable metric space, except where mentioned otherwise.
Definition 2.1. The collection of nonempty compact subsets of X with the Hausdorff metric is denoted by (C(X), d H ). The collection of nonempty bounded closed subsets of X with the Hausdorff metric is denoted by (BC(X), d H ). For Both spaces (C(X), d H ) and (BC(X), d H ) are complete and separable if (X, d) is complete and separable. Both spaces are complete if (X, d) is just assumed to be complete.
Definition 2.2 (Prokhorov metric). The collection of unit mass Borel (i.e. probability) measures on the Borel subsets of X with the topology of weak convergence is denoted by M(X). Weak convergence of ν n → ν means φ dν n → φ dν for all bounded continuous φ. The (standard) Prokhorov metric ρ on M(X) is defined by The Prokhorov metric ρ is complete and separable and induces the topology of weak convergence. Moreover, ρ is complete if (X, d) is just assumed to be complete. See [Bil99,pp 72,73]. We will not use the Prokhorov metric but mention it for comparison with the strong Prokhorov metric in Definition 2.4.
The Dirac measure δ a concentrated at a is defined by δ a (E) = 1 if a ∈ E and otherwise δ a (E) = 0.
If f : X → X or f : X → R, the Lipschitz constant for f is denoted by Lip f and is defined to be the least L such that d(f (x), f (y)) ≤ Ld(x, y) for all x, y ∈ X.
Definition 2.3 (Monge-Kantorovitch metric). The collection of those µ ∈ M(X) with finite first moment, i.e. those µ such that for some and hence any a ∈ X, is denoted by M 1 (X). The Monge-Kantorovitch metric d M K on M 1 (X) is defined in any of the three following equivalent ways: The maps π 1 , π 2 : X × X → X are the projections onto the first and second coordinates, and so µ and µ are the marginals for γ. In the third version the infimum is taken over X-valued random variables W and W with distribution µ and µ respectively but otherwise unspecified joint distribution.
Here and elsewhere, "dist" denotes the probability distribution on the associated random variable.
The metric space (M 1 (X), d M K ) is complete and separable. The moment restriction (2.1) is automatically satisfied if (X, d) is bounded. The second equality in (2.2) requires proof, see [Dud02,§11.8], but the third form of the definition is just a rewording of the second. The connection between d M K convergence in M 1 (X) and weak convergence is given by for some and hence any a ∈ X. See [Vil03, Section 7.2]. Suppose (X, d) is only assumed to be complete. If measures µ in M 1 (X) are also required to satisfy the condition µ(X \ spt µ) = 0, then (M 1 (X), d M K ) is complete, see [Kra06] and [Fed69,§2.1.16]. This condition is satisfied for all finite Borel measures µ if X has a dense subset whose cardinality is an Ulam number, and in particular if (X, d) is separable. The requirement that the cardinality of X be an Ulam number is not very restrictive, see [Fed69,§2.2.16].
It is often more natural to use the following strong Prokhorov metric rather than the Monge-Kantorovich or standard Prokhorov metrics in the case of a uniformly contractive IFS.
Definition 2.4 (Strong Prokhorov metric). The set of compact support, or bounded support, unit mass Borel measures on X is denoted by M c (X) or M b (X), respectively.
The strong Prokhorov metric d P is defined on M b (X) in any of the following equivalent ways: where the notation is as in the paragraph following (2.2).
Note that M c (X) ⊂ M b (X) ⊂ M 1 (X) ⊂ M(X). The first definition in (2.3) is symmetric in µ and µ by a standard argument, see [Dud02, proof of Theorem 11.3.1]. For discussion and proof of the second equality see [Rac91, p160 eqn(7.4.15)] and the other references mentioned there. The third version is a probabilistic reformulation of the second.
In particular, ν k → ν in the d P metric implies ν k → ν in the d M K metric and spt ν k → spt ν in the d H metric.
Proof. The first inequality follows directly from the definition of the Hausdorff metric and the second from the final characterisations in (2.2) and (2.3).
Completeness of M b (X) can be shown as follows and this argument carries across to M c (X).
It follows that (ν k ) k≥1 is d M K -Cauchy and hence converges to some measure ν in the d M K sense and in particular weakly. Moreover, spt (ν k ) k≥1 converges to some bounded closed set K in the Hausdorff sense, hence spt ν ⊂ K using weak convergence, and so ν ∈ M b (X). Suppose > 0 and using the fact If (X, d) is only assumed to be complete, but measures in M c (X) and M b (X) are also required to satisfy the condition µ(X \ spt µ) = 0 as discussed following Definition 2.3, then the same proof shows that Proposition 2.5 is still valid. The main point is that one still has completeness of (M 1 (X), d M K ).
Remark 2.6 (The strong and the standard Prokhorov metrics). Convergence in the strong Prokhorov metric is a much stronger requirement than convergence in the standard Prokhorov metric or the Monge-Kantorovitch metric. A simple example is given by X = [0, 1] and ν n = (1 − 1 n )δ 0 + 1 n δ 1 . Then ν n → δ 0 weakly and in the d M K and ρ metrics, but d P (ν n , δ 0 ) = 1 for all n.
If f : X → X is Borel measurable then the pushforward measure f (ν) is defined by f (ν)(A) = ν(f −1 (A)) for Borel sets A. The scaling property for Lipschitz functions f , namely follows from the definition of d P . Similar properties are well known and easily established for the Hausdorff and Monge-Kantorovitch metrics.

Iterated Function Systems
Definition 3.1. An iterated functions system [IFS] F = (X, f θ , θ ∈ Θ, W ) is a set of maps f θ : X → X for θ ∈ Θ, where (X, d) is a complete separable metric space and W is a probability measure on some σ-algebra of subsets of Θ. The map (x, θ) → f θ (x) : X × Θ → X is measurable with respect to the product σ-algebra on X × Θ, using the Borel σ-algebra on X. If Θ = {1, . . . , M } is finite and W (m) = w m then one writes F = (X, f 1 , . . . , f M , w 1 , . . . , w M ).
It follows f is measurable in θ for fixed x and in x for fixed θ. Notation such as E θ is used to denote taking the expectation, i.e. integrating, over the variable θ with respect to W .
Sometimes we will need to work with an IFS on a nonseparable metric space. The properties which still hold in this case will be noted explicitly. See Remark 3.6 and Theorem 6.4.
The IFS F acts on subsets of X and Borel measures over X, for finite and infinite Θ respectively, by We put aside measurability matters and interpret the integral formally as the measure which operates on any Borel set A ⊂ X to give dW (θ) (f θ (ν))(A). The latter is thought of as a weighted sum via W (θ) of the measures f θ (ν). The precise definition in the cases we need for infinite Θ is given by (3.3).
If F (E) = E or F (ν) = ν then E or ν respectively is said to be invariant under the IFS F .
In the study of fractal geometry one is usually interested in the case of an IFS with a finite family Θ of maps. If X = R 2 then compact subsets of X are often identified with black and white images, while measures are identified with greyscale images. Images are generated by iterating the map F to approximate lim k→∞ F k (E 0 ) or lim k→∞ F k (ν 0 ). As seen in the following theorem, under natural conditions the limits exist and are independent of the starting set E 0 or measure ν 0 .
In the study of Markov chains on an arbitrary state space X via iterations of random functions on X, it is usually more natural to consider the case of an infinite family Θ. One is concerned with a random process Z x n , in fact a Markov chain, with initial state x ∈ X, and (3.2) where the i n ∈ Θ are independently and identically distributed [iid] with probability distribution W and i = i 1 i 2 . . . . The induced probability measure on the set of codes i is also denoted by W .
Note that the probability P (x, B) of going from x ∈ X into B ⊂ X in one iteration is W {θ : f θ (x) ∈ B}, and P (x, ·) = dist Z x 1 . More generally, if the starting state is given by a random variable X 0 independent of i with dist X 0 = ν, then one defines the random variable Z ν n (i) = Z X0 n (i). The sequence Z ν n (i) n≥0 forms a Markov chain starting according to ν. We define F (ν) = dist Z ν 1 and in summary we have The operator F can be applied to bounded continuous functions φ : X → R via any of the following equivalent definitions: In the context of Markov chains, the operator F acting on functions is called the transfer operator. It follows from the definitions that F (φ) dµ = φ d(F µ), which is the expected value of φ after one time step starting with the initial distribution µ. If one assumes F (φ) is continuous (it is automatically bounded) then F acting on measures is the adjoint of F acting on bounded continuous functions. Such F are said to satisfy the weak Feller property -this is the case if all f θ are continuous by the dominated convergence theorem, or if the pointwise average contractive condition is satisfied, see [Ste01]. We will need to apply the maps in (3.2) in the reverse order. Define Then from the iid property of the i n it follows . However, the pathwise behaviour of the processes Z x n and Z x n are very different. Under suitable conditions the former is ergodic and the latter is a.s. convergent, see Theorems 3.2.c and 3.2.a respectively, and the discussion in [DF99].
The following Theorem 3.2 is known with perhaps two exceptions: the lack of a local compactness requirement in (c) and the use of the strong Prokhorov metric in (d).
The strong Prokhorov metric, first used in the setting of random fractals in [Fal86], is a more natural metric than the Monge-Kantorovitch metric when dealing with uniformly contractive maps and fractal measures in compact spaces. Either it or variants may be useful in image compression matters. In Theorem 6.4 we use it to strengthen the convergence results in [BHS05].
The pointwise ergodic theorems for Markov chains for any starting point as established in [Bre60,Elt87,BEH89,Elt90,MT93] require compactness or local compactness, see Remark 3.5. We remove this restriction in Theorem 3.2. The result is needed in Theorem 6.6 where we consider an IFS operating on the space (M 1 (X) V , d M K ) of V -tuples of probability measures. Like most spaces of functions or measures, this space is not locally compact even if X = R k . See Remark 3.5 and also Remark 6.8.
We assume a pointwise average contractive condition, see Remark 3.3. We need this in Theorem 6.6, see Remark 6.7.
The parts of the theorem have a long history. In the Markov chain literature the contraction conditions (3.7) and (3.13) were introduced in [Isa62] and [DF37] respectively in order to establish ergodicity. In the fractal geometry literature, following [Man77,Man82], the existence and uniqueness of attractors, their properties, and the Markov chain approach to generating fractals, were introduced in [Hut81, BD85,DS86,BE88,Elt87,Elt90]. See [Ste98,Ste01,DF99] for further developments and more on the history.
Theorem 3.2. Let F = (X, f θ , θ ∈ Θ, W ) be an IFS on a complete separable metric space (X, d). Suppose F satisfies the pointwise average contractive and average boundedness conditions for some fixed 0 < r < 1, all x, y ∈ X, and some a ∈ X.
a. For some function Π, all x, y ∈ X and all n, we have The map Π is called the address map from code space into X. Note that Π is defined only a.e.
If r < s < 1 then for all x, y ∈ X for a.e. i = i 1 i 2 . . . i n . . . there exists n 0 = n 0 (i, s) such that (3.9) d(Z x n (i), Z y n (i)) ≤ s n d(x, y), d( Z x n (i), Z y n (i)) ≤ s n d(x, y), d( Z x n (i), Π(i)) ≤ γ x s n , for n ≥ n 0 .
b. If ν is a unit mass Borel measure then F n (ν) → µ weakly where µ := Π(W ) is the projection of the measure W on code space onto X via Π. Equivalently, µ is the distribution of Π regarded as a random variable. In particular, F (µ) = µ and µ is the unique invariant unit mass measure. The map F is a contraction on (M 1 (X), d M K ) with Lipschitz constant r. Moreover, µ ∈ M 1 (X) and for every ν ∈ M 1 (X).
c. For all x ∈ X and for a.e. i, the empirical measure (probability distribution) weakly. Moreover, if A is the support of µ then there exists n 0 = n 0 (i, x, ) such that d. Suppose F satisfies the uniform contractive and uniform boundedness conditions (3.13) sup θ d(f θ (x), f θ (y)) ≤ rd(x, y) and L := sup θ d(f θ (a), a) < ∞ for some r < 1, all x, y ∈ X, and some a ∈ X. Then (3.14) d(Z x n (i), Z y n (i)) ≤ r n d(x, y), d( Z x n (i), Z y n (i)) ≤ r n d(x, y), d( Z x n (i), Π(i)) ≤ γ x r n , for all x, y ∈ X and all i. The address map Π is everywhere defined and is continuous with respect to the product topology defined on code space and induced from the discrete metric on Θ. Moreover, µ = Π(W ) ∈ M c and for any ν ∈ M b , Suppose in addition Θ is finite and W ({θ}) > 0 for θ ∈ Θ. Then A is compact and for any closed bounded E Moreover, F (A) = A and A is the unique closed bounded invariant set.
Next fix x. Since , Z a n−1 (i)) for all n, it follows that Z x n (i) and Z a n (i) a.s. converge exponentially fast to the same limit Π(i) (say) by the first inequality in (3.8). It also follows that (3.17) is simultaneously true with i replaced by i k+1 i k+2 i k+3 , . . . for every k. It then follows from (3.5) that Again using (3.5), This gives the second inequality in (3.8). See [Ste98] for details. The estimates in (3.9) are the standard consequence that exponential convergence in mean implies a.s. exponential convergence.
b. Suppose φ ∈ BC(X, d), the set of bounded continuous functions on X. Let ν be any unit mass measure. Since for a.e. i, Z x n (i) → Π(i) for every x, using the continuity of φ and dominated convergence, by the definition of µ for the last equality. Thus F n (ν) → µ weakly. The invariance of µ and the fact µ is the unique invariant unit measure follow from the weak Feller property. One can verify that F : M 1 (X) → M 1 (X) and F is a contraction map with Lipschitz constant r in the d M K metric. It is easiest to use the second or third form of (2.2) for this. The rest of (b) now follows.
c. The main difficulty here is that (X, d) may not be locally compact and so the space BC(X, d) need not be separable, see Remark 3.5. We adapt an idea of Varadhan, see [Dud02, p399, Thm 11.4.1].
There is a totally bounded and hence separable, but not usually complete, metric e on X such that (X, e) and (X, d) have the same topology, see [Dud02, p72, Thm 2.8.2]. Moreover, as the proof there shows, e(x, y) ≤ d(x, y). Because the topology is preserved, weak convergence of measures on (X, d) is the same as weak convergence on (X, e).
Let BL(X, e) denote the set of bounded Lipschitz functions over (X, e). Then BL(X, e) is separable in the sup norm from the total boundedness of e.
Suppose φ ∈ BL(X, e). By the ergodic theorem, since µ is the unique invariant measure for F , for a.e. i and µ a.e. y. Suppose x ∈ X and choose y ∈ X such that (3.18) is true. Using (a), for a.e. i e(Z x n (i), Z y n (i)) ≤ d(Z x n (i), Z y n (i)) → 0. It follows from (3.18) and the uniform continuity of φ in the e metric that for a.e. i, Let S be a countable dense subset of BL(X, e) in the sup norm. One can ensure that (3.19) is simultaneously true for all φ ∈ S. By an approximation argument it follows (3.19) is simultaneously true for all φ ∈ BL(X, e).
Since (X, e) is separable, weak convergence of measures ν n → ν is equivalent to φ dν n → φ dν for all φ ∈ BL(X, e), see [Dud02, Thm 11.3.3, p395]. Completeness is not needed for this. It follows that µ x n (i) → µ weakly as required. The result (3.12) follows from the third inequality in (3.9).
d. The three inequalities in (3.14) are straightforward as are the claims concerning Π.
It follows readily from the definitions that each of M c (X), M b (X), C(X) and BC(X) are closed under F , and that F is a contraction map with respect to d P in the first two cases and d H in the second two cases. The remaining results all follow easily.
Remark 3.3 (Contractivity conditions). The pointwise average contractive condition is implied by the global average contractive condition E θ r θ := r θ dW (θ) ≤ r, where r θ := Lip f θ . Although the global condition is frequently assumed, for our purposes the weaker pointwise assumption is necessary, see Remark 6.7.
In some papers, for example [DF99,WW00], parts of Theorem 3.2 are established or used under the global log average contractive and average boundedness conditions for some q > 0 and some a ∈ X. However, since d q is a metric for 0 < q < 1 and since (E θ g q (θ)) 1/q ↓ exp (E θ log g(θ)) as q ↓ 0 for g ≥ 0, such results follow from Theorem 3.2. In the main Theorem 5.2 of [DF99] the last two conditions are replaced by the equivalent algebraic tail condition.
One can even obtain in this way similar consequences under the yet weaker pointwise log average conditions. See also [Elt87].
Pointwise average contractivity is a much weaker requirement than global average contractivity. A simple example in which f θ is discontinuous with positive probability is given by 0 < < 1, for all x and y. The unique invariant measure is of course 1 2 δ 0 + 1 2 δ 1 . Uniqueness fails if = 0. A simple example where f θ is discontinuous with probability one is f θ = X {1} and θ is chosen uniformly on the unit interval. See [Ste98,Ste01] for further examples and discussion.
Remark 3.4 (Alternative starting configurations). One can extend (3.8) by allowing the starting point x to be distributed according to a distribution ν and considering the corresponding random variables Z ν n (i). Then (3.10) follows directly by using the random variables Z ν n (i) and Z µ n (i) in the third form of (2.2).
Analogous remarks apply in deducing the distributional convergence results in Theorem 3.2.d from the pointwise convergence results, via the third form of (2.3).
Remark 3.5 (Local compactness issues). Versions of Theorem 3.2.c for locally compact (X, d) were established in [Bre60,Elt87,BEH89,Elt90,MT93]. In that case one first proves vague convergence in (3.11). By ν n → ν vaguely one means φdν n → φdν for all φ ∈ C c (X) where C c (X) is the set of compactly supported continuous functions φ : X → R. The proof of vague convergence is straightforward from the ergodic theorem since C c (X) is separable. Moreover, in a locally compact space, vague convergence of probability measures to a probability measure implies weak convergence. That this is not true for more general spaces is a consequence of the following discussion.
The extension of Theorem 3.2.c to non locally compact spaces is needed in Section 6 and Theorem 6.6. In order to study images in R k we consider IFS's whose component functions act on the space (M 1 (R k ) V , d M K ) of V -tuples of unit mass measures over R k , where V is a natural number. Difficulties already arise in proving that the chaos game converges a.s. from every initial V -tuple of sets even for V = k = 1.
On the other hand, let W be a random measure with dist W = ν 0 . Independently of the value of W let W = W with probability 1 − n and W = τ n W with probability n . Then again from (2.2), It follows that ν n ∈ B (ν 0 ) and ν n ν in the d M K metric, nor does any subsequence. Since d M K implies weak convergence it follows that (ν n ) n≥1 has no convergent subsequence in the d M K metric.
It follows that C c (M 1 (R), d M K ) contains only the zero function. Hence vague convergence in this setting is a vacuous notion and gives no information about weak convergence.
Finally, we note that although (c) is proved here assuming the pointwise average contractive condition, it is clear that weaker hypotheses concerning the stability of trajectories will suffice to extend known results from the locally compact setting.
Remark 3.6 (Separability and measurability issues). If (X, d) is separable then the class of Borel sets for the product topology on X × X is the product σ-algebra of the class of Borel sets on X with itself, see [Bil99,p 244]. It follows that θ → d(f θ (x), f θ (y)) is measurable for each x, y ∈ X and so the quantities in (3.7) are well defined.
Separability is not required for the uniform contractive and uniform boundedness conditions in (3.13) and the conclusions in (d) are still valid with essentially the same proofs. The spaces M c (X), M b (X) and M 1 (X) need to be restricted to separable measures as discussed following Definition (2.3) and Proposition 2.5.
Separability is also used in the proof of (c). If one drops this condition and assumes the uniform contractive and boundedness conditions (3.13) then a weaker version of (c) holds. Namely, for every x ∈ X and every bounded continuous φ ∈ BC(X), for a.e. i The point is that unlike the situation in (c) under the hypothesis of separability, the set of such i might depend on the function φ.
In Theorem 6.4 we apply Theorem 3.2 to an IFS whose component functions operate on where V is a natural number. Even in the case V = 1 this space is not separable, see Example 2.6.

Tree Codes and Standard Random Fractals
Let F = {X, F λ , λ ∈ Λ, P } be a family of IFSs as in (1.1) and (1.2). We assume the IFSs F λ are uniformly contractive and uniformly bounded, i.e. for some 0 < r < 1, , a) < ∞ for all x, y ∈ X and some a ∈ X. More general conditions are assumed in Section 6.
We often use * to indicate concatenation of sequences, either finite or infinite. A tree code ω is a map ω : T → Λ. The metric space (Ω, d) of all tree codes is defined by If ω ∈ Ω and τ ∈ T then the tree code ω τ is defined by (ω τ ) (σ) := ω(τ * σ). It is the tree code obtained from ω by starting at the node τ . One similarly defines ω τ if ω is a finite tree code of height k and |τ | ≤ k.
If ω ∈ Ω and k is a natural number then the finite tree code ω k defined by (ω k)(σ) = ω(σ) for |σ| ≤ k. It is obtained by truncating ω at the level k.
The space (Ω, d) is complete and bounded. If Λ is finite then (Ω, d) is compact. The tree code ω associates to each node σ ∈ T the IFS F ω(σ) . It also associates to each σ = ∅ the function f 3) are then obtained by beginning with the set K 0 and iteratively applying the functions associated to the k nodes along each of the M k branches of depth k obtained from ω. A similar remark applies to µ ω k . Definition 4.2 (Fractal sets and measures). If K 0 ∈ C(X) and µ 0 ∈ M c (X) then the prefractal sets K ω k , the prefractal measures µ ω k , the fractal set K ω and the fractal measure µ ω , are given by It follows from uniform contractivity that for all ω one has convergence in the Hausdorff and strong Prokhorov metrics respectively, and that K ω and µ ω are independent of K 0 and µ 0 . The collections of all such fractals sets and measures for fixed {F λ } λ∈Λ are denoted by For each k one has (4.5) The M k sets K ω σ are called the subfractals of K ω at level k.
The maps ω → K ω and ω → µ ω are Hölder continuous. More precisely: Proposition 4.3. With L and r as in (4.1), Proof. Applying (4.3) with K 0 replaced by {a}, and using (4.1) and repeated applications of the triangle inequality, it follows that d H (K ω , a) ≤ (1 + r + r 2 + · · · )L = L/(1 − r) and so , it follows from (4.5) and contractivity that , the result for sets follows. The proof for measures is essentially identical; one replaces µ 0 by δ a in (4.3).

Figure 2. Random Sierpinski triangles and tree codes
Example 4.4 (Random Sierpinski triangles and tree codes). The relation between a tree code ω and the corresponding fractal set K ω can readily be seen in Figure 2. The IFSs F = (f 1 , f 2 , f 3 ) and G = (g 1 , g 2 , g 3 ) act on R 2 , and the f m and g m are similitudes with contraction ratios 1/2 and 1/3 respectively and fixed point m. If a node is labelled F , then reading from left to right the three main branches of the subtree associated with that node correspond to f 1 , f 2 , f 3 respectively. Similar remarks apply if the node is labelled G.
If the three functions in F and the three functions in G each are given weights equal to 1/3 then the measure µ ω is distributed over K ω in such a way that 1/3 of the mass is in each of the top level triangles, 1/9 in each of the next level triangles, etc.
The sets K ω and measures µ ω in Definition 4.2 are not normally self similar in any natural sense. However, there is an associated notion of statistical self similarity. For this we need the following definition. The reason for the notation ρ ∞ in the following definition can be seen from Theorem 7.1.
Definition 4.5 (Standard random fractals). The probability distribution ρ ∞ on Ω is defined by choosing ω(σ) ∈ Λ for each σ ∈ T in an iid manner according to P . The random set K = ω → K ω and the random measure M = ω → µ ω , each defined by choosing ω ∈ Ω according to ρ ∞ , are called standard random fractals.
The induced probability distributions on K ∞ and M ∞ respectively are defined by K ∞ = dist K and M ∞ = dist M.
It follows from the definitions that K and M are statistically self similar in the sense that where F is a random IFS chosen from (F λ ) λ∈Λ according to P , K 1 , . . . , K M are iid copies of K which are independent of F , and M 1 , . . . , M M are iid copies of M which are independent of F. Here, and in the following sections, an IFS F acts on M -tuples of subsets K 1 , . . . , K M of X and measures µ 1 , . . . , µ M over X by This extends in a pointwise manner to random IFSs acting on random sets and random measures as in (4.7). We use the terminology "standard" to distinguish the class of random fractals given by Definition 4.5 and discussed in ([Fal86, MW86, Gra87, HR98, HR00]) from other classes of random fractals in the literature.

V -Variable Tree Codes
5.1. Overview. We continue with the assumptions that F = {X, F λ , λ ∈ Λ, P } is a family of IFSs as in (1.1) and (1.2), and that {F λ } λ∈Λ satisfies the uniform contractive and uniform bounded conditions (4.1). In Theorem 6.6 and Example 6.8 the uniformity conditions are replaced by pointwise average conditions. In Section 5.2, Definition 5.1, we define the set Ω V ⊂ Ω of V -variable tree codes, where Ω is the set of tree codes in Definition 4.1. Since the {F λ } λ∈Λ are uniformly contractive this leads directly to the class K V of V -variable fractal sets and the class M V of V -variable fractal measures.
In Section 5.5 the probability distribution ρ V on the set Ω V of V -variable tree codes is defined and discussed. The probability P on Λ first leads to a natural probability P V on the index set A V for the IFS Φ V , see Definition 5.18. This then turns Φ V into an IFS (Ω V , Φ a , a ∈ A V , P V ) with weights whose measure attractor ρ * V is a probability distribution on its set attractor Ω * V . The projection of ρ * V in any coordinate direction is the same, is supported on Ω V and is denoted by ρ V , see Theorem 5.21.

V -Variability.
Definition 5.1 (V -variable tree codes and fractals). A tree code ω ∈ Ω is V -variable if for each positive integer k there are at most V distinct tree codes of the form ω τ with |τ | = k. The set of V -variable tree codes is denoted by Ω V .
Similarly a finite tree code ω of height p is V -variable if for each k < p there are at most V distinct finite subtree codes ω τ with |τ | = k.
For a uniformly contractive family {F λ } λ∈Λ of IFSs, if ω is V -variable then the fractal set K ω and fractal measure µ ω in (4.3) are said to be V -variable. The collections of all V -variable sets and measures corresponding to {F λ } λ∈Λ are denoted by respectively, c.f. (4.4).
If V = 1 then ω is V -variable if and only if |σ| = |σ | implies ω(σ) = ω(σ ), i.e. if and only if for each k all values of ω(σ) at level k are equal. In the case V > 1, if ω is V -variable then for each k there are at most V distinct values of ω(σ) at level k = |σ|, but this is not sufficient to imply V -variability.
Remark 5.2 (V -variable terminology). The motivation for the terminology "V -variable fractal" is as follows. Suppose all functions f λ m belong to the same group G of transformations. For example, if X = R n then G might be the group of invertible similitudes, invertible affine transformations or invertible projective transformations. Two sets A and B are said to be equivalent modulo G if A = g(B) for some g ∈ G. If K ω is V -variable and k is a positive integer, then there are at most V distinct trees of the form ω σ such that |σ| = k. If |σ| = |σ | = k and ω σ = ω σ , then from (4.5) In particular, K ω σ and K ω σ are equivalent modulo G. Thus the subfractals of K ω at level k form at most V distinct equivalence classes modulo G. However, the actual equivalence classes depend upon the level.
Similar remarks apply to V -variable fractal measures.
Proposition 5.3. A tree code ω is V -variable iff for every positive integer k the finite tree codes ω k are V -variable.
Proof. If ω is V -variable the same is true for every finite tree code of the form ω k.
If ω is not V -variable then for some k there are at least V + 1 distinct subtree codes ω τ with |τ | = k. But then for some p the V + 1 corresponding finite tree codes (ω τ ) p must also be distinct. It follows ω (k + p) is not V -variable.
Example 5.4 (V -variable Sierpinski triangles). The first tree code in Figure 2 is an initial segment of a 3-variable tree code but not of a 2-variable tree code, while the second tree is an initial segment of a 2-variable tree code but not of a 1-variable tree code. The corresponding Sierpinski type triangles are, to the level of approximation shown, 3-variable and 2-variable respectively.
Theorem 5.5. The Ω V are closed and nowhere dense in Ω, and where the bar denotes closure in the metric d.

5.
3. An IFS Acting on V -Tuples of Tree Codes.
Definition 5.6. The metric space (Ω V , d) is the set of V -tuples from Ω with the metric where d on the right side is as in Definition 4.1.
This is a complete bounded metric and is compact if Λ is finite since the same its true for V = 1. See Definition 4.1 and the comment which follows it. The induced Hausdorff metric on BC(Ω V ) is complete and bounded, and is compact if Λ is finite. See the comments following Definition 2.1.
The notion of V -variability extends to V -tuples of tree codes, V -tuples of sets and V -tuples of measures.
where K ωv and µ ωv are as in Definition 4.2.

V
(Ω V ) V note that a V -tuple of V -variable tree codes need not itself be V -variable.
Similar notation applies if the ω 1 , . . . , ω M are finite tree codes all of the same height.
We define maps on V -tuples of tree codes and a corresponding IFS on Ω V as follows. For a ∈ A V the map Φ a : Ω V → Ω V is defined for ω = (ω 1 , . . . , ω V ) by ,1) , . . . , ω J a (v,M ) ). Thus Φ a v (ω) is the tree code with base node I a (v), and at the end of each of its M base branches are attached copies of ω J a (v,1) , . . . , ω J a (v,M ) respectively.
The IFS Φ V acting on V -tuples of tree codes and without a probability distribution at this stage is defined by Note that Φ a : Ω * V → Ω * V for each a ∈ A V . Notation 5.11. It is often convenient to write a = (I a , J a ) ∈ A V in the form  Proof. It is readily checked that each Φ a is a contraction map with Lipschitz constant 1/M . We can establish directly that Φ V (E) := a∈A V Φ a (E) is closed if E is closed, since any Cauchy sequence from Φ V (E) eventually belongs to Φ a (E) for some fixed a. It follows that Φ V is a contraction map on the complete space (BC(Ω V ), d H ) with Lipschitz constant 1/M and so has a unique bounded closed fixed point (i.e. attractor).
In order to show this attractor is the set Ω * V from Definition 5.7, note that Ω * V is bounded and closed in Ω V . It is closed under Φ a for any a ∈ A V as noted before. Moreover, each ω ∈ Ω * V is of the form Φ a (ω ) for some ω ∈ Ω * V and some (in fact many) Φ a . To see this, consider the V M tree codes of the form ω v m for 1 ≤ v ≤ V and 1 ≤ m ≤ M , where each m is the corresponding node of T of height one. There are at most V distinct such tree codes, which we denote by ω 1 , . . . , ω V , possibly with repetitions. Then from (5.3) So Ω * V is invariant under Φ V and hence is the unique attractor of the IFS Φ V . In the previous theorem, although Φ V is an IFS, neither Theorem 3.2 nor the extensions in Remark 3.6 apply directly. If Λ is not finite then Ω V is neither separable nor compact. Moreover, the map Φ V acts on sets by taking infinite unions and so we cannot apply Theorem (3.2).d to find a set attractor for Φ V , since in general the union of an infinite number of closed sets need not be closed.
As a consequence of the theorem, approximations to V -variable V -tuples of tree codes, and in particular to individual V -variable tree codes, can be built up from a V -tuple τ of finite tree codes of height 0 such as τ = (λ * , . . . , λ * ) for some λ * ∈ Λ, and a finite sequence a 0 , a 2 , . . . , a k ∈ A V , by computing the height k finite tree code Φ a0 • · · · • Φ a k (τ ). Here we use the natural analogue of (5.3) for finite tree codes. See also the diagrams in [BHS05, Figures 19,20].

Constructing Tree Codes from Addresses and Conversely.
Definition 5.13 (Addresses for V -variable V -tuples of tree codes). For each sequence a = a 0 a 1 . . . a k . . . with a k ∈ A V and Φ a k as in (5.3), define the corresponding V -tuple ω a of tree codes by (5.6) ω a = (ω a 1 , . . . , ω a V ) := lim for any initial (ω 0 1 , . . . , ω 0 V ) ∈ Ω V . The sequence a is called an address for the V -variable V -tuple of tree codes ω a . The set of all such addresses a is denoted by A ∞ V . Note that the tree code Φ a0 • Φ a1 • · · · • Φ a k (ω 0 1 , . . . , ω 0 V ) is independent of (ω 0 1 , . . . , ω 0 V ) ∈ Ω V up to and including level k, and hence agrees with ω a for these levels.
The sequence in (5.6) converges exponentially fast since Lip Φ a k is ≤ 1/M . The map a → ω a : A ∞ V → Ω * V is many-to-one, since the composition of different Φ a s may give the same map even in simple situations as the following example shows.
Example 5.14 (Non uniqueness of addresses). The map a → ω a : A ∞ V → Ω * V is many-to-one, since the composition of different Φ a s may give the same map even in simple situations. For example, suppose Since M = 1 tree codes here are infinite sequences, i.e. 1-branching tree codes. One readily checks from (5.3) that Φ a (ω, ω ) = (F * ω, F * ω), Φ b (ω, ω ) = (F * ω, F * ω ), and so The following definition is best understood from Example 5.17.
The tree skeleton depends on the maps J a k (w, m), but not on the maps I a k (w, m) and hence not on the set {F λ } λ∈Λ of IFSs and its indexing set Λ.
The V -tuple of tree codes (ω a 1 , . . . , ω a V ) can be recovered from the address a = a 0 a 1 . . . a k . . . as follows.
Proposition 5.16 (Tree codes from addresses). If a = a 0 a 1 . . . a k . . . ∈ A ∞ V is an address, I a k and J a k are as in (5.5), and J a v is the tree skeleton corresponding to the J a k , then for each σ ∈ T and 1 ≤ v ≤ V , The proof is implicit in Example 5.17. A formal proof can be given by induction.  Example 5.17 (The Espalier 1 technique). We use this to find tree codes from addresses and addresses from tree codes.
We first show how to represent an address a = a 0 a 1 . . . a k . . . ∈ A ∞ V by means of a diagram as in Figure 3. From this we construct the V -variable V -tuple of tree codes (ω 1 , . . . , ω V ) ∈ Ω * V with address a.
Conversely, given a V -variable V -tuple of tree codes (ω 1 , . . . , ω V ) ∈ Ω * V we show how to find the set of all its possible addresses. Moreover, given a single tree code ω ∈ Ω V we find all possible (ω 1 , . . . , ω V ) ∈ Ω * V with ω 1 = ω and all possible addresses in this case. For the example here let Λ = {F, G} where F and G are symbols. Suppose M = 3 and V = 5. Suppose a = a 0 a 1 . . . a k . . . ∈ A ∞ V is an address of (ω 1 , . . . , ω V ) ∈ Ω * V , where (5.9) We will see that up to level 2 the tree codes ω 1 and ω 2 are those shown in Figure 2. Although ω 1 and ω 2 are 3-variable and 2-variable respectively up to level 2, it will follow from Figure 3 that they are 5-variable up to level 3 and are not 4-variable.
The diagram in Figure 3 is obtained from a = a 0 a 1 a 2 a 3 . . . by espaliering V copies of the tree T in Definition 4.1 up through an infinite lattice of V boxes at each level 0, 1, 2, 3, . . . . One tree grows out of each box at level 0, and one element from Λ is assigned to each box at each level. When two or more branches pass through the same box from below they inosculate, i.e. their sub branches merge and are indistinguishable from that point upwards. More precisely, a determines the diagram in the following manner. For each level k and starting from each box v at that level, a branch terminates in box number J a k (v, 1) at level k + 1, a branch terminates in box J a k (v, 2) at level k + 1 and a branch terminates in box J a k (v, 3) at level k + 1. The element I a k (v) ∈ Λ is assigned to box v at level k.
Conversely, any such diagram determines a unique address a = a 0 a 1 a 2 a 3 . . . . More precisely, consider an infinite lattice of V boxes at each level 0, 1, 2, 3, . . . . Suppose at each level k there is either F or G in each of the V boxes, and from each box there are 3 branches , and , each branch terminating in a box at level k + 1. From this information one can read off I a k (v) and J a k (v, m) for each k ≥ 0, 1 ≤ v ≤ V and 1 ≤ m ≤ M , and hence determine a.
The diagram, and hence the address a, determines the tree skeleton J a v by assigning to each node of the copy of T growing out of box v at level 0, the number of the particular box in which that node sits. If ω a = (ω 1 , . . . , ω V ) is the V -tuple of tree codes with address a then the tree code ω v is obtained by assigning to each node of the copy of T growing out of box v at level 0 the element (fruit?) from Λ in the particular box in which that node sits.
Conversely, suppose ω ∈ Ω V is a single V -variable tree code. Then the set of all possible ω ∈ Ω * V ⊂ Ω V of the form ω = (ω 1 , ω 2 , . . . , ω V ) with ω 1 = ω, and the set of all diagrams and corresponding addresses a ∈ A ∞ V for such ω, is found as follows. Espalier a copy of T up through the infinite lattice with V boxes at each level in such a way that if σ 0 . . . σ k and σ 0 . . . σ k sit in the same box at level k then the sub tree codes ω σ 0 . . . σ k and ω σ 0 . . . σ k are equal. Since ω is V -variable, this is always possible. From level k onwards the two sub trees are fused together.
The possible diagrams corresponding to this espaliered T are constructed as follows. For each σ ∈ T the element ω(σ) ∈ Λ is assigned to the box containing σ. By construction, this is the same element for any two σ's in the same box. The three branches of the diagram from this box up to the next level are given by the three sub branches of the espaliered T growing out of that box. If T does not pass through some box, then the F or G in that box, and the three branches of the diagram from that box to the next level up, can be assigned arbitrarily.
In this manner one obtains all possible diagrams for which the tree growing out of box 1 at level 0 is ω. Each diagram gives an address a ∈ A ∞ V as before, and the corresponding ω a = (ω 1 , . . . , ω V ) ∈ Ω * V with address a satisfies ω 1 = ω. In a similar manner, the set of possible diagrams and corresponding addresses can be obtained for any ω = (ω 1 , ω 2 , . . . , ω V ) ∈ Ω * V ⊂ Ω V . 5.5. The Probability Distribution on V -Variable Tree Codes. Corresponding to the probability distribution P on Λ in (1.2) there are natural probability distributions ρ V on Ω V , K V on K V and M V on M V . See Definition 5.1 for notation and for the following also note Definition 5.7.
Definition 5.18 (Probability distributions on addresses and tree codes). The probability distribution P V on A V , with notation as in (5.5), is defined by selecting a = (I, J) ∈ A V so that I(1), . . . , I(V ) ∈ Λ are iid with distribution P , so that J (1, 1) The probability distribution P ∞ V on A ∞ V , the set of addresses a = a 0 a 1 . . ., is defined by choosing the a k to be iid with distribution P V .
The probability distribution ρ * V on Ω * V is the image of P ∞ V under the map a → ω a in (5.6). The probability distribution ρ V on Ω V is the projection of ρ * V in any of the V coordinate directions. (By symmetry of the construction this is independent of choice of direction.) One obtains natural probability distributions on fractals sets and measures, and on V -tuples of fractal sets and measures as follows.
The probability distributions K * V and K V on K * V and K V respectively are those induced from ρ * V and ρ V by the maps (ω 1 , . . . , ω V ) → (K ω1 , . . . , K ω V ) and ω → K ω in Definitions 5.7 and 5.1. Similarly, the probability distributions M * V and M V on M * V and M V respectively are those induced from ρ * V and ρ V by the maps (ω 1 , . . . , ω V ) → (µ ω1 , . . . , µ ω V ) and ω → µ ω . That is, K * V , K V , M * V and M V are the probability distributions of the random objects (K ω1 , . . . , K ω V ), K ω , (µ ω1 , . . . , µ ω V ) and µ ω respectively, under the probability distributions ρ * V and ρ V on (ω 1 , . . . , ω V ) and ω. Since the projection of ρ * V in each coordinate direction is ρ V it follows that the projection of K * V in each coordinate direction is K V and the projection of M * V in each coordinate direction is M V . However, there is a high degree of dependence between the components and in general ρ * Definition 5.20 ((The IFS acting on the set of V -tuples of tree codes)). The IFS Φ V in (5.4) is extended to an IFS with probabilities by (5.10) Theorem 5.21. A unique measure attractor exists for Φ V and equals ρ * V . In particular, the projection of ρ * V in any coordinate direction is is an IFS and the R a are contractive with Lipschitz constant 1/2 under the metric d(a, b) = 2 −k , where k is the least integer such that a k = b k . Thus this IFS has a unique attractor which from Definition 5.18 is P ∞ V . Since each Φ a : Ω V → Ω V has Lipschitz constant 1/M from Theorem 5.12, it follows that Φ a has Lipschitz constant 1/M in the strong Prokhorov (and Monge-Kantorovitch) metric as a map on measures. It also follows that Φ V has a unique attractor from Theorem 5.12 and Remark 3.6.
Finally, if Π is the projection a → ω a : A ∞ V → Ω V in (5.6), it is immediate that Π•R a = Φ a •Π and hence the attractor of Φ V is Π(P ∞ V ) = ρ * V by Definition 5.18. The projection of ρ * V in any coordinate direction is ρ V from Definition 5.18.
Remark 5.22 (Connection with other types of random fractals). The probability distribution ρ V on Ω V is obtained by projection from the probability distribution P ∞ V on A ∞ V , which is constructed in a simple iid manner. However, because of the combinatorial nature of the manyto-one map the distribution ρ V is very difficult to analyse in terms of tree codes. In particular, under the distribution ρ V on Ω V and hence on Ω, the set of random IFSs ω → F ω(σ) for σ ∈ T has a complicated long range dependence structure. (See the comments following Definition 4.1 for the notation F ω(σ) .) For each V -variable tree code there are at most V isomorphism classes of subtree codes at each level, but the isomorphism classes are level dependent.
Moreover, each set of realisations of a V -variable random fractal, as well as its associated probability distribution, is the projection of the fractal attractor of a single deterministic IFS operating on V -tuples of sets or measures. See Theorems 6.4 and 6.6.
For these reasons ρ V , K V and M V are very different from other notions of a random fractal distribution in the literature. See also Remark 6.9.

Convergence and Existence Results for SuperIFSs
We continue with the assumption that F = {X, F λ , λ ∈ Λ, P } is a family of IFSs as in (1.1) and (1.2).
The set K V of V -variable fractal sets and the set M V of V -variable fractal measures from Definition 5.1, together with their natural probability distribution K V and M V from Definition 5.19, are obtained as the attractors of IFSs under suitable conditions, see Theorems 6.4 and 6.6. The Markov chains corresponding to these IFSs provide MCMC algorithms, such as the "chaos game", for generating samples of V -variable fractal sets and Vvariable fractal measures whose empirical distributions converge to the stationary distributions K V and M V respectively.
where the metrics on the right are as in Section 2.
The metrics d H and d M K are complete and separable, while the metric d P is complete but usually not separable. See Definitions 2.1, 2.3 and 2.4, the comments which follow them, Proposition 2.5 and Remark 2.6. The metric d M K is usually not locally compact, see Remark 3.5.
Let (6.3) be the corresponding IFSs, with P V from Definition 5.18. These IFSs are called superIFSs.
Two types of conditions will be used on families of IFSs. The first was introduced in (4.1). Definition 6.3 (Contractivity conditions for a family of IFSs). The family F = {X, F λ , λ ∈ Λ, P } of IFSs is uniformly contractive and uniformly bounded if for some 0 ≤ r < 1, y) and sup λ max m d(f λ m (a), a) < ∞ for all x, y ∈ X and some a ∈ X. (The probability distribution P is not used in (6.4). The second condition is immediate if Λ is finite.) The family F is pointwise average contractive and average bounded if for some 0 ≤ r < 1 , a) < ∞ for all x, y ∈ X and some a ∈ X.
The following theorem includes and strengthens Theorems 15-24 from [BHS05]. The space X may be noncompact and the strong Prokhorov metric d P is used rather than the Monge-Kantorovitch metric d M K .
Then the superIFSs F C V and F Mc V satisfy the uniform contractive condition Lip F a ≤ r. Since (C(X) V , d H ) is complete and separable, and (M c (X) V , d P ) is complete but not necessarily separable, the corresponding conclusions of Theorem 3.2 and Remark 3.6 are valid.
In particular (1) F C V and F Mc V each have unique compact set attractors and compactly supported separable measure attractors. The attractors are K * V and K * V , and M * V and M * V , respectively. Their projections in any coordinate direction are K V , K V , M V and M V , respectively.
(2) The Markov chains generated by the superIFSs converge at an exponential rate.
(3) Suppose (K 0 1 , . . . , K 0 V ) ∈ C(X) V . If a = a 0 a 1 · · · ∈ A ∞ V then for some (K 1 , . . . , K V ) ∈ K * V which is independent of (K 0 1 , . . . , Convergence is exponential in both cases. Analogous results apply for M * V , K * V and M * V , with d P or d H as appropriate. There are similar results for V -tuples of sets or measures. Proof. The assertion Lip F a ≤ r follows from (6.1) by a straightforward argument using Definitions 2.1 and 2.4, equation (2.4) and the comment following it, and equations (4.7), (6.1) and (6.2). So the analogue of the uniform contractive condition (3.13) in Theorem 3.2 is satisfied, while the uniform boundedness condition is immediate since F is finite. From Theorem 3.2.d and Remark 3.6, F C V and F Mc V each has a unique set attractor which is a subset of C(X) V and M c (X) V respectively, and a measure attractor which is a probability distribution on the respective set attractor.
It remains to identify the attractors with the sets and distributions in Definitions 5.1, 5.7, 5.18 and 5.19. Let Π denote one of the maps depending on the context. In the last two cases it follows from (5.3) and (6.2) that Π•Φ a = F a • Π. Also denote by Π the extension of Π to a map on sets, on V -tuples of sets, on measures or on V -tuples of measures, respectively. It follows from Theorem 3.2.d together with Definitions 5.1, 5.7 and 5.18 that (6.8) The rest of (i) follows from Theorems 5.12 and 5.21. The remaining parts of the theorem follows from Theorem 3.2 and Remark 3.6.
Remark 6.5 (Why use the d P metric? ). For computing approximations to the set of V -variable fractals and its associated probability distribution which correspond to F , the main part of the theorem is (iv) with either sets or measures. The advantage of (M c (X), Theorem 6.6 (Average contractive conditions). Let F = {X, F λ , λ ∈ Λ, P } be a possibly infinite family of IFSs on a complete separable metric space (X, d) satisfying (6.5).
Then the superIFS F M1 V satisfies the pointwise average contractive and average boundedness conditions is complete and separable, the corresponding conclusions of Theorem 3.2 are valid.
In particular has a unique measure attractor and its projection in any coordinate direction is the same. The attractor and the projection are denoted by M * V and M V , and extend the corresponding distributions in Theorem 6.4.
Remark 6.7 (Global average contractivity). One might expect that the global average contractive condition E λ E m Lip f λ m < 1 on the family F would imply the global average contractive condition E a Lip F a < 1, i.e. would imply that the superIFS F M1 V is global average contractive. However, this is not the case.
Next let a * = F 1 2 F 1 2 and choose µ = (δ 0 , δ 0 ), µ = (δ 1 , δ 0 ), so µ and µ differ in the box on which f 1 always acts and agree in the box on which f 2 always acts. Note d M K (µ, µ ) = 1/2. Then Again using the first form of (2. 2) with f (x) = |x|, it follows that d M K F a * (µ), F a * (µ ) ≥ 3/4, so Lip F a * ≥ 3/2. Since there are 16 possible maps a ∈ A V , each selected with probability 1/16, it follows that So for such 0 < < 2/15 the IFS F M1 V is not global average contractive. But since E m Lip f m = 1− /4 it follows from Theorem 6.6 that F M1 V is pointwise average contractive, and so Theorem 3.2 can be applied. Let F = {R 2 , F λ , λ ∈ R 2 , N (0, σ 2 I)} where F λ = {f λ 1 , f λ 2 ; 1/2, 1/2} and N (0, σ 2 I) is the symmetric normal distribution in R 2 with variance σ 2 . The functions f λ 1 and f λ 2 are uniquely specified by the requirements that they be similitudes with positive determinant and 0). A calculation shows σ = 1.42 implies E λ E m Lip f λ m ≈ 0.9969 and so average contractivity holds if σ ≤ 1.42. If |λ| is sufficiently large then neither f λ 1 nor f λ 2 are contractive. The IFS F λ can also be interpreted as a map from the space C([0, 1], R 2 ), of continuous paths from [0, 1] to R 2 , into itself as follows: Then one can define a superIFS acting on such functions in a manner analogous to that for the superIFS acting on sets or measures. Under the average contractive condition one obtains L 1 convergence to a class of V -variable fractal paths, and in particular V -variable fractal curves, from (−1, 0) to (1, 0). We omit the details. Remark 6.9 (Graph directed fractals). Fractals generated by a graph directed system [GDS] or more generally by a graph directed Markov system [GDMS], or by random versions of these, have been considered by many authors. See [Ols94,MU03] for the definitions and references. We comment here on the connection between these fractals and V -variable fractals.
In particular, for each experimental run of its generation process, a random GDS or GDMS generates a single realisation of the associated random fractal. On the other hand, for each run, a superIFS generates a family of realisations whose empirical distributions converge a.s. to the probability distribution given by the associated V -variable random fractal.
To make a more careful comparison, allow the number of functions M in each IFS F λ as in (1.1) to depend on λ. A GDS together with its associated contraction maps can be interpreted as a map from V -tuples of sets to V -tuples of sets. The map can be coded up by a matrix a as in (5.5), where M there is now the number of edges in the GDS.
If V is the number of vertices in a GDS, the V -tuple (K 1 , . . . , K V ) of fractal sets generated by the GDS is a very particular V -variable V -tuple. If the address a = a 0 a 1 . . . a k . . . for (K 1 , . . . , K V ) is as in (5.6), then a k = a for all k. Unlike the situation for V -variable fractals as discussed in Remark 5.2, there are at most V distinct subtrees which can be obtained from the tree codes ω v for K v regardless of the level of the initial node of the subtree.
More generally, if (K 1 , . . . , K V ) is generated by a GDMS then for each k, a k+1 is determined just by a k and by the incidence matrix for the GDMS. Each subtree ω v σ is completely determined by the value ω v (σ) ∈ Λ at its base node σ and by the "branch" σ k in σ = σ 1 . . . σ k .
Realisations of random fractals generated by a random GDS are almost surely not V -variable, and are more akin to standard random fractals as in Definition 4.5. One comes closer to Vvariable fractal sets by introducing a notion of a homogeneous random GDS fractal set analogous to that of a homogeneous random fractal as in Remark 9.4. But then one does not obtain a class of V -variable fractals together with its associated probability distribution unless one makes the same definitions as in Section 5. This would be quite unnatural in the setting of GDS fractals, for example it would require one edge from any vertex to any vertex. 7. Approximation Results as V → ∞.
Theorems 7.1 and 7.3 enable one to obtain empirical samples of standard random fractals up to any prescribed degree of approximation by using sufficiently large V in Theorem 6.4(iv). This is useful since even single realisations of random fractals are computationally expensive to generate by standard methods. Note that although the matrices used to compute samples of V -variable fractals are typically of order V × V , they are sparse with bandwidth M .
The next theorem improves the exponent in [BHS05, Theorem 12] and removes the dependence on M . The difference comes from using the third rather than the first version of (2.2) in the proof.
Proof. We construct random tree codes W V and W ∞ with dist W V = ρ V and dist W ∞ = ρ ∞ . In order to apply the last equality in (2.2) we want the expected distance between W V and W ∞ , determined by their joint distribution, to be as small as possible. Suppose be the corresponding random tree code, using the notation of (5.8) and (5.7). It follows from Definition 5.18 that dist W V = ρ V .
Let the random integer K = K(A) be the greatest integer such that, for 0 ≤ j ≤ K, if |σ| = |σ | = j and σ = σ then J A 1 (σ) = J A 1 (σ ) in (5.7). Thus with v = 1 as in Example 5.17 the nodes of T are placed in distinct buffers up to and including level K.
Let W ∞ be any random tree code such that if |σ| > K then dist W ∞ (σ) = P and W ∞ (σ) is independent of W ∞ (σ ) for all σ = σ. where Proof. The first two estimates follow from Theorem 5.5 and Proposition 4.3. For the third, let W V and W ∞ be the random codes from the proof of Theorem 7.1. In particular, Let Π be the projection map Ω → K ω given by (4.3) and (6.8). Then K V = dist Π • W V , K ∞ = dist Π • W ∞ , and from the last condition in (2.2) If α ≤ 1 then from (4.6) on taking expectations of both sides, using Hölder's inequality and applying (7.2), If α ≥ 1 then from the last two lines in the proof of Proposition (4.3), and so, using this and arguing as before, This gives the third estimate. The fourth estimate is proved in an analogous manner.
Sharper estimates can be obtained arguing directly as in the proof of Theorem 7.1. In particular, the exponent α can be replaced by log(1/r) log(M 2 /r) .

Example of 2-Variable Fractals
Consider the family F = {R 2 , U, D, 1 2 , 1 2 } consisting of two IFSs U = (f 1 , f 2 ) (Up with a reflection) and D = (g 1 , g 2 ) (Down) acting on R 2 , where The corresponding fractal attractors of U and F are shown at the beginning of Figure 4. The probability of choice of U and D is 1 2 in each case. The 2-variable superIFS acting on pairs of compact sets is F C 2 = (C(R 2 ) 2 , F a , a ∈ A 2 , P 2 ). There are 64 maps a ∈ A 2 , each a 2 × 3 matrix. The probability distribution P 2 assigns probability 1 64 to each a ∈ A 2 . In iteration 4 in Figure 4 the matrix is a = U 2 1 U 1 2 . Applying F a to the pair of sets (E 1 , E 2 ) from iteration 3 gives The process in Figure 4 begins with a pair of line segments. The first 6 iterations and iterations 23-26 are shown. After about 12 iterations the sets are independent of the initial sets up to screen resolution. After this the pairs of sets can be considered as examples of 2-variable 2-tuples of fractal sets corresponding to F .
The generation process gives an MCMC algorithm or "chaos game" and acts on the infinite state space (C(R 2 ) 2 , d H ) of pairs of compact sets with the d H metric. The empirical distribution along a.e. trajectory from any starting pair of sets converges weakly to the 2-variable superfractal probability distribution on 2-variable 2-tuples of fractal sets corresponding to F . The empirical distribution of first (and second) components converges weakly to the corresponding natural probability distribution on 2-variable fractal sets corresponding to F .

Concluding Comments
Remark 9.1 (Extensions). The restriction that each IFS F λ in (1.1) has the same number M of functions is for notational simplicity only.
In Definition 5.18 the independence conditions on the I and J may be relaxed. In some modelling situations it would be natural to have a degree of local dependance between (I(v), J(v)) and (I(w), J(w)) for v "near" w.
The probability distribution ρ V is in some sense the most natural probability distribution on the set of V -variable code trees since it is inherited from the probability distribution P ∞ V with the simplest possible probabilistic structure. We may construct more general distributions on the set of V -variable code trees by letting P ∞ V be non-Bernoulli, e.g. stationary. Instead of beginning with a family of IFSs in (1.2) one could begin with a family of graph directed IFSs and obtain in this manner the corresponding class of V -variable graph directed fractals.
Remark 9.2 (Dimensions). Suppose F = {R n , F λ ; λ ∈ Λ, P } is a family of IFSs satisfying the strong uniform open set condition and whose maps are similitudes. In a forthcoming paper we compute the a.s. dimension of the associated family of V -variable random fractals. The idea is to associate to each a ∈ A V a certain V × V matrix and then use the Furstenberg Kesten theory for products of random matrices to compute a type of pressure function.
Remark 9.3 (Motivation for the construction of V -variable fractals). The original motivation was to find a chaos game type algorithm for generating collections of fractal sets whose empirical distributions approximated the probability distribution of standard random fractals.
More precisely, suppose F = {(X, d), F λ , λ ∈ Λ, P } is a family of IFSs as in (1.2). Let V be a large positive integer and S be a collection of V compact subsets of X, such that the empirical distribution of S approximates the distribution K ∞ of the standard random fractal associated to F by Definition 4.5. Suppose S * is a second collection of V compact subsets of X obtained from F and S as follows. For each v ∈ {1, . . . , V } and independently of other w ∈ {1, . . . , V }, select E 1 , . . . E M from S according to the uniform distribution independently with replacement, and independently of this select F λ from F according to P . Let the vth set in S * be F λ (E 1 , . . . E M ) = 1≤m≤M f λ m (E m ). Then one expects the empirical distribution of S * to also approximate K ∞ .
The random operator constructed in this manner for passing from S to S * is essentially the random operator F a in Definition 6.2 with a ∈ A V chosen according to P V .
If M = 1 in (1.1) then each F λ is a trivial IFS (f λ ) containing just one map, and the family F in (1.2) can be interpreted as a standard IFS. If moreover V = 1 then the corresponding superIFS in Definition 6.2 can be interpreted as a standard IFS operating on (X, d) with set and measure attractors K and µ, essentially by identifying singleton subsets of X with elements in X. For M = 1 and V > 1 the superIFS can be identified with an IFS operating on X V with set and measure attractors K * V and µ * V . Conversely, any standard IFS can be extended to a superIFS in this manner. The projection of K * V in any coordinate direction is K, but K * V = K V . The attractors K * V and µ * V are called correlated fractals. The measure µ * provides information on a certain "correlation" between subsets of K. This provides a new tool for studying the structure of standard IFS fractals as we show in a forthcoming paper.
The case V = 1 corresponds to homogeneous random fractals and has been studied in [Ham92,Kif95,Ste01b]. The case V → ∞ corresponds to standard random fractals as defined in Definition 4.5, see also Section 7. See also [Asa98] for some graphical examples.
For a given class F of IFSs and positive integer V > 1, one obtains a new class of fractals each with the prescribed degree V of self similarity at every scale. The associated superIFS provides a rapid way of generating a sample from this class of V -variable fractals whose empirical distribution approximates the natural probability distribution on the class.
Large V provides a method for generating a class of correctly distributed approximations to standard random fractals. Small V provides a class of fractals with useful modelling properties.