19
$\begingroup$

It is well-known that one can get the Lebesgue measure on [0, 1] by tossing a fair coin infinitely (countably) many times and mapping each sequence to a real number written out in binary.

I was trying to explore what happens if you follow the same procedure with a biased coin. I managed to prove that if the induced measure is absolutely continuous with respect to the Lebesgue measure, then the density must be discontinuous on at least a dense set (which includes all rational numbers in [0, 1] with a finite binary expansion).

But I suspect it's much worse than that. When I try to visualize the cumulative distribution function, it seems to have a "fractal staircase" type of shape, so I suspect the measure is, in fact, singular, but I can't prove it.

Q1. Are there any standard techniques for proving a measure is singular ?

Q2. I strongly suspect that a natural question like this has already been resolved. Any link to a textbook and/or paper would be appreciated.

$\endgroup$
1
  • $\begingroup$ Reference: P. Billingsley "Probability and Measure" Third Edition. page 407. (From comments to a MSE question.) $\endgroup$ – r.e.s. Sep 20 '16 at 14:24
20
$\begingroup$

For $\omega \in [0,1]$, let $X_i(\omega)$ be the $i$th binary digit of $\omega$. (If $\omega$ is a dyadic rational and thus has two binary expansions, let's say we choose the expansion that ends with all 0s; it makes no difference). Under Lebesgue measure, the $X_i$ are iid Bernoulli $1/2$ random variables, so by the strong law of large numbers, $\frac{1}{n}(X_1 + \dots + X_n) \to 1/2$ almost surely. In other words, the set $A_{1/2} := \{\omega : \lim_{n \to \infty} \frac{1}{n} (X_1(\omega) + \dots + X_n(\omega)) = \frac{1}{2}\}$ has Lebesgue measure $1$.

If $\mu_p$ is the measure coming from a coin that comes up heads with probability $p \ne 1/2$, then under $\mu_p$, the $X_i$ are iid Bernoulli $p$. By the strong law again, we have $\mu_p(A_p) = 1$. But $A_p$ and $A_{1/2}$ are clearly disjoint, so Lebesgue measure and $\mu_p$ are mutually singular.

I guess the "standard technique" here is to use a zero-one type theorem from probability giving an almost sure statement about limiting behavior, and look for a place where the two measures exhibit different limiting behavior.

$\endgroup$
5
  • $\begingroup$ This is a nice answer - I think it's essentially the same as mine, but yours has the advantage of relying on more well-known technology (the SLLN). $\endgroup$ – Anthony Quas Sep 20 '16 at 8:50
  • $\begingroup$ When you have a hammer, everything looks like a nail. I agree that a more elementary argument (such as Nate's) is better. $\endgroup$ – Gerald Edgar Sep 20 '16 at 17:28
  • $\begingroup$ This is a truly excellent answer. I am keeping this as Exhibit A for how a probabilistic argument neatly proves a result which seems very intractable by analysis type techniques. I suspect the "hard analysis" part goes into proving the strong law of large numbers. $\endgroup$ – Anindya Sep 20 '16 at 23:23
  • $\begingroup$ @Anindya: Sort of, but proving the strong law in this case isn't particularly difficult. $\endgroup$ – Nate Eldredge Sep 20 '16 at 23:59
  • $\begingroup$ This classical argument can give more, namely the Hausdorff dimension of the measures $\mu_p$ and the sets $A_p$. For an exposition and references see, e.g., math.stonybrook.edu/~bishop/Bishop_Peres_Jan_22_2015.pdf $\endgroup$ – Yuval Peres Sep 23 '16 at 17:32
15
$\begingroup$

Yes. You're right; the measure is singular. One soft way to do this is to use ergodic theory. The "coin-tossing measures" are all distinct ergodic shift-invariant measures on $\{0,1\}^{\mathbb N}$ and any two ergodic invariant measures for any fixed transformation are mutually singular. The map from sequences of 0's and 1's to $[0,1]$ is 1-1 off a countable set, and so mutual singularity is preserved when the measures are transferred to $[0,1]$.

One reference for all of this is Peter Walters' book, An Introduction to Ergodic Theory (publ. Springer Graduate Texts in Mathematics).

$\endgroup$
2
  • 1
    $\begingroup$ I swtiched to Nate's answer as this was a very direct argument which nails the result. I will follow up on your Ergodic Theory reference though. It's very interesting that a pretty simple and natural question is leading into quite deep waters. Thanks. $\endgroup$ – Anindya Sep 20 '16 at 23:26
  • $\begingroup$ I'm glad you got what you wanted. The Birkhoff ergodic theorem that is at the heart of my answer is a generalization of the Strong Law of Large Numbers, so the answers are, in fact, quite similar even though they look different. $\endgroup$ – Anthony Quas Sep 20 '16 at 23:32
12
$\begingroup$

Just a side comment: if you pass from binary to trinary, you can still obtain the Lebesgue measure by choosing the digits $0$, $1$, $2$, with probabilities $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ (something one may call "a fair trinary coin"). Now, if you use the "biased" coin $(\frac{1}{2},0,\frac{1}{2})$, then you'll arrive exactly at the Cantor function, which puts mass $1$ to the Cantor set (which has null Lebesgue measure).

$\endgroup$
1
  • 1
    $\begingroup$ That's really interesting. Great observation ! $\endgroup$ – Anindya Sep 20 '16 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.