INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A04

SIMPSON’S PARADOX IN THE FAREY SEQUENCE

Rasa Šleževičienė-Steuding

Departamento de Matemáticas, Universidad Autónoma de Madrid, C. Universitaria de Cantoblanco, 28 049

Madrid, Spain

                           rasa.steuding@uam.es

Jörn Steuding

Departamento de Matemáticas, Universidad Autónoma de Madrid, C. Universitaria de Cantoblanco, 28 049

Madrid, Spain

                           jorn.steuding@uam.es

Received: 6/6/05, Revised: 12/2/05, Accepted: 2/4/06, Published: 2/14/06

Abstract

We investigate the appearance of Simpson’s paradox in the Farey sequence of reduced fractions in the unit interval.

1. Introduction and statement of results

In statistics it frequently occurs that the data seems to contradict our intuition. For instance, Cohen & Nagel [1] cited actual death rates from tuberculosis in Richmond (Virginia) and New York from 1910 that verified the following propositions:

• the death rate for African Americans was lower in Richmond than in New York,

• the death rate for Caucasians was lower in Richmond than in New York,

• the death rate for the total combined population of African Americans and Caucasians was higher in Richmond than in New York.

How can it be? We may illustrate this with another numerical example, namely

\frac{3}{5} < \frac{8}{13}  and  \frac{7}{10} < \frac{5}{7},  but  \frac{3 + 7}{5 + 10} = \frac{2}{3} > \frac{13}{20} = \frac{8 + 5}{13 + 7}.

This phenomenon is called Simpson’s paradox after E.H. Simpson [6] who published in 1951 an influential paper on this topic. Of course, Simpson’s paradox is not a paradox but just a simple fact about fractions. Nevertheless, it has a variety of surprising applications arising from links between proportions, probabilities, and their representations as fractions. A short historical overview on Simpson’s paradox can be found in Mittal [5].

Usually, statistical data is given as some subset of the set of rational numbers ℚ. In this note we investigate the appearance of Simpson’s paradox within ℚ. For an enumeration of ℚ we shall use the Farey sequence of reduced fractions in the unit interval.

For n ∈ ℕ the Farey sequence F_{n} is the ordered list of all reduced fractions in the unit interval having denominators less than or equal to n, i.e.,

F_{n} := \{\frac{a}{b} ∈ ℚ : 0 ≤ a ≤ b ≤ n, gcd(a, b) = 1\} ,

where, as usual, gcd(a, b) denotes the greatest common divisor of the integers a and b. Consecutive Farey fractions \frac{a}{b} < \frac{c}{d} satisfy bc − ad = 1, resp.

\frac{c}{d} − \frac{a}{b} = \frac{1}{bd}.

Thus, F_{n} is not equidistantly distributed; this property makes Farey fractions useful tools in the theory of Diophantine approximations (see the classical paper of Ford [2]). The Farey sequence can be build from F_{1} by taking mediants of \frac{0}{1} and \frac{1}{1}. For \frac{a}{b}, \frac{c}{d} ∈ F_{n} their mediant is defined by \frac{a+c}{b+d}. If \frac{a}{b} ≤ \frac{c}{d}, then it is easily seen that

\frac{a}{b} ≤ \frac{a + c}{b + d} ≤ \frac{c}{d};

equality holds if and only if \frac{a}{b} = \frac{c}{d}. For consecutive elements \frac{a}{b}, \frac{c}{d} ∈ F_{n}, their mediant is an element of F_{b+d}. The limit of the Farey sequence, ∪_{n∈ℕ}F_{n}, consists exactly of the reduced fractions in the interval [0, 1].

It is a natural question to ask how often Simpson’s paradox occurs in the Farey sequence. So we are interested in the system of diophantine inequalities

0 ≤ \frac{a}{b} < \frac{A}{B} , 0 ≤ \frac{c}{d} < \frac{C}{D},  and  \frac{a + c}{b + d} > \frac{A + C}{B + D}  (1)

for given integers A, B, C, D. It is easily seen that a certain asymmetry is necessary for this phenomenon to happen. Assume that BC = AD, resp. \frac{A}{B} = \frac{C}{D}. Then, obviously, the mediant \frac{A+C}{B+D} coincides with both, which shows that \frac{a}{b} and \frac{c}{d} both are less than \frac{A+C}{B+D}. Further, the case of A = 0 is uninteresting. Therefore, in the sequel we may assume w.l.o.g. that 0 < \frac{A}{B} < \frac{C}{D} ≤ 1.

First of all, we note that there are infinitely many examples for Simpson’s paradox everywhere in the Farey sequence. As a matter of fact, it is elementary to check that for any positive integer n with gcd(n, B) = 1 and gcd(n, D) = 1, and satisfying the inequalities:

0 < \frac{a}{b} = \frac{A}{B} − \frac{1}{n} < \frac{A}{B} and 0 < \frac{c}{d} = \frac{C}{D} − \frac{1}{n^{2}} < \frac{C}{D},

then

\frac{a + c}{b + d} > \frac{A + B}{C + D} for n > \frac{1}{2} (1 + \sqrt{1 + 4\frac{(B + D)^{2}}{BC − AD}}) .

The last example gives a slight indication as to whether or not Simpson’s paradox is a rare event. We shall prove that, given two fractions 0 < \frac{A}{B} < \frac{C}{D} in the Farey sequence F_{n}, pairs (\frac{a}{b}, \frac{c}{d}) ∈ F_{n}^{2} satisfying (1) occur with positive probability (in the sense of a Laplace experiment), as n → ∞.

Theorem. For two fractions 0 < \frac{A}{B} < \frac{C}{D} ≤ 1 in the Farey sequence F_{n}, we have

lim_{n→∞} \frac{♯ \{(\frac{a}{b}, \frac{c}{d}) ∈ F_{n}^{2} : \frac{a}{b} < \frac{A}{B}, \frac{c}{d} < \frac{C}{D} and \frac{a+c}{b+d} > \frac{A+C}{B+D} \}}{♯ \{(\frac{a}{b}, \frac{c}{d}) ∈ F_{n}^{2} : \frac{a}{b} < \frac{A}{B}, \frac{c}{d} < \frac{C}{D} \}} = δ > 0

with

δ := δ (\frac{A}{B} , \frac{C}{D} ) := \frac{1}{9} \frac{BD}{AC} \{\frac{1}{2}Δ^{2}(D^{2}Ψ(1) − 2BDΨ(0) + B^{2}Ψ(−1)) +

+\frac{A}{B} (BΔΥ(0) − (DΔ + \frac{1}{2} \frac{A}{B} ) Υ(1))\},

where

Υ(ℓ) := \frac{36}{4 − ℓ^{2}} min \{1, ∇^{−2−ℓ}\} − \frac{9}{2 − ℓ} min \{∇^{2−ℓ}, ∇^{−2−ℓ}\} ,  (2)
Ψ(ℓ) := \frac{9}{2 − ℓ}( min \{∇^{2−ℓ}, ∇^{−2−ℓ}\} − min \{(\frac{D}{B} )^{2−ℓ} , (\frac{D}{B} )^{−2−ℓ}\} ) +  (3)

+\frac{36}{4 − ℓ^{2}} ( min \{1, (\frac{D}{B} )^{−2−ℓ}\} − min \{1, ∇^{−2−ℓ}\} ),

Δ := \frac{BC − AD}{BD(B + D)}  and ∇ := \frac{D(A + C)}{BC − AD}.  (4)

The expression δ looks rather complicated on first sight but it simply is a rational function of A, B, C, D.

Note that there also exist examples with equality between the mediants. For instance,

\frac{1}{5} < \frac{2}{5}, \frac{14}{25} < \frac{3}{5},  and  \frac{1 + 14}{5 + 25} = \frac{1}{2} = \frac{2 + 3}{5 + 5}.

As the proof of the theorem will show the set of such examples has zero-density.

2. Proof of the theorem

There is an interesting geometrical interpretation of the Farey sequence. The Farey fractions \frac{a}{b} ∈ F_{n} correspond to the points with integer coordinates (a, b) situated in the triangle given by {(x, y) ∈ ℝ^{2} : 0 ≤ x, y, x + y ≥ n}, which can be seen from the origin, i.e., for which a and b are coprime. As we shall see below, for the proof of the theorem we have to count lattice points under this and further conditions.

We start with asymptotic formula for the number of Farey fractions \frac{a}{b} ∈ F_{n} under a given magnitude. Let ξ ∈ (0, 1] be fixed, then

♯ \{\frac{a}{b} ∈ F_{n} : \frac{a}{b} ≤ ξ\} = 1 + ∑_{1≤b≤n} ∑_{{1≤a≤bξ \atop gcd(a,b)=1}} 1 = Σ(n; ξ),

say. Following the argument which gives an asymptotic formula for the cardinality of F_{n} (see [3]), we find

Σ(n; ξ) = \frac{3ξ}{π^{2}} n^{2} + O(n log n),  (5)

where the implicit constant in the error term is absolute. Thus

♯ \{(\frac{a}{b}, \frac{c}{d}) ∈ F_{n}^{2} : \frac{a}{b} < \frac{A}{B} , \frac{c}{d} < \frac{C}{D} \} = Σ (n; \frac{A}{B} ) Σ (n; \frac{C}{D} )
= \frac{9}{π^{4}} \frac{AC}{BD}n^{4} + O(n^{3} log n).  (6)

In order to estimate the proportion in question we have to do a similar computation under the additional restriction (1) for the related mediants. Let

♯ \{(\frac{a}{b}, \frac{c}{d}) ∈ F_{n}^{2} : \frac{a}{b} < \frac{A}{B} , \frac{c}{d} < \frac{C}{D} and \frac{a + c}{b + d} > \frac{A + C}{B + D} \} = Σ(n) + Σ_{0}(n),

where Σ_{0}(n) counts the number of those tuples (\frac{a}{b}, \frac{c}{d}) for which ac = 0. It follows from (5) that Σ_{0}(n) ≪ n^{2} and so their contribution is negligible. We have

Σ(n) = ∑_{1≤b≤n} ∑_{1≤d≤n} ∑_{1≤a<b \frac{A}{B} ,gcd(a,b)=1} ∑_{{1≤c<d \frac{C}{D} ,gcd(c,d)=1 \atop a+c>(b+d) \frac{A+C}{B+D}}} 1.  (7)

Denote by μ(n) the Möbius μ-function, i.e., μ(1) = 1, μ(n) = (−1)^{ν} if n is the product of ν distinct primes, and μ(n) = 0 otherwise (if n has some square divisor). In view of the well-known formula

∑_{d|m} μ(d) = \{ \begin{matrix}1 & if m = 1, \\ 0 & otherwise, \end{matrix}

we can rewrite (7) as

Σ(n) = ∑_{1≤b≤n} ∑_{1≤d≤n} ∑_{1≤a<b \frac{A}{B}} ∑_{{1≤c<d \frac{C}{D} \atop a+c>(b+d) \frac{A+C}{B+D}}} ∑_{α|gcd(a,b)} μ(α) ∑_{γ|gcd(c,d)} μ(γ)

= ∑_{1≤b≤n} ∑_{1≤d≤n} ∑_{α|b} μ(α) ∑_{γ|d} μ(γ) ∑_{{1≤a<b \frac{A}{B} \atop α|a}} ∑_{{1≤c<d \frac{C}{D} \atop γ|c,a+c>(b+d) \frac{A+C}{B+D}}} 1.

First we shall consider the inner two sums, which count the lattice points (x, y) ∈ ℤ^{2} with x ≡ 0 mod α, y ≡ 0 mod γ lying above the straight line x + y = (b + d)\frac{A+C}{B+D} inside the rectangle 1 ≤ x < b\frac{A}{B}, 1 ≤ y < d\frac{C}{D}. Since these are exactly the lattice points of the sublattice αℤ × γℤ in the convex region

R(b, d) := \{(x, y) ∈ ℝ^{2} : 1 ≤ x < b\frac{A}{B} , 1 ≤ y < d\frac{C}{D}, x + y > (b + d)\frac{A + C}{B + D} \} ,

the number of these lattice points equals asymptotically the volume of R(b, d) divided by the volume of a fundamental parallelepiped. It is not difficult to see that the error term is of the order of the boundary (see Lemma 2.1.1 in Huxley [4]). Thus,

∑_{{1≤a<b \frac{A}{B} \atop α|a}} ∑_{{1≤c<d \frac{C}{D} \atop γ|c,a+c>(b+d) \frac{A+C}{B+D}}} 1 = \frac{vol(R(b, d))}{αγ} + O (\frac{length(R(b, d))}{α + γ}) .  (8)

Note that the volume of R(b, d) does not depend on α and γ. In the next step we shall compute this volume.

By simple geometric arguments it follows that the region R(b, d) is

• a single point or empty if and only if

b\frac{A}{B} + d\frac{C}{D} ≤ (b + d)\frac{A + C}{B + D};

• a triangle of volume

\frac{1}{2}Δ^{2}(dB − bD)^{2}

(where Δ is defined by (4)) if and only if

d\frac{C}{D} ≤ (b + d)\frac{A + C}{B + D} < b\frac{A}{B} + d\frac{C}{D};

• a trapezoid of volume

\frac{A}{B} (bdBΔ − b^{2} (DΔ + \frac{1}{2} \frac{A}{B} ))

if and only if

(b + d)\frac{A + C}{B + D} < d\frac{C}{D}.

Other cases of intersections of a half-plane with a rectangle cannot occur; to see this note that b < b + d and \frac{A}{B} < \frac{A+B}{C+D}, and thus

b\frac{A}{B} < (b + d)\frac{A + C}{B + D}.

Let us remark that all of the above listed cases occur for any given 0 < \frac{A}{B} < \frac{C}{D} as n → ∞. In fact, this will imply, as we shall see below, the existence and the positivity of the proportion δ = δ(\frac{A}{B}, \frac{C}{D}).

The contribution of the main term from (8) to Σ(n) may be written as

Σ(n) = Σ_{Δ}(n) + Σ_{♢}(n) + error(n),  (9)

where Σ_{Δ}(n) and Σ_{♢}(n) are the sums of the terms with R(b, d) triangle or trapezoid, i.e.,

Σ_{Δ}(n) := ∑_{1≤b≤n} ∑_{{1≤d≤n \atop d \frac{C}{D} ≤(b+d) \frac{A+C}{B+D} <b \frac{A}{B} +d \frac{C}{D}}} ∑_{α|b} \frac{μ(α)}{α} ∑_{γ|d} \frac{μ(γ)}{γ} · \frac{1}{2}Δ^{2}(bD − dB)^{2},

Σ_{♢}(n) := ∑_{1≤b≤n} ∑_{{1≤d≤n \atop (b+d) \frac{A+C}{B+D} <d \frac{C}{D}}} ∑_{α|b} \frac{μ(α)}{α} ∑_{γ|d} \frac{μ(γ)}{γ} · \frac{A}{B} (bdBΔ − b^{2} (DΔ + \frac{1}{2} \frac{A}{B} )) ,

and error(n) is the error term with respect to (8). We may rewrite the condition of summation for the triangle and for the trapezoid by

b\frac{D}{B} < d ≤ b\frac{D(A + C)}{BC − AD} = b∇ and b∇ = b\frac{D(A + C)}{BC − AD} < d,

respectively. Recall that Euler’s ϕ-function ϕ(b) is for b ∈ ℕ defined as the number of positive integers a ≤ b that are coprime to b. It satisfies the identity

ϕ(b) = b ∑_{d|b} \frac{μ(d)}{d}.

Taking this into account, we find

Σ_{Δ}(n) = \frac{1}{2}Δ^{2} ∑_{1≤b≤n} \frac{ϕ(b)}{b} ∑_{b \frac{D}{B} <d≤min\{n,b∇\}} \frac{ϕ(d)}{d}(bD − dB)^{2},  (10)

Σ_{♢}(n) = \frac{A}{B} ∑_{1≤b≤n} \frac{ϕ(b)}{b} ∑_{b∇<d≤n} \frac{ϕ(d)}{d} (bdBΔ − b^{2} (DΔ + \frac{1}{2} \frac{A}{B} )) .  (11)

In order to evaluate these double sums, we have to compute the asymptotics for certain sums involving Euler’s ϕ-function.

It is well-known that

∑_{1≤b≤n} ϕ(b) = \frac{3}{π^{2}} n^{2} + O(n log n).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A04 7

By partial summation, it follows that

∑_{N≤k≤M} ϕ(k)k^{ℓ} = \frac{6}{(2 + ℓ)π^{2}} (M^{2+ℓ} − N^{2+ℓ}) + O (M^{ℓ+1} log M)

for ℓ ≥ −1. Then, for ℓ ∈ {0, ±1}, we have

∑_{1≤b≤n} ϕ(b)b^{ℓ} ∑_{xb<d≤n} ϕ(d)d^{−ℓ}

= \frac{6}{(2 − ℓ)π^{2}} (n^{2−ℓ} ∑_{1≤b≤min\{n,n/x\}} ϕ(b)b^{ℓ} − x^{2−ℓ} ∑_{1≤b≤min\{n,n/x\}} ϕ(b)b^{2}) +

+O(n^{1−ℓ} log n ∑_{1≤b≤n} ϕ(b)b^{ℓ})

= \frac{n^{4}}{π^{4}} Υ(x; ℓ) + O(n^{3}(log n)^{2}),

where

Υ(x; ℓ) := \frac{36}{4 − ℓ^{2}} min\{1, x^{−2−ℓ}\} − \frac{9}{2 − ℓ} min\{x^{2−ℓ}, x^{−2−ℓ}\}.

Similarly,

∑_{1≤b≤n} ϕ(b)b^{ℓ} ∑_{{1≤d≤n \atop xb<d≤yb}} ϕ(d)d^{−ℓ}

= ∑_{1≤b≤min{n,n/y}} ϕ(b)b^{ℓ} ∑_{xb<d≤yb} ϕ(d)d^{−ℓ} +

+ ∑_{min{n,n/y}<b≤min{n,n/x}} ϕ(b)b^{ℓ} ∑_{xb<d≤n} ϕ(d)d^{−ℓ}

= \frac{6(y^{2−ℓ} − x^{2−ℓ})}{(2 − ℓ)π^{2}} ∑_{1≤b≤min\{n,n/y\}} ϕ(b)b^{2} +

+\frac{6}{(2 − ℓ)π^{2}} (n^{2−ℓ} ∑_{min\{n,n/y\}<b≤min\{n,n/x\}} ϕ(b)b^{ℓ} +

−x^{2−ℓ} ∑_{min{n,n/y}<b≤min{n,n/x}} ϕ(b)b^{2}) + O(n^{1−ℓ} log n ∑_{1≤b≤n} ϕ(b)b^{ℓ})

= \frac{n^{4}}{π^{4}} Ψ(x, y; ℓ) + O(n^{3}(log n)^{2}),

where

Ψ(x, y; ℓ) := \frac{9}{2 − ℓ}( min\{y^{2−ℓ}, y^{−2−ℓ}\} − min\{x^{2−ℓ}, x^{−2−ℓ}\}) +

+\frac{36}{4 − ℓ^{2}} ( min\{1, x^{−2−ℓ}\} − min\{1, y^{−2−ℓ}\}),

valid also for ℓ ∈ {0, ±1}. Using this in (10) and (11), it yields

Σ_{Δ}(n) = \frac{n^{4}}{π^{4}} \frac{1}{2}Δ^{2}(D^{2}Ψ(1) − 2BDΨ(0) + B^{2}Ψ(−1)) + O(n^{3}(log n)^{2}),
Σ_{♢}(n) = \frac{n^{4}}{π^{4}} \frac{A}{B} (BΔΥ(0) − (DΔ + \frac{1}{2} \frac{A}{B} ) Υ(1)) + O(n^{3}(log n)^{2}),

where Υ(ℓ) = Υ(∇; ℓ) is given by (2) and Ψ(ℓ) = Ψ(\frac{D}{B}, ∇; ℓ) by (3). For the error term in (8) we note that in all cases

length(R(b, d)) ≪ b\frac{A}{B} + d\frac{C}{D}

and this leads to the estimate error(n) ≪ n^{3} in (9). Hence, we finally obtain

Σ(n) = \frac{n^{4}}{π^{4}} \{\frac{1}{2}Δ^{2}(D^{2}Ψ(1) − 2BDΨ(0) + B^{2}Ψ(−1)) +

+\frac{A}{B} (BΔΥ(0) − (DΔ + \frac{1}{2} \frac{A}{B} ) Υ(1))\} +

+O(n^{3}(log n)^{2}).

Dividing this by the quantity in (6), we get the required proportion, and conclude the proof of the theorem.

3. Concluding remarks

The rather complicated expression for δ = δ(\frac{A}{B}, \frac{C}{D}) was checked by computer experiments. It is interesting to compare the values of δ for different data A, B, C, D. For instance,

δ (\frac{1}{2}, \frac{1}{1}) = \frac{11}{216} = 0.05092 …,
δ (\frac{1}{3}, \frac{2}{3}) = \frac{1}{72} = 0.01388 …,
δ (\frac{1}{7}, \frac{1}{2}) = \frac{1597}{6615} = 0.24142 ….

In each of these three cases, computing the corresponding proportions Σ(n)/(Σ(n; \frac{A}{B})Σ(n; \frac{C}{D})) for n = 200, we have obtained values that differ from the corresponding proportion δ by less than 7 · 10^{−4}.

It is also interesting to ask for a global proportion, i.e., when 0 < \frac{A}{B} < \frac{C}{D} ≤ 1 are chosen randomly. However, with respect to this question our approach seems to be rather technical. We have computed the corresponding quantity

λ(n) := \frac{♯ \{(\frac{a}{b}, \frac{A}{B}, \frac{c}{d}, \frac{C}{D} ) ∈ F_{n}^{4} : \frac{a}{b} < \frac{A}{B}, \frac{c}{d} < \frac{C}{D} and \frac{a+c}{b+d} > \frac{A+C}{B+D} \}}{♯ \{(\frac{a}{b}, \frac{A}{B}, \frac{c}{d}, \frac{C}{D} ) ∈ F_{n}^{4} : \frac{a}{b} < \frac{A}{B}, \frac{c}{d} < \frac{C}{D} \}}

for several values of n and obtained the following values:

\begin{matrix}n & 10 & 20 & 30 \\ λ(n) & 0.03755… & 0.03750… & 0.03847… \end{matrix}

We conjecture that the limit of λ(n) for n → ∞ exists and is positive, probably around the value 0.04; however, we did not succeed in proving that and leave it as an open problem.

Acknowledgments

The authors are grateful to the anonymous referee for his or her valuable remarks and corrections to a first version of this article.

References

[1] M.R. Cohen, E. Nagel, An Introduction to Logic and Scientific Method, New York: Harcourt, Brace and Co 1934

[2] L.R. Ford, Fractions, Amer. Math. Monthly 45 (1938), 586-601

[3] G.H. Hardy, E.M. Wright, An introduction to the theory of numbers, Oxford University Press 1979, 5th ed.

[4] M.N. Huxley, Area, lattice points, and exponential sums, The Clarendon Press, Oxford University Press, New York 1996

[5] Y. Mittal, Homogeneity of subpopulations and Simpson’s paradox, J. Amer. Stat. Assoc. 86, No. 413 (1991), 167-172

[6] E.H. Simpson, The interpretation of interaction in contingency tables, Journal of the Royal Statistical Society, Series B 13 (1951), 238-241