@ Applied General Topology c© Universidad Politécnica de Valencia Volume 13, no. 1, 2012 pp. 61-79 Random selection of Borel sets II Bernd Günther Abstract The theory of random Borel sets as presented in part I of this paper is developed further. Special attention is payed to the reconstruction of the topology of the underlying space from our presentation of the measure algebra, to an analysis of capacities in context of random Borel sets, to inspection processes on the unit segment and to the Markov process of random allocation. 2010 MSC: Primary 60D05; Secondary 54H05 Keywords: Random Borel sets 1. Introduction We present four topics from the theory of random Borel sets as laid out in the first part of this paper: 1. It is well known [5, thm.13.1] that the topology of a Polish space can be modified such that an arbitrarily prescribed Borel subset is turned into a closed and open subset without modifying the Borel algebra as a whole, and in consequence it is not possible to characterize open subsets or closed subsets in the standard Borel algebra by invariant properties. In spite of this defi- ciency, we are going to demonstrate in section 2 that our “dyadic” algebra Y [2, §5] provides us with a special representation of the standard Borel algebra that easily distinguishes open sets from general Borel sets. This discrepancy should not come as a surprise, because Y has built in G∞-invariance [2, §3] but fails the invariance under the larger group consisting of all measure preserv- ing homeomorphisms [2, §9], characteristic for the standard measure algebra. Evidently, Y has a more rigid structure, and the isomorphism [2, §6] forgets certain properties. 62 B. Günther 2. In section 3 we investigate the possibility to apply Choquet capacities in context of random Borel sets in a manner similar to the closed case. This turns out to be infeasible. However, a simple description of random Borel sets in terms of stochastic processes can be given, leading to an elegant and abstract characterization. For practical and numerical purposes the “dyadic algebra” is superior, as will be seen for instance in section 5. 3. In [8] Straka and Štěpán used inspection processes to deal with random Borel sets on the unit segment, but they seem to have overlooked the fact that not every inspection process corresponds to a random set. The problem will be dealt with in section 4. 4. The combinatorial concept of random allocation describes the proba- bilistic allotment of objects to certain places and the observation of the time evolution of their distribution [6]. In each round one may allocate a single object, or a fixed finite number of objects, or an infinite set. An example for the second case consists of the numbered lots drawn in each round in a lottery drawing, where one may observe which numbers appeared at least once after r rounds. Thus in the i-th run we select a finite random set Bi consisting of the numbers drawn, and observe the growth of the accumulated set Cr := ⋃r i=1 Bi over the Markov time r. If the lottery is fair, the random variable Bi assumes each set containing the correct number of elements with equal probability. In more general examples, one may relax the assumption that the sets Bi have a predetermined size but still require all sets of the same size to have the same probability. We may play the same game using infinite sets for Bi, in our case Borel sets. Having equal probability for all sets of the same measure would require location independence of the distribution of Bi, but we know from [2, §9] that the best we can achieve is G∞-invariance. In section 5 we compute expected value and second moment of the size of the accumulated sets Cr in a numerically feasible way. This paper uses the same terms and notations as part I; in particular X de- notes a compact metric space carrying a non atomic measure μ with Supp(μ) = X; Y (μ) denotes the Borel algebra of μ-measurable sets, identifying two sets if they differ only in a 0-set. Y denotes the “coordinate representation” of Y (μ) introduced in [2, §5]. 2. Reconstruction of the topology The isomorphism between the algebras Y and Y (μ) was proved using reso- lutions of either of two species, labelled type I and type II [2, Def.4.4], and it was already observed that the type I resolutions establish a close link between measure and topology. This is illustrated by the following proposition: Proposition 2.1. If a type I resolution is used for the isomorphism theorem [2, Thm.6.1], then: i) The Borel set corresponding to a sequence (xnm) can be chosen as open if and only if xnm = supN≥n 2 n−N# { k : 2N−nm ≤ k < 2N−n+1,xNk = 1 } for Random selection of Borel sets II 63 all n,m. ii) The Borel set corresponding to a sequence (xnm) can be chosen as closed if and only if xnm = infN≥n 2n−N# { k : 2N−nm ≤ k < 2N−n+1,xNk > 0 } for all n,m. iii) A Borel set is Jordan measurable (i.e. its boundary is a 0-set [3, Ch.3]) if and only if it satisfies both (i) and (ii). Proof. To prove (i) let us assume xnm = supN≥n 2 n−N# { k : 2N−nm ≤ k < 2N−n+1,xNk = 1 } for all n,m and set Bn := (⋃ m:xnm=1 Anm )◦ . We observe Bn+1 ⊇ Bn because xnm = 1 ⇒ xn+1,2m = xn+1,2m+1 = 1 and consider the open set B := ⋃ n Bn. Therefore μ(Anm ∩ B) = limN→∞ μ(Anm ∩ BN) = limN→∞ ∑ k:xNK=1,2N−nm≤k<2N−n+1m μ(ANK) = limN→∞ 2 −N# {k : xNK = 1, 2N−nm ≤ k < 2N−n+1m } = 2nxnm hence the sequence (xnm) corresponds to the open set B under our isomorphism theorem (if necessary we replace μ by 1 ϕ μ). Conversely, if B is open we can use inner regularity to find a compact subset K ⊆ Anm ∩ B whose measure is as close to that of Anm ∩ B as we please and then choose N ≥ n such that maxk diamANk is a Lebesgue number for the open covering consisting of B and �K. The limit condition follows. (ii) is dual to (i) and does not require separate proof. Sufficiency of (iii) follows from (i) and (ii). It remains to establish necessity, so let us consider a sequence (xnm) satisfying both (i) and (ii). We construct the sets Cn :=(⋃ m:xnm=0 Anm )◦ and C := ⋃ n Cn, and just like above we see that C is an open set representing the complement of B, i.e. μ ( B��C ) = 0. But by construction B ∩ C = ∅ and therefore ∂B ⊆ � (B ∪ C) = B��C must be a 0-set. � Remark 2.2. This means that (xnm) represents an open set if and only if limN→∞ 2n−N ∑ 2N−nm≤k<2N−n+1m 0 0 for all m,n, and remark 2.2 implies 0 = limN→∞ 2n−N ∑ 2N−nm≤k<2N−n+1m (1 − x′Nk) = 1 − x′nm for all 64 B. Günther m,n, in particular μ(A′) = 1 since x′00 = 1. Hence �A′ is an open subset of X with measure 0, and since Supp(μ) = X we must have A′ = X, i.e. A is dense. Similarly, if the element (x′′nm)0≤m<2n,n∈N0 ∈ Y represents an open subset A′′ contained in A, then x′′nm ≤ xnm < 1 and remark 2.2 implies 0 = limN→∞ 2n−N ∑ 2N−nm≤k<2N−n+1m x ′′ Nk = x ′′ nm, in particular μ(A ′′) = 0 since x′′00 = 0. Since A ′′ is open it must be empty and A has empty interior. � 3. The capacity problem Our construction of probability measures for random Borel sets [2, Thm.7.1] requires resolutions and thus utilizes a particular “coordinate representation” of the standard Borel algebra. In contrast, random closed sets can be defined by capacities in a coordinate independent way. A coordinate free presentation can be given in the Borel setting too, but rather different from the closed case. We start by preparing some tools. 3.1. Finite partitions. Definition 3.1. A finite partition B = {B1, . . .Bn} of X is a finite set of Borel subsets Bi ⊆ X such that (1) ∀i : μ(Bi) > 0 (2) ∀i �= j : μ(Bi ∩ Bi) = 0 (3) ∑ i μ(Bi) = 1. We set mesh B := maxi diamBi. We observe that the mesh of a partition is defined by metric properties, not by set theoretic ones. Proposition 3.2. For any two Borel subsets A,B ⊆ X and each ε > 0 there exists δ > 0 such that for each finite partition C = {C1, . . .Cn} of X with mesh C < δ (3.1) ∣∣∣∣∣μ(A ∩ B) − ∑ i μ(A ∩ Ci)μ(B ∩ Ci) μ(Ci) ∣∣∣∣∣ < ε Proof. For every finite partition C of X we define an orthogonal projection operator TC in the Hilbert space L2(μ) by (3.2) TCf := ∑ i ∫ Ci fdμ μ(Ci) χCi A short calculation shows that TC is the orthogonal projection onto the finite dimensional subspace spanned by the indicator functions χCi. Now suppose ε > 0 and a continuous function f are given; we choose δ > 0 such that d(x,y) < δ ⇒ d(f(x),f(y)) < ε, observing that f must be uni- formly continuous by compactness of X. Then for mesh C < δ we must have |TCfx − fx| < ε uniformly and therefore ‖TCf − f‖2 ≤ ε. Now, finally, suppose A and B are given and choose continuous function f,g such that ‖χA − f‖2 < ε and ‖χB − g‖2 < ε; then using the case above pick Random selection of Borel sets II 65 δ > 0 such that ‖TCf − f‖2 ≤ ε and ‖TCg − g‖2 ≤ ε for mesh C < δ. Ob- serving ‖TC‖ ≤ 1 we obtain ‖TCχA − χA‖2 ≤ ‖TC (χA − f)‖2 + ‖TCf − f‖2 + ‖f − χA‖2 ≤ ‖χA − f‖2 + ‖TCf − f‖2 + ‖f − χA‖2 ≤ 3ε and similarly ‖TCχB − χB‖2 ≤ 3ε. Now |〈χA,χB〉 − 〈TCχA,TCχB〉| ≤ |〈χA − TCχA,χB〉| + |〈TCχA,χB − TCχB〉| ≤ ‖χA − TCχA‖2 ‖χB‖2 + ‖TCχA‖2 ‖χB − TCχB‖2 ≤ 6ε. Since 〈χA,χB〉 = μ(A ∩ B) and 〈TCχA,TCχB〉 = ∑ i μ(A∩Ci)μ(B∩Ci) μ(Ci) condi- tion (3.1) follows. � Corollary 3.3. For every Borel subset A ⊆ X and each ε > 0 there exists δ > 0 such that for each finite partition B = {B1, . . .Bn} with mesh B < δ (3.3) 0 ≤ μ(A) − ∑ i μ(A ∩ Bi)2 μ(Bi) < ε Proof. ∑ i μ(A∩Bi)2 μ(Bi) = ∑ i μ(Bi) ( μ(A∩Bi) μ(Bi) )2 ≤ ∑i μ(Bi) μ(A∩Bi)μ(Bi) = ∑i μ(A ∩ Bi) = μ(A). The rest follows from an application of proposition 3.2 to the case A = B. � Observe that (3.4) Mεδ := ⋂ B:mesh B<δ { A ∣∣∣∣∣ ∑ i μ(A ∩ Bi)2 μ(Bi) ≥ μ(A) − ε } ⊆ Y (μ) is an event because the uncountable intersection may be replaced by an inter- section over a dense countable family of finite partitions without affecting the result. Our proposition states ∀ε > 0 : ⋃n Mε 1n = Y (μ). 3.2. Generating systems of the Borel algebra. The following proposition clearly distinguishes random Borel sets from their closed counterpart, because in the closed setting the subsets of the form YB = { A ⊆ X ∣∣∣A ∩ B �= ∅} gen- erate the Borel algebra and thus pave the way for capacities: Proposition 3.4. The σ-algebra generated by the subsets (3.5) YB := { A ⊆ X ∣∣∣μ(A ∩ B) > 0} ⊆ Y (μ) with B ranging over all Borel subsets of X is strictly smaller than the Borel alge- bra on Y (μ); for instance it does not contain the event M := { A ⊆ X ∣∣∣μ(A) > 12 } . Proof. Suppose the contrary. Then by [4, Ch.I,§5,Thm.D] there exists a se- quence of Borel sets Bn such that M is contained in the σ-algebra F generated by the countably family of events YBn. Consider A ′ ∈ M, i.e. A′ ⊆ X with μ(A′) > 1 2 . Clearly F cannot distinguish A′ from any other subset A′′ such that for all n: μ(A′ ∩ Bn) > 0 ⇔ μ(A′′ ∩ Bn) > 0; hence any such subset must be contained in M and therefore should satisfy μ(A′′) > 1 2 . Set Γ := { n ∣∣∣μ(A′ ∩ Bn) > 0} ⊆ N. Using the intermediate value theorem for non atomic measures we can find a subset Cn ⊆ A′ ∩Bn for each n ∈ Γ, such 66 B. Günther that 0 < μ(Cn) < 2 −n−2, and then in particular μ (⋃ n∈Γ Cn ) < 1 4 and thus A′′ := ⋃ n∈Γ Cn ⊆ A′ with μ(A′′) < 14. For n ∈ Γ we have A′′ ∩ Bn ⊇ Cn and therefore μ(A′′ ∩ Bn) > 0, while for n ∈ N\Γ we obtain A′′ ∩Bn ⊆ A′ ∩Bn and μ(A′ ∩ Bn) = 0. From the above we conclude A′′ ∈ M, a contradiction. � Proposition 3.5. The Borel algebra on Y (μ) is generated by the events (3.6) Yt,B := { A ⊆ X ∣∣∣μ(A ∩ B) < t} ⊆ Y (μ) with B ranging over all Borel subsets of X and 0 < t < 1. Actually it is sufficient to restrict B to a dense subset of Y (μ) (such as all open or all compact subsets of X) and t to a dense subset of ]0,1[. Proof. Define metric d on Y (μ) by d(A,B) := max (μ(A \ B) ,μ(B \ A)). Since 1 2 μ(A�B) ≤ d(A,B) ≤ μ(A�B) this generates the customary topol- ogy. Since μ(B \ A) = μ(B) − μ(B ∩ A) we obtain μ(B \ A) < ε ⇔ ∀δ > μ(B)−ε : μ(A ∩ B) < δ. Hence the ε-ball around B with respect to the metric d is given by { A ⊆ X ∣∣∣μ (A ∩ �B) < ε} ∩ ⋂ n { A ⊆ X ∣∣∣μ(A ∩ B) < μ(B) − ε + 1 n } = Yε,�B ∩ ⋂ n Yμ(B)−ε+ 1 n ,B (3.7) Therefore these sets generate the topology and hence all Borel sets in Y (μ). � Unfortunately, the events Yt,B do not constitute a ring, i.e. they are are incompatible with unions or intersections. Therefore the construction of mea- sures will require us to consider finite intersections: Yt1,...tr,B1,...Br := { A ⊆ X ∣∣∣μ(A ∩ B1) < t1 and . . .μ(A ∩ Br) < tr} = r⋂ i=1 Yti,Bi. 3.3. The probability space. For every finite partition B = {B1, . . .Bn} we consider the map qB : Y (μ) → In(3.8) A �→ ( μ(A ∩ B1) μ(B1) , . . . μ(A ∩ Bn) μ(Bn) ) (3.9) and denote by νB the image of the probability measure on Y (μ) on In under the map qB. In will be equipped with the metric dB ( tj, t ′ j ) := √∑ j μ(Bj) ( tj − t′j )2 . Random selection of Borel sets II 67 Consider a finite partition C = {C1, . . .Cm}. Then for any other finite partition B = {B1, . . .Bn}, not necessarily a refinement of C, we define a map qBC : I n → Im(3.10) (t1, . . . tn) �→ (u1, . . .um)(3.11) ui := ∑ j μ(Bj ∩ Ci) μ(Ci) tj(3.12) Notice that the map qBC is a contraction: by convexity for each i:⎛ ⎝∑ j μ(Bj ∩ Ci) μ(Ci) ( tj − t′j )⎞⎠ 2 ≤ ∑ j μ(Bj ∩ Ci) μ(Ci) ( tj − t′j )2 , hence dC ( qBC (tj) ,q B C ( t′j )) = √∑ i μ(Ci) (∑ j μ(Bj ∩Ci) μ(Ci) ( tj − t′j ))2 ≤√∑ i,j μ(Ci) μ(Bj∩Ci) μ(Ci) ( tj − t′j )2 = √∑ j μ(Bj) ( tj − t′j )2 = dB ( tj, t ′ j ) . B = {B1, . . .Bn} is called refinement of C = {C1, . . .Cm} if for any two indices i,j either μ(Ci ∩ Bj) = 0 or μ(Ci \ Bj) = 0. Under this condition equation (3.12) assumes the form ui = ∑ j:μ(Ci∩Bj) =0 μ(Bj) μ(Ci) tj. If B is a refinement of C and A an arbitrary finite partition, then qBC qAB = qAC and qBC qB = qC Theorem 3.6. The system of measures νB satisfies the following two condi- tions: (1) qBC νB = νC for every refinement B of C. (2) For each ε > 0 there exists δ > 0 such that (3.13) νB ( (tk) ∈ In : ∑ k μ(Bk) ( tk − 1 2 )2 > 1 4 − ε ) > 1 − ε for each finite partition B = {B1, . . .Bn} with mesh B < δ. Conversely: every system of probability measures satisfying these properties derives from a probability measure P on Y (μ) as system of images νB = qBP. Proof. We extend definition (3.8) to a map qB : Z(μ) → In, qB(f) = (t1, . . . tn), tk := 1 μ(Bk) ∫ Bk fdμ; by reasons of compactness this is easily checked to be an in- verse limit representation. It now suffices to show that the subset Y (μ) ⊆ Z(μ) corresponds precisely to the set M of all those f ∈ Z(μ), whose represen- tations (t1, . . . tn) = qB(f) satisfy the condition ∀ε > 0∃δ > 0∀ mesh B < δ : ∑ k μ(Bk) ( tk − 12 )2 > 1 4 − ε. corollary 3.3 readily implies Y (μ) ⊆ M. But for f ∈ Z(μ) \ Y (μ) we can find ε > 0 with μ(ε < f < 1 − ε) > ε; let C = {C1,C2,C3} be the partition C1 := {f ≤ ε}, C2 := {ε < f < 1 − ε}, C3 := {f ≥ 1 − ε}. If B is any refinement of C, then (t1, . . .tn) = qB(f) satis- fies ∑ k μ(Bk) ( tk − 12 )2 ≤ 1 4 − ε2 and therefore f �∈ M. � 68 B. Günther Example 3.7. Suppose we are given a random closed set A with capacity functional τ(K) = P (A ∩ K �= 0). Considering this as random Borel set we get for any finite partition B = {B1, . . .Bn} the corresponding capacity as νB ( ∏ i [0, ti[) = P (∀i : μ(A ∩ Bi) < tiμ(Bi)) = 1 − sup { τ ( ⋃ i Ki) ∣∣∣∀i : Ki compact,Ki ⊆ Bi,μ(Ki) > (1 − ti) μ(Bi)}. 3.4. The process aspect. We may now describe random Borel sets as sto- chastic processes as follows: Theorem 3.8. For any random Borel set A consider the process assigning to each compact set (each open set, each Borel set) K the random variable YK := μ(A∩K) μ(K) with values in I. (For μ(K) = 0 we may define YK arbitrarily or disregard it entirely.) Then: (1) YK1∪K2 = μ(K1) μ(K1∪K2)YK1 + μ(K2) μ(K1∪K2)YK2 provided K1 ∩ K2 = ∅. (2) For each finite partition K = {K1, . . .Kn} consider the sum ∑ i μ(Ki)Y 2 Ki . Then ∑ i μ(Ki)Y 2 Ki → YX a.s. if mesh K → 0. (Notice YX = μ(A).) Conversely, any process satisfying these two properties derives from a random Borel set, whose distribution is uniquely characterized by these properties. The proof is a direct application of theorem 3.6 making a few observations: Consider two sets K,L. Then |YK − YL| = ∣∣∣ μ(K\L)μ(K) YK\L + μ(K∩L)μ(K) YK∩L− μ(L\K) μ(L) YL\K − μ(K∩L)μ(L) YK∩L ∣∣∣ ≤ μ(K\L)μ(K) + μ(L\K)μ(L) + μ(K ∩ L) ∣∣∣ 1μ(K) − 1μ(L) ∣∣∣. This immediately implies YK = YL if μ(K�L) = 0; moreover YKn → YK uniformly if Kn → K in the topology of Y (μ). Since the compact sets and the open sets are dense in Y (μ) they suffice to define YB for any Borel set B as uni- form limit. Furthermore, just like in the proof of [2, Lem.4.1] it can be shown that the compact sets, whose boundary is of measure 0, (or the open sets, whose boundary is of measure 0) are dense in Y (μ). This readily implies that any finite partition of the compact space X into Borel sets can be arbitrarily closely approximated by a finite partition into compact sets or into open sets. Condi- tion (2) means ∑ i μ(Ki) ( YKi − 12 )2 = ∑ i μ(Ki)Y 2 Ki − ∑i μ(Ki)YKi + 14 =∑ i μ(Ki)Y 2 Ki − YX + 14 and is preserved by the extension to Borel sets. Now observe corollary 3.3. Then define the measure νB as the joint distribution of the random variables YB1, . . .YBn. Lemma 3.9. For any Borel set B, the random variable YB is the a.s.-limit∑ i μ(Bi) μ(B) Y 2Bi → YB with B = {B1, . . .Bn} ranging over the partitions of B such that mesh B → 0. Proof. Since 0 ≤ YBi we have ∑ i μ(Bi) μ(B) Y 2Bi ≤ ∑ i μ(Bi) μ(B) YBi = YB for each partition of B. Now set C := �B and supplement every partition of B with one of C to obtain a partition of X without increasing the mesh. Then also∑ i μ(Ci) μ(C) Y 2Ci ≤ YC. Furthermore μ(B) ∑ i μ(Bi) μ(B) Y 2Bi + μ(C) ∑ i μ(Ci) μ(C) Y 2Ci → YX by theorem 3.8, which can happen only if ∑ i μ(Bi) μ(B) Y 2Bi → YB and ∑ i μ(Ci) μ(C) Y 2Ci → YC. � Random selection of Borel sets II 69 Proposition 3.10. For any two random Borel sets represented by processes YK resp. Y ′ K we can define a new process (3.14) YK ∧ Y ′K := lim ∑ i μ(Ki) μ(K) YKiY ′ Ki as a.s.-limit taken over all finite partitions K = {K1, . . .Kn} of K such that mesh K → 0. This new process represents the intersection of the two given random Borel sets. Proof. Apply proposition 3.2. � Lemma 3.11. Two random Borel sets represented by processes YK resp. Y ′ K are independent as random variables if and only if for any two Borel sets (com- pact sets, open sets) K and L the random variables YK and Y ′ L are independent. Proof. Apply proposition 3.5. � Definition 3.12. A random Borel set represented by a process YK is called isotropic, if for every ε > 0 there exists a finite partition B = {B1, . . .Bn} of X with mesh B < ε, such that for any two indices 1 ≤ i �= j ≤ n there exists a permutation π ∈ Sn with π(i) = j, such that the joint distribution of YKπ(1), . . .YKπ(n) coincides with the joint distribution of YK1, . . .YKn. Notice that under the condition above in particular E (YKi) = E ( YKj ) for any two indices i,j, and since YX = ∑ i μ(Ki)YKi we obtain E (YX) =∑ i μ(Ki)E (YKi) = E ( YKj ) ∑ i μ(Ki) = E ( YKj ) for each j. Proposition 3.13. Consider two independent random Borel sets A and B, at least one of which is assumed isotropic. Then E (μ(A ∩ B)) = E (μ(A)) E (μ(B)). Proof. Assume Y ′K is isotropic and apply proposition 3.10: E (μ(A ∩ B)) = E (YX ∧ Y ′X) = lim ∑ i μ(Ki)E (YKi)E ( Y ′Ki ) = (lim ∑ i μ(Ki)E (YKi))E (Y ′ X) = (limE ( ∑ i μ(Ki)YKi))E (Y ′ X) = E (YX)E (Y ′ X) = E (μ(A)) E (μ(B)). � 4. Random Borel sets on the unit segment and inspection processes In [8] random Borel sets on the unit segment were uniquely characterized by their inspection processes, neglecting the fact that not every inspection process corresponds to a random Borel set. Every random variable ϕ satisfying conditions (1–2) below can be interpreted as an inspection process of a random variable with values in a certain function space and hence is more general than a random set; the special case or random sets is determined by condition (3) below. For any random Borel subset X of the unit segment I we consider the in- spection process Xt := λ(X ∩ [0, t]) = ∫ t 0 χXdλ, where λ is Lebesgue measure on I. Observe that Xt as a function of t is continuous, increasing and al- most everywhere differentiable with derivative almost surely equal to χX [7, 70 B. Günther Thm8.8,p.168]. That means Xt is the primitive (syn. antiderivative) of the indicator function χX. Observe that this implies that the paths Xt are much better behaved than the paths of Brownian motion, which are almost surely nowhere differentiable [1, Thm.12.25,p.261]. We consider the set of functions ϕ : I → R subject to the conditions (1) ϕ(0) = 0 (2) ∀0 ≤ x ≤ y ≤ 1 : 0 ≤ ϕ(y) − ϕ(x) ≤ y − x (3) sup ∑ k [ϕ(tk+1)−ϕ(tk)]2 tk+1−tk = ϕ(1), where the supremum is taken over all finite decompositions of the unit segment 0 = t0 < t1 < · · · < tn = 1. Notice that the functions satisfying conditions (1) and (2) constitute a com- pact convex set Z of the space of all continuous functions on I equipped with the topology of uniform convergence by the theorem of Arzela-Ascoli. By Y ⊂ Z we denote the subspace of functions satisfying all three conditions (1–3). Lemma 4.1. For all x,y ∈ R and α,β > 0 with α + β = 1 the inequality (x + y)2 ≤ x2 α + y2 β holds. Proof. 0 ≤ (√ β α x − √ α β y )2 = β α x2 − 2xy + α β y2 = ( 1 α − 1 ) x2 − 2xy +( 1 β − 1 ) y2 = 1 α x2 + 1 β y2 − (x + y)2. � Lemma 4.2. All functions ϕ ∈ Z satisfy sup ∑k [ϕ(tk+1)−ϕ(tk)]2tk+1−tk ≤ ϕ(1). More- over, if the decomposition 0 = u0 < u1 < · · · < uN = 1 is a refinement of 0 = t0 < t1 < · · · < tn = 1, then ∑N−1 k=0 [ϕ(uk+1)−ϕ(uk)]2 uk+1−uk ≥ ∑n−1 k=0 [ϕ(tk+1)−ϕ(tk)]2 tk+1−tk . Proof. ∑n−1 k=0 [ϕ(tk+1)−ϕ(tk)]2 tk+1−tk = ∑n−1 k=0 (tk+1 − tk) [ ϕ(tk+1)−ϕ(tk) tk+1−tk ]2 ≤ ∑n−1k=0 (tk+1− tk) [ ϕ(tk+1)−ϕ(tk) tk+1−tk ] = ∑n−1 k=0 [ϕ(tk+1) − ϕ(tk)] = ϕ(1). Now consider three points 0 ≤ v1 < v2 < v3 ≤ 1; then an application of lemma 4.1 to x := ϕ(v2) − ϕ(v1), y := ϕ(v3) − ϕ(v3), α := v2−v1v3−v1 and β := v3−v2 v3−v1 yields [ϕ(v3)−ϕ(v1)]2 v3−v1 ≤ [ϕ(v2)−ϕ(v1)]2 v2−v1 + [ϕ(v3)−ϕ(v2)]2 v3−v2 , and this concludes the proof. � Remark 4.3. For every function ϕ ∈ Z there is a Lebesgue measurable function ψ : I → I with ϕ(t) = ∫ t 0 ψ(v)dv for all t ∈ I (consider positive measure defined on intervals [x,y] by ϕ(y) − ϕ(x) and apply the Radon-Nikodym theorem). Lemma 4.4. Suppose ϕ is the antiderivative ϕ(t) = ∫ t 0 ψ(v)dv of a mea- surable function ψ : I → I, and suppose a sequence of decompositions ζn ={ 0 = t (n) 0 < t (n) 1 < · · · < t (n) Nn = 1 } of the unit segment is given with limn→∞ meshζn = 0. Then limn→∞ ∑Nn−1 k=0 [ ϕ ( t (n) k+1 ) −ϕ ( t (n) k )]2 t (n) k+1 −t(n) k = ∫ 1 0 ψ(v)2dv. Random selection of Borel sets II 71 Proof. We define a sequence of functions fn : I → I by fn(t) := ϕ ( t (n) k+1 ) −ϕ ( t (n) k ) t (n) k+1 −t(n) k if t (n) k ≤ t < t (n) k+1. By [7, Thm8.8,p.168] fn → ψ almost everywhere, and consequently f2n → ψ2 almost everywhere. Hence by Lebesgue’s dominated convergence theorem limn→∞ ∫ 1 0 fn(v) 2dv = ∫ 1 0 ψ(v)2dv. � Proposition 4.5. A function ϕ ∈ Z is the antiderivative of an indicator func- tion if and only if it satisfies condition (3). Proof. In view of lemma 4.4 condition 3 translates to ∫ 1 0 ψ(1 − ψ)dλ = 0. This means that ψ can assume values different from 0 or 1 only on a 0-set, i.e. ψ almost surely equals an indicator function. � By proposition 4.5 we may identify inspection processes satisfying condi- tion (3) with random Borel sets. Evidently, this condition is a relation among the increments of the inspection process, and one suspects that these incre- ments cannot be independent. Proposition 4.6. Suppose the inspection process Xt := λ(X ∩ [0, t]) = ∫ t 0 χXdλ corresponding to a random Borel set X has independent increments. Then there exists a fixed (deterministic) Borel set B such that X ≡ B a.s. Proof. We consider two numbers 0 ≤ x < y ≤ 1 and an integer n ∈ N. Setting h := y−x n , tk := x + kh, 0 ≤ k ≤ n, we telescope Xy − Xx =∑n k=0 ( Xtk+1 − Xtk ) . Furthermore set bt := E (Xt). Independence of incre- ments then implies Var (Xy − Xx) = Var n∑ k=0 ( Xtk+1 − Xtk ) (4.1) = n∑ k=0 Var ( Xtk+1 − Xtk ) (by independence)(4.2) = n∑ k=0 ( E (( Xtk+1 − Xtk )2) − (E (Xtk+1 − Xtk ))2 ) (4.3) = hE n∑ k=0 ( Xtk+1 − Xtk )2 tk+1 − tk − h n∑ k=0 ( btk+1 − btk )2 tk+1 − tk (4.4) → hE ( Xtk+1 − Xtk ) − h n∑ k=0 ( btk+1 − btk )2 tk+1 − tk (by condition 3)(4.5) = h ( btk+1 − btk ) − h n∑ k=0 ( btk+1 − btk )2 tk+1 − tk (4.6) Now Var (Xy − Xx) = 0 is obtained by letting n → ∞ and hence h → 0; this means Xy − Xx ≡ by − bx a.s. Hence the function t �→ bt must also satisfy 72 B. Günther condition 3 and defines the Borel set B required by our theorem. (On a sideline we may observe that the function t �→ bt satisfies conditions 1 and 2, therefore∑n k=0 (btk+1 −btk ) 2 tk+1−tk ≤ y − x.) � 5. An application to random allocation Our random allocation experiment will be developed from a random Borel set that is a stronger version of example [2, Ex.7.5]; that means we construct a probability measure on the space of Borel sets B by prescribing the dis- tribution of the composite random variable B �→ μ(B) (condition (1) below) and then inductively lifting the measure over the fibers of the projection maps pn+1n : I 2n+1 → I2n familiar from [2, §7] (condition (2) below). The intended computation of first and second moments requires some detailed preparations. So we suppose we are given (1) a random variable x00 distributed on I and (2) another random variable u symmetrically distributed on [−1,1] such that (5.1) ∀ε > 0 : P (|u| ≥ 1 − ε) > 0 Then we define random variables xnm for n > 0, 0 ≤ m < 2n inductively by picking identically distributed copies unm of u, independent from one another and from all xrk, r ≤ n, and setting xn+1,2m = xnm + unm min (xnm,1 − xnm)(5.2) xn+1,2m+1 = xnm − unm min (xnm,1 − xnm)(5.3) Observe that the scaling factor min (xnm,1 − xnm) is chosen such that it en- sures 0 ≤ xn+1,2m ≤ 1 and 0 ≤ xn+1,2m+1 ≤ 1. Also notice that this is almost the same as [2, Ex.7.5], with the difference that our random variables need not possess a density, and with [2, Eq.7.8] replaced by the much weaker assumption (5.1). The system of random variables is invariant under G∞. For fixed n, the joint distribution of the random variables xn0, . . .xn,2n−1 defines a probability measure νn on I 2n, and we claim that [2, Eq.7.1] is satisfied and hence a probability measure on the space of Borel sets Y (μ) is obtained. By Gn-invariance E (( xnm − 12 )2) is independent of m and we can define (5.4) an := E (( xnm − 1 2 )2) = E ( 2−n 2n−1∑ m=0 ( xnm − 1 2 )2) By Jensen’s inequality the sum Sn := 2 −n ∑2n−1 m=0 ( xnm − 12 )2 increases with n; hence, if we can show an → 14, we can conclude that Sn converges to 14 almost surely and therefore in probability. Thus [2, Eq.7.1] will be proved. Random selection of Borel sets II 73 We visualize our random variables as tree with root x00, such that each xnm has two descendents xn+1,2m and xn+1,2m+1. Fix 0 < ε < 1 2 and set q := 1 2 P (|u| ≥ 1 − 2ε) > 0. We claim (5.5) P (∣∣∣∣xnm − 12 ∣∣∣∣ ≥ 12 − ε ) ≥ q for all n > 0. For, assume m = 2k is even and xn−1,k ≥ 12, then xnm = xn−1,k +un−1,k (1 − xn−1,k) = (1 − un−1,k)xn−1,k +un−1,k ≥ 12 (1 − un−1,k) + un−1,k = 12 (1 + un−1,k). But since un−1,k ≥ 1 − 2ε with probability at least q we obtain xnm ≥ 1 − ε with probability at least q provided xn−1,k ≥ 12. The cases xn−1,k ≤ 12 or m odd are handled similarly. Now observing the independence of un−1,k from xn−1,k we conclude that the event Anm that xnm itself or at least one of its ancestors xrk in our tree satisfies ∣∣xrk − 12∣∣ ≥ 12 − ε has probability P (Anm) ≥ 1 − (1 − q)n. We claim an ≥ ( 1 2 − ε )2 [1 − (1 − q)n]. lim infn an ≥ ( 1 2 − ε )2 will follow, and therefore, since ε was arbitrary, limn an = 1 4 . To this end consider the event A (r) nm ⊆ Anm such that the first ancestor of xnm satisfying ∣∣xrk − 12∣∣ ≥ 12 − ε occurs at level r and observe that A (r) nm is invariant under the subgroup of Gn leaving the range 2n−rk ≤ � < 2n−r(k + 1) invariant; therefore (5.6) ∫ A (r) nm ( xnm − 1 2 )2 dP = ∫ A (r) nm 2r−n 2n−r(k+1)−1∑ �=2n−rk ( xn� − 1 2 )2 dP However, by Jensen’s inequality we have 2r−n ∑2n−r(k+1)−1 �=2n−rk ( xn� − 12 )2 ≥( 2r−n ∑2n−r(k+1)−1 �=2n−rk xn� − 12 )2 = ( xrk − 12 )2 ≥ (1 2 − ε )2 on A (r) nm and there- fore ∫ A (r) nm ( xnm − 12 )2 dP ≥ ( 1 2 − ε )2 P ( A (r) nm ) . Hence ∫ Anm ( xnm − 12 )2 dP = ∑ r ∫ A (r) nm ( xnm − 12 )2 dP ≥ ( 1 2 − ε )2 ∑ r P ( A (r) nm ) = ( 1 2 − ε )2 P (Anm) ≥ ( 1 2 − ε )2 [1 − (1 − q)n]. This concludes the proof. Assumption 1. For the remainder of this subsection we assume that the random variable u is uniformly distributed on [−1,1]. 74 B. Günther Observe that with this assumption E ( h(xnm) ∣∣∣x10 = t) = E (h(xn−1,m) ∣∣∣x00 = t) for any function h! In consequence E ( h(xnm) ∣∣∣x00 = t)(5.7) = 1 2 +1∫ −1 E ( h(xnm) ∣∣∣x10 = t + u min (t,1 − t))du(5.8) = 1 2 +1∫ −1 E ( h(xn−1,m) ∣∣∣x00 = t + u min (t,1 − t)) du(5.9) = 1 2 min(t,1 − t) min(1,2t)∫ max(0,2t−1) E ( h(xn−1,m) ∣∣∣x00 = v) dv(5.10) Applying the foregoing to h(t) = t2 leads to the functions fn(t) = E ( x2nm ∣∣∣x00 = t), whose special role has already been investigated in [2, §8]: f0(t) := t 2(5.11) fn+1(t) := 1 2 min(t,1 − t) min(1,2t)∫ max(0,2t−1) fn(u)du(5.12) f1(t) = t 2 + 1 3 [min(t,1 − t)]2(5.13) By induction one can easily prove fn(t) ≤ t for all n. Since f1 ≥ f0 we also infer by induction fn+1 ≥ fn for all n. Consequently there must be a limit function f∞(t) = limn→∞ fn(t), at least lower semicontinuous, and satisfying t2 ≤ f∞(t) ≤ t with (5.14) f∞(t) = 1 2 min(t,1 − t) min(1,2t)∫ max(0,2t−1) f∞(u)du Equation (5.14) immediately implies that f∞ is continuous on the whole inter- val I, even at 0 and 1. By induction one can prove (5.15) fn(t) − fn(1 − t) = 2t − 1 for all n, thus gn(t) := t − fn(t) is symmetric around 12, gn(1 − t) = gn(t), g0(t) = t(1 − t), gn+1(t) = 12t 2t∫ 0 gn(u)du for 0 ≤ t ≤ 12 and gn ↓ 0 for n → ∞. Random selection of Borel sets II 75 0.1 0.2 0.3 0.4 0.5 0.05 0.10 0.15 0.20 0.25 Figure 1. First few iterates of gn. Lemma 5.1. Under assumption 1, f∞(t) = t for all t ∈ I. Proof. Suppose the contrary and consider the function h(t) := t − f∞(t); then h is continuous, h ≥ 0, h(0) = h(1) = 0, h(t) = 1 2 min(t,1−t) min(1,2t)∫ max(0,2t−1) h(u)du and there exists t0 ∈]0,1[ such that h(t0) = max u∈I h(u) > 0. If t0 ≤ 12, then h(t0) = 1 2t0 2t0∫ 0 h(u)du < 1 2t0 2t0∫ 0 h(t0)du = h(t0), a contradiction. Similarly, if t0 ≥ 12, then h(t0) = 12(1−t0) 1∫ 1−2t0 h(u)du < 1 2(1−t0) 1∫ 1−2t0 h(t0)du = h(t0) and we arrive again at a contradiction. � Observe that lemma 5.1 provides an independent proof that our construc- tion leads to a well defined probability on Y . The first few iterates fn of the Fredholm equation (5.12) (or equivalently, of gn, cf. figure 1) can be evaluated in closed form, later ones can be obtained numerically. Now we repeat our random Borel set drawing experiment independently and with identical distribution, at the i-th run obtaining a Borel set Bi. Then Cr := ⋃r i=1 Bi models the set of elements allocated up to run r; the set valued random variables Cr constitute a Markov chain over the time variable r. Theorem 5.2. Let P be the probability measure on I obtained as the distribu- tion of x00, i.e. of the measure of the Borel set obtained in a single run of our random experiment. Then at Markov time r the accumulated Borel set has the expected measure 1 − [∫ (1 − x)dP(x) ]r and variance (5.16) ∞∑ m=0 2−m−1 [∫ (2fm(1 − x) − fm+1(1 − x)) dP(x) ]r − [∫ (1 − x)dP(x) ]2r (The case of a Dirac measure P located at the “fixed weight” x is displayed in figure 2.) 76 B. Günther 0.2 0.4 0.6 0.8 1.0 0.02 0.04 0.06 0.08 Figure 2. Square root of variance for Markov times r = 2,5,10. The proof requires a few preparations, starting with a stronger continuity property of the ∧-product than given in [2, Lem.5.2]: Proposition 5.3. The ∧-product is a jointly continuous map ∧ : Zh×Zh → Zh in the Hilbert space topology and ‖a ∧ x − a ∧ y‖2 ≤ √ ‖a‖2 · ‖x − y‖2. Proof. We recall that for all z = (znm)0≤m<2n,n≥0 ∈ Y the sequence 2−n ∑2n−1 m=0 z 2 nm is increasing with supn∈N0 2 −n ∑2n−1 m=0 z 2 nm = ‖z‖22 (cf. [2, eq.5.4]). For any two vectors z′,z′′ ∈ Z we have ‖z′ − z′′‖22 ≤ 1 because all |z′nm − z′′nm| ≤ 1. This applies in particular to z = a ∧ x − a ∧ y. Hence for each 0 ≤ α < ‖a ∧ x − a ∧ y‖22 ≤ 1 we can find n ∈ N0 such that 2−n ∑2n−1 m=0 z 2 nm > α. Now pick numbers 0 ≤ αm < 1 such that 2−n ∑2n−1 m=0 αm ≥ α and z2nm > αm for each 0 ≤ m < 2n; by definition of the ∧-product there ex- ists N0 ≥ n such that for all N ≥ N0 and each 0 ≤ m < 2n the inequality 2n−N ∑(m+1)2N−n−1 k=m2N−n aNk |xNk − yNk| > √ αm ≥ αm holds (remember αm ≤ 1, hence √ αm ≥ αm). By summing over all m we obtain 2−N ∑2N −1 k=0 aNk |xNk− yNk| > 2−n ∑2n−1 m=0 αm ≥ α and hence, using the Cauchy-Schwarz inequality: ‖a‖2 · ‖x − y‖2 ≥ √ 2−N ∑2N −1 k=0 a 2 Nk · √ 2−N ∑2N −1 k=0 (xNk − yNk) 2 > α. Since α < ‖a ∧ x − a ∧ y‖22 was arbitrary this implies ‖a‖2·‖x − y‖2 ≥ ‖a ∧ x − a ∧ y‖ 2 2. This implies continuity of the ∧-product with respect to the Hilbert space topology because ‖x ∧ y − x0 ∧ y0‖2 ≤ √ ‖x0‖2 · ‖y − y0‖2+ √ ‖y‖2 · ‖x − x0‖2 for x,x0,y,y0 ∈ Z. � Lemma 5.4. For each x = (xnm) ∈ Z consider the sequence x(r) = ( x (r) nm ) ∈ Z defined by (5.17) x(r)nm := { xr,�m2r−n r ≤ n xnm r ≥ n Random selection of Borel sets II 77 Then limr→∞ x(r) = x in the Hilbert space topology of Z (cf. [2, §5]). Observe that x ∈ Z ⇒ x(r) ∈ Z, but in general x(r) �∈ Y even if x ∈ Y . Proof. x (r) n,2m = x (r) n,2m+1 for n > r, therefore ∥∥x − x(r)∥∥2 = ∑∞n=r+1 ∑2n−1−1m=0 2−n−1 (xn,2m − xn,2m+1)2. For r → ∞ this is the remainder of a convergent series x200 + ∑∞ n=1 ∑2n−1−1 m=0 2 −n−1 (xn,2m − xn,2m+1)2 = ‖x‖2 and hence con- verges to 0 for r → ∞. � Corollary 5.5. For each finite sequence of vectors xi = (xi;nm)0≤m<2n,n∈N0 ∈ Z, 1 ≤ i ≤ s: (5.18) ( s∧ i=1 xi ) nm = lim N→∞ 2n−N (m+1)2N−n−1∑ k=m2N−n s∏ i=1 xi;Nk Proof. By induction on s one can easily show (5.19) ( s∧ i=1 x (r) i ) nm = ⎧⎪⎪⎨ ⎪⎪⎩ 2n−r (m+1)2r−n−1∑ k=m2r−n s∏ i=1 xi;rk r ≥ n s∏ i=1 xi;r,�m2r−n r ≤ n The corollary now follows from continuity of the ∧-product taking the limit r → ∞. � Proof of theorem 5.2. We switch to complements, setting B′i := �Bi, C′r := �Cr = ⋂r i=1 B ′ i, thus translating unions into intersections, which is equivalent but in better agreement with our preparations. Now the proof resembles that of [2, Thm.8.2]. In coordinate representation, let the random Borel set B′i correspond to the process ξ (i) nm, then by corollary 5.5 C ′ r corresponds to ξnm = limN→∞ 2 n−N∑(m+1)2N−n−1 k=m2N−n ∏r i=1 ξ (i) Nk. Therefore E ( ξ00|ξ(1)00 , . . .ξ (r) 00 ) = lim N→∞ 2−N 2N −1∑ k=0 E ( r∏ i=1 ξ (i) Nk ∣∣∣ξ(1)00 , . . .ξ(r)00 ) (5.20) = lim N→∞ 2−N 2N −1∑ k=0 r∏ i=1 E ( ξ (i) Nk|ξ (i) 00 ) (5.21) = r∏ i=1 ξ (i) 00(5.22) 78 B. Günther and with ξ00 = μ(C ′ r) = 1 − μ(Cr), ξ(i)00 = μ(B′i) = 1 − μ(Bi) this leads to 1 − E (μ(Cr)) = ∫ E ( ξ00 ∣∣∣ξ(1)00 = 1 − t1, . . .ξ(r)00 = 1 − tr ) (P ⊗ · · · ⊗ P) (dt1 · · ·dtr) (5.23) = ∫ r∏ i=1 (1 − ti) (P ⊗ · · · ⊗ P) (dt1 · · ·dtr)(5.24) = [ 1 − ∫ tP(dt) ]r (5.25) Now the second moments are obtained as follows: E ( ξ200|ξ(1)00 , . . .ξ (r) 00 ) = lim N→∞ 2−2N ⎡ ⎣2N −1∑ k=0 r∏ i=1 E ( ξ (i)2 Nk |ξ (i) 00 ) + 2N −1∑ a =b=0 r∏ i=1 E ( ξ (i) Naξ (i) Nb|ξ (i) 00 )⎤⎦ (5.26) = lim N→∞ 2−2N [ 2N −1∑ k=0 r∏ i=1 fN ( ξ (i) 00 ) + 2N −1∑ a =b=0 r∏ i=1 ( 2fv(a,b)−1 ( ξ (i) 00 ) − fv(a,b) ( ξ (i) 00 ))](5.27) Integrating the summand 2−2N ∑2N −1 k=0 ∏r i=1 fN ( ξ (i) 00 ) over the product mea- sure P ⊗ · · · ⊗ P leads to 2−N [∫ fN(1 − t)P(dt) ]r and drops out in the limit N → ∞. This leaves us with (5.28) E ( μ(C′r) 2 ) = lim N→∞ 2−2N 2N −1∑ a =b=0 [∫ ( 2fv(a,b)−1 (1 − t) − fv(a,b) (1 − t) ) P(dt) ]r Observing # {(a,b)|v(a,b) = m} = 22N−m we arrive at E ( μ(C′r) 2 ) = ∞∑ m=1 2−m [∫ (2fm−1 (1 − t) − fm (1 − t))P(dt) ]r (5.29) Var ( μ(Cr) 2 ) = Var ( μ(C′r) 2 ) = ∞∑ m=1 2−m [∫ (2fm−1 (1 − t) − fm (1 − t))P(dt) ]r − [∫ (1 − t)P(dt) ]2r (5.30) � Random selection of Borel sets II 79 References [1] L. Breiman, Probability, volume 7 of Classics in Applied Mathematics. siam, 1992. [2] B. Günther, Random selection of Borel sets, Appl. Gen. Topol. 11, no. 2 (2010), 135–158. [3] H. Hadwiger, Vorlesungen über Inhalt, Oberfläche und Isoperimetrie, volume 93 of Grundlehren. Springer, 1957. [4] P. R. Halmos, Measure Theory, volume 18 of GTM. Springer, 1974. [5] A. S. Kechris, Classical descriptive set theory, volume 156 of GTM. Springer, 1995. [6] V. F. Kolchin, B. A. Sevast’yanov and V. P. Chistyakov, Random allocations, Scripta Series in Mathematics. John Wiley & Sons, 1978. [7] W. Rudin, Real and Complex Analysis, Series in Higher Mathematics, MacGraw-Hill, 2nd edition, 1974. [8] 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. (Received July 2011 – Accepted March 2012) B. Günther (dr.bernd.guenther@t-online.de) DB Systel GmbH, Development Center Databases T.SVD32, Weilburger Straße 28, 60326 Frankfurt am Main, Germany Random selection of Borel sets II. By B. Günther