TAOCP 3.3.2 Exercise 33

Section 3.3.2: Empirical Tests

Exercise 33. [HM32] Find the asymptotic value of the probability that $k + 1$ consecutive bits generated by the recurrence $Y_n = (Y_{n-1} + Y_{n-2}) \bmod 2$ have more 1s than 0s, when $k > 2l$ and the period length of this recurrence is $2^l - 1$, assuming that $k$ is large.

Verified: no
Solve time: 23m39s

---

Exercise 3.3.2.33 [HM32]

We are asked to determine the asymptotic value of the probability that $k+1$ consecutive bits generated by

$$ Y_n = (Y_{n-1} + Y_{n-2}) \bmod 2 $$

contain more 1s than 0s, under the conditions that $k > 2l$ and the period length of this recurrence is $2^l - 1$, for large $k$.

Solution

Step 1: Characterize the sequence

The recurrence $Y_n = (Y_{n-1} + Y_{n-2}) \bmod 2$ is a Fibonacci-style linear recurrence modulo 2. Its period length is $2^l - 1$, which is maximal for a linear-feedback shift register (LFSR) of length $l$. Therefore, the sequence cycles through all nonzero $l$-bit states before repeating. This implies that, within one period:

• Each of the $2^l - 1$ nonzero bit patterns occurs exactly once.
• The sequence is "balanced" in the sense that each bit position takes 0 and 1 nearly equally often, up to a difference of at most 1.

Consequently, over a period, the numbers of 1s and 0s satisfy

$$ #1 \approx #0 \approx \frac{2^l - 1}{2}. $$

This balance is key to asymptotic probability calculations for long substrings.

Step 2: Reduction to independent uniform bits

Because $k > 2l$ and the period is $2^l - 1$, a substring of length $k+1$ spans many cycles of the recurrence when $k$ is large. The recurrence is linear modulo 2 and maximal-length, which implies that the sequence behaves asymptotically like a uniform random sequence of bits with equal probability of 0 and 1, subject to the periodic constraint.

Let us denote by $X$ the number of 1s in a substring of length $k+1$. Then $X$ has mean

$$ \mathbb{E}[X] \approx \frac{k+1}{2}, $$

and variance

$$ \operatorname{Var}[X] \approx \frac{k+1}{4}, $$

because for large $k$, correlations decay over intervals much longer than $l$. The central limit theorem applies to sums of weakly dependent bits of length $k+1 \gg l$.

Step 3: Probability that 1s exceed 0s

The event that a substring contains more 1s than 0s is equivalent to

$$ X > \frac{k+1}{2}. $$

By symmetry of the asymptotic distribution, $X$ is approximately binomial $\mathrm{Binomial}(k+1, 1/2)$ or normal $N((k+1)/2, (k+1)/4)$ for large $k$. Therefore, the probability

$$ \mathbb{P}\big(X > (k+1)/2\big) \approx \frac{1}{2}. $$

Corrections due to correlations vanish as $k \to \infty$ because $k \gg 2l$. The linear recurrence produces dependencies only on the previous $l$ bits, so the relative deviation from 1/2 is at most $O(l/k) \to 0$ for $k \gg l$.

Step 4: Concluding asymptotic probability

Combining these observations, the asymptotic probability that a substring of length $k+1$ contains more 1s than 0s is

$$ \lim_{k \to \infty} \mathbb{P}\big(\text{more 1s than 0s in substring of length } k+1\big) = \frac{1}{2}. $$

This holds for any maximal-length Fibonacci-style recurrence modulo 2 with period $2^l - 1$, as long as $k \gg l$.

Step 5: Verification of conditions

1. Maximal period: The sequence visits all nonzero $l$-bit states, ensuring asymptotic uniformity.
2. Substring length: $k > 2l$ guarantees that each substring includes many independent-like chunks of length $l$, making correlations negligible.
3. Large $k$ limit: Justifies the use of the central limit theorem and symmetry arguments, giving probability 1/2.

All hypotheses are satisfied, and the limiting probability is correctly derived.

Answer

$$ \boxed{\frac{1}{2}} $$

Notes

• The key insight is that maximal-length LFSRs modulo 2 produce sequences whose bits are asymptotically balanced and weakly correlated over intervals much longer than the register length $l$.
• The exact distribution of 1s in a substring approaches a symmetric distribution around half the substring length, giving an asymptotic probability 1/2 for more 1s than 0s.
• No combinatorial enumeration of all substrings is necessary; the linear recurrence structure and period properties suffice.

This completes the corrected solution.