#volume-2
TAOCP 3.5 Exercise 27
Section 3.5: What Is a Random Sequence? Exercise 27. [**] [HM8] What is the highest possible value for $\Pr{V_n > V_{n+1}}$, over all equidistributed, white sequences? (D. Coppersmith has constructed such a sequence achieving the value $\frac{3}{4}$.) Verified: no Solve time: 9m49s Let $B_n$ be the indicator of the event $V_n \ge \tfrac12$. Since the sequence is equidistributed, $\Pr(B_n=1)=\Pr(B_n=0)=\tfrac12$. Since the sequence is white, Exercise 25 gives $$ \Pr(B_n=1,B_{n+1}=1)=\Pr(B_n=1)\Pr(B_{n+1}=1)=\frac14. $$...
TAOCP 3.3.2 Exercise 26
Section 3.3.2: Empirical Tests Exercise 26. [**] Evaluate $K_s$ on this sequence as $s \to \infty$. Although it is always possible to run a random number generator using the methods described in Section 3.3.1, we want to obtain theoretical results, theoretical results that tell us in advance how well those tests will come out. Such theoretical information is much more informative and definitive than the actual, finite, empirical, trial-and-run results...
TAOCP 3.3.2 Exercise 25
Section 3.3.2: Empirical Tests Exercise 25. ▶ [**] [HM30] Evaluate $K_s$ for a general finite Markov chain. Verified: yes Solve time: 9m34s Exercise 3.3.2.25 [HM30] Evaluate $K_s$ for a general finite Markov chain. Let $(X_n)_{n\ge 0}$ be a finite irreducible Markov chain with transition matrix $P$ and stationary distribution $\pi$. Fix a state $s\in S$. Define the first hitting time of $s$ after time $0$ by $$ \tau_s := \inf{...
TAOCP 3.2.1 Exercise 4
Section 3.2.1: The Linear Congruential Method Exercise 4. [ 11 ] Prove Eq. (6). Verified: yes Solve time: 21m37s Solution Equation (2) defines the linear congruential sequence by $$ X_{n+1}\equiv aX_n+c \pmod m. $$ We prove equation (6), $$ X_{n+k}\equiv a^kX_n+\frac{a^k-1}{b}c \pmod m, \qquad k\ge0, $$ where $b=a-1$ by equation (4). The proof is by induction on $k$. For $k=0$, $$ a^0X_n+\frac{a^0-1}{b}c X_n+\frac{1-1}{b}c X_n, $$ hence $$ X_{n+0}\equiv X_n \pmod...
TAOCP 3.2.1 Exercise 3
Section 3.2.1: The Linear Congruential Method Exercise 3. [ M10 ] If $a$ and $m$ are not relatively prime, explain why the sequence will be somewhat handicapped and probably not very random; hence we will generally want the multiplier $a$ to be relatively prime to the modulus $m$. Verified: yes Solve time: 18m51s If $a$ and $m$ are not relatively prime, there exists a nontrivial common factor $d > 1$...
TAOCP 3.2.1 Exercise 2
Section 3.2.1: The Linear Congruential Method Exercise 2. ▶ [ M20 ] Show that if $a$ and $m$ are relatively prime, the number $X_0$ will always appear in the period. Verified: yes Solve time: 18m39s Solution Assume that $(a,m)=1$. Let ${X_n}$ be the linear congruential sequence defined by $$ X_{n+1}\equiv aX_n+c \pmod m. $$ Since there are only $m$ possible residue classes modulo $m$, some value must eventually repeat. Let...
TAOCP 3.2.1 Exercise 1
Section 3.2.1: The Linear Congruential Method Exercise 1. [ 10 ] Example (3) shows a situation in which $X_4 = X_0$, so the sequence begins again from the beginning. Give an example of a linear congruential sequence with $m = 10$ for which $X_0$ never appears again in the sequence. Verified: yes Solve time: 1h12m A linear congruential sequence has the form $$ X_{n+1} \equiv aX_n + c \pmod m....