TAOCP 5.1.1 Exercise 18

We are given a sequence of \(N = 2^n\) independent random \(n\)-bit integers \(X_0, X_1, \ldots, X_{N-1}\).

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.1: Inversions

Exercise 18. [M30] (T. Hibbard, CACM 6 (1963), 210.) Let $n > 0$, and assume that a sequence of $2^n$ $n$-bit integers $X_0, \ldots, X_{2^n - 1}$ has been generated at random, where each bit of each number is independently equal to 1 with probability $p$. Consider the sequence $X_0 \oplus 0, X_1 \oplus 1, \ldots$, where $\oplus$ denotes the "exclusive or" operation on the binary representations. Thus if $p = 0$, the sequence is $0, 1, \ldots, 2^n - 1$, and if $p = 1$ it is $2^n - 1, \ldots, 1, 0$; and when $p = \frac{1}{2}$, each element of the sequence is a random integer between 0 and $2^n - 1$. For general $p$ this is a useful way to generate a sequence of random integers with a biased number of inversions, although the distribution of the elements of the sequence taken as a whole is uniform in the sense that each $n$-bit integer has the same distribution. What is the average number of inversions in such a sequence, as a function of the probability $p$?

Verified: yes
Solve time: 1h29m

We are given a sequence of (N = 2^n) independent random (n)-bit integers (X_0, X_1, \ldots, X_{N-1}). Each bit of each (X_i) equals (1) with probability (p) and (0) with probability (q = 1-p). The sequence to be examined is
[ Y_i = X_i \oplus i \qquad (0 \le i < 2^n), ] where (\oplus) denotes bitwise exclusive or. An inversion is a pair ((i,j)) with (i < j) and (Y_i > Y_j). We want the expected number of inversions [ E_n = \mathbb{E}\bigl[#{(i,j): 0 \le i < j < 2^n,; Y_i > Y_j}\bigr]. ]

Because the (X_i) are independent, the (Y_i) are independent as well. By linearity of expectation, [ E_n = \sum_{0 \le i < j < 2^n} \mathbb{P}(Y_i > Y_j). ]

For a fixed pair (i < j), we compare the binary representations of (Y_i) and (Y_j) from the most significant bit (MSB) downwards. The bits at different positions are independent. The (k)-th bit of (Y_i) depends on the (k)-th bit of (i): [ Y_i^{(k)} = \begin{cases} X_i^{(k)} & \text{if } i_k = 0,\ 1 - X_i^{(k)} & \text{if } i_k = 1. \end{cases} ]

Let (A = \mathbb{P}(\text{two independent bits are equal}) = p^2 + q^2) and (B = \mathbb{P}(\text{two independent bits are different}) = 2pq). For two indices with given MSBs, the probabilities that their MSBs compare as (Y_i > Y_j) and that they are equal are:

[ \begin{array}{c|c|c} (i_{\text{MSB}}, j_{\text{MSB}}) & \mathbb{P}(Y_i > Y_j \text{ at MSB}) & \mathbb{P}(Y_i = Y_j \text{ at MSB}) \ \hline (0,0) & pq & A \ (1,1) & pq & A \ (0,1) & p^2 & B \ (1,0) & q^2 & B \end{array} ]

We split the sum for (E_n) according to the MSB of (i) and (j). Let (H = 2^{n-1}). The indices (0,\ldots,H-1) have MSB (0); indices (H,\ldots,2^n-1) have MSB (1).

Case 1: Both in the first half ((i,j < H)). There are (\binom{H}{2}) such pairs. For each, [ \mathbb{P}(Y_i > Y_j) = pq + A \cdot P_{n-1}(i,j), ] where (P_{n-1}(i,j)) is the probability that the lower (n-1) bits make (Y_i > Y_j) (with the same independent bit distributions). Summing over all pairs gives [ \binom{H}{2} pq + A E_{n-1}. ]

Case 2: Both in the second half ((i,j \ge H)). By symmetry this gives the same contribution: [ \binom{H}{2} pq + A E_{n-1}. ]

Case 3: (i) in the first half, (j) in the second half ((i < H \le j)). There are (H^2) such pairs. For each, [ \mathbb{P}(Y_i > Y_j) = p^2 + B \cdot P_{n-1}(i_{\text{low}}, j_{\text{low}}), ] where (i_{\text{low}}, j_{\text{low}}) are the lower (n-1) bits. Because (X_i) and (X_j) are independent even when (i_{\text{low}} = j_{\text{low}}), the sum over all (i_{\text{low}}, j_{\text{low}}) involves the probability for independent copies. We define [ T_m = \sum_{x=0}^{2^m-1}\sum_{y=0}^{2^m-1} \mathbb{P}(Y_x > Y_y), ] where in each term (Y_x) and (Y_y) are generated from independent (X_x, X_y) with the same bitwise distribution. The contribution of Case 3 is [ H^2 p^2 + B, T_{n-1}. ]

Adding the three cases we obtain the recurrence for (E_n): [ E_n = 2\Bigl(\binom{H}{2} pq + A E_{n-1}\Bigr) + H^2 p^2 + B T_{n-1}, \qquad H = 2^{n-1}. \tag{1} ]

Now we derive a recurrence for (T_m). For (m \ge 1) let (H_m = 2^{m-1}). Split the (m)-bit indices into two halves of size (H_m). Because all pairs are independent, we sum the four blocks:

  • both in first half: (H_m^2 pq + A T_{m-1});
  • both in second half: (H_m^2 pq + A T_{m-1});
  • (x) in first, (y) in second: (H_m^2 p^2 + B T_{m-1});
  • (x) in second, (y) in first: (H_m^2 q^2 + B T_{m-1}).

Adding and using (p^2 + 2pq + q^2 = 1) and (A + B = 1) gives [ T_m = H_m^2 + 2 T_{m-1}, \qquad H_m = 2^{m-1}, \quad T_0 = 0. \tag{2} ]

Solving (2): [ T_m = \sum_{k=1}^m 2^{m-k} \cdot 2^{2k-2} = 2^{m-1}\sum_{k=1}^m 2^{k-1} = 2^{m-1}(2^m-1) = \frac{4^m - 2^m}{2}. \tag{3} ]

Now substitute (3) and the explicit values into (1). We have [ \binom{H}{2} = \frac{H(H-1)}{2} = 2^{n-2}(2^{n-1}-1), \quad 2\binom{H}{2} pq = (2^{2n-2} - 2^{n-1})pq, ] [ H^2 p^2 = 2^{2n-2} p^2, ] [ B T_{n-1} = 2pq \cdot \frac{4^{n-1} - 2^{n-1}}{2} = 2^{2n-2} pq - 2^{n-1} pq. ]

The sum of the terms not containing (E_{n-1}) is [ C_n = 2^{2n-2}(pq + p^2 + pq) - 2^n pq = 2^{2n-2}(p^2 + 2pq) - 2^n pq. ] Since (p^2 + 2pq = p(p+2q) = p(1+q)), we can write [ C_n = 2^{2n-2} p(1+q) - 2^n pq. ]

The recurrence becomes [ E_n = 2A E_{n-1} + C_n, \qquad A = p^2 + q^2 = 1 - 2pq, \quad E_0 = 0. \tag{4} ]

Let (r = 2A = 2(p^2+q^2) = 2 - 4pq). The solution of (4) is [ E_n = \sum_{k=1}^n r^{n-k} C_k = \sum_{k=1}^n r^{n-k} \bigl(4^{k-1} p(1+q) - 2^k pq\bigr). ]

Evaluate the two geometric sums: [ \sum_{k=1}^n r^{n-k} 4^{k-1} = \frac{4^n - r^n}{4 - r} = \frac{4^n - r^n}{2(1+2pq)}, ] [ \sum_{k=1}^n r^{n-k} 2^k = \frac{2^{n+1} - 2 r^n}{2 - r} = \frac{2^n - r^n}{2pq}. ]

Hence [ E_n = p(1+q),\frac{4^n - r^n}{2(1+2pq)} - pq,\frac{2^n - r^n}{2pq} = \frac{p(1+q)(4^n - r^n)}{2(1+2pq)} - \frac{2^n - r^n}{2}. ]

Putting everything over the common denominator (2(1+2pq)) and noting that [ (1+2pq) - p(1+q) = 1+2pq - p(2-p) = 1 - p^2 = q(1+p), ] we obtain the symmetric closed form:

[ \boxed{E_n = \frac{p(1+q),4^n + q(1+p),\bigl(2(p^2+q^2)\bigr)^n - (1+2pq),2^n}{2(1+2pq)}} ] where (q = 1-p).

Verification of boundary cases:

  • (p = 0): (q = 1), (r = 2). Formula gives (\frac{0 + 1\cdot 2^n - 1\cdot 2^n}{2} = 0). The sequence is (0,1,\ldots,2^n-1) (no inversions).
  • (p = 1): (q = 0), (r = 2). Formula gives (\frac{1\cdot 4^n + 0 - 1\cdot 2^n}{2} = \frac{4^n-2^n}{2} = \binom{2^n}{2}). The sequence is (2^n-1,\ldots,0) (all pairs inverted).
  • (p = \frac12): (q = \frac12), (r = 1), (1+2pq = \frac32), (p(1+q) = q(1+p) = \frac34). Formula becomes [ E_n = \frac{\frac34(4^n - 1) + \frac34(1 - 2^n)}{3} = \frac{4^n - 2^{n+1} + 1}{4} = \frac{(2^n-1)^2}{4}, ] which matches the expected inversions for independent uniform (n)-bit integers.