New York Journal of Mathematics

New York J. Math. 4 (1998) 249–257.

Metric Diophantine Approximation and Probability

Doug Hensley

Abstract. Let p_{n}/q_{n} = (p_{n}/q_{n})(x) denote the nth simple continued fraction convergent to an arbitrary irrational number x ∈ (0, 1). Define the sequence of approximation constants θ_{n}(x) := q_{n}^{2}|x − p_{n}/q_{n}|. It was conjectured by Lenstra that for almost all x ∈ (0, 1),

lim_{n→∞} \frac{1}{n} |\{j : 1 ≤ j ≤ n and θ_{j}(x) ≤ z\}| = F (z)

where F (z) := z/ log 2 if 0 ≤ z ≤ 1/2, and \frac{1}{log 2} (1−z +log(2z)) if 1/2 ≤ z ≤ 1. This was proved in [BJW83] and extended in [Nai98] to the same conclusion for θ_{k_{j}} (x) where k_{j} is a sequence of positive integers satisfying a certain technical condition related to ergodic theory. Our main result is that this condition can be dispensed with; we only need that k_{j} be strictly increasing.

Contents

1. Introduction 249 2. Probabilities and operators 250 3. Non-independent trials are good enough. 255 References 257

1. Introduction

Metric questions about Diophantine approximation can be approached by means of ergodic theory, dynamical systems, weak mixing and so on. At the heart of this approach lies the observation that not only is the map T : [0, 1]\Q → [0, 1]\Q given by T : x → ⟨1/x⟩ =: 1/x − [1/x] ergodic, but that T : Ω → Ω := ([0, 1]\Q) × [0, 1] given by T : (x, y) → (⟨1/x⟩, 1/([1/x]+y)) is ergodic with better mixing properties. The associated measure, invariant under T assigns to measurable A ⊂ Ω mass ∫_{A} \frac{1}{log 2} ∫_{A} \frac{dx dy}{(1+xy)^{2}} . Here we take a different tack. It goes back to the pioneering work that led to the Gauss-Kuzmin theorem, and the thread continues with the work of Wirsing and Babenko on the convergence rate in that theorem. Most recently, Vallée et al have had signal success with this circle of ideas, analyzing for

\begin{matrix}c \\ ◯ \end{matrix}1998 State University of New York ISSN 1076-9803/98

Received July 14, 1998.

Mathematics Subject Classification. 11K50 primary, 11A55, 60G50 secondary.

Key words and phrases. continued fractions, distribution, random variable.

instance the lattice reduction algorithm in two dimensions [Val95]. This approach uses functional analysis and classical probability. Discussion of linear operators, eigenvalues, and eigenvectors requires that a linear space be specified. We shall get around to this, but for now it suffices to note that the definition below of L would make sense for any reasonable space of functions. At the heart of our approach lies the fact that if X is a random variable on U := [0, 1]\Q with density f, then T^{n}X has density L^{n}f where Lf(t) = ∑_{k=1}^{∞}(k + t)^{−2}f(1/(k + t)) (for t ∈ [0, 1], else zero) and that L has dominant eigenvalue 1 with corresponding eigenfunction g(t) := 1/(log 2(1 + t)). From this it follows that well-separated values of T^{n}X are nearly independent random variables, so that the usual tools of classical probability can be brought into play.

These statements about random variables and density can be rephrased so as to avoid explicit mention of probability: X is a measurable function from U to U, and ϕ : [0, 1] → [0, 1] is defined by ϕ(y) = m({x ∈ U : X(x) ≤ y}) where m denotes Lebesgue measure. If ϕ is differentiable on [0, 1], then f := ϕ′ is the density of the random variable X. Similarly, the density of T^{n}X is

(d/dy) m({x ∈ U : T^{n}X(x) ≤ y}) = L^{n}f,

a fact which is used in the pioneering work mentioned above and in all subsequent developments along this line.

Recall (from the abstract) that p_{n}/q_{n} = (p_{n}/q_{n})(x) denotes the nth simple continued fraction convergent to an arbitrary irrational number x ∈ (0, 1), while θ_{n}(x) := q_{n}^{2}|x − p_{n}/q_{n}|. Also,

F (z) := \begin{cases}z/ log 2 & if 0 ≤ z ≤ 1/2 \\ \frac{1}{log 2}(1 − z + log(2z)) & if 1/2 ≤ z ≤ 1. \end{cases}

Our main result is

Theorem 1.1. If (k_{j}) is a strictly increasing sequence of positive integers, and 0 < z < 1, then (with respect to Lebesgue measure)

lim_{n→∞} \frac{1}{n}|\{j : 1 ≤ j ≤ n and θ_{k_{j}}(x) ≤ z\}| = F (z)

for almost all x ∈ (0, 1).

2. Probabilities and operators

The probability Q_{r,f}(z) that θ_{r}(X) ≤ z, when the initial density for X is f, is essentially F (z), as we shall see. In the case f ≡ 1, this is due to Knuth. [BJW83]. What is new here is that there is a kind of near-independence of these events for widely separated values of r, and uniformly over a certain class of initial probability distributions f.

Let V_{r} denote the r-fold Cartesian product of the positive integers. For an arbitrary sequence v ∈ V_{r} of r positive integers, let [v] := [0; v_{1}, v_{2}, … v_{r}] = p_{r}/q_{r}, let {v} := [0; v_{r}, v_{r−1}, … v_{1}] = q_{r−1}/q_{r}, and let |v| := q_{r}. Let v_{−} := (v_{2}, … v_{r}) and let v^{−} := (v_{1}, … v_{r−1}), so that p_{r} = |v_{−}| and q_{r−1} = |v^{−}|. Then for x ∈ [0, 1]\Q,

(1)  x = \frac{p_{r} + (T^{r}x)p_{r−1}}{q_{r} + (T^{r}x)q_{r−1}}
θ_{r}(x) = \frac{T^{r}x}{1 + \{v\}T^{r}x}
L^{r}[(1 + ut)^{−2}] = ∑_{v∈V_{r}} |v|^{−2}(1 + u[v])^{−2}(1 + ({v} + u{v_{−}})t)^{−2}
(L^{r}f)(t) = ∑_{v∈V_{r}} |v|^{−2}(1 + {v}t)^{−2}f([v + t])

where [v + t] := [0; v_{1}, v_{2}, … v_{r−1}, v_{r} + t]. (Thus if f is a convex combination of probability density functions of the form (1+u)(1+ut)^{−2}, then so is Lf.) The claim above about the dominant eigenvalue of L can now be given specific content. For an arbitrary function f of bounded variation and zero except in [0, 1], (which we will call good) let ∥f∥ be the total variation of f on the real line. (Thus any probability density function has norm at least 2). We have (specializing from Lemma 6 [Hen92, p 346])

Lemma 2.1. Uniformly over 0 ≤ t ≤ 1 and good probability density functions f of bounded variation, L^{r}f = \frac{1}{log 2(1+t)} + O(((\sqrt{5} − 1)/2)^{r}∥f∥).

Again let f be a good probability density function. Let I(S) := 1 if S is a true statement, else zero. Let X be a random variable on [0, 1] with density f. Then the density of T^{r}X is L^{r}f. Let v = v(x, r) denote the sequence of the first r partial quotients in the continued fraction expansion of x, so that x = [v+t] where t = T^{r}x.

We now consider the probability P_{r,z,f} that {v(X, r)} ≤ z. In the case r = 1, this is

P_{1,z,f} = ∫_{x=0}^{1} f(x)I(⌊1/x⌋ ≤ z) dx = ∑_{{k:1/k≤z}} ∫_{t=0}^{1}(k + t)^{−2}f(1/(k + t)) dt

on substituting x = 1/(k + t). The similar substitution

x = [v + t] = [v_{1}, v_{2}, … v_{r−1}, v_{r} + t]

has dx/dt = |v|^{−2}(1 + {v}t)^{−2}, so the probability P_{r,z,f} that {v} ≤ z is given by

P_{r,z,f} = ∫_{t=0}^{1} ∑_{v∈V_{r},{v}≤z} |v|^{−2}(1 + {v}t)^{−2}f([v + t]) dt. (2)

Much of what lies ahead has to do with conditional probabilities, conditional random variables, and their associated conditional densities. If E_{1} is an event (measurable subset of U) with positive probability (that is, m(E_{1}) > 0), then the conditional probability of another event E_{2} given E_{1} is by definition

prob(E_{1} and E_{2})/prob(E_{1}) = m(E_{1} ∩ E_{2})/m(E_{1}).

Most of our events have to do with some random variable X on U with density f, and some function τ : U → U. Suppose D_{1} ⊂ R and let E_{1} = X^{−1}D_{1} = {x ∈ U : X(x) ∈ D_{1}}. The conditional probability that τ(X) ∈ D_{2} given X ∈ D_{1} is then m((τ ∘ X)^{−1}D_{1} ∩ X^{−1}D_{2})/m(X^{−1}D_{1}), and the conditional density for τ(X) given that X ∈ D_{1} is the function

t → (d/dt) m({x : τ(X(x)) ≤ t and X(x) ∈ D_{1}})/m(X^{−1}(D_{1})).

The conditional density given that {v(X, r)} ≤ z, for T^{r}X is

g_{r,z,f} := ∑_{v∈V_{r},{v}≤z} |v|^{−2}(1 + {v}t)^{−2}f([v + t])/P_{r,z,f}. (3)

Let h_{r,z,f}(t) := g_{f,r,z}(t)P_{r,z,f}. By convention both f and g take the value 0 off [0, 1].

Because g_{r,z,f} is the conditional density of T^{r}X given v(x, r) ≤ z, where X is a random variable on (0, 1) with density f, it follows that if Y is a random variable on (0, 1) with density g := g_{r,z,f} and B is a measurable subset of [0, 1) then

(4) prob[{v(X, r)} ≤ z and T^{r}X ∈ B]/prob[{v(X, r)} ≤ z] = prob[Y ∈ B]

We are now in a position to state and prove

Theorem 2.1. Uniformly over good probability density functions f, over 0 ≤ z ≤ 1, and over 0 ≤ t ≤ 1,

h_{r,z,f} := ∑_{v∈V_{r},{v}≤z} |v|^{−2}(1 + {v}t)^{−2}f([v + t])

is good and satisfies

h_{r,z,f}(t) = \frac{z}{log 2(1 + tz)} + O(rz((\sqrt{5} − 1)/2)^{r}∥f∥)

Proof. It is clear that the resulting function again has bounded variation. The real issue is whether it satisfies the estimate. We begin by proving a weaker version of the theorem, in which the z in the error term is replaced with 1. For this weaker version, the ground floor of induction is trivial. Let λ = (\sqrt{5} − 1)/2. Let V_{r}(z) denote the set of all v ∈ V_{r} so that {v} = q_{r−1}/q_{r} ≤ z. Now assume that for some r,

| ∑_{v∈V_{r}(z)} |v|^{−2}(1 + t\{v\})^{−2}f([v + t]) − \frac{z}{log 2(1 + tz)}| ≤ C_{r}λ^{r}

Then

∑_{v∈V_{r+1}(z)}|v|^{−2}(1 + t{v})^{−2} =

= ∑_{n=[1/z]+1}^{∞} n^{−2} ∑_{v∈V_{r}} |v|^{−2}(1 + {v}/n)^{−2}(1 + t/(n + {v}))^{−2}f([v, n + t])

+ ∑_{v∈V_{r}\V_{r}(⟨1/z⟩)} |v|^{−2}([1/z] + t + {v})^{−2}

= ∑_{n=[1/z]}^{∞}(n + t)^{−2} ∑_{v∈V_{r}} |v|^{−2}(1 + {v}/(n + t))^{−2}f([v + t])

− ∑_{v∈V_{r}(⟨1/z⟩)} |v|^{−2}([1/z] + t)^{−2}(1 + {v}/([1/z] + t))^{−2}f([v, [1/z] + t)

The first term here is

∑_{n=[1/z]}^{∞}(n + t)^{−2} · g(1/(n + t)) + O(λ^{r}z∥f∥)

from Lemma 2.1, while the second term is

− ([1/z] + t)^{−2} · (\frac{1}{log 2} \frac{⟨1/z⟩}{1 + ⟨1/z⟩/([1/z] + t)} + ΘC_{r}(λ^{r}∥f∥))

where |Θ| ≤ 1, on the induction hypothesis. The total thus simplifies to

z/(log 2(1 + tz)) + O(λ^{r}∥f∥) + ΘC_{r}[1/z]^{−2}∥f∥.

This leads to a recurrence C_{r+1} = C_{r} + O(1) from which it follows that (r^{−1}C_{r}) is bounded and the weak version of the theorem follows. For the strong version, we just note that given the weak version, the strong version follows immediately since the two error terms in passing from r to r + 1 were O(λ^{r}z + C_{r}[1/z]^{−2}). □

Corollary 2.2. Uniformly over good probability density functions f, over 0 ≤ z ≤ 1, and over 0 ≤ t ≤ 1,

∑_{v∈V_{r},\{v\}≥z} |v|^{−2}(1 + \{v\}t)^{−2}f([v + t]) = \frac{1}{log 2} \frac{1 − z}{(1 + t)(1 + tz)} + O(r(1 − z)λ^{r}∥f∥).

In view of Corollary 2.2, the conditional density for T^{r}X given initial density f and given that q_{r−1}/q_{r}(X) ≤ z is, on the one hand, a good density, and on the other hand, z/((1+tz) log(1+z))+O(rλ^{r}∥f∥), while the conditional density, given that q_{r−1}/q_{r}(X) ≥ z, is again on the one hand a good density, and on the other, (1 − z)/((log 2 − log(1 + z))(1 + t)(1 + tz)) + O(rλ^{r}∥f∥). Now consider a sequence k_{j} of positive integers such that k_{1} ≥ r and k_{j+1} − k_{j} ≥ r for all j.

The probability Q_{r,f}(z) that θ_{r}(X) ≤ z, when the initial density for X is f, is

Q_{r,f}(z) = ∑_{v∈V_{r}} |v|^{−2} ∫_{t=0}^{1}(1 + {v}t)^{−2}f([v + t])I(t/(1 + {v}t) ≤ z) dt

= ∫_{t=0}^{1} ∑_{v∈V_{r}} |v|^{−2}(1 + {v}t)^{−2}f([v + t])(1 − I({v} ≤ 1/z − 1/t)) dt

Let u^{∗} := 0 if u < 0, u if 0 ≤ u ≤ 1, and 1 if u > 1. Taking (1/z − 1/t)^{∗} in place of t in Theorem 2.1 breaks into two cases. If z ≤ 1/2 we get

Q_{r,f}(z) = 1 − \frac{1}{log 2} (∫_{z}^{z/(1−z)}(1/t − z/t^{2}) dt + ∫_{z/(1−z)}^{1} \frac{1}{1 + t} dt) + O(λ^{r}∥f∥)

= \frac{z}{log 2} + O(λ^{r}∥f∥).

For z > 1/2 we get instead

Q_{r,f}(z) = 1 − \frac{1}{log 2} ∫_{z}^{1}(1/t − z/t^{2}) dt + O(λ^{r}∥f∥)

In either case, this says

Q_{r,f}(z) = F (z) + O(λ^{r})∥f∥ (5)

as claimed at the outset of this section.

Next we consider the conditional density ρ_{r,z,f,ϵ}(t) of T^{r}X when the initial density for X is f, given that θ_{r}(X) _{<}^{>}z according to whether ϵ = 0 or 1. This is again a good density, with norm not more than a constant multiple of ∥f∥, (the multiple may and does depend on z) we claim.

We first note that the probability, on initial density f, that θ_{r}(X) ≤ z is at least Cz + O(λ^{r}). So for fixed z > 0, and r sufficiently large, it is at least Kz. Similarly, the probability that θ_{r}(X) ≥ z is at least K(1 − z) for r sufficiently large. Next, we need some estimate of the possible growth of ∥ρ_{r,z,f,ϵ}∥/∥f∥ with increasing r. The scaling factor that results from dividing

∑_{v∈V_{r}} |v|^{−2}(1 + {v}t)^{−2}f([v + t])(1 − I({v} ≤ 1/z − 1/t))

by Q_{r,f}(z) or by (1 − Q_{r,f}(z)), according to whether ϵ = 0 or 1, is at most O(1/z) or O(1/(1 − z)). Apart from this effect, we have a norm of at most

∑_{v∈V_{r}} |v|^{−2}∥(1 + {v}t)^{−2}f([v + t])I({v}_{<}^{>}z^{−1} − t^{−1})∥.

A lemma on total variation is now needed.

Lemma 2.2. If g is a positive function of bounded variation on R and is zero outside [0, 1] and h is a positive, increasing function on R with h(1) = 1, or positive and decreasing with h(0) = 1, then the total variation of gh is no more than that of g.

Proof. Write g as g_{1} − g_{2} where both are zero on (−∞, 0), increasing, and constant on (1, ∞), so that the total variation of g is equal to 2g_{1}(1) = 2g_{2}(1). Then gh = g_{1}h − g_{2}h. This gives a representation of gh as the difference of two increasing functions, both zero on (−∞, 0) and both equal and constant on (1, ∞). By reflecting g we see that the same holds if h is positive and decreasing with h(0) = 1. □

Now by repeated application of the lemma, and taking into account that the total variation of f([v + t]) is no more than that of f, we calculate that

(6) ∑_{v∈V_{r}} |v|^{−2}∥(1 + {v}t)^{−2}f([v + t])I({v}_{<}^{>}z^{−1} − t^{−1})∥

≤ ∑_{v∈V_{r}} |v|^{−2}∥(1 + {v}t)^{−2}f([v + t])∥

≤ ∑_{v∈V_{r}} |v|^{−2}∥f([v + t])∥ ≤ ( ∑_{v∈V_{r}} |v|^{−2})∥f∥ ≤ 2∥f∥

From this it follows that for all δ ∈ (0, 1/2), and whether we require θ_{r}(X) < z or θ_{r}(X) > z, there exists R(δ) > 0 and K(δ) > 0 so that ∥f_{r,z}∥ ≤ K(δ)∥f∥, uniformly in δ ≤ z ≤ 1 − δ for r ≥ R(δ).

Now the probability, on initial density f, that θ_{k_{1}}(X) ≤ z, is F (z) + O(λ^{r}∥f∥). (Recall, all k_{j} > r). The conditional density of T^{k_{1}}X = Y (say) given this event is a normalized version of the sum of all terms (with v ∈ V (k_{1})) of the form |v|^{−2}(1 + {v}t)^{−2}I[t ≤ z/(1 − z{v})]f([v + t]), or given instead the complementary event, the same expression but with I[t ≥ z/(1 − z{v})] in place of I[t ≤ z/(1 − z{v})].

In either case, this is a function of bounded variation. In either case, provided z ∈ [δ, 1 − δ], that variation is bounded by K(δ)∥f∥.

Fix n large, and consider the sequence T^{k_{j}}X, 1 ≤ j ≤ n. Fix γ > 0. To satisfy a technical condition at the end of the paper, we also require that γ/(F (z)+γ) < 1/4. Consider the probability that more than (F (z) + 2γ)n of the j have θ_{k_{j}} ≤ z. For large n, we can break this finite sequence into O(n^{3/4}) subsequences, each of which has k_{j+1} > k_{j} + n^{3/4}, and each of which has at most, but on the order of, (n^{1/4}) entries. This way, r = n^{3/4} is comfortably larger than the number of trials O(n^{1/4}) in a subsequence. The initial density f_{0} is the density of T^{k}1, where k is the least of the k_{j} in our subsequence. For each such subsequence of length N say (N depends on the subsequence), the event E(ϵ_{1}, … ϵ_{N}), where (ϵ_{1}, ϵ_{2}, … ϵ_{N}) ∈ {0, 1}^{N}, is the set of all x ∈ [0, 1)\Q for which θ_{k_{j}} < z if and only if ϵ_{j} = 0, 1 ≤ j ≤ N.

Let r_{j} := k_{j+1} − k_{j}, with r_{0} := k_{1}. A step consists of replacing f_{j} with f_{j+1} := ρ_{r_{j},z,f_{j},ϵ_{j+1}}, the conditional density, given that θ_{k_{j}}(Y) _{<}^{>}z, of T^{r_{j}}Y where Y is a random variable on U with density f_{j}. Thus the input to the next step is again a good density, with a certain norm. The norm of the ‘working’ f_{j} may increase, by at most a factor of K(δ) each time. If the number N of steps is small compared to the minimum r_{j}, this is not much of a problem, because at each stage, the working ‘initial’ probability density function f_{j} has norm no greater than K^{j}. The probability, at each trial within the subsequence, and for any prior history of trials within that subsequence, that θ_{k_{j}} > z, is less than F (z)+γ. That is, the conditional probability that θ_{k_{jm}} > z, given that θ_{k_{j_{l}}} < z exactly when ϵ_{l} = 0 for 1 ≤ l ≤ m, is less than F (z) + γ.

(We take n large enough that K(δ)^{n^{1/4}}λ^{n^{3/4}} < γ/2). The probability that a particular subsequence has more than its own length, multiplied by F (z)+2γ, cases of θ_{k_{j}} > z, can be shown (see below) to be bounded above by O(exp(−Cγ^{2}n^{1/4})). Keeping in mind that this claim has yet to be established, we continue with the main line of the proof.

The probability that any one of the subsequences has such an atypical success ratio, is O(n^{3/4} exp(−Cγ^{2}n^{1/4})) which tends to zero. This shows that the probability of an atypically high success ratio is asymptotically zero. The same arguments apply to the case of an atypically low success ratio, simply by redefining success to mean θ_{k_{j}} < z. This proves that Nair’s theorem^{1} holds for any strictly increasing sequence (k_{j}) of positive integers, as claimed.

3. Non-independent trials are good enough.

‘The probability that a particular subsequence has more than its own length, multiplied by F (z) + 2γ, cases of θ_{k_{j}} > z, can be shown (see below) to be bounded above by O(exp(−Cγ^{2}n^{1/4})).’ We now make good on this claim. For the remainder of this section, we shall use n to mean the number of trials. This new value of n will be on the order of the old value of n^{1/4}.

We have a kind of near-independence: If

E := E(k_{1}, k_{2}, … k_{n}, ϵ_{1}, ϵ_{2}, … ϵ_{n}) = {x ∈ [0, 1]\Q : θ_{k_{j}}(x) < z iff ϵ_{j} = 0} (7)

then the conditional probability that θ_{k_{n+1}} < z given that x ∈ E is F (z) + O(λ^{r}) and so less than F (z) + γ. Thus if (a_{0}, a_{1}) is the sequence

(a_{0}, a_{1}) := (prob(θ_{k_{1}}(x) < z), prob[θ_{k_{1}}(x) > z])

1See http://nyjm.albany.edu:8000/j/1998/3A-9.html.

and (b_{0}, b_{1}) the sequence (1 − γ − F (z), F (z) + γ), then a_{0} > b_{0} and a_{0} + a_{1} = 1 = b_{0} + b_{1}.

Given two sequences (a_{0}, a_{1}, … a_{n}) and (b_{0}, b_{1}, … b_{n}) of non-negative numbers summing to 1, we say that a :> b if for all k < n, ∑_{0}^{k} a_{j} > ∑_{0}^{k} b_{j}.

Lemma 3.1. If a :> b, if (u_{k}) and (v_{k}) are sequences of numbers in [0, 1] with u_{k} < v_{k} for all k, and if a′ is given by a′_{j} = (1 − u_{j})a_{j} + u_{j−1}a_{j−1} and b′ by b′_{j} = (1 − v_{j})b_{j} + v_{j−1}b_{j−1}, (setting a_{−1} = b_{−1} := 0), then a′ :> b′.

Proof. We have

∑_{j=0}^{k} a′_{j} − b′_{j} = ∑_{j=0}^{k}(1 − u_{j})a_{j} + u_{j−1}a_{j−1} − (1 − v_{j})b_{j} − v_{j−1}b_{j−1}

= (1 − v_{k}) ∑_{0}^{k}(a_{j} − b_{j}) + v_{k} ∑_{0}^{k−1}(a_{j} − b_{j}) + a_{k}(v_{k} − u_{k}) > 0.

□

We apply this lemma with a = (a_{0}, a_{1}, … a_{n})[k_{1}, k_{2}, … k_{n}, ϵ_{1}, ϵ_{2}, … ϵ_{n}, z], defined by

a_{m} := prob[#{j : 1 ≤ j ≤ n and θ_{k_{j}} < z} = m] for 0 ≤ m ≤ n, and
b := (b_{0}, b_{1}, … b_{n}), where
b_{m} := (\begin{matrix}n \\ m \end{matrix}) (F (z) + γ)^{m}(1 − F (z) − γ)^{n−m}, 0 ≤ m ≤ n.

The claim is that with this a and b, a :> b. The proof is inductive, using Lemma 3.1 n times.

We shall be using a succession of a’s and b’s, which will be denoted by superscripts.

a^{1} := (a_{0}^{1}, a_{1}^{1}) = (prob[θ_{k_{1}} ≥ z], prob[θ_{k_{1}} < z]), while
b^{1} := (1 − F (z) − γ, F (z) + γ).

We have a^{1} :> b^{1} because prob[θ_{k_{1}} ≥ z] > 1 − F (z) − γ. This so far uses only the definition of :> and earlier material but not Lemma 3.1

Now let a_{0}^{2} := (prob[θ_{k_{1}} ≥ z and θ_{k_{2}} ≥ z], a_{1}^{2} := prob[one small theta], and a_{2}^{2} := prob[θ_{k_{1}} ≤ z and θ_{k_{2}} ≤ z]),

a^{2} := (a_{0}^{2}, a_{1}^{2}, a_{2}^{2}), and
b^{2} := ((1 − F (z) − γ)^{2}, 2(1 − F (z) − γ)(F (z) + γ), (F (z) + γ)^{2}).

We take a = a^{1}, b = b^{1}, a′ = a^{2}, and b′ = b^{2} in Lemma 3.1. Then we have

a′_{0} = (1 − u_{0})a_{0}, a′_{1} = (1 − u_{1})a_{1} + u_{0}a_{0}, a′_{2} = (1 − u_{2}) · 0 + u_{1}a_{1}

where u_{0} = prob[θ_{k_{2}} < z given θ_{k_{1}} ≥ z] and u_{1} = prob[θ_{k_{2}} < z given θ_{k_{1}} < z], while v_{0} = v_{1} = F (z) + γ. Applying Lemma 3.1 gives a_{2} :> b_{2}. Inductively, it gives a^{n} :> b^{n} which says that a :> b.

Thus the probability that more than n(F (z) + 2γ) cases of θ_{k_{j}} < z out of the first n values of θ_{k_{j}} is less than the probability, with a Bernoulli process which gives ‘heads’ with probability F (z) + γ, that more than n(F (z) + 2γ) of the first n trials come up heads.

Metric Diophantine Approximation and Probability 257

By standard exponential centering, this probability is, we claim, less than exp(−(3/8)nγ^{2}). Let Y_{j} be independent Bernoulli trials with a coin taking heads with probability α = F (z)+γ. (If F (z)+γ > 1 the probability in question is zero.) Now for ζ > 0,

Prob[∑_{j=1}^{n} Y_{j} ≥ n(α + γ)]

≤ e^{−ζn(α+γ)} ∑_{k≥n(α+γ)} e^{kζ}Prob[∑_{j=1}^{n} Y_{j} = k]

≤ e^{−ζn(α+γ)} ∑_{k=0}^{n} e^{kζ}Prob[∑_{j=1}^{n} Y_{j} = k] = e^{−ζn(α+γ)}(1 − α + αe^{ζ})^{n}

We take ζ = log(1 + γ/α) and recall that γ/α < 1/4. Thus

Prob[∑_{j=1}^{n} Y_{j} ≥ n(α + γ)] ≤ (1 + γ/α)^{−n(α+γ)}e^{nγ}.

Using the first two terms in the series expansion of log(1 + γ/α), this is less than exp(−(3/8)nγ^{2}/α) < exp(−nγ^{2}/4). This completes the proof of the theorem.

References

[BJW83] W. Bosma, H. Jager, and F. Wiedijk, Some metrical observations on the approximation by continued fractions, Indag. Math. 45 (1983), 281–299, MR 85f:11059.

[Hen92] D. Hensley, Continued fraction Cantor sets, Hausdorff dimension, and functional analysis, Journal of Number Theory 40 (1992), no. 3, 336–358, MR 93c:11058.

[Nai98] R. Nair, On metric diophantine approximation theory and subsequence ergodic theory, New York Journal of Mathematics 3A (1998), 117–124.

[Val95] B. Vallée, Méthodes d’analyse fonctionelle dans l’analyse en moyenne des algorithmes d’Euclide et de Gauss, C.R. Acad. Sci. Paris 321 (1995), 1133–1138, MR 97c:58088.

Department of Mathematics, Texas A&M University, College Station, TX 77843 Doug.Hensley@math.tamu.edu http://www.math.tamu.edu/˜ doug.hensley/

This paper is available via http://nyjm.albany.edu:8000/j/1998/4-16.html.