A von Neumann theorem for uniformly distributed sequences of partitions Ingrid Carbone and Aljoˇsa Volˇciˇc 9 Universit`a della Calabria 0 0 2 n Abstract a J In this paper we consider permutations of sequences of partitions, 6 1 obtaining a result which parallels von Neumann’s theorem on per- mutations of dense sequences and uniformly distributed sequences of ] A points. F . h 1 Introduction t a m [ S. Kakutani studied in [K] the notion of uniformly distributed sequences of 1 partitions of the interval [0,1]. He introduced the following construction. Fix v a number α ∈]0,1[. If π is any partition of [0,1], its α-refinement, denoted 1 3 by απ, is obtained subdividing the longest interval(s) of π in proportion 5 α/(1−α). By αnπ we denote the α-refinement of αn−1π. 2 . Let ω = {[0,1]} be the trivial partition of [0,1]. The sequence {αnω} will 1 0 be called the Kakutani α-sequence. 9 0 Definition 1.1 Given a sequence of partitions {π } of [0,1], with : n v Xi π = {[tn ,tn],1 ≤ i ≤ k(n)}, n i−1 i r a we say that it is uniformly distributed (u.d.) if for any continuous function f on [0,1] we have k(n) 1 1 lim f(tn) = f(t)dt (1) n→∞ k(n) i i=1 Z0 X or, equivalently, if the sequence of discrete measures k(n) 1 δ (2) tn k(n) i i=1 X 1 converges weakly to the Lebesgue measure λ restricted to [0,1]. Here δ is t the Dirac measure concentrated in t. We can now state Kakutani’s result (see [K] for more details). Theorem 1.2 The sequence {αnω} is uniformly distributed. This was a partial answer to the following question posed by the physicist H. Araki, which regarded random splittings of the interval [0,1]. Let X be 1 choosen randomly (with respect to uniform distribution) on [0,1] and then, inductively, onceX ,X ,...,X havebeenchosen, letX beapointchosen 1 2 n n+1 randomly (and uniformly) in the largest of the n + 1 intervals determined by the previous n points. Can we conclude that the associated sequence of cumulative distribution functions converges uniformly, with probability 1, to the distribution function of the uniform random variable on [0,1]? By a theorem due to Polya, this is equivalent to the condition expressed by (1). This question has been studied in [vZ] and [L] and later on in [PvZ]. Note that in the probabilistic setting we may neglect the possibility that thepartition obtainedin the n-thstep has morethan oneinterval of maximal length, since this event has probability zero. This is not the case for Kaku- tani’s construction, since for every α the partition {αnω} has, for infinitely many values of n, more than one interval of maximal length. In [ChV] the notion of (deterministic) u.d. sequences of partitions has been extended to probability spaces on complete metric spaces. In [CV] Kaktuani’s splitting procedure has been extended to higher dimension. Recently some new results revived the interest for the subject. In [V] we introduced the concept of ρ-refinement of a partition π, which generalizes Kakutani α - sequence, and we proved that the sequence {ρnω} is also u.d. We also investigated in [V] the connections of the theory of u.d. se- quences of partitions to the well-established theory of uniformly distributed (u.d.) sequences of points, showing how is it possible to associate (many) u.d. sequences of points to any u.d. sequence of partitions. A sequence of points {x } is u.d. on [0,1] if for every continuous function n f on [0,1] we have 1 n 1 lim f(x ) = f(t)dt. i n→∞ n i=1 Z0 X Since our methods allow to construct new u.d. sequences of points, we think these connections are interesting in view of possible applications to the 2 quasi-Monte Carlo method, which is in the last decades the main motivation for the study of u.d. sequences of points (see [N]). We continue to compare the two theories in the present paper, where we are concerned with the property analogous to the one studied by von Neumann in [vN], where it is proved the following theorem. Theorem 1.3 If {x } is a dense sequence of points in [0,1], then there exists n a rearrangement of these points, {x }, which is uniformly distributed. n k As we shall see, there is a remarkable difference between von Neumann’s result and its extensions to Borel measures on [0,1] and the corresponding resultweobtainforsequences ofpartitions(Theorem2.2). Weshallcomment on that in the last section of this paper. One of the consequences of von Nemann’s result is that there are many u.d. sequences of points. Our purpose is analogous: we want to show that there are many u.d. sequences of partitions. Before we proceed, we need to define the concepts of permutation of a partition and that of density of a sequence of partitions. Definition 1.4 Given a partition π = {[t ,t ],1 ≤ i ≤ k}, we denote by i−1 i l = t − t the lenght of its i-th interval. The diameter of π, denoted by i i i−1 diamπ, is equal to max l . 1≤i≤k i Definition 1.5 Given a sequence of partitions {π }, we say that it is dense n if lim diamπ = 0. n→∞ n Definition 1.6 If π = {[t ,t ],1 ≤ i ≤ k} is a partition, its permutation is i−1 i a partition π′ = {[s ,s ],1 ≤ h ≤ k} defined by the points s = h l , h−1 h h j=0 ij for 0 ≤ h ≤ k, where l = 0 and {i }, for 1 ≤ i ≤ k, is a permutation of the 0 j P indices {1,2,...,k}. We will denote by π! the set of all the permutations of π. Of course, if π splits [0,1] in k parts, π has at most k! permutations: if π has two or more intervals of the same length, the number of permutations is smaller than k! . The extreme case is when all the intervals of π have the same lenght. Then π! coincides with the singleton {π}. In the sequel we shall use the well known fact that uniform distribution of partitions can be tested by means of suitable families of functions and 3 sets (see, for instance, [KN], Section 1 of Chapter 1 and for more general probability spaces, [DT], Section 2.1). Definition 1.7 We say that a family F of fuctions defined on [0,1] is deter- mining if a sequence of partitions {π } is uniformly distributed if and only n if (1) holds restricted to all f ∈ F. It is very simple to show that the family of all characteristic functions of dyadic intervals Is = [h−1, h], for s ∈ IN and 1 ≤ h ≤ 2s, is a determining h 2s 2s family, i.e. a sequence of partitions {π } is u.d. if and only if n k(n) 1 1 lim χ (tn) = n→∞ k(n) Ihs i 2s i=1 X for all s ∈ IN and 1 ≤ h ≤ 2s. To simplify notation, we shall use in the sequel the following notation: k(n) 1 π (Is) = χ (tn), (3) n h k(n) Ihs i i=1 X denoting the measure defined in (2) by the same symbol π which is used for n the corresponding partition. 2 The main result We begin this section by showing that density is a necessary condition for the uniform distribution of a sequence of partitions. Proposition 2.1 Any uniformly distributed sequence of partitions {π } is n dense. Proof. Suppose the contrary. Then there exists an ε > 0 such that, for infinitely many indices, diamπ ≥ ε. Denote by n these indices and select n k for each n an interval I belonging to π having length at least ε. k n n k k Let m be a positive integer such that 1 is smaller than ε and consider m the points x = i , for 0 ≤ i ≤ 2m. Then each I contains at least two of i 2m nk them and therefore it contains at least one of the intervals J = [x ,x ], for i i−1 i 1 ≤ i ≤ 2m. It follows that at least one of these intervals J (denote it by i 4 J) is contained in infinitely many I ’s. Let now f be a continuous function n k having non vanishing integral, whose support is contained in J. Then the sequence k(n) 1 A = f(tn) n k(n) i i=1 X does not converge to 1f(t)dt when n tends to infinity, since A = 0 for all 0 nk k. This contradicts the uniform distribution of {π }. ⋆ R n The density is necessary for uniform distribution, but it is of course not sufficient. However, we have the following result, which is the main result of this paper. Theorem 2.2 If {π } is a dense sequence of partitions, then there exists a n sequence of partitions {σ }, with σ ∈ π !, which is uniformly distributed. n n n Proof. Let {π } be a dense sequence of partitions, and let k(n) denote the n number of intervals of π . n Since the binary intervals Is = [h−1, h] are a determining family, the h 2s 2s conclusion will be acheaved constructing, for each n, a permutation σ of π n n such that 1 lim σ (Is) = n→∞ n h 2s for any s ∈ IN and any 1 ≤ h ≤ 2s (see Definition 1.7 and formula (3)). Foranys ∈ IN, thereexists n ∈ IN such thatdiamπ ≤ 1 foralln ≥ n . s n 4s s Of course, if k(n) is the number of intervals of π , we have that k(n) ≥ 4s n for all n ≥ n . We may select a subsequence {n } so that n > n for all s s s+1 s s ∈ IN. When n < n , we just take σ = π . Suppose now s > 1 and let us 1 n n construct, for each n such that n ≤ n < n , a permutation σ of π such s s+1 n n that σ (It) is close to 1 for all t ≤ s, in a sense which will be made precise n h 2t later. First, order the intervals of the partition π with respect to their increas- n ing length. Then we shift to the right the first interval of π so that its right endpoint n is 1 and we move correspondingly the block of all the other intervals to the left. In this way the number of the intervals contained in I1 remains 1 5 unchanged or decreases by one unit. We repeat this procedure until we obtain a permutation of π , denoted by π1, such that n n k(n) k(n) −1 ≤ k(n)π1(I1) ≤ +1, 1 ≤ h ≤ 2. (4) 2 n h 2 Now we consider t = 2 and the corresponding dyadic intervals I2, with h 1 ≤ h ≤ 4. Let us denote by J1 = 1 −δ1(n), 1 +δ˜1(n) the interval of π1 1 2 1 2 1 n containing 1. Of course, δ˜1(n) > 0 ahnd δ1(n)+δ˜1(n) ≤ h1 . 2 1 1 1 4s We repeat in I1 \J1 and in I1\J1 the procedure used above in order to 1 1 2 1 get a convenient permutation of π1 . More precisely, we keep J1 fixed and n 1 order the two collections of intervals of the partition π1 contained in I1 \J1 n 1 1 and I1 \J1 respectively, with respect to their increasing lenght, and in each 2 1 of them we repeat the procedure described above, shifting the first interval to the right and the rest of them to the left and continue this procedure until the intervals are distributed, up to one unit, proportionally to the lenghts of I2 and I2 \J1, respectively, i.e. proportionally to 1 2 1 1 1 −δ1(n) α2(n) = 4 in I2 and α2(n) = 4 1 in I2 \J1. 1 1 −δ1(n) 1 2 1 −δ1(n) 2 1 2 1 2 1 In the same way we reorder all the intervals of π1 contained in I1 \ J1 n 2 1 until they are distributed proportionally (up to one unit) to 1 −δ˜1(n) 1 α2(n) = 4 1 in I2 \J1 and α2(n) = 4 in I2. 3 1 −δ˜1(n) 3 1 4 1 −δ˜1(n) 4 2 1 2 1 Since δ1(n)+δ˜1(n) ≤ 1 , it is clear that all the coefficients α2(n) may be 1 1 4s h estimated in terms of a function of s in the following way: 1 − 1 1 4 4s ≤ α2(n) ≤ 4 , 1 ≤ h ≤ 22. (5) 1 h 1 − 1 2 2 4s Since the lower and upper estimates in (5) do not depend on h, and we are assuming that n ≤ n < n , in the sequel we will write α2 instead of α2(n), s s+1 s h to simplify notation. We denote by π2 the permutation of π1 constructed above (which fixes n n J1). Note that π2 does not move intervals of π1 from I1 to I1 and from I1 1 n n 1 2 2 to I1; therefore for h = 1,2 we can write 1 (k(n)π1(I1)−1)α2 −1 ≤ k(n)π2(I2) ≤ k(n)π1(I1))α2 +1 n 1 s n h n 1 s 6 and k(n)π1(I1)α2 −1 ≤ k(n)π2(I2) ≤ k(n)π1(I1)α2 +1 n 2 s n h n 2 s for h = 3,4. If we put α1 = 1, taking (4) into account we get s 2 k(n)α1α2 −2α2 −1 ≤ k(n)π2(I2) ≤ k(n)α1α2 +α2 +1, 1 ≤ h ≤ 22. s s s n h s s s Let us make one more step in order to indicate how to procede for any t ≤ s. Denote by J2 and J2 the two intervals of π2 containing, respectively, the 1 2 n points 1 and 3 and set 4 4 1 1 3 3 J2 = −δ2(n), +δ˜2(n) and J2 = −δ2(n), +δ˜2(n) 1 4 1 4 1 2 4 2 4 2 (cid:20) (cid:20) (cid:20) (cid:20) with δ˜2(n),δ˜2(n) > 0. We also note that λ(J2) and λ(J2) are both bounded 1 2 1 2 from above by 1 . 4s Let us procedeed as before, but now in the four intervals I2\J1∪J2∪J2 h 1 1 2 for 1 ≤ h ≤ 23. By reordering all the intervals of π2 contained in each of n them we obtain a new partition π3 ∈ π2! (which keeps fixed J1,J2 and J2) n n 1 1 2 whose intervals are distributed proportionally (up to one unit) to certain coefficients α3(n) (which are determined as before), all of which satisfy the h inequalities 1 − 1 1 23 4s ≤ α3(n) ≤ 23 , 1 ≤ h ≤ 23. 1 h 1 − 2 22 22 4s Here we note again that, as in formula (5), the estimates do not depend on h, and n is fixed, so in the sequel we shall write α3 instead on α3(n). s h We note, as in the previous step, that π3 does not move intervals of π2 n n among the dyadic intervals I2, with 1 ≤ h ≤ 22. h We easily get k(n)α1α2α3 −2α2α3−2α3 −1 ≤ k(n)π3(I3) ≤ k(n)α1α2α3 +α2α3+α3+1 s s s s s s n h s s s s s s for all 1 ≤ h ≤ 23. 7 If is clear now that the same procedure can be repeated for all t ≤ s and that we can construct partitions πt ∈ πt−1! such that n n t t t t t t k(n) αj−2 αj−1 ≤ k(n)πt(It) ≤ k(n) αj+ αj+1, (6) s s n h s s j=1 i=2 j=i j=1 i=2 j=i Y X Y Y X Y where αt, with 2 ≤ t ≤ s, are the proportionality coefficients which satisfy s 1 1 − 1 1 α1 = and 2t 4s ≤ αt ≤ 2t , 2 ≤ t ≤ s. (7) s 2 1 s 1 − 2 2t−1 2t−1 4s Moreover, (6) implies the following estimates t t t k(n) πt(It)− αj ≤ 2 αj +1, 1 ≤ h ≤ 2t, 1 ≤ t ≤ s. (8) (cid:12) n h s (cid:12) s (cid:12) j=1 (cid:12) i=2 j=i (cid:12) Y (cid:12) X Y (cid:12) (cid:12) (cid:12) (cid:12) Now(cid:12)we observe that t(cid:12)he partition πt does not move the intervals of πt−1 n n contained in each dyadic interval It−1, with 1 ≤ h ≤ 2t−1, to another dyadic h interval It−1, with 1 ≤ k ≤ 2t−1, i.e. πt−1(It−1) = πt(It−1) for all t ≤ s, k n h n h 1 ≤ h ≤ 2t−1. Let us put σ = πs and observe that the condition n ≤ n < n implies n n s s+1 that n → ∞ if and only if s → ∞. If we divide the terms of (8) by k(n) and substitute πt by σ , we obtain n n |σ (It)−L (t)| ≤ R (t), 1 ≤ h ≤ 2t, 1 ≤ t ≤ s, (9) n h s n,s where t L (t) = αj, s s j=i Y and 1 t t R (t) = 2 αj +1 . n,s k(n)  s  i=2 j=i X Y   We will provide now estimates for L (t) − 1 and for R (t). To this s 2t n,s purpose we observe that from (7) we get for all 1 ≤ t ≤ s 1 t 2j 1 1 1− ≤ L (t) ≤ . 2t 4s! s 2t t 1− 2j jY=2 j=2 4s (cid:16) (cid:17) Q 8 If we substitute all the terms in the brackets of the previous formula by the smallest of them, we get 1 1 2t t−1 1 1 < 1− ≤ L (t) ≤ . 2t 2t 4s! s 2t 1− 2t t−1 4s (cid:16) (cid:17) We note that 2t 1−t 4s s 1− ≤ for all 1 ≤ t ≤ s 4s! (cid:18)4s −2s(cid:19) and elementary calculation shows that the sequence of these upper bounds, which depend only on s, tends to 1 when s tends to infinity. Then, for all 1 ≤ t ≤ s we have 1 1 4s s 1 0 < L (t)− ≤ − (10) s 2t 2t 4s −2s 2t (cid:18) (cid:19) and, consequently, L (t)− 1 → 0 when s tends to infinity. s 2t Moreover, for R (t) we have the following estimate: n,s 2 t t 1 2s−2 1 0 < R (t) ≤ αj + ≤ L (s)+ (11) n,s k(n) k(n) 4s s 4s i=2 j=i X Y for all 1 ≤ t ≤ s, therefore R (t) is bounded by a sequence which tends to n,s zero when s tends to infinity. Substituting (10) and (11) in formula (9), we get 1 1 2s−2 1 1 4s s σ (It)− ≤ R (t)+L (t)− ≤ L (s)+ + −1 . n h 2t n,s s 2t 4s s 4s 2t 4s −2s (cid:12) (cid:12) (cid:20)(cid:18) (cid:19) (cid:21) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) Putting a(cid:12)ll things together, we can conclude therefore that 1 σ (It) → when n → ∞ for all t ∈ IN. ⋆ n h 2t 9 3 Conclusions We have constructed the u.d. sequence {σ } from a dense sequence {π } by n n a precise algorithm which could be, in concrete situations, implemented step by step. On the other hand it would be interesting to have besides our result also a probabilistic statement expressed by the following Conjecture If {π } is a dense sequence of partitions and if each σ is taken n n at random from π ! for any n ∈ IN, then {σ } is uniformly distributed with n n probability 1. The (possible) confirmation of the correctness of this conjecture would not diminish the value of the result presented in this paper. If it is allowed to compare the questions we are treating with much more important ones, we all agree that the Borel theorem on normal numbers does not diminish the interest for finding concrete examples of such numbers. It is interesting to note also an essential difference between the theorem due to von Neumann and our result. It is well known that the conclusion of Theorem 1.3 holds if the measure λ is substituted by any Borel probability on [0,1] (see for instance Section 4 of Chapter 2 and, for a more general setting, Section 2 of Chapter 3, of [KN] and the bibliography cited there). This is not the case with our result, as it can be easily seen by taking a sequence of partitions {π }, where each π splits [0,1] in intervals of equal n n length. Then for any n ∈ IN the set of permutations π ! is a singleton and λ n is the only possible limit. This is of course an extreme case and it is not difficult to see by examples that in many cases, if {π } is a dense sequence of partitions, the correspond- n ing set M of all the probabilities which are limits of sequences {σ }, with n σ ∈ π !, contains more than just λ. n n This observation rises questions about the size of the set M (could it con- tain in some cases all the Borel measures?) and its geometric and topological properties (is it convex, is it closed?). The conjecture and the questions about M will be addressed in subse- quent papers. 10