Number of flips to get to a Set of Positive Lebesgue Measure
A consequence of Exercise 1.1.19 on page 13 of Stroock's "Probability Theory: An Analytic View" is that if a set $E\subset[0,1)$ has positive (Lebesgue) measure, then for almost every $x\in[0,1)$, a finite number of flips of its binary expansion will move $x$ to $E$. The exercise in Stroock suggests using the Kolmogorov 0-1 Law but it can also also be proved measure theoretically using an open cover approximation of $E$. I read and did this a long time ago but when thinking of something else recently, I wondered
- Given a set of positive measure, what is the expected number of flips required? (No clue.)
- Is the expected value finite? (I think so but I don't have a proof.)
Even for a set that is a finite union of dyadic intervals, it is not clear to me what the expected value is. For example, what is the maximum of the expected value over the collection of $E\subset[0,1)$ that is a finite union of dyadic intervals with measure 0.5?
I would appreciate it if someone can give me a reference if this is well known or some hint on how to do this if it is reasonably doable for someone who knows some measure theory (say at the level of Folland, Royden, or Rudin.)
Solution 1:
The expected number of flips can be infinite. I first show how to make it larger than any finite number.
Choose a large integer $n$. Divide $[0,1]$ into $2^n$ diadic intervals, which we indexed by $W_n:=\{ 0, 1 \}^n$. Choose real numbers $\alpha < \beta$. Let $X$ be the union of those dyadic intervals indexed by $w \in W_n$ for which at most $n/2+ \alpha \sqrt{n}$ of the entries of $w$ are one and let $Y$ be the corresponding union where $w$ has at least $n/2+\beta \sqrt{n}$ ones. By the central limit theorem, $|X|$ approaches $\sqrt{\frac{2}{\pi}} \int_{- \infty}^{\alpha} e^{-2 x^2} dx>0$ as $n \to \infty$. Also by the central limit theorem, with probability approaching $\sqrt{\frac{2}{\pi}} \int_{\beta}^{\infty} e^{-2 x^2} dx>0$, a random element of $[0,1]$ will lie in $Y$. To get from $Y$ to $X$ requires at least $(\beta-\alpha) \sqrt{n}$ flips. Fixing $\alpha$ and $\beta$ and sending $n$ to infinity, we have a family of sets whose measure approaches a positive limit while the expected number of flips goes to infinity. This also shows that the expectation of $\phi(\mbox{number of flips})$ goes to $\infty$, if $\phi: \mathbb{Z}_{\geq 0} \to \mathbb{R}$ is any function with $\lim_{t \to \infty} \phi(t)=\infty$.
Now, to get an infinite construction. We use a "fat cantor set" construction.
Choose a sequence $\alpha_k$ approaching infinity fast enough that $\prod_k \left(\sqrt{\frac{2}{\pi}} \int_{- \infty}^{\alpha_k} e^{-2 x^2} dx \right) >0$. Choose a sequence $\beta_k$ with $\beta_k > \alpha_k$. Choose $n_k$ large enough that $\sum \left ( (\beta_k-\alpha_k) \sqrt{n_k} \sqrt{\frac{2}{\pi}} \int_{\beta}^{\infty} e^{-2 x^2} dx \right)$ diverges, and also large enough the central limit approximations are very close to correct.
Let $X$ be the set of real numbers in $[0,1]$ whose first $n_1$ bits have at most $n_1/2+\alpha_1 \sqrt{n_1}$ ones and whose next $n_2$ bits have at most $n_2/2 + \alpha_2 \sqrt{n_2}$ bits, etcetera. Assuming that we include a number if either of its two binary representations are as specified, this is an intersection of closed conditions, hence closed. The measure is greater than $0$ by the condition on that the product is $>1$; the expected number of flips is infinite by the condition that the sum is $\infty$.