TAOCP 3.5: What Is a Random Sequence?
Section 3.5 exercises: 43/44 solved.
Section 3.5. What Is a Random Sequence?
Exercises from TAOCP Volume 2 Section 3.5: 43/44 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | verified | 1m12s |
| 2 | [10] | simple | verified | 1m12s |
| 3 | [M25] | math-medium | verified | 1m13s |
| 4 | ▶ [HM14] | hm-simple | verified | 1m15s |
| 5 | ▶ [HM22] | hm-medium | verified | 1m11s |
| 6 | [HM23] | hm-medium | verified | 4m01s |
| 7 | [HM27] | hm-hard | verified | 1m33s |
| 8 | [M15] | math-simple | verified | 1m24s |
| 9 | [HM20] | hm-medium | verified | 1m22s |
| 10 | ▶ [HM22] | hm-medium | solved | 3m46s |
| 11 | [M10] | math-simple | solved | 3m43s |
| 12 | [HM20] | hm-medium | verified | 1m07s |
| 13 | [HM27] | hm-hard | verified | 2m44s |
| 14 | [HM25] | hm-medium | verified | 3m40s |
| 15 | ▶ [HM30] | hm-hard | verified | 1m33s |
| 16 | [HM38] | hm-project | verified | 1m11s |
| 17 | [HM50] | hm-research | verified | 1m13s |
| 18 | ▶ [HM22] | hm-medium | solved | 3m44s |
| 19 | [HM35] | hm-hard | verified | 1m27s |
| 20 | ▶ [**] | solved | 4m18s | |
| 21 | [**] | verified | 1m15s | |
| 22 | ▶ [**] | verified | 1m01s | |
| 23 | [**] | verified | 3m44s | |
| 24 | ▶ [**] | solved | 3m44s | |
| 25 | [**] | verified | 1m02s | |
| 26 | [**] | verified | 3m06s | |
| 27 | [**] | solved | 3m12s | |
| 28 | ▶ [**] | verified | 1m14s | |
| 29 | [**] | solved | 3m34s | |
| 30 | ▶ [**] | solved | 1m57s | |
| 31 | [**] | solved | 4m25s | |
| 32 | [**] | verified | 2m24s | |
| 33 | [**] | - | - | |
| 34 | ▶ [**] | verified | 2m24s | |
| 35 | ▶ [HM35] | hm-hard | solved | 3m14s |
| 36 | [HM30] | hm-hard | verified | 3m39s |
| 37 | [M37] | math-project | verified | 1m15s |
| 38 | [M49] | math-research | solved | 3m20s |
| 39 | [HM45] | hm-project | verified | 2m45s |
| 40 | [M28] | math-hard | solved | 2m01s |
| 41 | [M21] | math-medium | verified | 2m37s |
| 42 | ▶ [M28] | math-hard | solved | 2m15s |
| 43 | [26] | hard | verified | 1m48s |
| 44 | ▶ [16] | medium | verified | 2m22s |
TAOCP 3.5 Exercise 1
No.
TAOCP 3.5 Exercise 2
The sequence has period $4$: $0,0,1,1,0,0,1,1,\ldots$ To test 2-distribution, examine the successive pairs: $00,\ 01,\ 11,\ 10,\ 00,\ 01,\ 11,\ 10,\ldots$ Each of the four binary numbers $00$, $01$, $...
TAOCP 3.5 Exercise 3
We are asked to construct a periodic ternary sequence that is 3-distributed.
TAOCP 3.5 Exercise 4
Let A(n)=S(n)\text{ and }T(n),\qquad B(n)=S(n)\text{ or }T(n).
TAOCP 3.5 Exercise 5
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...
TAOCP 3.5 Exercise 6
Let $S_1(n), S_2(n), \dots$ be an infinite sequence of statements about mutually disjoint events.
TAOCP 3.5 Exercise 7
For each pair $(i,j)$, let $A_{ij}=\{\,n\ge 0 : S_{ij}(n)\text{ is true}\,\}.$ The hypothesis states that for every $n>0$ there is exactly one pair $(i,j)$ such that $S_{ij}(n)$ is true.
TAOCP 3.5 Exercise 8
Assume that the sequence $\langle U_n\rangle$ is $(m,k)$-distributed, and let $d$ be a divisor of $m$.
TAOCP 3.5 Exercise 9
Lemma E states that if \lim_{n\to\infty}\frac1n\sum_{j=1}^{n}y_{jn}=a, \qquad \lim_{n\to\infty}\frac1n\sum_{j=1}^{n}y_{jn}^{\,2}=a^2,
TAOCP 3.5 Exercise 10
In TAOCP §3.
TAOCP 3.5 Exercise 11
**Exercise 3.
TAOCP 3.5 Exercise 12
Let M_n=\max(U_n,U_{n+1},\ldots,U_{n+k-1}).
TAOCP 3.5 Exercise 13
Let I=[\alpha,\beta), \qquad p=\beta-\alpha .
TAOCP 3.5 Exercise 14
Let $\{U_n\}_{n\ge0}$ be an $\infty$-distributed sequence and define the stopping times $f(n)$ recursively by $f(0)=0$ and, for $n\ge1$, f(n) = \min\{ m > f(n-1) : U_{m-1} > U_m \}.
TAOCP 3.5 Exercise 15
Let $L_n=f(n)-f(n-1).$ The definition of $f(n)$ implies that, beginning immediately after position $f(n-1)$, we inspect successive bits of the binary sequence until both symbols $0$ and $1$ have appea...
TAOCP 3.5 Exercise 16
Let $b \ge 2$ be an integer representing the number of kinds of coupons.
TAOCP 3.5 Exercise 17
Let $r = p/q$ be a rational number with $\gcd(p,q) = 1$, $q \ge 1$, and consider the sequence $U_n = r^n \bmod 1, \quad n = 0, 1, 2, \ldots,$ viewed as a $[0,1)$ sequence.
TAOCP 3.5 Exercise 18
We are asked to prove: > If $(U_n)$ is $k$-distributed, so is the sequence > > > >
TAOCP 3.5 Exercise 19
Definition R4 asserts that for every positive integer $s$, every residue class $t$ with $0 \le t < s$, and every fixed choice of preceding terms, the subsequence U_t,\ U_{t+s},\ U_{t+2s},\ \ldots is $...
TAOCP 3.5 Exercise 20
Let l_n^{(1)}\ge l_n^{(2)}\ge \cdots \ge l_n^{(n)} denote the lengths of the $n$ intervals determined by the first $n$ points $U_0,\ldots,U_{n-1}$, and define
TAOCP 3.5 Exercise 21
(a) No.
TAOCP 3.5 Exercise 22
Suppose $(U_n)$ is $k$-distributed.
TAOCP 3.5 Exercise 23
Let $(U_n)$ be a $[0,1)$ sequence.
TAOCP 3.5 Exercise 24
Let $(U_n)$ be a sequence in $[0,1)$.
TAOCP 3.5 Exercise 25
Let $C_k(n)=\frac1n\sum_{0\le j<n}\left(U_j-\frac12\right)\left(U_{j+k}-\frac12\right).$ Since $(U_n)$ is a ${0,1}$ sequence, $U_j^2=U_j$, and =U_jU_{j+k}-\frac12(U_j+U_{j+k})+\frac14.
TAOCP 3.5 Exercise 26
Let A=G=\{(x,y)\in[0,1)^2:x-\tfrac12\le y\le x \text{ or } x+\tfrac12\le y\}.
TAOCP 3.5 Exercise 27
**Exercise 3.
TAOCP 3.5 Exercise 28
Let $(X_n)$ be the periodic binary sequence (11), $0001\,0001\,1101\,1101\,0001\,0001\,1101\,1101\cdots,$ which is 3-distributed.
TAOCP 3.5 Exercise 29
**Exercise 3.
TAOCP 3.5 Exercise 30
Let $k$ be a positive integer.
TAOCP 3.5 Exercise 31
Let \nu_n=\#\{\,0\le j<n : U_j<\tfrac12\,\}.
TAOCP 3.5 Exercise 32
**Solution.
TAOCP 3.5 Exercise 34
**Exercise 3.
TAOCP 3.5 Exercise 35
Let $(X_n)$ be an R5-random binary sequence, and let $(a_n)$ be any computable increasing sequence of integers as in Definition R4.
TAOCP 3.5 Exercise 36
Let s_n=\frac{n(n+1)}2 .
TAOCP 3.5 Exercise 37
We are asked to construct a sequence that satisfies **Definition R4** but fails **Definition R5**.
TAOCP 3.5 Exercise 38
Let $A$ be a set of algorithms in the sense of Definition R6, and let $|A|=m$.
TAOCP 3.5 Exercise 39
Let z_n(u)=\#\{\,j\le n:0\le U_j<u\,\}, where $U_0,U_1,\ldots\in[0,1)$.
TAOCP 3.5 Exercise 40
Complete the proof of Lemma P1.
TAOCP 3.5 Exercise 41
Let $A$ be an algorithm that, given a cyclic binary sequence B_1,B_2,\ldots,B_N, attempts to predict each bit from the preceding bits.
TAOCP 3.5 Exercise 42
Let $X_1, \ldots, X_n$ be random variables with mean $\mu = \mathrm{E},X_j$ and variance $\sigma^2 = \mathrm{E},X_j^2 - (\mathrm{E},X_j)^2$, for $1 \le j \le n$.
TAOCP 3.5 Exercise 43
Let Theorem P be the result asserting that a prediction algorithm for the output of the Blum-Blum-Shub generator can be converted into a factoring algorithm for a **random** $R$-bit Blum integer $M$.
TAOCP 3.5 Exercise 44
Let the original table be an infinite sequence of digits x_1,x_2,x_3,\ldots that is valid in the usual sense: Every block of $k$ digits occurs with limiting frequency $10^{-k}$.