TAOCP 3.3.3 Exercise 20

Let $X_n$ be a linear congruential sequence X_{n+1} \equiv a X_n + c \pmod m, \quad 0 \le X_n < m, and define the iterates

taocpmathematicsalgorithmsvolume-1math-hard

Section 3.3.3: Theoretical Tests

Exercise 20. [M29] (U. Dieter.) Extend Theorem P by obtaining a formula for the probability that $X_n > X_{n+1} > X_{n+2}$, in terms of generalized Dedekind sums.

Exercises

In many cases, exact computations with integers are quite difficult to carry out, but we can attempt to study the probabilities that arise when we take the average over all real values of $x$ instead of restricting the calculation to integer values. Although these results are only approximate, they shed some light on the subject.

It is convenient to deal with numbers $U_n$ between zero and one; for linear congruential sequences, $U_n = X_n/m$, and we have $U_{n+1} = {aU_n + \theta}$, where $\theta = c/m$ and ${x}$ denotes $x \bmod 1$. For example, the formula for serial correlation now becomes

$$C = \left(\int_0^1 x{ax + \theta},dx - \left(\int_0^1 x,dx\right)^2\right) \bigg/ \left(\int_0^1 x^2,dx - \left(\int_0^1 x,dx\right)^2\right)$$

Verified: no
Solve time: 4m59s

Exercise 3.3.3.20, Fully Corrected Solution

Let $X_n$ be a linear congruential sequence

$$ X_{n+1} \equiv a X_n + c \pmod m, \quad 0 \le X_n < m, $$

and define the iterates

$$ s(x) = (a x + c) \bmod m, \qquad t(x) = s(s(x)) = a^2 x + (a+1)c \bmod m. $$

We seek the probability that

$$ X_n > X_{n+1} > X_{n+2} $$

over a full period of length $m$ in terms of generalized Dedekind sums.

Step 1. Indicator function decomposition

Define the indicator function for the event:

$$ 1_{{x > s(x) > t(x)}} = 1_{{x > s(x)}} \cdot 1_{{s(x) > t(x)}}. $$

From Theorem P, for a single-order inequality we have the sawtooth representation

$$ 1_{{x > s(x)}} = \frac{x - s(x)}{m} + \left(!\left(\frac{(a-1)x + c}{m}\right)!\right) + \frac{1}{2}, $$

$$ 1_{{s(x) > t(x)}} = \frac{s(x) - t(x)}{m} + \left(!\left(\frac{(a-1)s(x) + c}{m}\right)!\right) + \frac{1}{2}, $$

where

$$ \left(!\left(y\right)!\right) = y - \lfloor y \rfloor - \frac{1}{2}. $$

Hence, the number of states satisfying $x > s(x) > t(x)$ is

$$ N = \sum_{x=0}^{m-1} 1_{{x > s(x)}} \cdot 1_{{s(x) > t(x)}}. $$

Step 2. Expand the product

Let $b = a-1$. Substituting the sawtooth representations:

$$ \begin{aligned} N &= \sum_{x=0}^{m-1} \Biggl[ \frac{x - s(x)}{m} + \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr) + \frac{1}{2} \Biggr] \Biggl[ \frac{s(x) - t(x)}{m} + \Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr) + \frac{1}{2} \Biggr] \ &= \sum_{x=0}^{m-1} \Biggl[ \frac{(x - s(x))(s(x) - t(x))}{m^2} + \frac{x - s(x)}{m} \Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr) + \frac{s(x) - t(x)}{m} \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr) \ &\quad + \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr) \Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr) + \frac{1}{2}\frac{x - s(x)}{m} + \frac{1}{2}\frac{s(x) - t(x)}{m} \ &\quad + \frac{1}{2}\Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr) + \frac{1}{2}\Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr) + \frac{1}{4} \Biggr]. \end{aligned} $$

Step 3. Simplify linear and constant terms

Since $s(x)$ is a permutation modulo $m$, we have

$$ \sum_{x=0}^{m-1} (x - s(x)) = 0, \quad \sum_{x=0}^{m-1} (s(x) - t(x)) = 0. $$

Hence, the sums of the linear terms

$$ \sum_{x=0}^{m-1} \frac{(x - s(x))(s(x) - t(x))}{m^2},\quad \sum_{x=0}^{m-1} \frac{1}{2}\frac{x - s(x)}{m}, \quad \sum_{x=0}^{m-1} \frac{1}{2}\frac{s(x) - t(x)}{m} $$

all vanish. The constant term contributes

$$ \sum_{x=0}^{m-1} \frac{1}{4} = \frac{m}{4}. $$

Step 4. Quadratic sawtooth term

The quadratic sawtooth term is

$$ \sum_{x=0}^{m-1} \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr) \Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr) = \sum_{x=0}^{m-1} \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr) \Bigl(!\Bigl(\frac{a b x + a c}{m}\Bigr)!\Bigr), $$

since

$$ b s(x) + c = b(a x + c) + c = a b x + a c. $$

By the definition of the generalized Dedekind sum

$$ \sigma(h,k,c) = 12 \sum_{x=0}^{k-1} \Bigl(!\Bigl(\frac{x}{k}\Bigr)!\Bigr) \Bigl(!\Bigl(\frac{h x + c}{k}\Bigr)!\Bigr), $$

we have

$$ \sum_{x=0}^{m-1} \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr) \Bigl(!\Bigl(\frac{a b x + a c}{m}\Bigr)!\Bigr) = \frac{1}{12} \sigma(a b, m, a c). $$

Step 5. Mixed sums as generalized Dedekind sums

The remaining mixed sums are

$$ S_1 = \sum_{x=0}^{m-1} \frac{x - s(x)}{m} \Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr), \qquad S_2 = \sum_{x=0}^{m-1} \frac{s(x) - t(x)}{m} \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr), $$

with

$$ x - s(x) = -b x - c + m \left\lfloor \frac{a x + c}{m} \right\rfloor, \quad s(x) - t(x) = -b s(x) - c + m \left\lfloor \frac{a s(x) + c}{m} \right\rfloor. $$

Substituting, we write

$$ S_1 = \sum_{x=0}^{m-1} \left( -\frac{b x + c}{m} + \left\lfloor \frac{a x + c}{m} \right\rfloor \right) \Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr) = - \sum_{x=0}^{m-1} \frac{b x + c}{m} \Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr) + \sum_{x=0}^{m-1} \left\lfloor \frac{a x + c}{m} \right\rfloor \Bigl(!\Bigl(\frac{b s(x) + c}{m}\Bigr)!\Bigr). $$

Similarly,

$$ S_2 = - \sum_{x=0}^{m-1} \frac{b s(x) + c}{m} \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr) + \sum_{x=0}^{m-1} \left\lfloor \frac{a s(x) + c}{m} \right\rfloor \Bigl(!\Bigl(\frac{b x + c}{m}\Bigr)!\Bigr). $$

Each sum of the form $\sum x ((h x + q)/m)$ or $\sum \lfloor (h x + q)/m \rfloor ((s x + t)/m)$ is expressible as