TAOCP 3.5 Exercise 5

Section 3.5: What Is a Random Sequence?

Exercise 5. ▶ [HM22] Let $U_n = (2^{(9(n+1))/3}) \bmod 1$. What is $\Pr{U_n < \frac{1}{2}}$?

Verified: yes
Solve time: 1m11s

Solution

We are asked to determine $\Pr{U_n < \tfrac{1}{2}}$ for the sequence

$U_n = \bigl(2^{9(n+1)/3}\bigr) \bmod 1.$

First, observe that

$2^{9(n+1)/3} = 2^{3(n+1)} = 2^{3n+3} = 8 \cdot 2^{3n}.$

Hence we may write

$U_n = (8 \cdot 2^{3n}) \bmod 1.$

Since $(8 \cdot 2^{3n}) \bmod 1 = (2^{3n} \cdot 8) \bmod 1$, we can analyze the fractional part. Let ${x}$ denote the fractional part of $x$. Then

$U_n = {8 \cdot 2^{3n}}.$

Next, note that $2^{3n} = 8^n$, so

$U_n = {8 \cdot 8^n} = {8^{n+1}}.$

Therefore, the sequence simplifies to

$U_n = {8^{n+1}},$

where ${x}$ is the fractional part of $x$.

Now consider the binary expansion of powers of $2$. For any positive integer $m$, $2^m$ is an integer, so the fractional part of $2^m$ is zero. Therefore, $8^{n+1} = 2^{3(n+1)}$ is an integer for every $n$, so

$U_n = {8^{n+1}} = 0.$

Hence, for all $n \ge 0$, we have

$U_n = 0 < \frac{1}{2}.$

By Definition A in Section 3.5, $\Pr{U_n < \tfrac{1}{2}}$ is the limiting frequency of values of $n$ for which $U_n < \frac{1}{2}$. Since this is true for every $n$, the limiting frequency equals 1. Thus we conclude

$\Pr{U_n < \tfrac{1}{2}} = 1.$

This completes the proof.

∎

$$ \boxed{1} $$