An AMM Problem and solution for Math 490 Chaos
 
 
Formal view:
 
Problem 10843 (AMM) Let f(x)=2x (mod 1) on [0,1).
What is sup ?(A ? f -1(A)) where A is a finite union of intervals
with ?(A)=1/2 (? is the Lebesgue measure)?
 
Answer: 1/2
Solution: Let k be an integer >2 and ?=2-k. A is null.
Consider the following procedure:
In step 0 we add the interval [0,?] to A.
In step 1 we add the interval [1/2,1/2+?/2] to A.
In step 2 we add [1/4,1/4+?/4] and [3/4,3/4+?/4] to A.
...
In step i we add all intervals [o/2i,o/2i +?/2i]
(where o ranges over odd values< 2i) to A.
Note that ?/2i=2-(i+k)
...
 
We minimally edit any interval to be added to remove any
excess so that ?(A)?1/2. Stop when ?(A) reaches 1/2.
 
Since each addition to A covers as much of f -1(A) as its own
increment in the measure of A, ?(A ? f -1(A)) remains less than
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.