Hacker News Reader

Comment by thomasahle | Hacker News Reader

Pretty cool that you can determine the exact probability distribution for the digits of fraction expansion of a random real number:

lim_{n->inf} Pr[k_n = k] = -log_2(1 - 1/(k+1)^2)

And this was determine already in 1929! I think fraction expansions was all the rage back then. https://en.wikipedia.org/wiki/Gauss%E2%80%93Kuzmin_distribut...

View on HN

Yes! Not only that, here's something I found mind-blowing: for almost all real numbers, the nth root of the nth convergent's denominator has as limit the same value, and that value is e^(pi^2/12ln2).

Am typing from phone so can't write it down here properly, but some details at an old blog post of mine: https://shreevatsa.wordpress.com/2010/04/30/some-incredibly-...

there's also Khinchin's constant - for almost all real numbers, the geometric mean of the first n continued fraction coefficients approaches a constant K as ngoes to infinity. K is about 2.68 (the geometric mean of the Gauss-Kuzmin distribution).

I like to pair this with a more trivial fact - for almost all real numbers, the arithmetic mean of the first n digits of the decimal expansion, as n goes to infinity, approaches 4.5.

> for almost all real numbers, the arithmetic mean of the first n digits of the decimal expansion, as n goes to infinity, approaches 4.5.

Is this just because Almost All Reals are Normal, and so in every base they have an equal distribution of all digits ?

That’s exactly it.

Here's an even more trivial fact: For almost all real numbers, the geometric mean of the first N digits of the decimal expansion, as N goes to infinity, approaches zero. (Really really fast!)

and a less trivial one: the arithmetic mean of the continued fraction coefficients goes to infinity.

Results like this are a lot of fun, and like many a reasonable number of cool results in number theory, are "surprisingly easy". There's a proof only using two ideas:

1) Birkhoff ergodic theorem, which states for a "nice" dynamical system, the probability that certain events occur can be described explicitly by an invariant distribution (see [1]), and

2) Continued fractions have an associated "nice" dynamical system (the Gauss map) which has an explicit probability distribution that is not too challenging to compute.

Of course, writing this argument out takes a bit of work [2].

In fact, the argument is structured in the exact same way as the fact that uniformly randomly chosen numbers in [0,1] are normal (i.e. the digit frequencies in a base-b expansion are all 1/b).

However, proving such results about _specific_ numbers is notoriously hard [3]. As far as I am aware, there has not been a single irrational algebraic number proven to be normal. Normality of well-known constants like pi and e is also an open problem! I would not be surprised if proving distributional results for continued fraction expansions of pi is also very hard.

[1]: https://en.wikipedia.org/wiki/Ergodic_theory#Ergodic_theorem...

[2]: http://www.geometrie.tugraz.at/karpenkov/cf2011/cf2011s_7.pd...

[3]: https://en.wikipedia.org/wiki/Normal_number#Properties_and_e...

> However, proving such results about _specific_ numbers is notoriously hard [3]. As far as I am aware, there has not been a single irrational algebraic number proven to be normal. Normality of well-known constants like pi and e is also an open problem! I would not be surprised if proving distributional results for continued fraction expansions of pi is also very hard.

Is it known if algebraic numbers can be normal? I'm not a mathematician, but almost all numbers are normal, and almost all numbers are non-algebraic (or even non-computable!). Something akin to "most of the non-algebraics and non-computables are normal, and none of the algebraics are normal" is feasible, right? It contradicts the commonly held idea that e or sqrt(2) or pi are normal, but we don't even have a (non-constructuve) proof that there exist irrational algebraic normals, do we?

You're absolutely correct---countable sets have probability zero (with probability 1 a uniformly random number in [0,1] will irrational), and it would not be contradictory for all algebraic numbers to be non-normal. I am pretty sure it is unknown if there exist irrational algebraic normal numbers, even non-constructively.

One reason for believing that irrational algebraics, or pi, or e are normal, is a crude heuristic which is that "there is nothing special about base b". You can also take a computer and compute digit frequencies up to some very large precision, and see what happens. Generally speaking, it feels like "naturally defined numbers" should be normal unless there is a good reason for them not to be (and this is entirely independent of the fact that uniformly random numbers are normal). Proving this is a very different matter!

I don't know that I follow

> is a crude heuristic which is that "there is nothing special about base b

In this context. Imagine the stronger statement, for all bases b, sqrt(2) is not normal in base b. This is base-independent, and we know one base for which it is true (the irrational base sqrt(2), where it's 10). I assume this has something do with restricting b. This argument sounds reasonable for integer or rational bases, but not for noncomputable bases (where presumably sqrt(2) becomes non-computable, how does that work?)

Obviously if we restrict to integer/rational bases, I follow that argument.

Reply on news.ycombinator.com