# Is it practical to use infinite continued fraction to generate random numbers?

I observed the pattern of this irrational number: $$\sqrt{1 + \sqrt{2}}$$ and realized that each element $a_i$ occurred very randomly. For the first 100 elements, this is the result:

[1,1,1,4,6,1,2,2,2,1,1,6,1,179,48,1,356,1,1,3,15,2,1,4,8,3,1,1,1,5,1,1,9,1,19,1,
2,13,2,1,1,4,2,1,1,3,2,1,1,4,15,1,4,5,1,7,6,1,6,6,2,3,38,1,4,1,9,3,1,2,1,2,1,2,1
,1,3,1,4,1,2,4,1,4,1,1,1,58,6,3,4,203,4,14,2,1,1,41,2,2]


As I increase the length of this sequence, the number were even more arbitrary. So I wonder is there any previous work or paper which relates to random number generator using continued fraction approach? Any idea? Thank you.

-
Khinchin proved that almost all reals number have the property that if the continued fraction of $r$ is $[a_1, a_2, \dots, a_n, \dots ]$ then $\lim_{n \to \infty} (\prod_{j=1}^{n} a_j)^{\frac{1}{n}} = K_0$ Where $K_0$ is a constant independent of $r$ (called Khinchin's constant). I suppose that implies the continued fraction will become predictable (once you go beyond the precision you are using). Of course, this is not a proof... – Aryabhata Jul 9 '11 at 18:06
@Aryabhata: Thank you very much. – Chan Jul 12 '11 at 0:14
Aryabhata, if you know that a sequence of zeros and ones has the property that in the limit half the terms are zero, does that mean the sequence becomes predictable? – Gerry Myerson Jul 12 '11 at 1:29
@Gerry: As I said, "suppose" and "not a proof". The property you consider is not similar, though, IMO. (btw, you need the @Aryabhata to notify me of the comment). – Aryabhata Jul 13 '11 at 18:36
@Aryabhata, the property I consider is $\lim_{n\to\infty}(\prod_{j=1}^n a_j)^{1/n}=\sqrt e$ where $a_j$ is a sequence of ones and $e$s, which I think is similar to the Khinchin property. I really don't see how the existence of a limit can imply anything about the predictability of a sequence. Knowing the first million terms of the sequence tells you nothing about the next term that you didn't already know before you saw the first million terms. – Gerry Myerson Jul 14 '11 at 6:59

If one wants by some chance to model the Gauss–Kuzmin distribution then it might be feasible. Otherwise there seems to be little sense in it.

-
Besides, if one intends to use them as a random number generator, one should investigate if succesive numbers are independent or not... – leonbloy Jul 9 '11 at 17:46
+1: Interesting... – Aryabhata Jul 9 '11 at 18:07
@Andrew: Many thanks ;) – Chan Jul 12 '11 at 0:12

Very little is known about the continued fraction expansions of numbers other than rationals and quadratic irrationals. In particular, it is widely believed but not proved that the continued fraction of an irrational of degree exceeding 2 has arbitrarily large partial quotients.

Almost all reals (all but a set of measure zero) have the same limiting density of 1s, 2s, 3s, etc., in their continued fraction expansion, but again it is believed-but-not-known that familiar irrationals such as $\pi$ and the one you cite are in the full-measure set.

-
Thanks for the info. In fact, I couldn't find any paper related to this kind of continued fraction. I might have to come up with my own idea. – Chan Jul 12 '11 at 0:13

It is difficult to imagine sequences with a more brazenly skewed distribution than the above sequence. Such skewing is the norm with continued fractions.

There are various other problems with continued fractions as random number generators. One problem is that apart from the quadratic case, the quotients are not easy to compute. Another is that the quotients have some subtle dependencies.

-
Great thanks for the info. – Chan Jul 12 '11 at 0:15
@Chan: You are welcome. Sorry that it looks as if the prospects for a random number generator along these lines do not seem attractive. But continued fractions are very good tools not only for the approximation of irrationals by rationals, but also for the approximation of functions by rational functions. – André Nicolas Jul 12 '11 at 0:27