Tuesday, July 31, 2012

A natural function with very odd properties


    this is a matter of opinion and taste.
    YES- take Cantor Functions,
    also known as the Devil's staircase. Some readers knew this.


I base my exposition on the exposition in
How to Gamble if you Must
if you must

Consider the following game: Let 0 < p < 0.5.
much money you start with.
You repeat until you have 0 or you have 1.

This is analyzed. In the paper and is interesting.

and can stop.

If you play BOLDLY then
what is the probability that you will end with 1?
(We assume 0 ≤ x ≤ 1.)
F satisfies the following recurrence:





even though its strictly increasing.
However, I emailed the author who emailed me the following:

There are proofs in the book Probability and Measure by Patrick
more of a hard analysis type proof.

Ekhad, Georgiadis, Zeilberger have written a paper
How to Gamble if you're in a Hurry


  1. Doesn't "strictly increasing" mean x > y -> f(x) > f(y). Cantor functions are nondecreasing.

    1. Ah- good point.

      That raises the odd question- is there a strictly increasing
      function with dervi 0 at almost every point of [0,1],
      strictly increasing, and you can PROVE this easily
      (the function may be contrived).

    2. Can't be true if you want continuous as well.

  2. For #4, as Konstantin and I pointed out last time, there is a probabilistic example that's at least as natural as the gambling game: the Wiener process aka Brownian motion in one dimension. The gambling game is neat, and of a similar spirit. By analogy with the devil's staircase, maybe the points where the F has derivative zero (or where the player loses money?) form an uncountable measure zero set. Then we'll have random walk based examples for all three beasts.

    1. Please let me agree with Sasho, for the following pragmatic reason.

      A central teaching of modern quantum information science is that dynamical phenomena whose coarse-grained descriptions are naturally algebraic (e.g., projective quantum measurements) are associated to informatically equivalent fine-grained descriptions (e.g, Carmichael-style quantum trajectory unravellings) whose functional descriptors generically have the paradoxical traits that Lance's post describes.

      Hence, from a purely pragmatic point-of-view, students henceforth should be taught that these paradoxical functions are "natural".

      It's incredibly obvious, isn't it Mandrake?   :)

  3. Isn't the Cantor set natural when seen as {0,1}^Z for example? (A very natural family of objects, used in many places.)

    And isn't the boundary of a fractal a natural thing? Fractals also appear in many places, where the goal is not only to "define a funny function".

  4. Answer to #6 is gamma process!

    I still going with the stochastic process definition of natural. So I should mention the gamma process as what I think of as the "answer" to question 6: http://en.wikipedia.org/wiki/Gamma_process. It is a pure jump process and hence only has a countable number of jumps--this means its derivative is equal to zero almost everywhere. But, since there is a chance of jump in any arbitrarilly small time interval--it is a purely increasing process. It has lots of other nice properties--but I won't go into them now. (In general, any semi-martingale can be written as a determinsitic process plus a brownian motion process plus a gamma process. I consider semi-martingales the most natural processes we can work with, and the french school of probability proves theorems of this nature.)

    1. "In general, any semi-martingale can be written as a determinsitic process plus a brownian motion process plus a gamma process."

      Interesting. Can you give an accessible reference for this result?

  5. I agree with the previous anonymous comment: If you have ever viewed real numbers in terms of their decimal expansions I don't see how you can avoid acknowledging that the (say) decimal strings that only have 0 and 1 in their expansions is natural set.

  6. 1) Please elaborate- what is the 1-d Brownian Motion function?
    I assume its someting like, a particle starts at 0 and
    at every stage it goes left or right (how much?) and so
    f(t) = prob that its at place t. But I am unclear on this so
    please elaborate. I agree that something like that is clearly

    2) What is the Gamma Process?

    1. The gamma process is such that each increment looks like a gamma random variable. So it consists of a few jumps mixed with a more small jumps mixed with a huge number of tiny jumps, etc. One of my favorite properties of the gamma process is that it is a "perfect sun shade." Meaning if you were to sit under a gamma process you would be able to see in all directions EXCEPT straight up and down. So if the sun were perfectly over head, it wouldn't block any views at all--but it would block the sun out completely.

      I've rethought my answer to #2. I'm going with it being natural also. I had forgotten that zeros of a brownian motion form a perfect set and is uncountable. So I'm happy with that being natural also.

      So all three have nice probabilistic answers and so show that the properties are "generic."

    2. Gasarch,

      1-d brownian motion is usually defined as a probability distribution on functions f:R --> R with the following properties:

      * for any reals x, y, f(x) - f(y) is distributed like a gaussian random variable with mean 0 and variance (x-y)^2
      * the increments f(x_1) - f(x_2), f(x_2) - f(x_3), etc., for any x_1 < x_2 < x_3, ... are independent
      * f is continuous with probability 1

      A classical construction by Levy shows that such things exist. Another classical result is that with probability 1, a function sampled from this distribution is continuous and non-differentiable.

      Intuitively, the random variable f is a continuous time random walk on the real line: f(t) tells us the position at time t (well, and we have negative times, but let's restrict f to [0, 1) to make this easier). One can get the Brownian motion as the limit of discrete random walks with smaller and smaller steps. I.e. think of a random walk that proceeds in time steps of length delta and at each time i*delta moves to f((i-1)*delta) + N(0, delta) where N(0, delta) is a gaussian with mean 0 and variance delta^2. This defines f at points that are integer multiples of delta. To define f everywhere, interpolate linearly. Now, as delta goes to infinity, f converges to brownian motion in distribution. This in fact happens even if the steps are not guassian but follow any distribution with finite variance. This "central limit theorem" for random walks is the Donsker invariance principle.

      A great referene is the book by Moerters and Peres: http://research.microsoft.com/en-us/um/people/peres/brbook.pdf

    3. A correction: I meant as delta goes to 0.

  7. #2 - iirc any non-empty measure 0 subset of the interval without isolated points is Cantor (modulo an increasing continuous map of the interval). Being essentially unique makes it natural, I'd say.