midterm exam iv A1

Appendix J: Midterm Exam IV and Solutions

Midterm Exam IV (A. C. Yao, 1984)

Problem 1. Let S be a recurrence relation of the form

x_{0} = x_{1} = 2 ,
a(n)x_{n+2} + b(n)x_{n+1} + c(n)x_{n} = 1 for n ≥ 0 ,

where a, b, c are given polynomials with complex coefficients. We say that S is reducible, if there exist polynomials (with complex coefficients) s, t, l, m such that

l(n)u_{n+1} + m(n)u_{n} = a(n)x_{n+2} + b(n)x_{n+1} + c(n)x_{n} ,

where u_{n} = s(n)x_{n+1} + t(n)x_{n}.

For each of the following S, prove or disprove that S is reducible.

(A) [10 points]. a(n) = 4n^{2} − 4n − 15, b(n) = 8n^{2} − 18n + 4, and c(n) = 3n^{2} − 7n + 4.

(B) [30 points]. a(n) = 4(n^{2} + n + 1), b(n) = 3n^{3} − 4n^{2} + 8n + 19, and c(n) = 6n^{2} + 7n − 3.

Problem 2. Let n = 2^{k} for some integer k > 0. We will first define a class of permutations on {0, 2, 3, …, n − 1}. A signed-tree of order n is a complete balanced binary tree T with n leaves, with the two edges out of each internal node labeled with distinct Boolean values. The leaves from left to right are denoted v_{0}, v_{1}, …, v_{n−1}. Let σ_{T} (v_{i}) denote the integer 0 ≤ j < n whose binary representation is the concatenation of the labels from the root to v_{i}. Let us regard σ_{T} as the permutation (σ_{T} (v_{0}), σ_{T} (v_{1}), …, σ_{T} (v_{n−1})). An example of a signed-tree T of order 8 is shown below, in which σ_{T} (v_{3}) = 6 because 110 is the string of labels read from the root to v_{3}; σ_{T} is (4, 5, 7, 6, 2, 3, 1, 0) in this example.

[figure: v_{0}; v_{1}; v_{2}; v_{3}; v_{4}; v_{5}; v_{6}; v_{7}; 1; 0; 0; 1; 1; 0; 0; 1; 1; 0; 0; 1; 1; 0]

A2 greene and knuth: new appendices

Let Σ_{n} = { σ_{T} | T is a signed-tree of order n }. Consider a random σ_{T} chosen uniformly from Σ_{n}.

(A) [5 points]. What is the expected number of inversions in a random σ_{T}?

(B) [10 points]. Determine the expected number of element exchanges in each pass of a (4, 2, 1)-Shellsort applied to a random σ_{T}.

(C) [15 points]. Determine the expected value and the variance of the number of right-to-left maxima in a random σ_{T}.

(D) [40 points]. Determine the expected value of B in the ‘straight selection sort’ (Algorithm 5.2.3S in [Knuth III]), applied to a random σ_{T}.

(E) [20 points]. Determine the expected number of cycles in a random σ_{T}. Determine the expected order of a random i (0 ≤ i < n) in a random σ_{T}. [The order of i in a permutation σ is the length of the cycle that contains i. For example, the order of 2 in σ = (34)(0521) is 4.]

Problem 3. It’s the year 2525, and the making of biochips is a big industry. A synthetic organism known as maybesort can be produced cheaply, and we would like to study its suitability as a sorting device.

maybesort consists of an array A[1 : n]. Its relevant behavior under infrared light can be described as follows. Let α = a_{1}a_{2} … a_{n} be an n-bit string. Initially (at τ = 0), let A[j] = a_{j} for 1 ≤ j ≤ n. At each subsequent integer τ, a random integer 1 ≤ i < n is selected and the contents of A[i] and A[i + 1] are compared and exchanged if necessary to make A[i] ≤ A[i + 1]. Let T_{n}(α) be the random variable corresponding to the time when array A first becomes sorted. Let t_{n}(α) be the expected value of T_{n}(α), and let β_{n} denote the string 1^{2}0^{n−2}.

(A) [10 points]. Show that t_{n}(β_{n}) ≥ t_{n}(α) for all α with exactly two 1’s.

(B) [20 points]. Determine t_{n}(β_{n}) up to an additive term of O(n^{1.5}) or better.

Comment: Suppose n = 10^{6} and one time unit for maybesort is one picosec (10^{−12} sec). How would you rate its performance against today’s computers in sorting binary strings with exactly two 1’s?

solutions to midterm exam iv A3

Solutions to Midterm Exam IV

Solution to Problem 1.

(A) We are looking for possible solutions to

\begin{aligned}l(n)s(n + 1) & = 4n^{2} − 4n − 15 , \\ l(n)t(n + 1) + m(n)s(n) & = 8n^{2} − 18n + 4 , \\ m(n)t(n) & = 3n^{2} − 7n + 4 . \end{aligned}

Trial and error gives the solution

\begin{aligned}s(n) & = 2n + 1 , & t(n) & = 3n − 4, \\ l(n) & = 2n − 5 , & m(n) & = n − 1 . \end{aligned}

So, it is reducible.

(B) When a(n) = 4(n^{2} + n + 1), b(n) = 3n^{3} − 4n^{2} + 8n + 19, and c(n) = 6n^{2} + 7n − 3, the corresponding recurrence relation is irreducible, because there is no solution to

l(n)s(n + 1) = a(n) ,  (1.1)
l(n)t(n + 1) + m(n)s(n) = b(n) ,  (1.2)
m(n)t(n) = c(n) .  (1.3)

Here each of a(n) and c(n) has only two linear factors. A direct attack would examine all the possible assignments in (1.1) and (1.3) to l, m, s, t (with some coefficients left unspecified), and show that it’s impossible to satisfy (1.2). The following clever alternative method, due to Richard Beigel, is much more concise.

We use the notation f(n) div g(n) to denote the unique polynomial h(n) such that f(n) = g(n)h(n) + (polynomial with degree less than that of g). First observe that as b(n) is cubic, there are only two possibilities:

Case 1: l and s are linear, m and t are one quadratic and one constant;

Case 2: m and t are linear, l and s are one quadratic and one constant.

In Case 1, if m is quadratic, consider the linear polynomial h(n) defined as b(n) div m(n). As l(n)t(n + 1) is linear, h(n) has to be exactly s(n). But b(n) div m(n) = λ b(n) div c(n) for some constant λ, and hence is of the form λ(λ′n + λ′′), where both λ′ and λ′′ are real; s(n) cannot be of this form, as s(n + 1) is a factor of the polynomial n^{2} + n + 1, which is irreducible over the reals. The case when t is quadratic is ruled out by a similar argument.

In Case 2, if l is quadratic, we know from (1.2) that

t(n + 1) = λ(b(n) div l(n)) = λ(3n − 7) ,

i.e., t(n) = (3n − 10)λ. But 3n − 10 is not a factor of c(n). If s is quadratic, we know that m(n) = λ(b(n) div s(n)) = λ(3n − 7). But 3n − 7 is not a factor of c(n). [Note that Case 1 can also be argued this way.] We have ruled out all the possibilities.

Solution to Problem 2(A).

Let a_{n} be the expected number of inversions. Clearly,

a_{2} = \frac{1}{2} .

Let n = 2^{k} > 2. Take a random σ_{T} ∈ Σ_{n}, write σ_{T} = (σ_{T_{1}}, σ_{T_{2}}).

[figure: r; T_{1}; T_{2}; \overbrace{n/2}; \overbrace{n/2}]

With probability 1/2, we have

[figure: r; 0; 1] ,

in which case there is no inversion between numbers σ_{T_{1}} and σ_{T_{2}}. With probability 1/2, we have

[figure: r; 1; 0] ,

in which case there are exactly (n/2)^{2} inversions between members in σ_{T_{1}} and σ_{T_{2}}. Now σ_{T_{1}} and σ_{T_{2}} are both random signed-trees of order n/2, except that one of them will be a permutation of the numbers \{\frac{n}{2}, \frac{n}{2} + 1, …, n − 1}. Thus, we have

a_{n} = \frac{1}{2}(2a_{n/2}) + \frac{1}{2}((n/2)^{2} + 2a_{n/2}) = \frac{1}{8}n^{2} + 2a_{n/2} ,

and it follows that a_{n} = \frac{1}{4}n(n − 1) for n ≥ 2.

The simple form of this answer suggests that a simpler proof should be possible. And indeed, it is easy to see that the label strings for any two given leaves yield an inversion with probability 1/2. Thus the expected number of inversions of labels strings generated by any n-leaf signed tree T is \frac{1}{2} \binom{n}{2}, regardless of whether n is a power of 2 or T is complete or balanced.

Solution to Problem 2(B).

Assume n ≥ 4 and a_{1} = 0.

First Pass: Four files F_{i} (1 ≤ i ≤ 4) are separately sorted. Each F_{i} consists of n/4 numbers with distinct first k − 2 bits. In fact, the relative ordering of numbers in F_{i} gives a random permutation from Σ_{n/4}. Thus, the average number of inversions in F_{i} is a_{n/4} = \frac{1}{4} \frac{n}{4}( \frac{n}{4} − 1). The total average number of exchanges is thus 4a_{n/4} = \frac{n}{4}( \frac{n}{4} − 1).

Second Pass: After the first pass, the permutation will be a σ_{T} ∈ Σ_{n}, with the top k−2 levels having all left branches labeled 0, and right branches labeled 1. Each of the n/4 height-2 trees at the bottom is a random signedtree of order 4; call these lh2-trees (lowest height-2 trees). The only inversions are among elements in the same lh2-trees.

Each of the two subfiles to be sorted in this pass has its number of inversions equal to the number of lh2–trees with configuration

[figure: r; 1; 0] .

The expected number of exchanges is thus 2 · ( \frac{1}{2} · \frac{n}{4} ) = \frac{n}{4}.

Third Pass: Similar to the second pass; the expected number of exchanges is equal to the expected number of lowest height-1 trees with configuration

[figure: r; 1; 0] .

This is \frac{1}{2} · \frac{n}{2} = \frac{n}{4}.

Comment. Suppose Shellsort were used with l increments (2^{l−1}, …, 2, 1), where l ≤ k. A similar argument shows that the average number of exchanges on the first pass would be \frac{n}{4}(n/2^{l−1} −1), and each subsequent pass would have \frac{n}{4} on the average.

Solution to Problem 2(C).

Let g_{n}(z) = ∑_{k≥0} a_{nk}z^{k}, where a_{nk} is the probability that a random σ_{T} ∈ Σ_{n} has exactly k RL-max. Considering the two cases

[figure: r; 0; 1] and [figure: r; 1; 0] ,

we get for n ≥ 1

a_{2n,k} = \frac{1}{2}a_{n,k} + \frac{1}{2} ∑_{l≥0} a_{n,l}a_{n,k−l} .

This leads to

g_{2n}(z) = \frac{1}{2}g_{n}(z) + \frac{1}{2}(g_{n}(z))^{2} ,  for n ≥ 1 .  (2C.1)

Note that g_{1}(z) = z, and

g′_{2n}(z) = \frac{1}{2}g′_{n}(z) + g_{n}(z)g′_{n}(z) .  (2C.2)

Thus, using the fact g_{n}(1) = 1, we have

g′_{2n}(1) = \frac{3}{2}g′_{n}(1) ,

which implies

g′_{n}(1) = ( \frac{3}{2} )^{k} ,  k = lg n .  (2C.3)

This is the expected number of RL-max; it can also be written in the form n^{lg(3/2)} ≈ n^{0.585}.

To get the variance, recall that

Var_{n} = g′′_{n}(1) + g′_{n}(1) − (g′_{n}(1))^{2} .  (2C.4)

Now, from (2C.2),

g′′_{2n}(z) = \frac{1}{2}g′′_{n}(z) + (g′_{n}(z))^{2} + g_{n}(z)g′′_{n}(z) .

Thus, using (2C.3),

g′′_{2n}(1) = \frac{3}{2}g′′_{n}(1) + ( \frac{3}{2} )^{2k} .

Therefore

g′′_{n}(1) = \frac{4}{3}((3/2)^{2k} − (3/2)^{k}) ,  (2C.5)

and formulas (2C.3), (2C.4), (2C.5) give

Var_{n} = \frac{1}{3}((3/2)^{2k} − (3/2)^{k}) = \frac{1}{3}(n^{lg(9/4)} − n^{lg(3/2)}) .

Solution to Problem 2(D).

I. Some useful facts about Σ_{n}.

Fact 1. Σ_{n} is a permutation group.

Proof. Call an n × n matrix A = (a_{ij}) a permutation matrix if A contains exactly one 1 in each column, and in each row; all other entries are 0. Let Γ_{n} be the set of n × n permutation matrices defined recursively as the set of permutation matrices of the form \binom{B 0}{0 C} or \binom{0 B}{C 0} with B, C ∈ Γ_{n/2} and 0 being the matrix of all 0’s; Γ_{1} = {(1)}. It is easy to show by induction that Γ_{n} forms a subgroup of matrices under matrix multiplication. Now, associate each permutation ρ on {0, 1, …, n−1} with a unique n×n matrix A_{ρ} = (a_{ij}) where a_{ij} = 1 iff ρ(i) = j. It is clear that A_{ρρ′} = A_{ρ′} · A_{ρ}; also A_{ρ} is the identity matrix if ρ is the identity permutation. Thus, this association ρ → A_{ρ} is an isomorphism. As Γ_{n} is the image of Σ_{n} under this isomorphism, we have the desired result.

Fact 2. If ρ, ρ′ are random permutations uniformly chosen from Σ_{n}, then ρ · ρ′ is random (uniformly over Σ_{n}).

Proof. This follows from Fact 1 (even if the distribution of ρ′ is nonuniform).

II. About Algorithm S.

Algorithm S works in n − 1 passes for a file of n numbers. Let b_{j} be the number of RL-max, before the j-th pass starts, in the file consisting of the first n − j + 1 locations in the current array. Then the quantity B in the analysis of Algorithm 5.2.3S is (b_{1} − 1) + (b_{2} − 1) + ⋯ + (b_{n−1} − 1). Let us imagine that the algorithm has an extra, n-th, pass with b_{n} = 1. Let K_{n} denote the expected value of ∑_{1≤i≤n} b_{i}; then the answer we want is given by

B_{n} = K_{n} − n .  (2D.1)

We will concentrate on finding K_{n}.

Consider a random σ_{T} ∈ Σ_{n} being sorted by Algorithm S. If the root of T is

[figure: r; 0; 1] ,

then S can be considered as working first on the right subtree, then the left subtree, separately; this contributes \frac{1}{2} · 2K_{n/2} to K_{n}. If the root of T is

[figure: r; 1; 0] ,

the situation is more complicated, and we say the tree is inverted at the root. Let L_{n} denote the expected value of the total number of RL-max encountered in the first n/2 passes when sorting a random inverted tree. At the end of the (n/2)-th pass, the left half of the array contains a permutation ρ of \{0, 1, …, \frac{n}{2} − 1\}, and we will show that ρ is a random permutation uniformly chosen from Σ_{n/2}. This will imply that the second n/2 passes have an expected RL-max numbering K_{n/2}. To show ρ to be random, let T_{1}, T_{2} denote the left and right subtrees of T. At the end of the first n/2 passes, array location σ_{T}^{−1}(n − i) contains the number σ_{T} (n − i) for 1 ≤ i ≤ n/2. Or, equivalently, location j = σ_{T_{1}}^{−1}(\frac{n}{2} −i) contains the number σ_{T_{2}}(\frac{n}{2} − i), i.e., ρ(j) = σ_{T_{2}}(σ_{T_{1}}(j)). Thus ρ = σ_{T_{2}} · σ_{T_{1}}, and is random by Fact 2.

Summing both cases, we have shown that

K_{n} = \frac{1}{2}(2K_{n/2}) + \frac{1}{2}(L_{n} + K_{n/2})
= \frac{3}{2}K_{n/2} + \frac{1}{2}L_{n} .  (2D.2)

We will find L_{n} first. For example, L_{2} = 2, and L_{4} = (6+5+5+5)/4 = \frac{21}{4}.

III. More preliminary calculations.

Let M_{n} be the expected number of RL-max in a random σ_{T} from Σ_{n}. We know from 2(C) that, for n = 2^{k},

M_{n} = (3/2)^{k} .  (2D.3)

For a random σ_{T} ∈ Σ_{n}, let t_{nj} be the expected number of RL-max in (σ_{T} (0), σ_{T} (1), …, σ_{T} (n−j−1)), which is the file obtained by deleting the j rightmost numbers from σ_{T}. Let T_{n} denote ∑_{0≤j<n} t_{nj}. By considering the two possible different ways of labeling at the root, we obtain the following recurrence:

\begin{aligned}T_{n} & = \frac{1}{2}(2T_{n/2}) + \frac{1}{2}(T_{n/2} + (n/2)M_{n/2} + T_{n/2}) \\ & = 2 T_{n/2} + \frac{n}{4}M_{n/2} . \end{aligned}

Using (2D.3), we can solve the recurrence to obtain

T_{n} = \frac{1}{2}(3^{k} + 2^{k}) .  (2D.4)

We need one more definition besides M_{n}, T_{n}. Let σ_{T}^{(j)} denote the sequence of n − j numbers obtained from σ_{T} ∈ Σ_{n} by deleting the largest j elements. For example, if σ_{T} = (2 3 1 0), then σ_{T}^{(1)} = (2 1 0) and σ_{T}^{(2)} = (1 0). For a random σ_{T}, let v_{nj} denote the expected number of RL-max in σ_{T}^{(j)}. Let V_{n} = ∑_{0≤j<n} v_{nj}. Arguing as in the last paragraph, we can determine V_{n}. In fact,

V_{n} = \frac{1}{2}(3^{k} + 2^{k}) .  (2D.5)

IV. Determining L_{n}.

Take a random σ_{T} ∈ Σ_{n} with inversion at the root. There are four cases, each occurring with probability 1/4. Let us write down the expected number of RL-max in each case.

Case 1.

[figure: 1; 0; 1; 0; 1; 0; A; B; C; D]

In the first n/4 passes, the elements of D and A will be exchanged. As elements of B and C are greater than those of D, the elements of D once swapped to A will not give any RL-max. Thus, the expected number of RL-max in these n/4 passes will be equal to T_{n/4} + \frac{n}{4}M_{n/4} + \frac{n}{4}M_{n/4} + V_{n/4} (contributed by elements in D, C, B, A, respectively).

In the second n/4 passes, Algorithm S works on the array (D′, B, C), where D′ is D swapped and deformed. The expected number of RL-max is L_{n/2} (contributed by B and C).

Case 2.

[figure: 1; 0; 0; 1; 1; 0]
First n/4 passes: T_{n/4} + \frac{n}{4}M_{n/4} + V_{n/4} .
Second n/4 passes: L_{n/2} .

Case 3.

[figure: 1; 0; 1; 0; 0; 1]

Same result as in Case 2.

A10 greene and knuth: new appendices Case 4.

[figure: 1; 0; 0; 1; 0; 1]
First n/4 passes: L_{n/2} .
Second n/4 passes: V_{n/4} + \frac{n}{4}M_{n/4} + T_{n/4} .

(The first n/2 passes leave (A, D′, C), where D′ is random by the argument of part II.)

Summing over all four cases, we obtain

L_{n} = L_{n/2} + V_{n/4} + T_{n/4} + \frac{5}{16}n M_{n/4} ,

which simplifies because of (2D.3), (2D.4), and (2D.5):

L_{n} = L_{n/2} + 3^{k−2} + 2^{k−2} + \frac{5}{16}2^{k}(3/2)^{k−2}
= L_{n/2} + \frac{1}{4}(3^{k} + 2^{k}) .  (2D.6)

With L_{2} = 2, we solve (2D.6) to obtain for n = 2^{k} ≥ 2,

L_{n} = \frac{1}{8}3^{k+1} + 2^{k−1} − \frac{1}{8} .  (2D.7)

V. The Answer. From (2D.7) and (2D.2), we have

K_{n} = \frac{3}{2}K_{n/2} + \frac{1}{16}3^{k+1} + 2^{k−2} − \frac{1}{16} , n ≥ 2.

With K_{2} = 5/2, we solve the recurrence to obtain

K_{n} = \frac{1}{8}3^{k+1} + 2^{k} − \frac{1}{2}(3/2)^{k} + \frac{1}{8} , n ≥ 1.

And from (2D.1), we obtain the final answer:

B_{n} = \frac{1}{8}3^{k+1} − \frac{1}{2}(3/2)^{k} + \frac{1}{8} , k = lg n.

Solution to Problem 2(E).

Let us first derive some connections between the cycle structure of a random permutation in Σ_{2n} and of one in Σ_{n}. Write n = 2^{k}. Let us generate a random σ_{T} ∈ Σ_{2n} in two steps: First generate a random σ_{T′}; and later replace each leaf of T′ by either

[figure: r; 0; 1; or; r; 1; 0]

with equal probability. Take such a T′, and let (i_{1}i_{2} … i_{s}) be a cycle in σ_{T′}, where each i_{j} is a k-bit integer. If we take a random σ_{T} ∈ Σ_{2n} derived from T′, then the successor of i_{j}0 must be either i_{j+1}0 or i_{j+1}1, and similarly for i_{j}1. It follows that the 2s integers {i_{j}0, i_{j}1} will constitute either one cycle or two cycles in σ_{T}. In fact, if we form the cycle sequence i_{1}0 → i_{2}b_{2} → i_{3}b_{3} → ⋯ → i_{s}b_{s} in T, we will get one cycle if b_{s+1} = 1, and two cycles if b_{s+1} = 0; each possibility happens with probability 1/2. The above happens independently for each cycle in σ_{T′}.

We can conclude two facts: First, all cycles in Σ_{n} have lengths that are powers of 2; this, of course, follows also from the fact that Σ_{n} is a group of 2^{n−1} elements (see part D). Second, if we write g_{n}(z) = ∑_{l≥0} a_{nl}z^{l} where a_{nl} is the average number of cycles of length 2^{l} for a random permutation in Σ_{n}, then g_{2n}(z) can be obtained from g_{n}(z) by replacing each power z^{l} with \frac{1}{2}(z^{l+1} + 2z^{l}) = z^{l}(1 + \frac{1}{2}z). This implies g_{2n}(z) = (1 + \frac{z}{2} )g_{n}(z).

As g_{1}(z) = 1, we have, for n = 2^{k}, g_{n}(z) = (1 + \frac{1}{2}z)^{k}. The average number of cycles for a random permutation in Σ_{n} is thus equal to ∑_{l≥0} a_{nl} = g_{n}(1) = (3/2)^{k}.

The average order for a random integer for a σ_{T} ∈ Σ_{n} is equal to

\frac{1}{n} ∑_{l≥0} a_{nl}2^{l} · 2^{l} = \frac{1}{n}g_{n}(4) = (3/2)^{k} .

Solution to Problem 3.

(A) Let I_{n} be the set of all binary strings of length n with exactly two 1’s. For any nonnegative integer m, let J_{n,m} be the set of all strings of the form j_{1}j_{2} … j_{m}, where 1 ≤ j_{i} < n. For each α ∈ I_{n} and ρ = j_{1}j_{2} … j_{m} ∈ J_{n,m}, a maybesort array A initially containing α is transformed by the sequence of “comparison–exchanges” A[j_{1}] : A[j_{1} + 1], A[j_{2}] : A[j_{2} + 1], …, A[j_{m}] : A[j_{m} + 1]; let f(α, ρ) denote the resulting binary string in A. Take a random ρ uniformly from J_{n,m} and let q(α, m) denote the probability that f(α, ρ) ≠ 0^{n−2}1^{2}, i.e., the probability that α is not yet sorted after m steps in maybesort. Then

t_{n}(α) = ∑_{m≥0} q(α, m) .  (3.1)

Write the string α ∈ I_{n}, with the k-th and l-th bits being 1, as [k, l], 1 ≤ k < l ≤ n. Write [k, l] ≤ [k′, l′] if k ≤ k′ and l ≤ l′. A simple induction on m proves

Lemma 3.1. For any ρ ∈ J_{n,m},

f([k, l], ρ) ≤ f([k′, l′], ρ) if [k, l] ≤ [k′, l′] .

It follows from Lemma 3.1 that, for any α ∈ I_{n},

q(α, m) ≤ q(β_{n}, m) .  (3.2)

Combining (3.1) and (3.2), we obtain t_{n}(α) ≤ t_{n}(β_{n}) as desired

(B) Consider the process of sorting a string α ∈ I_{n} with maybesort as the movement of the two 1’s from left to right in the array A; we name the two 1’s as distinct objects S and L so that, when S and L occupy consecutive positions j and j +1, the “comparison–exchange” A[j] : A[j +1] has no effect on the array. Note that L is always to the right of S.

Let us divide the sorting process into two phases: The first phase ends when L reaches A[n], and the rest is the second phase. In the sorting process, an operation “A[j] : A[j + 1]” in the first phase is called a hit if it produces a movement of L; it is a hit in the second phase if it produces a movement of S.

Write

t_{n}(β_{n}) = F_{n} + G_{n} ,  (3.3)

where F_{n} is the average number of steps used in the first phase, and G_{n} is that in the second phase. In the first phase, exactly n − 2 hits will occur. Let F_{n} = C_{0} + C_{1} + ⋯ + C_{n−2}, where C_{i} is the average number of steps used after the i-th and up to the (i + 1)-st hits. Clearly, C_{i} = n − 1. Thus,

F_{n} = (n − 1)(n − 2) .  (3.4)

Now, at the end of phase 1, suppose S is in location z; then n − 1 − z hits will occur in phase 2, and the expected number of steps will be exactly (n − 1 − z) · (n − 1). Let Z denote the random variable corresponding to z; we have

G_{n} = E(n − 1 − Z) · (n − 1) .  (3.5)

We will evaluate E(n − 1 − Z); then (3.3), (3.4), and (3.5) will give the answer to t_{n}(β_{n}).

Let us represent the movements of S and L during the first phase on a two-dimensional lattice. If currently L is in A[l + 2] and S in in A[s + 1], we say that the configuration is the point (l, s) on the lattice. Initially, the configuration is (0,0).

[figure: (0, n − 2); (n − 2, n − 2); (n − 2, Z − 1); (0, 0); (n − 2, 0); l; s; s = l]

The sequence of movements of S and L in phase 1 traces a path on the lattice from (0,0) to a point having coordinates (l, s) = (n − 2, Z − 1).

Let m = n − 2. We can describe the random path as generated by the following process: Start at (0,0); at each step, say in configuration (l, s), move to (l + 1, s) or (l, s + 1) with equal probability except when s = l, in which case move to (l + 1, s); the path ends when l = m. We are interested in the random variable n − 1 − Z = m − (Z − 1), the difference between the two coordinates when the path ends.

It is simpler to consider an alternative process by removing the exception rule at s = l. Generate a path starting at (0,0); at each step move rightward or upward with equal probability, until one of l or s is equal to m. Let (X, Y) denote the final coordinates (l, s). Then |X − Y | has the same distribution as m − (Z − 1) in the more complicated process.

But the probability of reaching (X, Y) = (m, k) is 2^{−m−k} times the number of paths from (0, 0) to (m − 1, k), and there are \binom{m−1+k}{m−1} such paths. The probability of reaching (X, Y) = (k, m) is the same as the probability of reaching (m, k), for 0 ≤ k < m. Hence the probability that |X − Y | = d is

\frac{2}{2^{m+(m−d)}} \binom{m − 1 + m − d}{m − 1} = \frac{2^{d}}{2^{2m−1}} \binom{2m − 1 − d}{m − 1} ,  (3.6)

for 1 ≤ d ≤ m.

The expected value is

\frac{1}{2^{2m−1}} ∑_{d=1}^{m} d·2^{d}\binom{2m−1−d}{m−1} = \frac{1}{2^{2m−1}} ∑_{k=0}^{m−1}(m−k)·2^{m−k}\binom{m−1+k}{m−1}

= \frac{1}{2^{2m−1}} ( ∑_{k=0}^{m−1} 2m·2^{m−k}\binom{m−1+k}{m−1}

−∑_{k=0}^{m} m·2^{m−k}\binom{m+k}{m}+m\binom{2m}{m})

= \frac{1}{2^{2m−1}} (2m·2^{2m−1}−m·2^{m}·2^{m}+m\binom{2m}{m})

= \frac{2m}{2^{2m}} \binom{2m}{m};  (3.7)

here we have used the identity

∑_{k=0}^{m} \binom{m + k}{k}2^{−k} = 2^{m},  (3.8)

which holds because the sum of probabilities (3.6) must be 1.

Therefore, from (3.3), (3.4), and (3.7),

t_{n}(β_{n}) = (n − 1)(n − 2)(1 + \frac{1}{2^{2n−5}} \binom{2n − 4}{n − 2}).  (3.9)

Asymptotically, this gives

t_{n}(β_{n}) = n^{2} + \frac{2}{\sqrt{π}} n^{3/2} + O(n) .  (3.10)

Comments. If n = 10^{6} and one time unit for maybesort is one picosecond (10^{−12} sec), it will take about a second to do the sort. This is about the same as for one of today’s computers if we assume that the sort will take about n microseconds.

If maybesort is applied to an arbitrary bit string, it takes an average of O(n) steps to reduce the number of inversions by 1. Hence t_{n}(α) = O(n^{3}) for all α.

final exam iv A15

Appendix K: Final Exam IV and Solutions

Final Exam IV (A. C. Yao, 1984)

Problem 1. Let f(x) = ∑_{p≤x} \frac{1}{p ln p}, where the sum is over the primes p.

(A) [5 points]. Prove that the limit N = lim_{x→∞} f(x) exists and is finite. Use elementary arguments (without Stieltjes integrals) if you can.

(B) [10 points]. Determine the asymptotic value of f(x) − N up to an additive O((log x)^{−10}) error term.

Problem 2. [50 points total]

(A) [15 points]. Let (2 − e^{z})^{1/2} = ∑_{n≥0} a_{n}z^{n}. Determine the asymptotic value of a_{n}. Give your answer in the form of g(n)(1 + O(h(n))), where g and h are familiar functions.

(B) [15 points]. Let (1 + e^{z})^{−1} = ∑_{n≥0} a_{n}z^{n}. Determine the asymptotic value of a_{n} to within a multiplicative factor of 1 + O(100^{−n}) or better.

(C) [20 points]. Let λ = exp(−π/ tan(π/\sqrt{7} )), and f(n) = ∑_{k≥0}(−λ)^{k}k^{n}. Determine the asymptotic value of f(n) to within a multiplicative factor of 1 + o(1).

Comment: You may find useful the fact that there exists a constant K > 0 such that |p/q − \sqrt{7} | > K/q^{2} for all integers p and q. (This is a consequence of Liouville’s Theorem; see, e.g., Hardy and Wright, The Theory of Numbers, Section 11.7.)

Problem 3. (The Modest Cookie Monster) [35 points]. Consider a monster whose appetite for cookies decreases as its size increases. When we throw a cookie to such a monster with k cookies in its belly, with probability 1 − pk^{2} the monster will grow to size k + 1.

Let n > 0 be an integer and p = 1/n^{2}. Initially the monster has an empty stomach. Let X_{n,m} be the random variable corresponding to the size of the monster after m cookies have been thrown. Let α > 0 be any fixed real number. Question: Determine the asymptotic mean and variance of X_{n,⌈αn⌉} to within a multiplicative factor of 1 + o(1), as n → ∞.

Comment: This question arises in the analysis of a modified version of hashing with separate chaining, in which each key has two random hashing addresses. A key will be added to the list headed by its first hashing address, only if both addresses are nonempty.

Solutions to Final Exam IV

Solution to Problem 1.

(A) There are O(2^{n}/n) primes between 2^{n} and 2^{n+1}, and each term of the sum in this range of p is O(2^{−n}/n). Hence the total is ∑_{n≥1} O(1/n^{2}).

(B) The difference is

∫_{0}^{∞} \frac{dπ(t)}{t ln t} = ∫_{x}^{∞} \frac{1}{(ln t)^{m+1}} d ∫_{1.5}^{t} \frac{(ln u)^{m} dπ(u)}{u} = ∫_{x}^{∞} \frac{dC_{m}(t)}{(ln t)^{m+1}}

= \frac{C_{m}(t)}{(ln t)^{m+1}} |_{x}^{∞} + (m + 1) ∫_{x}^{∞} \frac{C_{m}(t) dt}{t(ln t)^{m+2}}

= −\frac{1}{m ln x} + O(\frac{1}{(log x)^{m+1}} ) + \frac{m + 1}{m} ∫_{x}^{∞} \frac{dt}{t(ln t)^{2}}

= \frac{1}{ln x} + O(\frac{1}{(log x)^{m+1}} ) for all m > 0.

Solution to Problem 2.

(A) Let w = z/ ln 2. We have 2−e^{z} = 2−e^{w ln 2} = (ln 4)(1−w)f(w), where

f(w) = 1 − (1 − w)\frac{ln 2}{2!} + (1 − w)^{2} \frac{(ln 2)^{2}}{3!} − ⋯

is analytic and nonzero for |w| < |1+2πi/ ln 2|. Thus the function \sqrt{2−e^{z}} = \sqrt{ln 4}\sqrt{1 − w}f(w)^{1/2} has coefficients rather like those of \sqrt{ln 4}\sqrt{1 − w}, and a_{n} = \sqrt{ln 4}(−1/ ln 2)^{n}\binom{1/2}{n}(1 + O(n^{−1})) = −C(ln 2)^{−n}n^{−3/2}(1 + O(n^{−1})), C = \sqrt{ln 2/2π}.

(B) These coefficients are known in closed form:

∑_{n≥0} a_{n}z^{n} = \frac{1}{e^{z} + 1} = \frac{1}{e^{z} − 1} − \frac{2}{e^{2z} − 1} = ∑_{n≥1} \frac{(1 − 2^{n})B_{n}z^{n−1}}{n!} ,

so a_{n} = (1 − 2^{n+1})B_{n+1}/(n + 1)!. We have a_{n} = 0 for even n > 0, and a_{2n−1} = (−1)^{n−1}π^{−2n}2^{1−2n}H_{∞}^{(2n)} = (−1)^{n−1}π^{−2n}2^{1−2n}(1 + 2^{−2n} + ⋯ + 99^{−2n})(1 + O(100^{−(2n−1)})).

(C) The strange behavior of this function is evident from the values f(10) = 9.474, f(11) = −3.899, f(12) = −119.3, f(13) = −289.5, f(14) = 997.1.

solutions to final exam iv A17

But its exponential generating function is quite simple:

∑_{n≥0} f(n)\frac{z^{n}}{n!} = ∑_{k,n≥0}(−λ)^{k}k^{n} \frac{z^{n}}{n!} = ∑_{k≥0}(−λe^{z})^{k} = \frac{1}{1 + λe^{z}} .

There are poles at z = x+iy where y is an odd multiple of π and x = − ln λ. We have

\frac{1}{1 + λe^{z}} = \frac{1}{x + iy − z} + \frac{1}{2} + \frac{B_{2}}{2!} (x + iy − z) + \frac{B_{4}}{4!} (x + iy − z)^{3} + ⋯

near z = x + iy, hence the asymptotic value of f(n) is

n!(\frac{1}{(x + iπ)^{n+1}} + \frac{1}{(x − iπ)^{n+1}} + O(\frac{1}{|x + 3iπ|^{n+1}} )).

For the stated λ we have x + iπ = e^{iθ}π/ sin θ, where θ = π/\sqrt{7}. Hence

f(n) ∼ \frac{2 n! (sin θ)^{n+1} cos(n + 1)θ}{π^{n+1}} ,

provided that the cosine factor is large enough to keep this term from being swamped by the O term.

To complete the proof, we will show that | cos nθ| = Ω(1/n). Suppose c is a constant such that | cos nθ| < c/n for infinitely many n. Then there are infinitely many pairs of integers (m, n) with |nπ/\sqrt{7} − (m + \frac{1}{2})π| < 2c/n. But this yields infinitely many rational p/q = 2n/(2m + 1) with

| \frac{p}{q} − \sqrt{7} | = \frac{2\sqrt{7}}{(2m + 1)π} |\frac{nπ}{\sqrt{7}} − \frac{(2m + 1)π}{2} | < \frac{28c}{πn^{2}} ,

contradicting Liouville’s theorem if c ≤ πK/28.

Solution to Problem 3.

Eigenoperator methods do not seem to apply to this problem, so we must work harder. First, let’s proceed heuristically: Suppose there is a function M such that approximately M(β)n cookies are required to make the monster’s size βn. Then 1/(1 − β^{2}) further cookies are needed to make it reach size βn + 1. So M′(β) = 1/(1 − β^{2}), and we suspect that the function

M(β) = ∫_{0}^{β} \frac{dx}{1 − x^{2}} = \frac{1}{2} ln \frac{1 + β}{1 − β} = arctanh β

has the stated property. For example, let β = \frac{1}{2}; about \frac{ln 3}{2}n cookies should make the monster half full.

Conversely, after αn cookies have been thrown, this argument suggests that the monster’s size should be about M^{−1}(α)n, where

M^{−1}(α) = tanh α = \frac{e^{α} − e^{−α}}{e^{α} + e^{−α}} .

There probably is a way to make this heuristic argument rigorous, and more generally to convert any “coupon collecting” result about the approximate distribution of the time needed to collect a given number of coupons into a dual result about the approximate distribution of the number of coupons collected up to a given time. The following derivation, however, takes a different tack: First we find formulas for the exact distribution of size at a given time, then we apply asymptotic methods to these formulas in order to compute the mean and variance. This approach involves lengthy but interesting formula manipulation that provides more information than requested in the problem.

Let g_{m}(z) be the probability generating function for X_{n,m}, so that p_{m,l} = [z^{l}] g_{m}(z) is the probability that the monster’s size is l after m cookies. Thus g_{1}(z) = z, g_{2}(z) = pz + (1 − p)z^{2}, g_{3}(z) = p^{2}z + 5p(1 − p)z + (1 − p)(1 − 4p)z^{3}. In general we have

g_{m}(z) = ∑_{l=0}^{m} a_{m,l}p^{m−l} ∏_{k=1}^{l−1}(1 − k^{2}p) z^{l}  (1)

where the integers a_{m+1,l} = l^{2}a_{m,l} + a_{m,l−1} form a triangular array that begins as follows:

1

1  1
1  5  1
1  21  14  1
1  85 147 30  1
1  341 1408 627 55  1

The law of formation shows that

a_{m,l} = [z^{m−l}] \frac{1}{(1 − z)(1 − 4z) … (1 − l^{2}z)} .  (2)

We can simplify formula (1) for the probability p_{m,l} = [z^{l}] g_{m}(z), because 1 − k^{2}p = (1 − k/n)(1 + k/n); this yields

p_{m,l} = \frac{a_{m,l} (n + l − 1)!}{n^{2m−1} (n − l)!} .  (3)

If we knew the approximate size of a_{m,l} we would therefore know the approximate probability p_{m,l}. The partial fraction expansion

\frac{1}{(1 − z)(1 − 2^{2}z) … (1 − l^{2}z)} = \frac{2}{(2l)!} ∑_{k=0}^{l} \binom{2l}{l + k}\frac{k^{2l}(−1)^{l−k}}{1 − k^{2}z}

gives us the asymptotic formula

a_{m,l} = \frac{2}{(2l)!} l^{2m} + O((l − 1)^{2m})

for fixed l as m → ∞. But this is not good enough, because we need to know a_{m,l} when l grows with m; simply expanding the generating function around its dominant singularity does not in this case provide the necessary information. The saddle-point method now comes to our rescue:

Lemma. Given a real number 0 < ρ < 1, there are functions a(ρ) and c(ρ) such that

a_{m,l} = c(ρ) a(ρ)^{2l} l^{2m−2l−1/2} (1 + O(1/m))  (4)

when l and m approach ∞ with ratio m/l = ρ.

Proof. Writing n for l, we want to estimate

a_{ρn,n} = [z^{(ρ−1)n}] \frac{1}{∏_{k=1}^{n}(1 − k^{2}z)} = \frac{1}{2πi} ∮ e^{nf(z)} \frac{dz}{z} ,  (5)

where

f(z) = (ρ − 1) ln \frac{1}{z} + \frac{1}{n} ∑_{k=1}^{n} \frac{1}{1 − k^{2}z}  (6)

and the path of integration encloses the origin inside |z| < 1/n^{2}. The substitutions z = w^{2}/n^{2} and f(z) = 2g(w) change this to

a_{ρn,n} = \frac{1}{π} ∫_{−π/2}^{π/2} e^{2ng(w)} dt ,  w = re^{it};  (7)

thus we choose a radius r < 1 and integrate around a semicircle. Here

g(w) = (ρ − 1) ln \frac{n}{w} + \frac{1}{n} ∑_{k=1}^{n} ∑_{j=1}^{∞} \frac{k^{2j}}{n^{2j}} \frac{w^{2j}}{2j}

= (ρ − 1) ln \frac{n}{w} + ∑_{j=1}^{∞} \frac{1}{2j + 1} \frac{w^{2j}}{2j} ∑_{l=0}^{∞} \binom{2j + 1}{l}B_{l} (\frac{−1}{n})^{l}

= (ρ − 1) ln n − (ρ − 1) ln w + h(w) + \frac{1}{4n} ln \frac{1}{1 − w^{2}} + O(n^{−2}), (8)

where

h(w) = ∑_{j=1}^{∞} \frac{w^{2j}}{(2j + 1)(2j)} = 1+ \frac{(1 − w) ln(1 − w) − (1 + w) ln(1 + w)}{2w} . (9)

As in most applications of the saddle point method, it is convenient to use the identity

g(re^{s}) = g(r) + \frac{s}{1!}ϑg(r) + \frac{s^{2}}{2!} ϑ^{2}g(r) + \frac{s^{3}}{3!} ϑ^{3}g(r) + ⋯,  (10)

where ϑ is the operator w \frac{d}{dw}; cf. [Knuth II, third edition, exercise 3.3.2–30]. For if we choose the radius of integration r near the saddle point, so that ϑg(r) = O(n^{−1}), and if we apply this identity with s = it and t = u/\sqrt{n}, our integral (7) takes the form

a_{ρn,n} = \frac{1}{π\sqrt{n}} ∫_{−π\sqrt{n}/2}^{π\sqrt{n}/2} exp(2ng(r) + iuO(n^{−1/2}) − u^{2}ϑ^{2}g(r)
− iu^{3}O(n^{−1/2}) + u^{4}O(n^{−1}) + ⋯) du .(11)

Now

\begin{aligned}ϑg(w) & = 1 − ρ + ∑_{j≥1} \frac{1}{2j + 1}w^{2j} + O(n^{−1}), \\ ϑ^{2}g(w) & =  ∑_{j≥1} \frac{2j}{2j + 1}w^{2j} + O(n^{−1}), \\ ϑ^{3}g(w) & =  ∑_{j≥1} \frac{4j^{2}}{2j + 1}w^{2j} + O(n^{−1}), \end{aligned}

etc. To make ϑg(r) small we choose r so that ∑_{j≥1} r^{2j}/(2j + 1) = ρ − 1:

ρr = r + \frac{r^{3}}{3} + \frac{r^{5}}{5} + ⋯ = arctanh r = M(r) .  (12)

Notice that this choice of r also makes

\begin{aligned}ϑ^{2}g(r) & = ϑg(r) + ϑ^{2}g(r) + O(n^{−1}) \\ & = 1 − ρ + ∑_{j≥1} r^{2j} + O(n^{−1}) = 1/(1 − r^{2}) − ρ + O(n^{−1}). \end{aligned}

Plugging this into (11) and using ∫_{−∞}^{∞} e^{−au^{2}} du = \sqrt{π/a} yields

\begin{aligned}a_{ρn,n} & = \frac{e^{2ng(r)}}{π\sqrt{n}} ∫_{−∞}^{∞} e^{−ϑ^{2}g(r)u^{2}} du (1 + O(n^{−1})) \\ & = \frac{n^{2(ρ−1)n}}{r^{2(ρ−1)n}} \frac{e^{2nh(r)}}{\sqrt{πn(1 − (1 − r^{2})ρ)}}(1 + O(n^{−1})) . \end{aligned}

This completes the proof of the lemma, establishing (4) with l = n, a(ρ) = e^{h(r)}/r^{ρ−1}, and c(ρ) = 1/\sqrt{π(1 − (1 − r^{2})ρ)}.

For example, the true value of a_{20,10} is 5,992,171,630,749,371,157,181; the approximation in the lemma, with 2r = M(r) for r ≈ .9575, gives 6.05×10^{21}. The true value of a_{100,70} is the 124-digit number 6,018, …,616; the lemma estimates 6.04 × 10^{123}. Carrying further accuracy in the proof of (4) would yield a complete asymptotic series, with the O(n^{−1}) terms replaced by b_{1}(ρ)/n + b_{2}(ρ)/n^{2} + · · ·.

Returning to probabilities, our formula (3) can now be converted to an asymptotic estimate, using Stirling’s formula to write (2l)! ∼ (2l/e)^{2l}\sqrt{4πl}:

p_{m,l} = \frac{n}{n + l} (\frac{l}{n})^{2m} \binom{n + l}{2l} C(ρ) A(ρ)^{2l} (1 + O(\frac{1}{n})),  (13)

where ρ = m/l, assuming that l, m, and n approach infinity at approximately proportional rates. Here

A(ρ) = 2e^{−1}a(ρ) = 2e^{h(r)−1}/r^{ρ−1},  (14)
C(ρ) = 2\sqrt{π} c(ρ) = 2/\sqrt{1 − (1 − r^{2})ρ},  (15)

and r is chosen so that

ρr = arctanh r = \frac{1}{2} ln \frac{1 + r}{1 − r} .  (16)

Formulas (9) and (16) imply that

e^{h(r)−1} = (\frac{1 − r}{1 + r} )^{(1+r)/2r} \frac{1}{1 − r} = \frac{e^{−ρ(r+1)}}{1 − r} = \frac{e^{−ρ}}{\sqrt{1 − r^{2}}} ,

so we can considerably simplify the formula for A(ρ):

A(ρ) = 2e^{−ρ}/\sqrt{1 − r^{2}} r^{ρ−1} .  (17)

The heuristic discussion we began with suggests that the probability will be negligible except when l and m are approximately βn and M(β)n for some β. For example, let n = 100 and β = \frac{1}{2}; then M(β) = ln \sqrt{3} ≈ .5493, so if m = 55 we expect the value of l to be near 50. Indeed, p_{55,40} is very small, approximately 8 × 10^{−7}, when n = 100, and the only probabilities ≥ .01 are

\begin{matrix}l = & 46 & 47 & 48 & 49 & 50 & 51 & 52 & 53 & 54 \\ p_{55,l} ≈ & .02 & .05 & .10 & .17 & .21 & .21 & .14 & .07 & .02 \end{matrix}

Let therefore m = αn and β = tanh α, so that α = M(β). We will express p_{m,l} with respect to βn as a central point of reference: Let

P (δ) = \frac{p_{m,l}}{p_{m,βn}} ,  l = (β + δ) n.  (18)

Our goal will be to show that this ratio P (δ) is “bell-shaped”; more precisely, we will prove that

P (δ) = exp(f_{1}δ + f_{2}δ^{2} + f_{3}δ^{3} + ⋯)  (19)

where each f_{k} is O(n) and where f_{1} is O(1). The value of f_{2} will be −cn + O(1). Once we have established this, the mean and variance desired in Problem 3 can be found. For we have

1 = ∑_{l=0}^{m} p_{m,l} = p_{m,βn} ∑_{l=−∞}^{∞} P (\frac{l}{n} − β)

∼ p_{m,βn} ∫_{−∞}^{∞} P (\frac{t}{n}) dt

= \sqrt{n} p_{m,βn} ∫_{−∞}^{∞} P (\frac{u}{\sqrt{n}}) du

= \sqrt{n} p_{m,βn} ∫_{−∞}^{∞} exp(−cu^{2} + O(n^{−1/2})) du

= \sqrt{\frac{πn}{c}}p_{m,βn}(1 + O(n^{−1/2}));

hence p_{m,βn} ∼ \sqrt{c/πn}. Next,

E(X_{m,αn}) − βn = ∑_{l=0}^{m}(l − βn)p_{m,l}

= p_{m,βn} ∑_{l=−∞}^{∞}(l − βn)P (\frac{l}{n} − β)

∼ \sqrt{\frac{c}{πn}} ∫_{−∞}^{∞} t P (\frac{t}{n}) dt

= \sqrt{\frac{cn}{π}} ∫_{−∞}^{∞} u P (\frac{u}{\sqrt{n}}) du

= \sqrt{\frac{cn}{π}} ∫_{−∞}^{∞} u exp(−cu^{2} + O(n^{−1/2})) du = O(1).

And in a similar fashion,

E((X_{n,αn} − \overline{X})^{2}) = ∑_{l}(l − βn + O(1))^{2}p_{m,l}

∼ \sqrt{\frac{c}{πn}} ∫_{−∞}^{∞}(t + O(1))^{2}P (\frac{t}{n}) dt

= n\sqrt{\frac{c}{π}} ∫_{−∞}^{∞}(u + O(n^{−1/2}))^{2}P (\frac{u}{\sqrt{n}}) du

= \frac{n}{2c}(1 + O(n^{−1/2})) .

To complete the solution, therefore, we want to establish (19). Formula (13) already shows that (19) holds with each f_{k} = O(n), so the remaining problem is to prove that f_{1} = O(1).

When m = αn and β = tanh α and l = (β + δ)n, the value of r = β + qδ + O(δ^{2}) satisfies

\frac{α}{β + δ} (β + qδ) = M(β + qδ) = M(β) + qδM′(β) + O(δ^{2}) ;

hence

q = \frac{α}{α − β/(1 − β^{2})} = −\frac{α(1 − β^{2})}{β − α(1 − β^{2})} .

We can now calculate ln(p_{m,l}/p_{m,βn}), ignoring low-order terms:

O(1) + O(δ^{2})

+ 2m ln(β + δ) + ln(n + l)! − ln(n − l)! − ln(2l)! + 2l ln A(α/(β + δ))

− 2m ln β − ln(n + βn)! + ln(n − βn)! + ln(2βn)! − 2βn ln A(α/β)

= O(1) + O(δ^{2}) + nδ(\frac{2α}{β} + 1 + ln(1 + β) + 1 + ln(1 − β) − 2 − 2 ln 2β

+ 2 ln 2 + \frac{2βq}{1 − β^{2}} − ln(1 − β^{2}) − \frac{2αq}{β} + 2q + 2 ln β),

and everything cancels out beautifully.

To find the coefficient c of −nδ^{2}, we can extend the accuracy to O(δ^{3}), with r = β + qδ + pδ^{2} + O(δ^{3}) when p = (α − β)q/(β − α(1 − β^{2}))^{2}. Or, we can use the relation p_{m,βn} ∼ \sqrt{c/πn} derived earlier. Both approaches give the same result,

c = \frac{1}{(1 − β^{2})(β − α(1 − β^{2}))};  (20)

this provides an excellent check on the calculations. The variance is ∼ n/2c.