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

© Copyright 2019 ExploreDoc