pdf preprint - Academics

Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 1
A Fair-Bold Gambling Function is Simply
Singular
Richard D. Neidinger
Abstract. A new variation on a classic singular function has derivative values that, unlike the
classic, can be simply characterized by secant slopes between dyadic rationals. A singular
function is defined to have have derivative zero almost everywhere, even though it is continuous and (in this case, strictly) increasing. Points where the derivative of the new variation is
zero and points where it is infinite are characterized in terms of binary digits. The classic function is described as the probability of reaching a goal when gambling on a fixed-probability
game; the variation uses an alternating probability.
1. THE BOLD GAMBLING FUNCTION. Suppose you go to Vegas with $750 and
plan to gamble until you reach a goal of $1,000 or go broke. Assume you repeatedly
play one game with a fixed probability a of winning, like betting on red in American
roulette where a = 18=38 :474. Each bet B is either lost or pays 1:1, so nets
either B or +B . The best strategy is bold gambling, where you bet the most you
can without going over your goal [5][6]. This particular scenario is a short game
where you can win only on the first or second bet, so the probability that you will
reach your goal is a + (1 a)a
:723. (You can beat Vegas most of the time!
Unfortunately, your expected value is only $723.) The probability of reaching your
goal as a function of initial stake is a strictly-increasing singular function, meaning it
continuously increases but has derivative zero almost everywhere!
1
0.9
probability of reaching goal
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
s tarting portion x of goal
0.8
1
Figure 1. The bold gambling function g1=3 (x) with bounding rectangles and secant slopes.
January 2014]
FAIR-BOLD SINGULAR FUNCTION
1
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 2
Let x denote the original portion of a goal, so 0 < x < 1. Bet x if x 1=2 or
bet 1 x if x > 1=2, and gain or drop the bet amount with probability a or 1 a,
respectively. Repeat such rounds until you win by reaching the goal of 1 or lose
with value 0. The bold gambling function ga (x) = probability of winning this game
starting with x. The introductory example computed g(18=38) (0:75) 0:723. The
graph of g(18=38) is visually close to the "fair" diagonal g1=2 (x) = x, but the singular
property occurs for any a 6= 1=2 in (0; 1). We focus on 0 < a < 1=2 < 1 a < 1,
and show the graph of g1=3 (x) as the limiting curve in Figure 1.
The graph of ga is a fractal where the entire image is the union of two smaller
copies that both shrink the horizontal by 1=2: the lower-left half shrinks the vertical
by a, and upper-right half shrinks the vertical by 1 a. Figure 1 shows the result of
repeating this process, starting with the unit square and fair diagonal. The geometric
transformations are given by simple probability reasoning. To win starting with x
1=2, you must win the first round with probability a and win the game with the result
2x, so
ga (x) = a ga (2x) for 0
x
1=2.
Thus, if (x; y) is a point on the graph, then (x=2; a y) is on the graph. To win starting
with x > 1=2, you may win round one OR lose round one and win the subsequent
game with x (1 x), so
ga (x) = a + (1
a) ga (2x
1) for 1=2
x
1.
Hence, If (x; y) is a point on the graph, then (1=2 + x=2; a + (1 a) y) is on the
graph.
The analytical properties of ga have been known for over a century, so we will
only argue the singular property and discuss the problem that will be solved with a
variation in the next section. The function ga has been called de Rahm’s function and
Lebesgue’s function and has many different definitions and motivations in [2], [3], [4],
[7], [8], [10], [11], [14], and [15], but we understand it as the bold gambling function
following the exposition in [5]. Intuitively, ga is continuous and strictly increasing.
The corners of the rectangles in Figure 1 occur at dyadic rationals (the denominator
is a power of 2), where the derivative does not exist, since it is zero from the right
and infinite from the left. Other points fall in a unique sequence of nested rectangles,
determined by the digits of the binary expansion of x. Let Sng (x) be the slope of the
diagonal of the rectangle width 2 n that bounds (x; ga (x)) (diagonals shown in Figure
1). If ga0 (x) exists, then it must be that the sequence of secant slopes Sng (x) ! ga0 (x).
(This is a general real analysis exercise: if f is differentiable at x and an ! x from the
left and bn ! x from the right, the difference quotients from an to bn must converge
g
to f 0 (x). [4]) By the transformation on each step, either Sn+1
(x) =
g
Sn+1
(x) =
1 a
1=2
a
1=2
Sng (x) or
Sng (x). What if ga0 (x) = c 6= 0? Then
g
Sn+1
(x)
c
= =1
g
n!1 Sn (x)
c
lim
but this is impossible, since each term of this sequence is either 2a or 2(1 a) and a 6=
1=2. The contradiction proves that ga0 (x) exists ) ga0 (x) = 0. Lebesgue’s Theorem
states that a monotone function is differentiable almost everywhere ([13], p. 112).
Thus, ga has derivative zero almost everywhere. This existential argument does not
tell us where the derivative is zero.
2
c
THE MATHEMATICAL ASSOCIATION OF AMERICA
[Monthly 121
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 3
The problem is that the secant slopes do not conclusively determine the derivative,
so that it is difficult to characterize exactly where the derivative is zero. Though short
of complete characterization, [11] handles points where the binary representation has
density (or frequency) of digit zero that exists and is not zero or one. A source of
difficulty and limitation in determining the derivative is found in our claim that
lim Sng (x) = 0 ; ga0 (x) = 0:
n!1
We postpone the technical counterexample to Section 4. Conceptually, in a binary
representation of x, strings of zeros produce very flat slopes, while strings of ones
very steep slopes. For example, look at the rectangle corner at x = 1=2 = (:1)2 in
Figure 1 and consider the slope from :1 to :100001 in binary versus the slope from
:011111 to :1. Crudely, the problem is that these different slopes are very near each
other due to the carry in binary arithmetic. Actually, the variation in the next Section
will also have vertical and horizontal slopes arbitrarily close to any point. However,
the binary arithmetic problem will be solved and we will be able to characterize the
derivative value in terms of Sn (x) and in terms of binary digits without restriction!
2. THE FAIR-BOLD GAMBLING FUNCTION. To play against a friend, let’s
make the game more fair. Instead of always giving the house the higher probability,
alternate probabilities a and 1 a on each round, so that on odd rounds you gain with
probability a, and on even rounds you gain with probability (1 a). Now, we must
require bold gambling, since otherwise you would only bet when the probability was
1
to your advantage. So the game is: you start with value 0 < x < 1; bet x if x
2
or bet 1 x if x > 21 ; and continue to play until you win (value 1) or lose (value
0). The fair-bold gambling function fa (x) = probability of winning this alternatingprobability game starting with x. For example, f1=3 (1=4) = 2=9 since you must first
win with probability a = 1=3 and then win again with probability (1 a) = 2=3.
This function was included in [14] where sequences of (what we call) probabilities
1
0.9
probability of reaching goal
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
s tarting portion x of goal
0.8
1
Figure 2. The fair-bold gambling function f1=3 (x) and the diagonal of a truly fair game.
January 2014]
FAIR-BOLD SINGULAR FUNCTION
3
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 4
were shown to create singular functions, though this particular function was not shown
and derivative values were not characterized. Figure 2 shows the graph of this fair-bold
gambling function. There now are points where the game is fair (on the diagonal) and
intervals where the game is to your advantage, even though you start with the lower
probability. Other values of a produce graphs in Figure 3 with only one cross-over
point The graph of fa has no sharp corners, looking more differentiable than ga , but
we will show that fa (x) is singular, having derivative zero almost everywhere. Intuitively, the graph is continuous and strictly increasing from (0,0) to (1,1), since if
you start with a little more value, your chances are a little better. Rigorous proof will
follow once we show how fa (x) is tied to the binary representation of x. The key
properties of this function can be understood in terms of geometric transformations of
the plane.
The game is symmetric, since if you start with probability a and amount x, then
your opponent is playing the same game but starting with probability 1 a and
amount 1 x. The opponent wins when you lose, so
1
fa (x) = f(1
a) (1
x):
(1)
This corresponds to rotation by 180 around (1=2; 1=2), which is given by R((x; y)) =
(1 x; 1 y). So
R((x; fa (x)) = (1
x; 1
fa (x)) = (1
x; f(1
a) (1
x)):
(2)
If we let Gf denote the graph of f in the unit square, then R(Gfa ) = Gf(1 a) . If
your probability function is f0:1 , then rotate its graph to get the opponent’s graph of
f0:9 as shown in Figure 3. This is not the inverse function f0:11 which is also shown
1
a=0.1
inverse
a=0.9
0.9
probability of reaching goal
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
starting portion x of goal
0.8
1
Figure 3. Rotate the graph of f0:1 around the center to get the graph of f0:9 .
for comparison. These more extreme parameters do suggest that the derivative could
be zero almost everywhere. We will find a set of measure one where the derivative is
4
c
THE MATHEMATICAL ASSOCIATION OF AMERICA
[Monthly 121
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 5
zero and a set of measure zero where the derivative is infinity. Curiously, the images
of these sets swap the measures, since points with derivative infinity correspond to
points on the inverse function that have derivative zero. This is a property of singular
functions in general.
The following fractal property shows how the graph relates to sub-pieces of itself.
Simple probability gives the relationships. First,
fa (x) = a f(1
a) (2x)
for 0
x
0:5,
(3)
since if you start with x 0:5, you must win the first round with probability a and
also win the resulting game where your first probability is now (1 a) and you have
2x. Second,
fa (x) = a + (1
a) f(1
a) (2x
1) for 0:5
x
1,
(4)
since if x > 0:5, you can either win the first round with probability a OR lose it
and win the resulting game where your first probability is now (1 a) and you have
x (1 x) = 2x 1. We will show that these functional equations correspond
to the iterated function system (IFS) shown in Figure 4 that attracts to the graph of
fa . The first transformation T1 = A1 R, where R is the rotation described above
1
1
1
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.5
0.4
0.4
0.4
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
0
0
0
0
0.2
0.4
0.6
U0
0.8
0
1
0.2
0.4
0.6
0.8
0
1
U1 = T1 (U0 ) [ T2 (U0 )
0.2
0.4
0.6
0.8
1
U2 = T1 (U1 ) [ T2 (U1 )
Figure 4. IFS converging to f1=3 .
and A1 (x; y) = (x=2; a y) simply shrinks into the lower left corner, multiplying the
height by a. The second transformation T2 = A2 R, where A2 is the affine map
into the upper right corner A2 ((x; y)) = (1=2 + x=2; a + (1 a)y), multiplying the
height by (1 a). We now show that T1 (Gfa ) [ T2 (Gfa ) = Gfa . Then this invariant
set must be the limit of the IFS by an application of the contraction mapping theorem
[1]. First, let’s see how T1 maps any point (x; fa (x)) to another point on the graph in
the lower left corner.
T1 ((x; fa (x))) = A1 ((1
=
=
January 2014]
1
x; f(1
x
2
1
x
2
; a f(1
; fa
a) (1
x))) by (2)
a) (1
1
x
2
FAIR-BOLD SINGULAR FUNCTION
x)
by (3).
5
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 6
Second, T2 maps any point (x; fa (x)) to another point on the graph in the upper right
corner.
T2 ((x; fa (x))) = A2 ((1
x; f(1
a) (1
1 1 x
+
; a + (1
2
2
x
x
; fa 1
= 1
2
2
=
x))) by (2)
a) f(1
a) (1
x)
by (4).
Together, for all x in the unit square, we see that T1 (Gfa ) [ T2 (Gfa ) = Gfa . In fact,
the function graph is easily produced by plotting around 15 iterations of the origin; or
do two steps at a time to preserve the order of the points.
The nested rectangles in Figure 5 will help us understand the values and derivative values of fa . Figure 5 superimposes sequential IFS images starting with the unit
square (as in Figure 4 but without the arrow) Every point is in a sequence of nested
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
Figure 5. Nested images of the unit square converging to f1=3 :
rectangles, or two such sequences at the corners. Since the x-axis is scaled by 1/2,
a binary representation x = (:b1 b2 b3 b4 : : :)2 completely determines the sequence of
rectangles. At level n, the rectangle of width 2 n spans from xn = (:b1 : : : bn 000)2
to x+
n = (:b1 : : : bn 111)2 , where the bar indicates repeating the covered digit(s) forever. The heights of these rectangles is some product of a’s and (1 a)’s. The third
pane of Figure 4 shows the heights a(1 a), a2 , (1 a)2 , (1 a)a corresponding to
x expansions that start with binary bits :00, :01, :10, :11, respectively. Each sequence
of rectangles produces a sequence of secant slopes Sn by connecting the corners. As
with bold gambling, fa is a singular function:
fa0 (x) exists ) fa0 (x) = 0.
6
c
THE MATHEMATICAL ASSOCIATION OF AMERICA
(5)
[Monthly 121
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
If this were not true, fa0 (x) would be a nonzero constant. Then lim
Sn+1
Sn
a
1=2
swp0000.tex
Sn+1
Sn
=
fa0 (x)
fa0 (x)
page 7
=1
1 a
,
1=2
but every
=
or
which cannot accumulate at 1 for a 6= 1=2, a contradiction.
When considering slope of the curve, two extreme points stand out. At x =
(:010101)2 = 1=3, the nested rectangle heights are always multiplied by a, producn
ing the sequence of secant slopes an =2 n = (2a) . For a < 1=2, this is the flattest
sequence possible and converges to zero. At x = (:101010)2 = 2=3, the nested
rectangle heights are always multiplied by (1 a), producing the sequence of secant
n
slopes (1 a)n =2 n = (2(1 a)) . For a < 1=2, this is the steepest sequence
possible and diverges to infinity. In fact, every point will be measured by the extent to
which it agrees with (:101010)2 , and we will find that more than a majority agreement
is required to make the slope infinite.
Lemma 1. Let x in [0; 1] have a binary representation x = (:b1 b2 b3 b4 : : :)2 , where
notation ()2 may be suppressed. Define
kn (:b1 b2 b3 b4 : : :) = the number of digits in b1 : : : bn that agree with 101010,
and an =
a
1
a
Then, fa (x) = fa (:b1 : : : bn ) + an
if n is even
:
if n is odd
kn
(1
a)kn fan (:bn+1 bn+2 bn+3 : : :).
Proof. Suppose x = (:b1 b2 b3 b4 : : :)2 is a binary representation. Then the functional
equations (3) and (4) imply the following in binary:
fa (:0 b2 b3 b4 : : :) =
fa (:1 b2 b3 b4 : : :) =
f(1 a) (:0 b3 b4 : : :) =
f(1 a) (:1 b3 b4 : : :) =
a f(1 a) (:b2 b3 b4 : : :)
a) f(1 a) (:b2 b3 b4 : : :)
(1 a) fa (:b3 b4 : : :)
a) +
a fa (:b3 b4 : : :)
a + (1
(1
After n consecutive applications of these rules, we see that fa (:b1 b2 b3 b4 : : :) = A +
an kn (1 a)kn fan (:bn+1 bn+2 bn+3 : : :) where A only depends on n and the digits
b1 : : : bn . In particular, fa (:b1 : : : bn ) = A + an kn (1 a)kn fan (0) = A.
Values of fa (x) must agree for different binary representations of a dyadic rational
x, even though different decompositions result from applying Lemma 1. For example,
fa :100 = fa (:011) = a , while pulling off two digits of the latter gives fa (:01) +
a2 fa (1) = a(1 a) + a2 .
Theorem 2. fa is strictly increasing and continuous.
Proof. Suppose x < y with binary representations that disagree for the first time at
digit index m + 1, so x = (:b1 :::bm 0bm+2 bm+3 : : :)2 and y = (:b1 :::bm 1cm+2 cm+3 : : :)2
where either rx = (:bm+2 bm+3 : : :)2 < 1 or ry = (:cm+2 cm+3 : : :)2 > 0. Let A =
fa (:b1 : : : bm ) and B = am km (1 a)km . Then, fa (x) = A + B fam (:0bm+2 bm+3 : : :) =
A + Bam fam+1 (rx ) A + Bam with equality only possible when rx = 1: Also,
A+
fa (y) = A + B fam (:1cm+2 cm+3 : : :) = A + B[am + am+1 fam+1 (ry )]
Bam with equality only possible when ry = 0: Since equalities are not both possible,
fa (x) < fa (y) and fa is strictly increasing.
n
To prove continuity, we want jfa (y) fa (x)j < . Choose n so (maxfa; 1 ag) <
n
" and choose so jy xj < 2 so x and y agree in m n binary digits. Thus,
jfa (y) fa (x)j = A + B fam (:1cm+2 cm+3 : : :) [A + B fam (:0bm+2 bm+3 : : :)]
m
A + B [A + 0] = B (maxfa; 1 ag) < ".
January 2014]
FAIR-BOLD SINGULAR FUNCTION
7
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 8
We now prove that the derivative is zero at all the rectangle corners in Figure 5,
which is not visibly obvious and is very different from the bold gambling function.
Theorem 3. If x is a dyadic rational in [0; 1] and a 6=
fa0 (x) = 0.
1
2
with 0 < a < 1, then
Proof. For any such a, observe that 4a(1 a) < 1, since this parabola has a maximum of 1 at 1=2. Let x in [0; 1) be a dyadic rational and consider the derivative from the right. Using x = (:b1 :::bm 00)2 , let A = fa (x) = f (:b1 :::bm ) and
B = am km (1 a)km . For 0 < h < 2 m , there is an integer j
0 such that
2 (m+2j+2) h < 2 (m+2j) . Then x + h = (:b1 : : : bm 0 : : : 0 d1 d2 d3 : : :) with 2j
zeros and some binary digits di . By Lemma 1, fa (x + h) = A + Bfam (:0 : : : 0 d1 d2 d3 : : :) =
A + Baj (1 a)j fam+2j (:d1 d2 d3 : : :) A + Baj (1 a)j . Thus,
fa (x + h)
h
Baj (1 a)j
= 2m+2 B (4a(1
2 (m+2j+2)
fa (x)
j
a)) ! 0
as h ! 0 which implies j ! 1. So, derivative from the right, D+ fa (x) = 0 at any
dyadic rational and any a 6= 1=2.
The derivative from the left follows from the rotation property (1), since
fa (x)
fa (x
h
h)
=
=
[1
f(1
f(1
a) (1
a) (1
x)]
x + h))
h
[1 f(1
h
f(1 a) (1
Since 1 x is dyadic rational, D fa (x) = D+ f(1
that fa0 (x) = 0.
a) (1
x)
a) (1
(x
h))]
:
x) = 0. We conclude
The above proof shows the key technique that distinguishes the fair-bold gambling
function from the bold gambling function (or most other singular functions). When
we use increasingly long strings of consecutive zeros (or consecutive ones) in a binary
expansion, the corresponding slope factor is a power of 4a(1 a) which becomes
arbitrarily small. For example, an alternative argument for the derivative from the
left could use 1’s in place of 0’s and successfully mimic the derivative from the right
argument.
Now restrict to points that are not dyadic rational, where the sequence of secant
slopes is completely unambiguous. Any such x has a unique representation x =
(:b1 b2 b3 b4 : : :)2 and specific counts kn (x) of how many of the first n digits agree
with agree with 101010. Then, by Lemma 1 (or the geometric transformations), the
secant slope
fa (:b1 : : : bn 111:::) fa (:b1 : : : bn 000:::)
2 n
an kn (x) (1 a)kn (x) (fan (1) fan (0))
=
2 n
Sn (x) =
So,
Sn (x) = (2a)n
kn (x)
(2(1
kn (x)
a))
:
(6)
The derivative is completely determined by this sequence of secant slopes.
8
c
THE MATHEMATICAL ASSOCIATION OF AMERICA
[Monthly 121
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 9
Theorem 4 (Derivative Bounding Theorem). For 0 < a < 1; a 6= 1=2, and fairbold gambling function fa , there exist ; > 0 such that for all x 2 (0; 1) with x not
dyadic rational, and for all h 6= 0 such that x + 2h 2 (0; 1),
fa (x + h)
h
Sn (x)
where 2
(n+1)
< jhj
2
n
fa (x)
Sn (x)
.
Before proving this theorem, we state the immediate consequence for all x in [0; 1]:
fa0 (x) = 0 , lim Sn (x) = 0;
n!1
fa0 (x)
= 1 , lim Sn (x) = 1:
n!1
By the singularity argument (following (5)), Sn (x) cannot have a nonzero real limit,
so the only other possibility is that Sn (x) fluctuates with multiple accumulation points
(maybe including 1) and the derivative does not exist. When x is dyadic rational in
this general characterization, Sn (x) can be specified to be either of the two different
sequences, since both go to zero.
Lemma 5. If x is not dyadic rational and x
kn (x
2
n
) = kn (x) +
so, Sn (x
2
n
) = Sn (x)
2
n
is in (0; 1), then
2 f 1; 2g;
where
1
a
a
.
Proof. Fix x = (:b1 b2 b3 b4 : : :)2 and n such that x + 2 n < 1. Then not all b1 to bn
are ones, so we can define the maximum m n such that bm = 0. Thus
x+2
x = (:b1 : : : bm 1 011
1bn+1 bn+2 : : :)2 and
n
0bn+1 bn+2 : : :)2 :
= (:b1 : : : bm 1 100
Where these have the same digits, there will be no difference in the kn counts. The
block of consecutive ones in x and the block of consecutive zeros in x + 2 n have
length n m 0. If n m is even, these blocks will both have exactly (n m)=2
digits that agree with :101010. Only the mth digit makes a difference, so kn (x +
2 n ) = kn (x) 1, depending on whether bm agrees with the corresponding digit in
:101010. If n m is odd, all but one digit will again balance in the kn count, leaving
just digits m and m + 1 that will make a difference, so kn (x + 2 n ) = kn (x) 2.
For x 2 n > 0, the same argument applies with the roles of binary bits 0 and 1
switched. The Sn (x 2 n ) claim follows directly from (6).
Proof of Derivative Bounding Theorem 4. Constants will be in terms of a
^ = minfa; 1
ag < 1=2 < maxfa; 1 ag = 1 a
^. Let x 2 (0; 1) with x not dyadic rational.
First consider h > 0 such that x + 2h < 1 and define n where 2 (n+1) < h 2 n .
In Figure 5, points at x and x + 2 n lie in neighboring (sharing a corner) rectangles
++
of width 2 n , with endpoints xn < x+
x+2 n <
n < xn , so xn < x < x + h
January 2014]
FAIR-BOLD SINGULAR FUNCTION
9
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
n
x+
= x++
n +2
n . (Conditions x + 2h < 1 and 2
Since fa is an increasing function,
fa (x + h)
h
fa (x)
10:34 a.m.
(n+1)
< h insure that x++
n
fa (x++
fa (xn )
n )
(n+1)
2
+
fa (x++
fa (x+
n )
n ) + fa (xn )
=2
2 n
= 2[Sn (x + 2
= 2[
2
"
1
n
a
a
^
page 10
1.)
fa (xn )
) + Sn (x)]
+ 1] Sn (x)
a
1
swp0000.tex
#
2
+ 1 Sn (x);
a
^
h
i
2
where the last equality uses Lemma 5. Define = 2 ((1 a
^)=^
a) + 1 to give the
upper bound conclusion for h > 0.
For the lower bound, we find a rectangle within (x; x + h), using the width 2 (n+2)
rectangle around x + 2 (n+2) . Specifically, start with n + 2 binary bits of x and
+
++
twice add 2 (n+2) to make endpoints xn+2 < x+
n+2 < xn+2 . Then x < xn+2 < x +
(n+1)
2 (n+2) < x++
< x + 2 (n+1) < x + h. So,
n+2 = xn+2 + 2
fa (x + h)
h
fa (x+
fa (x++
n+2 )
n+2 )
2 n
fa (x)
(n+2)
= Sn+2 (x + 2
=
1
4
1
4
1
a
)=4
Sn+2 (x)
a
2
a
^
2
1
a
^
(2^
a) Sn (x);
using Lemma 5 and (6). Define = a
^4 =(1 a
^)2 to give the lower bound conclusion
for h > 0.
For h < 0 with 0 < x + 2h and n where 2 (n+1) < h 2 n , the same argument works, based on points to the left. Specifically, the upper bound uses endpoints
xn < x 2 n < xn < x < x+
n to argue
fa (x)
fa (x + h)
h
2 Sn (x
Similarly, the lower bound uses x + h < x
xn+2 < x to argue
fa (x)
10
c
fa (x + h)
h
Sn+2 (x
2
n
) + Sn (x)
2
2
(n+1)
(n+2)
Sn (x).
< xn+2 < x
)=4
2
(n+2)
<
Sn (x).
THE MATHEMATICAL ASSOCIATION OF AMERICA
[Monthly 121
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 11
3. DERIVATIVE CHARACTERIZATION BY BINARY DIGIT SEQUENCE.
Since the derivative is given by the secant slopes and the secant slopes depend only on
the sequence of binary digits, we can characterize the value of the derivative at a point
in terms of kn (x)=n, measuring digit agreement with :101010. This could be called
the running portion of digits that agree with 101010,
qn (x) =
kn (x)
= portion of first n binary digits that agree with 1010:
n
Just to remove ambiguity, let’s specify the terminating binary expansion for dyadic
rationals, although it makes very little difference (at most 2 in kn (x)). We regroup (6)
in terms of qn ,
!
qn (x) n
1
a
n
Sn (x) = (2a)1 qn (x) (2(1 a))qn (x) = (2a)
.
a
The border between limit zero and limit infinity for this sequence is given by
(2a)
1
a
Q
= 1 , Q(a) =
a
ln(a)
ln(2a)
ln(1
a)
:
The function Q(a) is graphed in Figure 6, where fa0 (x) = 0 roughly when qn (x) stays
in the shaded region. This same Q(a) is introduced in [8] to state implications about
(x) of n digits
1
f ' (x) = infinity
0.8
f ' (x) = 0
n
running portion q
a
a
Q(a)
0.6
0.4
f ' (x) = 0
a
0.2
0
0
fa' (x) = infinity
0.2
0.4
0.6
0.8
1
a
Figure 6. Portion of digit agreement with 1010 determines fa0 .
(not characterizations of ) ga0 . Using Q(a), again regroup
!
Q(a)
(q (x) Q(a)) n
1 a
1 a n
Sn (x) = (2a)
=
a
a
1
a
a
(qn (x) Q(a)) n
.
(7)
January 2014]
FAIR-BOLD SINGULAR FUNCTION
11
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 12
Since Sn (x) boils down to a constant to the power of a sequence, the Derivative
Bounding Theorem 4 characterizes the derivative in terms of this sequence.
Corollary 6. If 0 < a < 1=2 and x 2 [0; 1],
fa0 (x) = 0 , lim (qn (x)
n!1
fa0 (x) = 1 , lim (qn (x)
n!1
If 1=2 < a < 1, then
Q(a)) n =
1;
Q(a)) n = +1:
1 and +1 are switched.
Again, since Sn (x) cannot have a nonzero real limit, the only other possibility is
that (qn (x) Q(a)) n fluctuates with multiple accumulation points, but this is different from saying qn (x) fluctuates. Unlike digit density results for other singular
functions ([8], [11], [12]), the conditions of Corollary 6 do not require that qn (x) has
a limit nor that the derivative exists, only how qn (x) relates to Q(a). We will focus
on the case a < 1=2 since otherwise the relationship flips as seen in Figure 6.
Corollary 7. Let 0 < a < 1=2 and x 2 [0; 1].
lim sup qn (x) < Q(a) ) fa0 (x) = 0;
fn : qn (x)
Q(a)g is infinite ) fa0 (x) does not exist.
Also, lim inf qn (x) > Q(a) ) fa0 (x) = 1 ) eventually qn (x) > Q(a).
Proof. If lim sup qn (x) < y < Q(a), then for some N and all n N , qn (x) < y
and (qn (x) Q(a)) n < (y Q(a)) n ! 1. By Corollary 6, fa0 (x) = 0. The
second claim supposes some subsequence qnk (x) Q(a), so (qnk (x) Q(a)) nk
0 and the limit cannot be 1. By Corollary 6, fa0 (x) 6= 0, and, by the singular
property (5), fa0 (x) does not exist. Similar arguments give the fa0 (x) = 1 implications.
Most x do fall into the derivative zero case. Consider choosing x in [0; 1] randomly
by choosing the binary digits with equal probability of 0 or 1. Since odd digits and
even digits will both tend to half 00 s and half 10 s, qn (x) ! 0:5 and 0:5 is in the
shaded region of Figure 6 for all a 6= 1=2. Thus fa0 (x) = 0 with probability one
(almost everywhere).
Corollary 7 leaves only a very restricted case undecided. If lim sup qn (x) = Q(a)
from below (meaning that eventually qn (x) < Q(a)), then it is possible that either
fa0 (x) = 0 or fa0 (x) does not exist (and can’t be 1), as determined by the limit
in Corollaryp6. To make an example where fa0 (x) = 0, one can show that kn =
dn Q(a)
ne is a non-decreasing sequence of non-negative integers that never increases by more than 1. pThus kn defines x by p
a sequence of agreement
with 1010
p
or not. Since n
Q(a)
n
k
n
Q(a)
n=2
for
n
4
,
n
(qn (x)
n
p
Q(a)) n
n=2 and by Corollary 6, fa0 (x) = 0. An example where fa0 (x) does
not exist, occurs for some rational numbers. While dyadic rationals are well behaved,
the behavior of other rationals depends on whether the repeating string of digits is odd
or even!
Theorem 8. Let 0 < a < 1=2 and x be a rational number in [0; 1]. Let m be the
length of the shortest block of repeating digits in the binary expansion of x: For even
12
c
THE MATHEMATICAL ASSOCIATION OF AMERICA
[Monthly 121
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 13
m, let k be the number of digits that agree with 1010 within such a repeating block
that starts at an odd index. If m is odd, fa0 (x) = 0. If m is even:
k
< Q(a) =) fa0 (x) = 0;
m
k
> Q(a) =) fa0 (x) = 1;
m
k
= Q(a) =) fa0 (x) does not exist.
m
In the last case, Sn (x) eventually cycles between m positive real values.
Proof. If m is odd, every block of 2m repeating digits will have exactly half that
agree with the expansion of :1010, since any agreement in the first m block will be
switched in the second block. Thus qn (x) ! 0:5, and fa0 (x) = 0 by Corollary 7 If
m is even, the number in a repeating block that agree with :1010 will always be k , so
that qn (x) ! k=m and the first two cases follow from Corollary 7 If k=m = Q(a),
we show that Sn (x) eventually cycles. The binary expansion of x will repeat forever
after c m digits of which u agree with 1010, for some c and u. For n c m, n =
c m + q m + i for some quotient q and remainder i = n mod m. Then kn (x) = u +
q k + ji where ji is the count of 1010-digit-agreement within i digits of the repeating
block. Then (qn (x) Q(a)) n = kn (x) n k=m = u + q k + ji (c k + q k +
i k=m) = (u c k) + (ji i k=m) which takes only m values depending on i =
n mod m, let’s call them p(i) = (u c k) + (ji i k=m). By Corollary 6, fa0 is not
p(n mod m)
zero (so it can’t exist) or infinity. By (7), Sn (x) = 1 a a
cycles through
m positive real values, and the Derivative Bounding Theorem 4 bounds all difference
quotients.
Usually Q(a) is irrational, making the last case is impossible, but it is easy to create examples of the last case by reverse engineering what is needed. Let’s create an
example where Corollary 7 doesn’t apply since lim qn (x) = Q(a) from below. By
the intermediate value theorem, fix a such that Q(a) = 3=4. Start a binary expansion
with a block of 4 that disagree with 1010, then repeat the block of 4 where all but the
first agree with 1010, defining x = (:010100100010)2 . Clearly qn (x) ! 3=4 from
below. Both components of p(i) are negative (u ck = 3 and ji i k=m ranges
from 3=4 to 0) making the slopes Sn very small, as verified by numerical computation. For this same a, you can find other points where the components of p(i) are
positive, making the cycle of slopes larger than one. This same x has fa0 (x) = 0 for a
smaller a and fa0 (x) = 1 for a larger a.
4. SECANT SLOPES CAN FAIL FOR BOLD GAMBLING. In contrast, the wellstudied bold gambling function ga cannot be characterized by secant slopes nor binary
digits. We will show a counterexample x where limn!1 Sng (x) = 0 but ga0 (x) does
not exist. We focus on a < 1=2.
The general relationships for ga are similar to and slightly simpler than our treatment of the fair-bold gambling function. In the very first Figure 1, we saw that every
left-half rectangle (corresponding to a zero digit in binary) multiplies height by a,
while right-half (digit one) multiplies by 1 a. For x in [0; 1] with binary representation x = (:b1 b2 b3 b4 : : :)2 , define wn to be the number of ones in the digits in b1 : : : bn ,
then Sng (x) = (2(1 a))wn (2a)n wn and
ga (x) = ga (:b1 : : : bn ) + (1
January 2014]
a)wn an
wn
ga (:bn+1 bn+2 bn+3 : : :).
FAIR-BOLD SINGULAR FUNCTION
(8)
13
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 14
To construct a specific counterexample, let a = 1=3 and define irrational
x = (:001 000 001 000 000 000 000 000 001 000 : : :)2
where digits are all zeros except for an isolated one at each digit with index 3i . Because
of the predominance of zeros, limn!1 Sng (x) = 0, so that the binary representation
would "incorrectly predict" that the derivative would be zero. However, consider the
slope from the left by subtracting a binary bit just to the left of the (i + 1)st one, so
xi = x 2 j where j = 3(i+1) 1; so
x2 = (:001 000 000 111 111 111 111 111 111 000 : : :)2
where the remaining digits continue in the same pattern as x. Note that xi has a string
of 2(3i ) ones. Since 3(i+1) = 3i + 3i + 3i , the denominator of the slope x xi =
i
i
i
i
2(2 3 )(2 3 )(2 3 ) = 2(8 3 ). Let ai be x truncated at the ith one. Let x
^i be xi
(i+1)
rounded up in the 3
+ 1 digit, so that it terminates after a string of k = 2(3i ) + 1
ones. Since xi < x
^i < ai < x,
ga (x)
x
ga (ai )
ga (xi )
>
xi
x
ga (^
xi )
:
xi
Use (8) to peel off the first 3i 1 digits of ai and x
^i that all agree and have i 1
i
ones. So, ga (ai ) = ga (ai 1 ) + (1 a)i 1 a3 i ga (:1) while ga (^
xi ) = ga (ai 1 ) +
i
i 1 3i i
k
(1 a) a
ga (:011: : :11). Then ga (ai ) ga (^
xi ) = (1 a)i 1 a3 i+1 [1
ga (:11: k: :11)]. The opposing player perspective 1 ga (1 x) = g(1 a) (x) yields
1 ga (:11: k: :11) = g(1 a) (2 k ) = (1 a)k . Thus
ga (ai )
x
(1
ga (^
xi )
=
xi
i
i
a)2(3 )+i a3
2(8 3i )
i+1
=
a
2
1
a
a
i
8(1
a)2 a
3i
which diverges to 1, since 8(1 a)2 a > 1 for a = 1=3. Thus ga is not differentiable
at x. This argument could work for arbitrarily small a by using some pi instead of 3i
pi
which would result in (2p (1 a)p 1 a) as the last factor above, although p = 2
would not work.
The counterexample is more subtle than simply saying that there is an arbitrarily close point with infinite derivative, since even the fair-bold fa has this property.
For the above irrational x, the predominance of zeros implies that qn (x) ! 1=2 and
fa0 (x) = 0, by Corollary 7. To get an arbitrarily close point where the derivative is
infinity, take the first n digits of x followed by 1010. However, we have proven that
limh!0 (fa (x + h) fa (x)) =h = 0.
5. CONCLUSION. The fair-bold gambling function combines the appeal of fractals,
gambling, and unintuitive calculus properties. Singular functions, that continuously
increase with derivative zero almost everywhere, have fascinated mathematicians for
a century. Many analysis students see the Cantor function that is horizontal on the removed middle-thirds, but more should see strictly increasing examples, such as those
developed over a century ago. The fair-bold gambling function makes it as simple as
possible to understand derivative values, based only on the bits of a binary representation of x, just look at kn the number of bits that agree with 1010. For a < 1=2, either
k
Sn = (2a)n kn (2(1 a)) n goes to zero and the derivative is zero, or it doesn’t and
14
c
THE MATHEMATICAL ASSOCIATION OF AMERICA
[Monthly 121
Mathematical Assoc. of America
American Mathematical Monthly 121:1
July 9, 2014
10:34 a.m.
swp0000.tex
page 15
the derivative does not exist. The corresponding statement for the classic bold gambling function was shown to be false. The strange looking fair-bold gambling function
will be sure to raise interesting questions, such as area under the curve, fractal dimension, and intersections with the diagonal (not fixed points because we are iterating the
IFS, not the function). The answers are accessible using the scaled self-similarity.
ACKNOWLEDGMENT. I thank Daniel Bernstein, since this project built on his undergraduate honors thesis
that studied known singular functions, including the bold gambling function, with different motivations and
proofs.
REFERENCES
1. M. F. Barnsley, Fractals Everywhere, second edition, Academic Press, Boston, MA, 1993.
2. L. Berg, M. Krüppel, De Rham’s singular function and related functions. Z. Anal. Anwendungen 19
(2000), no. 1, 227–237.
3. B. Bernstein, M. Karamolengos, T. Erber, Sneaky Plasticity and Mesoscopic Fractals, Chaos, Solitons,
Fractals 3 (1993), no. 3, 269-277.
4. D. Bernstein, Algorithmic Definitions of Singular Functions, Honors Thesis, Davidson College, Davidson, NC, May 2013, http://davidson.lyrasistechnology.org/islandora/object/davidson:44175.
5. P. Billingsley, The Singular Function of Bold Play, Amer. Sci. 71 (1983), no. 4, 392-397.
6. L. Bohorquez, J. Switkes, American roulette: a gambler’s ruin. College Math. J. 45 (2014), no. 1, 33–40.
7. E. Cesàro, Fonctions continues sans dérivée, Archiv der Math. und Phys. 10 (1906), 57–63.
8. G. de Rahm, Sur quelques courbes definies par des equations fonctionnelles, Univ. e Politec. Torino.
Rend. Sem. Mat. 16 1956/1957 101–113. Translated in [9].
9. G. A. Edgar (ed.), Classics on Fractals, Studies in Nonlinearity, Westview Press, Advanced Book Program, Boulder, CO, 2004, 284–297.
10. G. Faber, Über stetige Funktionen, Math. Ann. 69 (1910), no. 3, 372–443.
11. K. Kawamura, On the set of points where Lebesgue’s singular function has the derivative zero. Proc.
Japan Acad. Ser. A Math. Sci. 87 (2011), no. 9, 162–166.
12. J. Paradís, P. Viader, L. Bibiloni, A new singular function. Amer. Math. Monthly 118 (2011), no. 4, 344–
354.
13. H. L. Royden, P. M. Fitzpatrick, Real Analysis, fourth edition, Pearson (Prentice Hall), Boston, MA,
2010.
14. R. Salem, On some singular monotonic functions which are strictly increasing, Trans. Amer. Math. Soc.
53, (1943). 427–439.
15. L. Takács, An increasing continuous singular function. Amer. Math. Monthly 85 (1978), no. 1, 35–37.
RICHARD D. NEIDINGER received his B.A. from Trinity University in 1977 and his PhD from the University of Texas at Austin in 1984. Since then he has taught Mathematics and Computer Science at Davidson
College. He is interested in analysis, functional analysis, dynamical systems, and numerical analysis, specifically the numerical method of automatic differentiation. He founded Friends of Accion that brings educational
opportunity to youth in the Yucatan peninsula of Mexico.
Department of Mathematics and Computer Science, Davidson College, Davidson NC 28035
[email protected]
January 2014]
FAIR-BOLD SINGULAR FUNCTION
15

Download Report