or equal to λ(A)-ε/2. Strict inequality obtains when a bit of the preimage
of the added interval gratuitously falls in the pre-existing preimage of A. λ(A) will reach 1/2. This is so because the measure of the union of all intervals in all steps is 1. To see this, note that all reals with binary expansions containing a string of k consecutive 0's are in one of the intervals. If x=x1x2x3...xi100...00x i+k+2..., x will be in an interval of step i+1 (with o corresponding to x1x2x3...xi1). Now the measure of the set of all points with k consecutive 0's is one. A probabilistic argument proves this. Note the isomorphism between [0,1] under λ and sequences of tosses of a fair coin. Cast probabilistically we must show that almost surely each sequence contains k consecutive heads. The probability that k flips beginning at k has one or more tails is 1-1/2 k =p, beginning at 2k, again p, etc. so that the probability that the first n such sequences all contain at least one tail each is pn→0, so at least one sequence is free of tails (almost surely), so there is almost surely a sequence of k heads, and therefore the measure of the set of reals with k consecutive 0s in their binary representation is one. QED.
Informal view: Dynamics is the study of repeated applications of functions. We emphasize those functions with
these special characteristics: (1) They have periodic points everywhere (2) There are orbits (the
repeated applications of the function to an initial seed) that travel everywhere (3) Two close initial
points will eventually diverge widely; these functions we call chaotic. One of the simplest chaotic functions is the doubling function on [0,1]. Sometimes written
f(x)=2x (mod 1), one doubles the argument, and if the result is greater than one subtracts one from
the result. This function is indeed chaotic as we have shown in class. The dynamics of this function are very easy to study because of a special relationship (conjugacy)
between the doubling function and the left shift function on sequences of 0's and 1's,. If these
sequences are thought of as binary representations of numbers between 0 and 1, with the
imposition of a relatively simple distance function there is even continuity almost everywhere
(except at ½ and 1). The problem posted in AMM is this: If A is a finite collection of intervals in [0,1) and the
Lebesgue measure (total lengths) of A is 1/2, what is the biggest Lebesgue measure that the points
common to A and its preimage under f can be? Recall that the preimage of a set, B, is the set of
points that the function maps into the set B. My first approach to solving this problem was to consider a single interval as comprising A:
Below the line is A, above the line is the preimage of A under f. We can easily see that the
common points are just [0,1/4] whose measure is 1/4. Can we do better? Think of this as running
a company for profit (or minimum loss). Each bit of measure we spend on A is a cost, we are
allowed total costs of 1/2. Each bit of measure that A shares with the preimage of A is a profit, we
want to maximize the profits. Since we can see from the above diagram that in this case we have
lost the points from [1/4,1/2], we must find a way to minimize losses. What if we start with an A that is very narrow, so the first round losses will be minimized:
Now we have a very small loss. Where should we spend our next costs? Hey, right under the little
bit of the primage of A in the middle of the line!
Note how the addition of the second piece to A has added a third and fourth piece to the preimage
of A. So what do we do next? We cover them with the somewhat thinner pieces shown (the ones
that look almost like dots). Now the thinner pieces will generate even more tiny preimages (four
of them), and so on. You can look back at the formal view to see the details of how the
construction can be more formally described.
Pretty clearly, this procedure will result in an A and a preimage of A that agree almost completely
(except for the right half of the leftmost interval, and even that will get partly covered eventually by the
little bits of preimages from intervals close to the first one). So we have built an A and the
measure of A and the measure of its preimage are almost the same. The last remaining issue (and it’s a biggie) is how big will the measure of this A be? Since the
pieces are so tiny, maybe in aggregate they don’t amount to much. The answer is that they do, that
they amount to almost the whole interval. The point of the rest of this discussion is to prove that. Again looking back to the construction of the formal part, let’s ask for the measure of all the
pieces, if none are omitted. Well, we will add everything of the form [o/2i,o/2i +ε/2i] where o is
odd and k is some big number (ε=1/2k). If o=x=x1x2x3...xi and is odd, then being in the interval
means being of the form x1x2x3...xi00...00y where there are k consecutive 0's and y is any sequence
of 0's and 1's. We need to compute the measure of this set. We start by recalling the parallel between sequences of 0's and 1's under Lebesgue measure and
the probability measure for flipping of a fair coin, with 0 for tails and 1 for heads. The set of all
numbers with k consecutive 0's is equivalent to the set of all flip sequences with a run of k tails.
To show that this has measure 1, consider pik, the probability that beginning at the i*kth toss, there
is a string of k tails. pik=1/2k for all i, k and the events (for different i) are independent. Therefore,
the chance of NO string of k tails is (1-pik) for the i*kth digit, so the chance of no string of k tails
at i*k for any i<I is (1-pik)I which tends to 0 as I increases without limit. Therefore the chance of
no string of k tails at any i is 0, and the chance of a string of k tails is 1. Or to return to the unit
interval, the measure of the set of all numbers with a string of k 0's in a row is 1. This means that as the procedure adds intervals to A, eventually the measure of A will reach 1/2.
If this were not so, the union of all intervals would be less than 1/2, which is contrary to the result
of the preceeding paragraph.
