() @ Applied General Topology c© Universidad Politécnica de Valencia Volume 11, No. 2, 2010 pp. 135-158 Random selection of Borel sets Bernd Günther Abstract. A theory of random Borel sets is presented, based on dyadic resolutions of compact metric spaces. The conditional expecta- tion of the intersection of two independent random Borel sets is inves- tigated. An example based on an embedding of Sierpiński’s universal curve into the space of Borel sets is given. 2000 AMS Classification: Primary 60D05; Secondary 54H05 Keywords: Random Borel sets, dyadic spaces, Sierpiński’s universal curve 1. Introduction The theory of random sets is almost exclusively concerned with random closed sets [11, 15, 9], the subject of random Borel sets hardly being touched [11, Ch.I§2.5,p.41]. Probably the most elaborate exposition was given by Straka and Štěpán [17] where it was observed that the distribution of a random Borel subset A of the unit segment is uniquely determined by the distribution of its inspection process At := λ ([0, t] ∩ A), where λ denotes Lebesgue measure on I; but no characterization of the inspections processes occuring thus was given. This left the characterization of distributions essentially open. Also, the concept of inspection process does not easily generalize from I to other compact metric spaces. The well studied random closed sets are usually considered as elements of the hyperspace equipped with the Vietoris topology or some variation. We can conceive of situations where this design choice is inadequate. For instance, a probability measure on the compactum defines a function on its hyperspace that is upper semicontinuous but not continuous: Any closed subset can be arbitrarily closely approximated in the Vietoris topology by finite sets and hence by subsets of measure 0. In Robbins’ classical papers [12, 13] probabilis- tic properties of a randomly selected subset A are derived from the function F (x) := P (x ∈ A); however, unless the point x carries mass we would prefer to consider the sets A and A\{x} equivalent, and thus events like “x ∈ A” for 136 B. Günther fixed x and random A would be probabilistically meaningless. In applications such as image analysis using wavelets 0-sets are generally neglected. Allowing a random set to assume its values among Borel subsets, not just closed ones, leads to greater variety but reduces complexity by factoring out 0-sets. We must therefore emphasize that the method we are going to propose is not a generalization of the conventional one from closed subsets to Borel subsets, but a different approach that is intended for a different sort of applications. For instance, we are going to ask the following: Question 1. If two players independently choose random subsets A and B and announce their measures µ(A) and µ(B), what knowledge can we derive about µ(A ∩ B)? A modification of this would be appropriate if A is a picture (hence deter- ministic) submitted over a video channel and B is a random distortion: Question 2. If A is known and B is random, what is the conditional distri- bution of µ(A ∩ B) given µ(B)? This raises the question of invariance: If we were sure that the answer to question 2 depended only on µ(A), that is: only on the size of A but not its location, then both questions would be equivalent. The reader will probably observe that in the finite case both questions lead to the same hypergeometric distribution. Unfortunately, in the infinite case we have to settle for a slightly weaker property, because complete location invariance will be shown to be impossible. The general setting of our paper will be as follows: Standing Assumption. Let X denote a compact metric space equipped with a non-atomic Borel probability measure such that Supp µ = X. Thus µ has vanishing point masses and the only open 0-subset is the empty set1. In section 2 the measure algebra Y (µ) of all Borel subsets of X (canceling those with µ-measure 0) will be presented in an abstract setting. A geometric model for this space will be developed in section 5, but first we need two digressions. The first one is about isometries of Cantor’s discontinuum, which will be utilized in context of the invariance property mentioned above. Larger sets of automorphisms have been studied (eg. [14]), but it will follow from section 9 that they wouldn’t be an improvement in our context. In section 4 we review Sierpińskis “intermediate value” theorem for measures [16] and the Hausdorff-Alexandroff theorem representing compacta as continuous images of the Cantor space ([1, Ch.II,§6,Thm.VI’] [6, Ch.6,§26.2]); in combination they state that any compact metric probability space is (more or less) measure isomorphic to Cantor’s discontinuum equipped with Haar measure. In section 5 we will study a particular subspace Y of the Hilbert cube that will be shown to be isomorphic to Y (µ) in section 6, using the methods of section 4. This enables 1It can be shown that a measure with these properties exists if and only if X is dense in itself. Random selection of Borel sets 137 us to give a nice description of probability measures on Y (µ) in section 7. Section 8 is devoted to the study of question 1. The impossibility to reach the idealized design goal of complete location invariance will be established in section 9. The space Y (µ) contains something like a 1-skeleton that will be shown to be homeomorphic to Sierpinśki’s universal curve in section 10; this also provides us with the easiest non trivial example of a probability measure on Y (µ). The relation between random Borel and random closed sets will be investigated in section 11. 2. The space of Borel sets We denote by Y (µ) ⊆ L2(µ) the subset of all Borel sets in X, identifying a set A with its characteristic function χA and considering two sets as equivalent if their symmetric difference has measure 0. From L2(µ) it inherits the Hilbert space topology and the weak topology. In addition, Y (µ) is an Abelian group under the operation △ “symmetric difference” with ∅ as 0-element and with −A = A for all A ∈ Y (µ). We define a group valuation on Y (µ) by |A| := µ(A); evidently we have |A1△A2| ≤ µ (A1 ∪ A2) ≤ |A1| + |A2|. Thus Y (µ) is a topological group. Notice that this space is the Lebesgue measure algebra familiar from de- scriptive set theory [8, Exc.17.2,p.104]. Lemma 2.1. All three topologies on Y (µ) coincide: (1) The group topology defined above. (2) The Hilbert space topology induced from L2(µ). (3) The weak topology induced from L2(µ). Y (µ) is norm closed in L2(µ). Proof. The first topology is induced by the metric d1(A, B) = µ (A△B) = µ (A \ B) + µ (B \ A), the second one by d2(A, B) = ‖χA − χB‖2 = √ µ (A \ B) 2 + µ (B \ A) 2 . Therefore 1 2 d1 ≤ d2 ≤ d1, and the two metrics are equivalent. Trivially, the weak topology on Y (µ) is coarser than the norm topology, and we have to show the reverse relation. For A ∈ Y (µ) and ε > 0 the sets U1 := { B | |〈χA, χB − χA〉| < ε 2 } = { B | µ (A \ B) < ε 2 } and U2 := { B | |〈χ∁A, χB − χA〉| < ε 2 } = { B | µ (B \ A) < ε 2 } are weak neighborhoods of A such that U1 ∩ U2 ⊆ {B | µ (A△B) < ε}, hence the weak topology is finer than the group topology on Y (µ). The last statement is obvious. � We observe that the set operations ∩ and ∁ as well as the measure function µ are continuous on Y (µ). As an auxiliary object we denote by Z(µ) ⊂ L2(µ) the set of all functions 0 ≤ f ≤ 1. This set inherits the norm topology and the weak topology from L2(µ); the latter is compact by the Banach-Alaoglu theorem. 138 B. Günther Lemma 2.2. Y (µ) is weakly dense in Z(µ). Proof. Consider a function g ∈ Z(µ) and a weak neighborhood of g defined as the set of all h ∈ Z(µ) such that |〈fi, h − g〉| < 1 with suitable functions f1, . . . fn ∈ L 2(µ). Without loss of generality (observe ‖h − g‖2 ≤ 1) we may assume that each fi is a step function fi = ∑mi j=1 αij χAij and that g is a step function g = ∑mn+1 j=1 αn+1,j χAn+1,j with 0 ≤ αn+1,j ≤ 1 and Aij ∩ Aik = ∅ for j 6= k. If B1, . . . BN is the collection of all intersections Aij ∩ Aℓk with non zero measure, then we may write fi = ∑N j=1 βij χBj and g = ∑N j=1 γj χBj with 0 ≤ γj ≤ 1 and Bj ∩ Bk = ∅ for j 6= k. Choose points xj ∈ Bj . Then by our standing assumption 0 = µ ({xj}) < µ (Bj ) and therefore Sierpiński’s mean value theorem ensures the existence of sets Cj ⊆ Bj with µ (Cj ) = γj µ (Bj ). ⋃N j=1 Cj ∈ Y (µ) is contained in the given weak neighborhood of g. � There are two intrinsic characterizations of Y (µ) as a subset of Z(µ). First: Y (µ) is the extreme set of the convex set Z(µ), because any f ∈ Z(µ) can be written as f = 1 2 f 2 + 1 2 [ 1 − (1 − f )2 ] . Second: pointwise multiplication provides us with a product on Z(µ) (let’s not worry about its continuity here), and Y (µ) is the set of idempotents. Furthermore, on Y (µ) the product equals the intersection of sets. These observations will be utilized in section 5. Y (µ) can easily be identified as a weak Gδ in Z(µ); in particular it is Polish (cf. [8, Exc.17.43,p.117] and [2, Ch.IX,§6.1,Thm.1]) It should be observed that lemma 2.2 states a much stronger property than would be obtained by an application of the Krein-Milman theorem [3, Ch.II,§7.1,Thm1], which would merely assure us that the convex hull of Y (µ) is weakly dense in Z(µ). However, the property is familiar from Lindenstrauss’ proof of Liapounoff’s theorem [10], applied to the measures fiµ. 3. Isometries of Cantor’s discontinuum For us, Cantor’s discontinuum is the compact Abelian groupC = ZN2 , equipped with the dyadic ultrametric |t − t′|2 = 2 − min{n:tn−t′n 6=0}, t = (tn), t ′ = (t′n). Observe that the ordering of the coordinates enters essentially. Furthermore, C is a probability space equipped with the Haar measure. By G∞ we denote the group of isometries of C; by the Arzela-Ascoli theorem this group is compact. To obtain a simple description we consider the projection maps pn : Z N 2 → Z n 2 onto the first n coordinates. It follows immediately from the definition that every isometry must factor over pn and provide us with a ladder of permutations πn ∈ S2n : Random selection of Borel sets 139 Definition 3.1. A permutation π : Zn2 ≈ Z n 2 is called filtered, if there exists a commutative ladder of permutations (not necessarily automorphisms) as in (3.1) with π = πn. The group of all filtered permutations is denoted Gn. (3.1) Zn2 πn≈ �� p n n−1 // // Z n−1 2 πn−1≈ �� // // · · · // // Z22 π2≈ �� p 2 1 // // Z12 π1≈ �� Zn2 p n n−1 // // Z n−1 2 // // · · · // // Z22 p 2 1 // // Z12 We obtain G∞ = lim←−n Gn; as inverse limit of finite discrete (hence compact) groups this is a compact group. Hence any isometry is measure preserving. Furthermore, the action of G∞ on C is transitive but not 2-transitive: indeed, for two pairs of points x, y ∈ C and x′, y′ ∈ C, an isometry γ ∈ G∞ with γx = x′ and γy = y′ exists if and only if |x − y|2 = |x ′ − y′|2. 4. Review of measurable dyadic spaces The classical result obtained by Hausdorff and Alexandroff states that every compactum can be represented as a dyadic space, i.e. as continuous image of Cantor’s discontinuum. We have to squeeze measure theoretic properties out of this theorem. The dyadic resolutions we are about to construct should be compared to the “rastering” of an image and will be the fundamental tool in our analysis of the space of Borel sets in section 6. Lemma 4.1. Every point of x ∈ X has a fundamental sequence of open neigh- borhoods U with µ (∂U ) = 0. Proof. For a given point x ∈ X choose a continuous function ϕ : X → I with ϕ−1(0) = x. Let C ⊂ I be the at most countable subset of all points t ∈ I with µ ( ϕ−1(t) ) > 0; for any t ∈ I \ C the open neighborhood U := ϕ−1 ([0, t[) of x satisfies ∂U ⊆ ϕ−1(t) and therefore µ (∂U ) = 0. � Lemma 4.2. Suppose A is a locally closed subset of X with µ(A) > 0 and µ (∂A) = 0. Then for any 0 < β < µ(A) there exists a locally closed subset B ⊂ A with µ(B) = β and µ (∂B) = µ (∂ (A \ B)) = 0. We recall that a set is locally closed if it is the intersection of a closed and an open set [2, Ch.I,§3.4]. This adds a condition about the boundary to Sierpiński’s theorem [16]. Proof. We construct two sequences of open subsets Un, Vn ⊂ A ◦ such that Un ∩ Vn = ∅, Un ⊆ Un+1, Vn ⊆ Vn+1, β − 1 n ≤ µ (Un) < β, µ(A) − β − 1 n ≤ µ (Vn) < µ(A) − β and µ (∂Un) = µ (∂Vn) = 0. Clearly we can start with U1 = V1 = ∅. At inductive stage n, if µ (Un) = β or µ (Vn) = µ(A) − β we are finished, so let us assume 0 < β − µ (Un) < µ(A) − µ (Un) − µ (Vn). Let K ⊆ A◦ \ ( U n ∪ V n ) be a compact subset with µ(K) > β − µ (Un). Using atomicity of µ and lemma 4.1 we can cover K by finitely many open subsets Wi of A◦ \ ( U n ∪ V n ) with µ (Wi) < 1 n+1 and µ (∂Wi) = 0. Let j be the maximal 140 B. Günther number such that µ (W1 ∪ . . . ∪ Wj−1) < β−µ (Un). Then µ (W1 ∪ . . . ∪ Wj ) ≥ β−µ (Un) and, since µ (Wj ) < 1 n+1 , µ (W1 ∪ . . . ∪ Wj−1) >= β−µ (Un)− 1 n+1 . Set Un+1 := Un ∪ W1 ∪ . . . ∪ Wj−1. Again, if µ (Un+1) = β we are finished. Otherwise we have µ(A) − µ (Un+1) − µ (Vn) > µ(A) − µ (Vn) − β > 0. Let K′ ⊆ A◦ \ ( U n+1 ∪ V n ) be a compact subset with µ (K′) > µ(A) − µ (Vn) − β and cover K′ by finitely many open subsets W ′i of A ◦ \ ( U n+1 ∪ V n ) with µ (W ′i ) < 1 n+1 and µ (∂W ′i ) = 0. Let j be the maximal number such that µ ( W ′1 ∪ . . . ∪ W ′ j−1 ) < µ(A)−µ (Vn)−β. Then µ ( W ′1 ∪ . . . ∪ W ′ j−1 ) ≥ µ(A)− µ (Vn) − β − 1 n+1 , set Vn+1 := Vn ∪ W ′ 1 ∪ . . . ∪ W ′ j−1. Now U := ⋃ n Un and V := ⋃ n Vn are disjoint open subsets of A ◦ with µ(U ) = β and µ(V ) = µ(A) − β. Since ∂U ⊆ A \ (U ∪ V ) we must have µ (∂U ) = 0. � Lemma 4.3. Suppose we are given real numbers βi > 0 with β := ∑n−1 i=0 βi ≤ 1. Then for any 0 < ε < 1 and N ≥ 4 ε maxi β βi we can find numbers ki ∈ N (in particular ki > 0) such that ∑n−1 i=0 ki = N and ∣ ∣ ∣ βi ki − β N ∣ ∣ ∣ ≤ ε N . Proof. Set ϑ := maxi β βi . First choose integer k′i ∈ Z with ∣ ∣ ∣ N βi β − k′i ∣ ∣ ∣ ≤ 1 2 . Then |N − ∑ i k′i| = ∣ ∣ ∣ ∑n−1 i=0 ( N βi β − k′i )∣ ∣ ∣ ≤ n 2 and hence, by adjusting at most n 2 cases ki := k ′ i ± 1 we can assure ∑n−1 i=0 ki = N and ∣ ∣ ∣ N βi β − ki ∣ ∣ ∣ ≤ 3 2 . Since N ≥ 4ϑ ≥ 4β βi we have N βi β ≥ 4 and in particular ki > 0. This gives us ∣ ∣ ∣ kiβ N βi − 1 ∣ ∣ ∣ ≤ 3β 2N βi ≤ 3ϑ 2N ≤ 1 2 and therefore ∣ ∣ ∣ N βi kiβ − 1 ∣ ∣ ∣ ≤ 3ϑ N , hence ∣ ∣ ∣ βi ki − β N ∣ ∣ ∣ ≤ 3βϑ N 2 ≤ 3ϑ N 2 ≤ 3ε 4N . � Definition 4.4. A type I resolution of X consists of a double sequence of locally closed subsets Anm ⊆ X, n ∈ N0, 0 ≤ m < 2 n, subject to the following conditions: (1) A00 = X (2) Anm ∩ Ank = ∅ for m 6= k (3) An+1,2m ∪ An+1,2m+1 = Anm (4) lim n→∞ max2 n−1 m=0 diam Anm = 0 (5) µ (∂Anm) = 0 (6) There exists a sequence of numbers εn > 0 with ∑ n εn < ∞ such that 1−εn 2 µ (Anm) ≤ µ (An+1,2m) , µ (An+1,2m+1) ≤ 1+εn 2 µ (Anm) Proposition 4.5. Every compactum satisfying our standing assumption has a type I resolution. Proof. We construct the sets Anm by induction on n, pushing ahead from step n to step n + N for a suitable number N and then assembling the inter- mediate sets as pairwise disjoint unions. Observing lemma 4.1 we can chop up Anm into a disjoint union of locally closed sets Anm = ∐r j=0 Bj with Random selection of Borel sets 141 µ (∂Bj) = 0 and diam Bj ≤ 1 2 diam Anm; moreover, since Supp µ = X we have µ (Bj ) > 0. For any 0 < ε < 1 lemma 4.3 ensures the existence of numbers kj ∈ N such that ∑ j kj = 2 N and ∣ ∣ ∣ 1 kj µ (Bj) − 2 −N µ (Anm) ∣ ∣ ∣ ≤ ε N 2N , provided 2N N ≥ 4(Anm) εµ(Bj ) . Using lemma 4.2 we can partition each Bj into a disjoint union of kj locally closed sets Bj = ∐ ℓ∈Ij AN ℓ, #Ij = kj , with µ (∂AN ℓ) = 0 and µ (AN ℓ) = 1 kj µ (Bj ), so that in particular ∣ ∣µ (AN ℓ) − 2 −N µ (Anm) ∣ ∣ ≤ ε N 2N . Each of the intermediate sets An+v,w, 0 ≤ v ≤ N , 2 vm ≤ w < 2v(m + 1), is the disjoint union An+v,w = ∐ ℓ∈J AN ℓ, #J = 2 v. Thus 2−vµ (An+v,w) = ∑ ℓ∈J 2 −vµ (AN ℓ), and by convexity ∣ ∣2−vµ (An+v,w) − 2 −N µ (Anm) ∣ ∣ ≤ ε N 2N . Equivalently, ∣ ∣ ∣ 2N−v µ(An+v,w) µ(Anm) − 1 ∣ ∣ ∣ ≤ ε N µ(Anm) and therefore2 ∣ ∣ ∣ 2µ(An+v+1,2w) µ(An+v,w) − 1 ∣ ∣ ∣ ≤ 4ε N µ(Anm) and ∣ ∣ ∣ 2µ(An+v+1,2w+1) µ(An+v,w) − 1 ∣ ∣ ∣ ≤ 4ε N µ(Anm) if ε is chosen small enough. This takes care of condition 6 in definition 4.4, where the steps from n + 1 to n + N contribute a total of at most ∑N v=1 4ε N µ(Anm) = 4ε µ(Anm) to the sum of all error terms εn. � Remark: The proof shows that we can arrange for the total error ∑ n εn to be arbitrarily small. Example 4.6. On Cantor’s discontinuum, construct a type I resolution as follows. For 0 ≤ m < 2n consider the dual expansion m = ∑n−1 k=0 εn−k2 k and set Cnm := p −1 n (ε1, . . . εn). Notice that Cnm is closed and open, diam (Cnm) = 2−n−1 and ν (Cnm) = 2 −n. Lemma 4.7. For any type I resolution the finite unions of the sets Anm con- stitute a dense subset of the space of all Borel sets Y (µ). Proof. Inner and outer regularity of µ [8, Thm.17.10] and small diameter of the sets Anm. � Theorem 4.8. Each compactum X satisfying our standing assumption can be represented as continuous image of Cantors discontinuum f : C ։ X, such that there exists a measurable inverse function g : X → C whose points of discontinuity constitute a 0-set, with f g = idX strictly and gf = idC a.s. Moreover, there exists a continuous, strictly positive density function ϕ : C → R with g∗µ = ϕν and f∗ν = 1 ϕg µ, where ν is Haar measure on C. ϕ may be chosen as close to 1 as we please. Notice for instance that the fibers of f must be non void 0-sets. X can be changed into Cantor’s discontinuum by altering it at a 0-set. The probability spaces (X, µ) and (C, ϕν) are measure isomorphic. Proof. Observe that for any sequence of numbers mn with mn+1 = 2mn or mn+1 = 2mn + 1 for each n we have 2 nµ (Anm) = ∏n−1 k=0 2µ(Ak+1,mk+1 ) µ(Ak,mk ) and 2Observe that |x − 1| ≤ ε ≤ 1 2 and |y − 1| ≤ ε ≤ 1 2 imply ∣ ∣ ∣ x y − 1 ∣ ∣ ∣ ≤ 4ε 142 B. Günther that the product converges uniformly for all such sequences mn. Hence, if we define a continuous function ϕn : C → R to assume the value 2 nµ (Anm) on Cnm, then this function will converge uniformly to a continuous function ϕ : C → R, ϕ > 0. For N ≥ n we have ∫ Cnm ϕN dν = ∑2N −n(m+1)−1 k=2N −nm ∫ CN k ϕN dν = ∑2N −n(m+1)−1 k=2N −nm µ (AN k) = µ (Anm) and therefore ∫ Cnm ϕdν = µ (Anm). Define fn : C → X to be the continuous map that assumes on Cnm a constant value contained in Anm. This sequence of functions converges uniformly to a map f : C → X with f (Cnm) ⊆ Anm. For a point x ∈ X consider the unique sequence mn with x ∈ Anm. There is a unique point y ∈C with y ∈ Cnmn for all n, therefore f (y) ∈ ⋂ Anmn . Hence f (y) = x. Define gn : X → C to be the function that assumes on Anm a constant value contained in Cnm; notice that gn is measurable and is continuous except possibly at ⋃ m ∂Anm. This sequence converges uniformly to a function g : X → C with g (Anm) ⊆ Cnm that is measurable and is continuous except possibly at X0 := ⋃ n,m ∂Anm; notice µ (X0) = 0. Since f g (Anm) ⊆ f (Cnm) ⊆ Anm we must have f g = idX strictly, by the same argument as above. g (Anm) ⊆ Cnm implies Anm ⊆ g −1 (Cnm), but since for fixed n these sets constitute a partition of X we must have Anm = g −1 (Cnm). Hence ∫ Cnm ϕdν = µ (Anm) = µ ( g−1Cnm ) = (g∗µ) Cnm. Since the finite unions of the sets Cnm generate all Borel sets we conclude ϕν = g∗µ. Now let Y0 := f −1 (X0) ⊆C be the inverse image of the singularity set of g. Then g−1 (Y0) = g −1f −1 (X0) = (f g) −1 (X0) = X0 and in particular ∫ Y0 ϕdν = µ ( g−1Y0 ) = µ (X0) = 0. Since the continuous density ϕ is everywhere positive we conclude ν (Y0) = 0. Let’s consider a point y ∈ C \ Y0; for n pick m such that y ∈ Cnm. Then f (y) ∈ Anm \ X0 ⊆ Anm and therefore gf (y) ∈ Cnm. This can happen for arbitrary n only if gf (y) = y. We claim f −1A◦nm ⊆ Cnm. For a point y ∈ f −1A◦nm we pick k such that y ∈ Cnk, then f (y) ∈ Ank. If we had k 6= m we could conclude Ank ∩Anm = ∅ and hence Ank ∩ A ◦ nm = ∅ and hence f (y) 6∈ A ◦ nm, thus arriving at a contra- diction. Therefore we have Cnm ⊆ f −1Anm ⊆ f −1 (A◦nm ∪ X0) ⊆ Cnm ∪ Y0. This implies f −1 (Anm \ X0) = Cnm \ Y0, in particular ν ( f −1 (Anm) \ Y0 ) = ν ( f −1 (Anm \ X0) ) = 2−n and hence ν ( f −1Anm ) = 2−n. This implies ∫ Anm 1 ϕg dµ = ∫ Anm df∗ν and therefore 1 ϕg µ = f∗ν. Finally, ϕ can be made arbitrarily close to 1 because the error sum ∑ n εn in condition 6 of definition 4.4 is completely at our disposal. � Notice that theorem 4.8 allows to transport the group action of G∞ on C onto X by πx := f πg(x). The map x 7→ πx is a measure isomorphism of 1 ϕg µ and is continuous except at a 0-set, and the equation (πσ)x = π (σx) holds for almost all x, the exception set depending on σ. The action is transitive in the strict sense, i.e. for each x ∈ X the orbit equals the entire space G∞x = X. Random selection of Borel sets 143 Definition 4.9. A type II resolution of X consists of a double sequence of Borel subsets Anm ⊆ X, n ∈ N0, 0 ≤ m < 2 n, subject to the following conditions: (1) A00 = X (2) Anm ∩ Ank = ∅ for m 6= k (3) An+1,2m ∪ An+1,2m+1 = Anm (4) µ (An+1,2m) = µ (An+1,2m+1) = 1 2 µ (Anm) (5) The finite unions of the sets Anm are dense in Y (µ). Type II resolutions have the advantage of reproducing the measure on X exactly, but otherwise they are considerably weaker. Easy examples such as taking X as disjoint union of two closed segments of length 1 3 and 2 3 show that the properties of type I and type II resolutions are mutually exclusive in general. Proposition 4.10. Every compactum satisfying our standing assumption has a type II resolution. Evidently, this holds for the unit segment; the general case then follows from the isomorphism theorem for measures (cf. [8, Thm.17.41], [5, §41]). For com- parison: using type II resolutions instead of type II in the proof of theorem 4.8 just reproduces the ordinary isomorphism theorem. However, here it is not necessary to adjust our measure by a density function. Proposition 4.11. For any compactum X satisfying our standing assumption there exists a measurable function g : X → C such that g∗µ = ν, where ν is Haar measure on C. Moreover, for any Borel subset A ⊆ X there exists a Borel subset B ⊆C such that µ ( A△g−1B ) = 0. Thus Y (µ) ≈ Y (ν). 5. The coordinate space Let Z denote the set of all sequences of real numbers xnm, n ∈ N0, 0 ≤ m < 2n, subject to the conditions 0 ≤ xnm ≤ 1(5.1) xnm = 1 2 (xn+1,2m + xn+1,2m+1)(5.2) Z is a closed subset of the Hilbert cube and thus inherits a compact topology, that will be called the weak topology. Notice that Z is convex. Lemma 5.1. For all (xnm) ∈ Z (5.3) x2nm + ∞ ∑ r=n+1 (m+1)2r−n−1−1 ∑ k=m2r−n−1 2n−r−1 (xr,2k − xr,2k+1) 2 ≤ xnm Proof. We show by induction on N ≥ n that (5.4) x2nm + N ∑ r=n+1 (m+1)2r−n−1−1 ∑ k=m2r−n−1 2n−r−1 (xr,2k − xr,2k+1) 2 = 2n−N (m+1)2N −n−1 ∑ k=m2N −n x2N k 144 B. Günther The inductive step is as follows: 2n−N (m+1)2N −n−1 ∑ k=m2N −n x2N k + (m+1)2N −n−1 ∑ k=m2N −n 2n−N−2 (xN +1,2k − xN +1,2k+1) 2 (5.5) = 2n−N−2 (m+1)2N −n−1 ∑ k=m2N −n [ (xN +1,2k + xN +1,2k+1) 2 + (xN +1,2k − xN +1,2k+1) 2 ] (5.6) = 2n−N−1 (m+1)2N −n−1 ∑ k=m2N −n ( x2N +1,2k + x 2 N +1,2k+1 ) (5.7) = 2n−N−1 (m+1)2N +1−n−1 ∑ k=m2N +1−n x 2 N +1,k(5.8) Similarly one shows (5.9) 2n−N (m+1)2N −n−1 ∑ k=m2N −n xN k = xnm and the asserted lemma follows from x2N k ≤ xN k. � This implies in particular that Z is contained in the Hilbert space of all sequences satisfying (5.2), equipped with the scalar product (5.10) 〈xnm, x ′ nm〉 := x00x ′ 00 + ∞ ∑ n=1 2n−1−1 ∑ m=0 2−n−1 (xn,2m − xn,2m+1) ( x′n,2m − x ′ n,2m+1 ) Thence Z inherits another topology, finer than the one above. Lemma 5.2. On Z there is a product (xnm) = (x ′ nm) ∧ (x ′′ nm) defined by (5.11) xnm = lim N→∞ 2n−N (m+1)2N −n−1 ∑ k=m2N −n x′N kx ′′ N k It satisfies xnm ≤ √ x′nmx ′′ nm and is continuous as a function Zh × Zh → Zw, the suffixes indicating Hilbert space topology and weak topology, respectively. The bilinear map Zw ×Zw → Zw is separately continuous [3, Ch.III,§5.1]. The ∧-product is commutative and associative. Random selection of Borel sets 145 Proof. For all N ≥ n we obtain 2n−N (m+1)2N −n−1 ∑ k=m2N −n x′N kx ′′ N k + (m+1)2N −n−1 ∑ k=m2N −n 2n−N−2 ( x ′ N +1,2k − x ′ N +1,2k+1 )( x ′′ N +1,2k − x ′′ N +1,2k+1 ) (5.12) = 2n−N−2 (m+1)2N −n−1 ∑ k=m2N −n [ ( x′N +1,2k + x ′ N +1,2k+1 )( x′′N +1,2k + x ′′ N +1,2k+1 ) + ( x′N +1,2k − x ′ N +1,2k+1 )( x′′N +1,2k − x ′′ N +1,2k+1 ) ] (5.13) = 2n−N−1 (m+1)2N −n−1 ∑ k=m2N −n ( x′N +1,2kx ′′ N +1,2k + x ′ N +1,2k+1x ′′ N +1,2k+1 ) (5.14) = 2n−N−1 (m+1)2N +1−n−1 ∑ k=m2N +1−n x′N +1,kx ′′ N +1,k(5.15) Lemma 5.1 and the Cauchy-Schwarz inequality imply that the perturbation term in (5.12) converges to 0. We obtain (5.16) xnm := lim N→∞ 2n−N (m+1)2N −n−1 ∑ k=m2N −n x′N kx ′′ N k = x′nmx ′′ nm + ∞ ∑ r=n+1 (m+1)2r−n−1−1 ∑ k=m2r−n−1 2n−r−1 ( x′r,2k − x ′ r,2k+1 )( x′′r,2k − x ′′ r,2k+1 ) This demonstrates the asserted joint continuity condition right away, as well as the relation xnm ≤ √ x′nmx ′′ nm via another application of lemma 5.1 and the Cauchy-Schwarz inequality. Obviously the so defined sequence xnm satisfies (5.1) and (5.2). Commutativity and associativity are easily checked. For fixed (x′mk) the convergence of the series (5.16) is uniform, this implies separate continuity on Zw × Zw. � Proposition 5.3. For any x = (xnm) ∈ Z the following conditions are equiv- alent: (1) x is an extreme point of Z. (2) x ∧ x = x (3) x200 + ∑∞ n=1 ∑2n−1−1 k=0 2 −n−1 (xn,2k − xn,2k+1) 2 = x00 (4) limn→∞ 2 −n ∑2n−1 m=0 ( xnm − 1 2 )2 = 1 4 146 B. Günther Proof. With 1− x := (1 − xnm) we get x = 1 2 x∧ x + 1 2 [1 − (1 − x) ∧ (1 − x)], hence (1)⇒(2). (3) is just the 00-component of (2). In terms of our scalar product (5.10) condition (3) means ‖x‖ 2 = x00. Now assume x = 1 2 x′ + 1 2 x′′. Then, observing lemma 5.1 we can conclude x00 = ∥ ∥ 1 2 x′ + 1 2 x′′ ∥ ∥ 2 = 1 4 ‖x′‖ 2 + 1 2 〈x′, x′′〉 + 1 4 ‖x′′‖ 2 ≤ ( 1 2 ‖x′‖ + 1 2 ‖x′′‖ )2 ≤ ( 1 2 √ x′00 + 1 2 √ x′′00 )2 ≤ 1 2 x′00 + 1 2 x′′00 = x00. Therefore we must have 〈x ′, x′′〉 = ‖x′‖‖x′′‖, i.e. x′ and x′′ must be collinear, and 1 2 √ x′00 + 1 2 √ x′′00 = √ 1 2 x′00 + 1 2 x′′00, i.e. x ′ 00 = x ′′ 00. This implies x′ = x′′ = x and establishes the equivalence of the first three conditions, and the equation 2−n 2n−1 ∑ k=0 ( xnm − 1 2 )2 = 2−n 2n−1 ∑ k=0 x2nm − x00 + 1 4 = ( x00 − 1 2 )2 + n ∑ r=1 2r−1−1 ∑ k=0 2−r−1 (xr,2k − xr,2k+1) 2 (5.17) takes care of (4). � Remark 5.4. Equation (5.17) shows that the sequence 2−n ∑2n−1 m=0 ( xnm − 1 2 )2 increases with n and has limit ≤ 1 4 , for all (xnm) ∈ Z. Definition 5.5. We denote by Y ⊆ Z the subspace of all points satisfying the equivalent conditions of proposition 5.3. Now observe that on Y we have ‖(xnm)‖ 2 = x00. Hence for fixed (x ′ nm) the norm distance ‖(x′nm − x ′′ nm)‖ = √ x′00 + x ′′ 00 − 2〈(x ′ nm) , (x ′′ nm)〉 is continuous as a function of (x′′nm) on Yw. Therefore the weak topology and the Hilbert space topology coincide on Y . This subspace is closed with respect to the ∧-product, because for x, y ∈ Y we have (x ∧ y) ∧ (x ∧ y) = (x ∧ x) ∧ (y ∧ y) = x ∧ y, hence x ∧ y ∈ Y . Thus ∧ induces a continuous product on Y . Y is a weak Gδ in Z, in particular it is Polish. We can easily establish the density of Y in Z. For given R, N and (xnm) ∈ Z we will construct (ynm) ∈ Y with |xN m − yN m| ≤ 2 −R; then |xnm − ynm| ≤ 2−R for n ≤ N follows from (5.2). Pick numbers km ∈ N0 such that ∣ ∣xN m − km 2R ∣ ∣ ≤ 2−R. We now define yN +R,ℓ such that it assumes the value 1 exactly km times in the range m2R ≤ ℓ < (m+1)2R and is 0 otherwise. Observing (5.2) this defines (ynm) uniquely, and yN m = km 2R . Moreover, (ynm) ∈ Y because ynm − 1 2 = ±1 2 for n ≥ N + R. The group G∞ we encountered in section 3 acts continuously on Y . Suppose we are given a ladder of filtered permutations πn like in diagram (3.1), and consider the dual expansion m = ∑n−1 i=0 εn−i2 i of a number 0 ≤ m < 2n. Set (ε′1, . . . ε ′ n) := πn (ε1, . . . εn) and πn(m) := ∑n−1 i=0 ε ′ n−i2 i. Since xn,πn(m) = 1 2 ( xn+1,πn+1(2m) + xn+1,πn+1(2m+1) ) this induces an operation of G∞ on Z, Random selection of Borel sets 147 continuous in the topology of your choice. Condition 4 of proposition 5.3 is obviously invariant under G∞, therefore G∞Y ⊆ Y . 6. The isomorphism theorem Theorem 6.1. Let (Anm) be a resolution of either type, and define a map h : Y (µ) → Y , h(B) = (xnm) by xnm := 2 n ∫ B∩Anm 1 ϕg dµ (where ϕ and g are as in theorem 4.8) in case of type I, and xnm := 2 nµ (B ∩ Anm) in case of type II. h is a homeomorphism. The intersection corresponds to the ∧-product, and the complement of a set represented by (xnm) corresponds to (1 − xnm). Notice that in particular, x00 = ∫ B 1 ϕd dµ in case of type I and x00 = µ(B) in case of type II. Proof. We consider h as map h : Z(µ) → Z and observe that it is continuous if the spaces are equipped with either weak or Hilbert space topology, using the same choice for both spaces. We will show h (Y (µ)) ⊆ Y below. Let B = ⋃ i Anmi be a finite union of elements of the resolution (n is some fixed number); then xnm = 1 if m appears among the mi and xnm = 0 oth- erwise. The collection of all sequences of this form has been recognized as dense at the end of section 5, and by compactness (weak topology) we have h (Z(µ)) = Z. The equation h (f1f2) = h (f1) ∧ h (f2) is immediate for finite unions ⋃ i Anmi and hence for step functions ∑ i αiχAnmi , but since the map (f1, f2) 7→ h (f1) ∧ h (f2) is continuous as a map Z(µ)h × Z(µ)h → Zw and since the described step functions are norm dense, it must hold generally. In particular we obtain h(f ) = h ( f 2 ) = h(f ) ∧ h(f ) and therefore h(f ) ∈ Y if f ∈ Y (µ). Now assume h (f1) = h (f2). For abbreviation, let’s write µ̃ = 1 ϕg µ in case I and µ̃ = µ in case II, then by definition the 00-component of h equals h00(f ) = ∫ f dµ̃. Therefore ∫ f1f2dµ̃ = h00 (f1f2) = (h (f1) ∧ h (f2))00 = (h (f1) ∧ h (f1))00 = h00 ( f 21 ) = ∫ f 21 dµ̃ and similarly ∫ f1f2dµ̃ = ∫ f 22 dµ̃. Therefore ∫ (f1 − f2) 2 dµ̃ = 0. Hence h : Z(µ) ≈ Z is a homeomorphism (in either kind of topology). � The reader may notice that the homeomorphism h transports the “a.s.- action” of G∞ on X defined after theorem 4.8 to the action on Y from section 5. 7. Probability measures on the space of Borel sets For us, a probability measure on Y (µ) ≈ Y is a Borel probability measure ν on the compact space Z (weak topology) such that ν (Z \ Y ) = 0, this being computable by condition 4 of proposition 5.3. The definition of the compact space Z may be rephrased as follows: Denote by pn+1n : I 2n+1 → I2 n the map pn+1n (x0, . . . x2n+1−1) = ( x′0, . . . x ′ 2n−1 ) , x′m := 1 2 (x2m + x2m+1), Then Z = lim←−n I2 n taken along the maps pn+1n . Let pn : Z → I2 n be the natural projection, and consider the measures νn := pnν on 148 B. Günther I2 n . They determine ν uniquely [4, Ch.III,No.4,§5]. We arrive at the following characterization: Theorem 7.1. A probability measure ν on Y corresponds bijectively to a se- quence of probability measures νn = pnν on I 2n such that pn+1n νn+1 = νn and for all ε > 0 (7.1) lim n→∞ νn { 2−n 2n−1 ∑ m=0 ( xnm − 1 2 )2 ≤ 1 4 − ε } = 0 ν is invariant under G∞ if and only if each νn is invariant under Gn. The reader will have noticed that the sequence of numbers in (7.1) is de- creasing, and we just have to exclude a strictly positive limit. Also, the event in (7.1) is invariant under Gn because Gn simply permutes the coordinates xnm. We can now construct the measures νn inductively subject to the conditions above, starting with an arbitrary measure ν0 on the unit segment. νn+1 can be chosen Gn+1-invariant if νn is Gn-invariant. The inductive step requires the distribution of mass along the fibers of pn+1n , to which end we must surmount a difficulty displayed in figure 1. Assume ε > 0 and N > n are fixed. We say that a point (xk) ∈ I 2n with 2−n ∑2n−1 k=0 ( xk − 1 2 )2 ≤ 1 4 − ε is critical if the entire fiber ( pNn )−1 (xk) is contained in the ball 2 −N ∑2N −1 k=0 ( x′k − 1 2 )2 ≤ 1 4 −ε. Figure 1. Critical and non critical fibers of q : I2 → I Lemma 7.2. Let 0 < x < 1 and consider the “projection” q : Im → I, q (x1, . . . xm) = 1 m ∑m k=1 xk. Then max { ∑m k=1 ( xk − 1 2 )2 : 1 m ∑m k=1 xk = x } = m−1 4 + ( mx −⌊mx⌋− 1 2 )2 . Random selection of Borel sets 149 Proposition 7.3. (xk) ∈ I 2n is critical if and only if 2n−1 ∑ k=0 ( 2N−nxk − ⌊ 2N−nxk ⌋ − 1 2 )2 < 2n−2 − 2N ε. Hence it suffices to choose N large enough such that 2N−nε > 1 4 to exclude any critical points. Example 7.4. We define νN inductively using a function ϕ : I 2n ×I2 N → R+ such that ϕ (x, x′) 6= 0 ⇒ pNn (x ′) = x(7.2) ∀x ∈ I2 n : ∫ x′∈(pN n )−1(x) ϕ (x, x′) λ (dx′) = 1(7.3) where λ denotes Lebesgue measure on R2 N −2n . Then for any function f : I2 N → R we define (7.4) ∫ f dνN := ∫ ∫ ϕ (x, x′) f (x′) λ (dx′) νn (dx) One could for example take the following choice: A (x) :=    x ′ ∈ ( pNn )−1 (x) : 2−N 2N −1 ∑ k=0 ( x′k − 1 2 )2 > 1 4 − ε    (7.5) ϕ (x, x′) := { λ (A (x)) −1 x′ ∈ A (x) 0 x′ 6∈ A (x) (7.6) Notice that λ (A (x)) > 0 if N is chosen according to proposition 7.3. Then (7.7) νN  (x′k) ∈ I 2N : 2−N 2N −1 ∑ k=0 ( x′k − 1 2 )2 > 1 4 − ε   = 1 Example 7.5. Let’s consider our random Borel sets as stochastic process as follows: at time n+1 we split up the random variable xnm into two random vari- ables xn+1,2m, xn+1,2m+1 subject to the condition xnm = 1 2 (xn+1,2m + xn+1,2m+1), thus picking a point in the fiber displayed in figure 1. This forces the difference of the new values into the interval xn+1,2m−xn+1,2m+1 ∈ [−2 min (xnm, 1 − xnm) , 2 min (xnm, 1 − xnm)]. Except for the necessary scaling this is done inde- pendently and with identical distribution defined by a density function ϕn : [−1, +1] → R + subject to the conditions ϕn(−t) = ϕn(t), ∫ +1 −1 ϕn(t)dt = 1 and (7.8) lim n→∞    ∫ |t|≥1−ε ϕn(t)dt    2n = 1 for each ε > 0. For instance we could use ϕn(t) := cn exp ( (nt)2 ) , with suitable normalization factors cn. 150 B. Günther This leads to measures νn on I 2n with density functions Φn : I 2n → R + defined inductively as follows: Φn+1 (x0, . . . x2n+1−1) := Φn (x̃0, . . . x̃2n−1) 2n−1 ∏ i=1 ϕn ( x2m−x2m+1 2 min(x̃m,1−x̃m) ) 2 min (x̃m, 1 − x̃m) (7.9) x̃m := 1 2 (x2m + x2m+1)(7.10) where Φ0 : I → R + must satisfy ∫ 1 0 Φ(t)dt = 1, otherwise arbitrary. Gn- invariance is immediate, and the following lemma ensures the assumptions of theorem 7.1: Lemma 7.6. Suppose ε > 0 and δ > 0 are given. Choose (1) r ∈ N such that 2−r < 3ε 1−ε , (2) ϑ > 0 such that (1 − ϑ)r > 1 − δ, (3) N ∈ N such that for all n ≥ N the inequality [ ∫ |t|≥1−2−r−2ε ϕn(t)dt ]2n ≥ 1 − ϑ holds. Then for all n ≥ N +r we obtain νn ( (xk) ∈ I 2n : 2−n ∑2n−1 k=0 ( xk − 1 2 )2 ≥ 1 4 − ε ) > 1 − δ. Proof. Let us define points (xsm)0≤m<2s ∈ I 2s for n−r ≤ s ≤ n by downward induction xnm := xm and xs−1,m := 1 2 (xs,2m + xs,2m+1); we consider the coor- dinate xs−1,m as “parent” of the “children” xs,2m and xs,2m+1. This provides us with a set of trees with nodes labeled xsm, with root nodes xn−r,m and leave nodes xm. A leave node xm = xnm will be called “good” if at least one element of its chain of ancestors xs,ms for n − r ≤ s ≤ n satisfies ∣ ∣xs,ms − 1 2 ∣ ∣ ≥ 1 2 − 2−r−2ε. Since we must necessarily have ms2 n−s ≤ m < (ms + 1) 2 n−s and 2−(n−s) ∑(ms+1)2 n−s i=ms2n−s xi = xs,ms we conclude 1 2 − 2−r−2ε ≤ 2−(n−s) ∣ ∣ ∣ ∑(ms+1)2 n−s i=ms2n−s ( xi − 1 2 ) ∣ ∣ ∣ ≤ 2−(n−s) ∑(ms+1)2 n−s i=ms2n−s ∣ ∣xi − 1 2 ∣ ∣ ≤ 2−(n−s)−1 (2n−s − 1) + 2−(n−s) ∣ ∣xm − 1 2 ∣ ∣ and therefore ∣ ∣xm − 1 2 ∣ ∣ ≥ 1 2 − 2n−s−r−2ε ≥ 1 2 − ε 4 for every good leave node xm. We claim that with probability ≥ (1 − ϑ)r at most one leave node in each of the 2n−r trees is bad, more generally: at most one level ℓ node in each tree is bad with probability ≥ (1 − ϑ)ℓ for 1 ≤ ℓ ≤ r. We start by considering level 1, i.e. the 2n−r pairs of children xn−r+1,2m, xn−r+1,2m+1 of the root nodes. At least one child of a root node is good with probability ∫ |t|≥1−2−r−2ε ϕn(t)dt; hence each of the trees contains at most one bad node of level 1 with probability [ ∫ |t|≥1−2−r−2ε ϕn(t)dt ]2n−r ≥ (1 − ϑ)2 −r ≥ 1 − ϑ. By definition both children of a good level ℓ node are good level ℓ + 1 nodes, and we have at most 2n−r Random selection of Borel sets 151 bad ones at level ℓ with probability (1 − ϑ)ℓ. Each of these has at least one good child with probability ≥ 1 − ϑ by the same estimate as above, leading to a probability ≥ (1 − ϑ)ℓ+1 of our event at level ℓ + 1. We conclude that with probability ≥ 1 − δ at least 2n − 2n−r leave nodes xm satisfy ∣ ∣xm − 1 2 ∣ ∣ ≥ 1 2 − ε 4 and therefore ( xm − 1 2 )2 ≥ 1 4 − ε 4 . Hence 2−n ∑2n−1 m=0 ( xm − 1 2 )2 ≥ (1 − 2−r) ( 1 4 − ε 4 ) ≥ 1 4 − ε. � Example 7.7. We could opt to push the entire mass of I2 n onto its 1-skeleton. This choice will be discussed in depth in section 10. 8. Conditional expectation and variance The coordinates xnm in Y may be considered as random variables ξnm : Y → I with ξnm = 1 2 (ξn+1,2m + ξn+1,2m+1) and limn→∞ 2 −n ∑2n−1 m=0 ( ξnm − 1 2 )2 = 1 4 a.s. The intersection of random sets is represented by the ∧-product. We will be using a G∞-invariant probability measure on Y as constructed in sec- tion 7; furthermore we will assume that ξ00 equals the measure of our ran- dom set, so either type II resolutions have to be used or adjustment by a density function must be allowed. For two numbers 0 ≤ k 6= m < 2n we consider their dual expansions k = ∑n−1 i=0 δn−i2 i m = ∑n−1 i=0 εn−i2 i and define v(m, k) := min{i : εi 6= δi} = − lb |m − k|2. We prepare to answer question 1. Lemma 8.1. There exists a sequence of functions fn : I → I such that E (ξnm|ξ00) = ξ00(8.1) E ( ξ 2 nm|ξ00 ) = fn (ξ00)(8.2) E (ξnmξnk|ξ00) = 2fv(m,k)−1 (ξ00) − fv(m,k) (ξ00) if m 6= k(8.3) lim n→∞ fn = idI ν0-a.s.(8.4) Proof. Trivially, ξ00 is G∞-invariant. Invariance of ν therefore implies that E (ξnm|ξ00) is independent of m, and (8.1) follows from ξ00 = 2 −n ∑2n−1 m=0 ξnm. The same argument shows that E ( ξ2nm|ξ00 ) is independent of m, and (8.2) may be taken as definition of the function fn. (8.4) follows from limn→∞ 2 −n ∑2n−1 m=0 ξ 2 nm = ξ00 a.s. Again by G∞-invariance, E (ξnmξnk|ξ00) =: F (n, v(m, k), ξ00) for m 6= k depends only on n, v(m, k) and ξ00. Observing ξnmξnk = 1 4 (ξn+1,2mξn+1,2k + ξn+1,2m+1ξn+1,2k + ξn+1,2mξn+1,2k+1 +ξn+1,2m+1ξn+1,2k+1) and v(2m, 2k) = v(2m + 1, 2k) = v(2m, 2k + 1) = v(2m + 1, 2k + 1) = v(m, k) we can drop the first argument of F and write E (ξnmξnk|ξ00) = F (v(m, k), ξ00). 152 B. Günther In the equation ξ2nm = 2 2(n−N ) ( ∑(m+1)2N −n−1 ℓ=m2N −n ξN ℓ )2 = 22(n−N ) ( ∑(m+1)2N −n−1 ℓ=m2N −n ξ2N ℓ + ∑(m+1)2N −n−1 a6=b=m2N −n ξN aξN b ) for N ≥ n we count the number of pairs a, b with specific dyadic distance and obtain fn (ξ00) = 2 n−N fN (ξ00)+ ∑N r=n+1 2 n−rF (r, ξ00) = 2 n−N−1fN +1 (ξ00)+ ∑N +1 r=n+1 2 n−rF (r, ξ00) and hence 2fN (ξ00) = fN +1 (ξ00) + F (N + 1, ξ00). � Theorem 8.2. For two any two independent random variables A and B as- suming Borel subsets of X as values we obtain (8.5) E (µ(A ∩ B)|µ(A), µ(B)) = µ(A)µ(B) (8.6) Var (µ(A ∩ B)|µ(A), µ(B)) = ∞ ∑ n=0 2−n−1 [ 2fn (µ(A)) − fn+1 (µ(A)) − µ(A) 2 ] [2fn (µ(B)) −fn+1 (µ(B)) − µ(B) 2 ] Here Var (η|F) = E ( η2|F ) − E (η|F) 2 . The functions fn are those from lemma 8.1. In general context, this is about all that can be said concerning intersections of independent random sets. More specific results will be obtained in section 10. Proof. In coordinate representation, let the random Borel set A correspond to the process ξ′nm and B to the independent process ξ ′′ nm, then A∩B corresponds to ξnm = limN→∞ 2 n−N ∑(m+1)2N −n−1 k=m2N −n ξ′N kξ ′′ N k. Therefore E (ξ00|ξ ′ 00, ξ ′′ 00) = lim N→∞ 2−N 2N −1 ∑ k=0 E (ξ′N kξ ′′ N k|ξ ′ 00, ξ ′′ 00)(8.7) = lim N→∞ 2−N 2N −1 ∑ k=0 E (ξ′N k|ξ ′ 00) E (ξ ′′ N k|ξ ′′ 00)(8.8) = ξ′00ξ ′′ 00(8.9) and that proves (8.5). Similarly, (8.10) E ( ξ200|ξ ′ 00ξ ′′ 00 ) = lim N→∞ 2−2N   2N −1 ∑ k=0 E ( ξ′2N k|ξ ′ 00 ) E ( ξ′′2N k|ξ ′′ 00 ) + 2N −1 ∑ a6=b=0 E (ξ′N aξ ′ N b|ξ ′ 00) E (ξ ′′ N aξ ′′ N b|ξ ′′ 00)   Counting the number of pairs with specific dyadic distance and applying lemma 8.1 now proves (8.2). � Random selection of Borel sets 153 9. Impossibility of complete location invariance Through the action of G∞ our compactum X is “measure homogeneous”. For any two raster blocks Anm and Ank of the same level n there is a transfor- mation π ∈ G∞ taking the one to the other modulo a 0-set. Because of the fail- ure of 2-transitivity this does not extend to more general subsets, for instance, Anm = An+1,2m∪An+1,2m+1 cannot be transformed into An+1,2m∪An+1,2m+2. Consequently, question 2 in the introduction does not have a general answer derivable from knowledge of µ(A) alone. One could try to improve this state of affairs by picking a larger trans- formation group than G∞. This, however, turns out to be impossible ex- cept in trivial cases. If we had such a group whose operation was at least 2-transitive, then (8.3) would imply that 2fn−1 − fn is ν0-almost surely inde- pendent of n and therefore, observing (8.4), fn = idI ν0-a.s. for all n. But then E (ξnm (1 − ξnk) |ξ00) = ξ00 − fn (ξ00) = 0 ν0-a.s. for all n, m, k, which is only possible if all mass of ν0 is located at the two points 0 and 1. 10. The Sierpiński example Let E∞ ⊆ Z be the set of all points (xnm), such that at each level n, all xnm ∈{0, 1} with at most one permissible exception. Since any such sequence satisfies 2−n ∑2n−1 k=0 ( xnk − 1 2 )2 ≥ 1 4 − 2−n we actually have E∞ ⊆ Y . It can also be described as the set of all points of Z which are carried to the 1-skeleton of I2 n by the natural projection map pn : Z → I 2n , hence E∞ is a compact subspace of Y that could be called its 1-skeleton. Figure 2. Sierpiński’s universal curve Not the entire 1-skeleton of the cubes will be used by this construction. The projection p20 : I 2 → I maps the four vertices (0, 1, 0, 1), (1, 0, 0, 1), (0, 1, 1, 0) and (1, 0, 1, 0) to the interior point ( 1 2 , 1 2 ) ; these vertices must be avoided. Hence we define E1 as 1-skeleton of I 2 and, for n > 1, En ⊆ I 2n as the 154 B. Günther 1-skeleton of ( pnn−1 )−1 En−1. This inverse image consists of a collection of 2- dimensional faces, one for each edge of En−1, whose interior is disregarded. Hence En is obtained from En−1 by replacing each edge by the boundary of a square. E4 is displayed in figure 2. Evidently, E∞ = lim←−n En is homeomorphic to Sierpiński’s universal curve [7, Ex.I.1.11,p.9]. En consists of 4 n edges, labeled σab for a = (a1, . . . an) ∈ İ n and b = (b1, . . . bn) ∈ Z n 2 as follows: For any number 0 ≤ m < 2 n we construct the dual expansion m = ∑n−1 i=0 mn−i2 i; if now k is such that mk 6= bk but ∀ℓ < k : mℓ = bℓ, then we stipulate that the points (x0, . . . x2n−1) ∈ σab must satisfy the equation xm = ak. Identifying m with the sequence m = (m1, . . . mn) ∈ Z n 2 , the condition means in terms of the dyadic ultrametric distance in Z n 2 : xm = a− lb|m−b| 2 In particular, for any filtered permutation g ∈ Gn we have gσab = σa,gb. Observe that we obtain one equation for all coordinates except for xr with r = ∑n−1 i=0 bn−i2 i. Furthermore (10.1) pn0 (σab) = [ n ∑ k=1 ak2 −k, 2−n + n ∑ k=1 ak2 −k ] in particular, any such interval is covered 2n-fold. We want to construct a G∞-invariant probability measure on E∞, starting from a probability measure ν0 on the unit segment with 0 point masses and Supp ν0 = I. Equation (10.1) tells us how to distribute mass along the edge σab, where all such edges bearing the same first index a will be served evenly. A compatible sequence of measures on En is obtained, leading to a measure on E∞ ⊂ Y . For this measure we can give a much stronger version of theorem 8.2 and can determine the conditional distribution of µ(A ∩ B) given µ(A) and µ(B) completely: Theorem 10.1. Suppose two Borel sets A and A′ are randomly and indepen- dently chosen. If µ(A) and µ (A′) are given, then µ (A ∩ A′) can assume only countably many values. These occur with the following probabilities: (10.2) P ( µ (A ∩ A′) = a′n ∞ ∑ k=n+1 2−kak + an ∞ ∑ k=n+1 2−ka′k + n−1 ∑ k=1 aka ′ k2 −k ∣ ∣ ∣ µ(A) = t, µ (A′) = t′ ) = 2−n for all n ∈ N, where t = ∑∞ k=1 ak2 −k and t′ = ∑∞ k=1 a ′ k2 −k are dual expansions and the “Sierpiński” measure constructed above is used on Y (µ). Proof. Since ν0 is assumed not to have any point masses it is sufficient to give the proof for irrational numbers t, t′, where the dyadic expansion is unique. We define for b, b′ ∈ Zn2 : (10.3) Nn (b, b ′) := 2−n ∑ m6=b,b′ a− lb|m−b| 2 a′− lb|m−b′| 2 Random selection of Borel sets 155 then Nn converges almost surely to µ (A ∩ A ′). For the evaluation of the prod- uct on the right hand side of (10.3) we have to distinguish three cases (observe the special properties of the dyadic ultrametric): (1) |m − b|2 < |m − b ′|2 = |b − b ′|2 (2) |b − b′|2 < |m − b|2 = |m − b ′|2 (3) |m − b′|2 < |m − b|2 = |b − b ′|2 Observing # { m ∈ Zn2 | |m|2 = 2 −k } = 2n−k we obtain (10.4) 2nNn (b, b ′) = a′ − lb|b−b′| 2 ∑ 0<|m−b|2<|b−b ′| 2 a− lb|m−b|2 + ∑ |m−b|2=|m−b ′| 2 >|b−b′| 2 a− lb|m−b|2 a ′ − lb|m−b|2 +a− lb|b−b′| 2 ∑ 0<|m−b′| 2 <|b−b′| 2 a ′ − lb|m−b′| 2 (10.5) = a′ − lb|b−b′| 2 ∑ 0<|m|2<|b−b ′| 2 a− lb|m|2 + a− lb|b−b′|2 ∑ 0<|m|2<|b−b ′| 2 a′ − lb|m|2 + ∑ |m|2>|b−b ′| 2 a− lb|m|2 a ′ − lb|m|2 (10.6) = a′ − lb|b−b′| 2 ∑ k>− lb|b−b′| 2 2n−kak + a− lb|b−b′| 2 ∑ k>− lb|b−b′| 2 2n−ka′k + ∑ k<− lb|b−b′| 2 2n−kaka ′ k The theorem follows. � 11. On the relation of random closed and random Borel sets In the introduction it has been emphasized that our approach to random Borel sets is not an extension of the theory of random closed sets. In this section we are going to investigate the relation. Let T = 2X denote the hyperspace of X, i.e. the space of non void closed subsets carrying the Vietoris topology. Since any closed subset is Borel we obtain a natural, non continuous function q : T → Y (µ). Proposition 11.1. There exists a finer topology on T generating the same Borel sets, turning T into a Polish space and q : T → Y (µ) into a continuous map. In particular, q : T → Y (µ) is measurable with respect to the Vietoris topology. Proof. i) For any fixed B ∈ Y (µ) the graph Γ (fB) ⊆ T × Y (µ) of the upper semicontinuous function fB : T → R, fB(A) := µ (A ∩ B) is a Gδ, hence Polish. For fB is the infimum of a decreasing sequence of continuous functions ϕn ↓ fB [2, Ch.IX,§1.6,Prop.5] and Γ (fB) = ⋂ n { (x, y) ∈ T × Y (µ) ∣ ∣fB(x) − 1 n < y < ϕn(x) + 1 n } . 156 B. Günther ii) For any dense sequence (Bn)n∈N in Y (µ) the graph Γ(F ) of the function F : T → RN with coordinates fBn is Polish because it is homeomorphic to ∏ n Γ (fBn ). iii) The graph Γ ( F̃ ) of the function F̃ : T → RY (µ) with coordinates fB is Polish; we show that it is homeomorphic to Γ(F ). The restriction from all Borel sets to the sequence (Bn)n∈N provides us with a natural (hence contin- uous) projection map π : Γ ( F̃ ) → Γ(F ), π ( A, F̃ (A) ) = (A, F (A)) which is bijective. To show that the inverse π−1 is bijective too it suffices to prove that for each Borel set B the function gB : Γ(F ) → R, gB (A, F (A)) = fB(A) is continuous. This is evidently true if B is an element of our dense se- quence, because then fB(A) is simply the B-coordinate of F (A). In the gen- eral situation we select a subsequence (Bnk )k∈N of Borel sets converging to B. Then ∣ ∣ ∣ gB (A, F (A)) − gBnk (A, F (A)) ∣ ∣ ∣ = ∣ ∣ ∣ fB(A) − fBnk (A) ∣ ∣ ∣ = |µ (A ∩ B) −µ (A ∩ Bnk )| ≤ µ (B△Bnk ) and therefore limk→∞ gBnk = gB uniformly. iv) The graph Γ(q) ⊆ T × Y (µ) of q : T → Y (µ) is Polish and therefore a Gδ in T × Y (µ). We claim Γ(q) ≈ Γ ( F̃ ) and have to show that the map (A, q(A)) ↔ ( A, F̃ (A) ) is continuous in both directions. For any Borel set B the B-coordinate of ( A, F̃ (A) ) equals fB(A) = µ (A ∩ B) which is a continuous function of q(A) because intersection is continuous on Y (µ). For the reverse it is sufficient to observe d (q(A), q (A0)) = µ (A△A0) = f∁A0 (A)−fA0 (A) + µ (A0). v) We now identify T with the graph Γ(q) by means of the bijection i : T ≈ Γ(q) defined by i(A) = (A, q(A)) and consider the topology on T obtained by transporting back the topology of Γ(q) over i. Since i−1 (Γ ∩ (U × Y (µ))) = U the new topology is finer than the Vietories topology. Under this identification the map q corresponds to the projection map Γ →֒ T × Y (µ) → Y (µ) and is therefore continuous. It remains to show that for any Borel subset B ⊆ Γ(q) the inverse i−1(B) ⊆ T is Borel with respect to the Vietoris topology. We observe that the natural projection π : T × Y (µ) → T provides us with a continuous bijection π : Γ(q) → T and our inverse image i−1(B) = q(B) is the continuous bijective image of a Borel set. We now observe that the spaces T and Γ(q), being Polish, are in particular Lusin [2, Ch.IX,§6.4,Prop.12]. Then B as Borel subset of a Lusin space is a Lusin space itself [2, Ch.IX,§6.7,Thm.3], hence its continuous bijective image π(B) is again a Lusin space and therefore Borel. � Proposition 11.1 allows to consider any random closed set, i.e. any random variable with values in T , as random Borel set by composition with the mea- surable map q : T → Y (µ). However, this may involve a loss of information by generating a coarser event algebra. It can be shown that no information is lost if and only of there exists a subset B ⊆ T of probability 1 such that q is one-to-one on B. Since this applies for instance to random closed sets which are almost certainly regular closed [11, Def.4.29,p.63] this covers quite a Random selection of Borel sets 157 few examples. The obvious counterexamples are random closed sets that have almost certainly measure 0, such as random finite sets or Buffon’s needle. On the other hand, random Borel sets are better adapted to image processing than random closed sets, for instance because of their relation to wavelets (see below). It is no accident that random Borel sets cannot distinguish sets that differ only by a 0-set, since such a small difference would not be visible in an image. Lemma 11.2. The sequence of vectors e(N k) = ( e (N K) nm ) n≥0,0≤m<2n with N ≥ 0 and 0 ≤ k < 2N−1, defined by (11.1) e(N k)nm =          1 N = 0, k = 0 2 N −1 2 n ≥ N > 0, k2n+1−N ≤ m < ( k + 1 2 ) 2n+1−N −2 N −1 2 n ≥ N > 0, ( k + 1 2 ) 2n+1−N ≤ m < (k + 1)2n+1−N 0 else constitutes a complete ON-system in the Hilbert space considered in section 5. For any vector x = (xnm) we have 〈 x, e(00) 〉 = x00 and 〈 x, e(N k) 〉 = 2− N +1 2 (xN,2k − xN,2k+1) for N > 0. Proof. Observing that our system of numbers can satisfy e (N k) n,2m − e (N k) n,2m+1 6= 0 only if n = N > 0 and m = k all computations are rather straightforward. (5.1) checks easily, and so does ∥ ∥e(N k) ∥ ∥ 2 = 1. The relations 〈 x, e(00) 〉 = x00 and 〈 x, e(N k) 〉 = 2− N +1 2 (xN,2k − xN,2k+1) for N > 0 are obvious. This immediately implies orthonormality; furthermore any vector x perpendicular to all e(N k) must satisfy x00 = 0, xN,2k = xN,2k+1 for all N > 0 and all k as well as (5.1) and hence x = 0. � From the lemma above it should be clear that our approach to random Borel sets is essentially an expansion in terms of the ON-base e(N k). On the unit seg- ment this corresponds to the L2-functions 2− N +1 2 ( χ[ 2k 2N , 2k+1 2N [ − χ[ 2k+1 2N , 2k+2 2N [ ) , i.e. to the Haar wavelet [18, Def.1.1] or rather to those constituents of the Haar wavelet that live on the unit segment. References [1] P. Alexandroff and H. Hopf, Topologie, Chelsea, 1972. [2] N. Bourbaki, General Topology, Elements of Mathematics, Hermann and Addison- Wesley, 1966. [3] N. Bourbaki, Topological Vector Spaces I-V, Elements of Mathematics, Springer, 1987. [4] N. Bourbaki, Integration I (Chapters 1-6), Elements of Mathematics, Springer, 2004. [5] P. R. Halmos,Measure Theory, volume 18 of GTM, Springer, 1974. [6] F. Hausdorff, Mengenlehre, Göschens Lehrbücherei. Walter de Gruyter & Co., 2nd edi- tion, 1927. [7] S. B. Nadler Jr, Continuum Theory, volume 158 of Pure and Applied Mathematics, Marcel Dekker, Inc., 1992. 158 B. Günther [8] A. S. Kechris, Classical descriptive set theory, volume 156 of GTM, Springer, 1995. [9] S. Li, Y. Ogura and V. Kreinovich, Limit Theorems and Applications of Set-Valued and Fuzzy Set-Valued Random Variables, Theory and Decisions Library, Kluwer, 2002. [10] J. Lindenstrauss, A short proof of liapounoff’s convexity theorem, J. Math. Mech. 15 (1966), no. 6, 971–972. [11] I. Molchanov, Theory of random sets, Probability and Its Applications. Springer, 2005. [12] H. E. Robbins, On the measure of random set, Ann. Math. Statist. 15 (1944), 70–74. [13] H. E. Robbins, On the measure of random set II, Ann. Math. Statist. 16 (1945), 342–347. [14] C. Rosendal, The generic isometry and measure preserving homeomorphism are con- jugate to their powers, Fund. Math. 205 (2009), 1–27. [15] R. Schneider and W. Weil, Stochastic and Integral Geometry, Probability and its Ap- plications, Springer, 2008. [16] W. Sierpiński, Sur les fonctions d’ensemble additives et continues, Fund. Math. 3 (1922), 240–246. [17] F. Straka and J. Štěpán, Random sets in [0,1], In J. Visek and S. Kubik, editors, Infor- mation theory, statistical decision functions, random processes, Prague 1986, volume B, pages 349–356, Reidel, 1989. [18] P. Wojtaszczyk, A Mathematical Introduction to Wavelets, volume 37 of Student Text, London Mathematical Society, 1997. Received April 2010 Accepted September 2010 B. Günther (dr.bernd.guenther@t-online.de) DB Systel GmbH, Development Center Databases T.SID32, Hahnstraße 40, 60528 Frankfurt am Main, Germany Random selection of Borel sets. By B. Günther