Expected Cardinality of the First n Coefficients of a Continued Fraction Is there anything known about the asymptotic expected growth of $card\{a_0,a_1,...,a_n\}$, where the $a_i$ are the first $n$ coefficient of a continued fraction $[a_0; a_1, ... ]$?
 A: Results of Diamond and Vaaler (see Flajolet-Vallee-Vardi survey) and others would seem to indicate that the cardinality for a "random" number grows logarithmically with $n.$
A: Since the question asks about an expectation, one needs to specify a probability space of continued fractions. It seems the most natural such space is the interval $[0,1)$ with the density function $1/(1+x)$ that is the natural invariant measure in the study of continued fractions. It is known (Khinchin) that the probability that $a_i=r$ is equal to $\log(1+\frac1{r(r+2)})/\log 2$. Therefore the expected number of distinct $a_i$ among $a_1,\dots,a_k$ is (by linearity of expectation)
$$
\sum_{r=1}^\infty \bigg( 1 - \bigg(1- \frac{\log(1+\frac1{r(r+2)})}{\log 2} \bigg)^k \bigg).
$$
(The $r$th summand is the probability that $r$ occurs at least once among $a_1,\dots,a_k$.) When $\frac1{r(r+2)}$ is small compared with $\frac1k$, then the $r$th summand is approximately $k\log(1+\frac1{r(r+2)})/\log 2 \asymp \frac k{r^2}$; the contribution of such terms where $r>R$ say (with $R$ large compared with $\sqrt k$) is $O(k/R)$. The contribution of the initial $\sqrt k$ or so terms should have order of magnitude $\sqrt k$. So I suspect that the expected number of distinct $a_i$ among the first $k$ partial quotients is asymptotic to some constant times $\sqrt k$. Numerical experimentation is reasonably consistent with this, with the constant quite close to $2.1$.
