Cantor function
|
|
In mathematics, the Cantor function, named after Georg Cantor, is a function c : [0,1] → [0,1] defined as follows:
- Express x in base 3. If possible, use no 1s. (This makes a difference only if the expansion ends in 022222... = 100000... or 200000... = 122222...)
- Replace the first 1 with a 2 and everything after it with 0.
- Replace all 2s with 1s.
- Interpret the result as a binary number. The result is c(x).
For example:
- 1/4 becomes 0.02020202... base 3; there are no 1s so the next stage is still 0.02020202...; this is rewritten as 0.01010101...; when read in base 2, this is 1/3 so c(1/4)=1/3.
- 1/5 becomes 0.01210121... base 3; the first 1 changes to a 2 followed by 0s to produce 0.02000000...; this is rewritten as 0.01000000...; when read in base 2, this is 1/4 so c(1/5)=1/4.
(It may be much easier to understand this definition by looking at the graph below than by grasping the algorithm.)
This function is the most frequently cited example of a real function that is continuous but not absolutely continuous. It has no derivative at any member of the Cantor set; it is constant on intervals of the form (0.x1x2x3...xn022222..., 0.x1x2x3...xn200000...), and every point not in the Cantor set is in one of these intervals, so its derivative is 0 outside of the Cantor set. Extended to the left with value 0 and to the right with value 1, it is the cumulative probability distribution function of a random variable that is uniformly distributed on the Cantor set. This probability distribution has no discrete part, i.e., it does not concentrate positive probability at any point. It also has no part that can be represented by a density function; integrating any putative probability density function that is not almost everywhere zero over any interval will give positive probability to some interval to which this distribution assigns probability zero. See Cantor distribution. The Cantor function is the standard example of what is sometimes called a devil's staircase.
Alternative definition
Below we define a sequence of functions fn on the interval that converges to the Cantor function.
Let f0(x) = x.
Then fn+1(x) will be defined in terms of fn(x).
Let fn+1(x) = 0.5 fn(3x) when 0 ≤ x ≤ 1/3.
Let fn+1(x) = 0.5 when 1/3 ≤ x ≤ 2/3.
Let fn+1(x) = 0.5 + 0.5 fn(3 (x − 2/3)) when 2/3 ≤ x ≤ 1.
Observe that fn converges to the Cantor function. Also notice that the choice of starting function does not really matter, provided f0(0) = 0 and f0(1) = 1 and f0 is bounded.
Generalizations
Let <math>y=\sum_{k=1}^\infty b_k 2^{-k}<math> be the dyadic (binary) expansion of the real number 0 ≤ y ≤ 1 in terms of binary digits bk={0,1}. Then consider the function <math>C_z(y)=\sum_{k=1}^\infty b_k z^{k}<math>. For z = 1/3, the inverse of the function <math>x= (2/3) C_{1/3}(y)<math> is the Cantor function. That is, y = y(x) is the Cantor function. In general, for any z < 1/2, Cz(y) looks like the Cantor function turned on its side, with the width of the steps getting wider as z approaches zero.
The Minkowski question mark function visually loosely resembles the Cantor function, having the general appearance of a "smoothed out" Cantor function. The question mark function has the interesting property of having vanishing derivatives at all rational numbers, and yet being an absolutely continuous, strictly increasing function.ru:Канторова лестница