## ?'(x)

Yesterday I talked about the function $?(x)$. If you recall (or rather, if you don’t… if you do recall, you can probably skip to the next paragraph), I defined this function by lining up two infinite binary trees. One tree was obtained by taking mediants, giving us the Stern-Brocot tree, while the other was obtained by taking midpoints, giving us a tree of “dyadic” fractions (denominators are powers of two). To evaluate $?(x)$, you find $x$ in the Stern-Brocot tree, and then $?(x)$ is the value in the corresponding position of the dyadic tree.

Instead of thinking about infinite binary trees, let us think about cutting each tree off at some level, $n$. The pictures from yesterday’s post are, if you ignore the vertical dots, the trees when $n=2$. In the dyadic tree, we will obtain all fractions $m/2^p$ where $0 is odd and $1\leq p\leq n+1$. Said another way, we will get all of the values $m/2^{n+1}$ where $0 (not necessarily odd anymore). If you think about it for a few moments, you’ll notice that these points are equally spaced in the interval, each being $1/2^{n+1}$ away from its neighbors. This is not the case for the Stern-Brocot tree.

In the truncated Stern-Brocot tree, points are scattered through the interval (0,1). We can see that they are scattered in a way that is symmetric around 1/2, but what else can we say? Think about choosing some number, $b$, of buckets, call them $B_0,\ldots,B_{b-1}$. Let $B_i$ collect all of the points from the truncated Stern-Brocot tree whose value lies between $i/b$ and $(i+1)/b$. Of course, I’m being a little loose with my endpoints, but hopefully the idea comes across. If you choose an appropriate number of buckets, depending on the depth of your truncated tree, you can arrange that no point is an endpoint of a bucket’s interval.

Anyway, when you’re done with that, count how many points are in each bucket. This defines a function from the interval $[0,1]$ to non-negative integers, where the value at all points in $B_i$ is the count of the number of Stern-Brocot points in the bucket $B_i$. Here’s an example graph, obtained by taking the depth 10 Stern-Brocot tree, and putting points into 59 buckets (unless I coded something up wrong :)):

You could next scale this graph vertically by a constant so that the total area of all of the rectangles is 1. That is, you could make the graph that of a probability distribution. Of course, the distribution you get will depend on not ony the depth of the tree, but also how many buckets you choose. Since I’m only vaguely sure what I’m talking about, let me not say much more about that.

A less graphical way to think about all of this is that, for each $n$, I define two random variables $X_n$ and $Y_n$. The first, $X_n$ picks a value from all of the nodes in the Stern-Brocot tree of depth $n$, assuming each is equally likely. The second is basically the same, using the dyadic tree instead. I’m not particularly well-versed in probability, but I guess you are allowed to take the limit of these probability distributions, let’s say $X=\lim X_n$, and similarly $Y=\lim Y_n$. This defines two probability functions on the interval $[0,1]$ (well, I suppose technically it probably defines a probability function on the rationals there…).

How are the two distributions related? Well, basically the same way as the trees are related by $?(x)$. In particular, we have

$P(a\leq X\leq b)=P(?(a)\leq Y\leq ?(b))$

Since $Y$ is just the uniform distribution (the dyadic points are equally distributed, recall), the probability on the right is just $?(b)-?(a)$. Let $\mu$ be the graph of the probability function for $X$, so that the probability on the left is the integral $\int_a^b \mu\ dx$. We have, then

$\displaystyle \int_a^b \mu(x)\ dx=?(b)-?(a)$

This looks so much like the fundamental theorem of calculus that we want to say that $?'(x)=\mu(x)$. You could also read it as saying that $?(x)$ is the cumulative distribution function of $\mu(x)$. Thinking back to my buckets from earlier, this means that if I define the value over the interval covered by $B_i$ to be the sum of the counts of all the values in all the buckets up to $B_i$, then I should get a graph that looks like $?(x)$. You be the judge:

Of course, we probably aren’t exactly allowed to say $?'(x)=\mu(x)$. Consider the rational $s/t$, and suppose that $?'(s/t)$ exists, i.e., that

$\displaystyle\lim_{x\to s/t}\dfrac{?(x)-?(s/t)}{x-s/t}$

exists. If this two sided limit exists, then we can calculate it by coming at it from either side. Let’s think about $x\to s/t^+$, that is, from the right. But let’s simplify some more, still. If the one-sided limit exists, then we can calculate it by calculating the limit of the difference quotient for any sequence of values $x$ converging to $s/t$. The sequence of values, on the right of $s/t$, that I want to consider are those neighbors, on the right, of $s/t$, in the Stern-Brocot sequences.

Let’s say that the first neighbor is the right child of $s/t$ in the Stern-Brocot tree, and call it $p/q$. Then all of the successive neighbors are the successive left children of $p/q$. These points are all of the points $(ms+p)/(mt+q)$, for positive values $m$. If we let $m\to \infty$, these weighted mediants converge to $s/t$.

So let’s consider the following:

$\displaystyle\lim_{m\to\infty}\dfrac{?\left(\frac{ms+p}{mt+q}\right)-?\left(\frac{s}{t}\right)}{\frac{ms+p}{mt+q}-\frac{s}{t}}$.

Let’s start simplifying in the denominator. That fraction is $(pt-sq)/(t(mt+q))$, but since $p/q$ and $s/t$ are neighbors in some Farey sequence, this difference is 1. So the denominator is $1/(t(mt+q))$.

In the numerator, we are evaluating $?(x)$ at weighted mediants of $s/t$ and $p/q$. The corresponding $?(x)$ values are then weighted averages. Playing with the formulas a little bit, you can determine that

$?\left(\frac{ms+p}{mt+q}\right)=\dfrac{(2^m-1)?(s/t)+?(p/q)}{2^m}$.

Combining all of the formulas so far, and simplifying, it turns out that the limit we are after is just

$\displaystyle\lim_{m\to\infty}\left(?(p/q)-?(s/t)\right)\cdot t\cdot (mt+q)\cdot 2^{-m}$

Of course, that power of two wins the race to infinity, and so this limit is 0.

We have shown then, that if $?'(p/q)$ exists, then it is 0. Since $?(x)$ isn’t a constant graph, we better have $?'(x)$ non-zero on the irrationals. Perhaps I’ll leave that to you.

I should, of course, mention that I learned about this reading the paper “On the Minkowski measure” by Linas Vepstas, available online here (along with a handful of other papers that look fun). Hopefully I haven’t mangled anything too badly.

Advertisements