TAOCP 3.4.1: Numerical Distributions
Section 3.4.1 exercises: 26/33 solved.
Section 3.4.1. Numerical Distributions
Exercises from TAOCP Volume 2 Section 3.4.1: 26/33 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | verified | 1m09s |
| 2 | [M16] | math-medium | verified | 1m26s |
| 3 | ▶ [14] | simple | verified | 1m34s |
| 4 | [M20] | math-medium | solved | 3m28s |
| 5 | ▶ [21] | medium | verified | 2m54s |
| 6 | [HM21] | hm-medium | verified | 1m41s |
| 7 | ▶ [**] | solved | 5m13s | |
| 8 | [M15] | math-simple | verified | 1m20s |
| 9 | [HM10] | hm-simple | solved | 2m06s |
| 10 | ▶ [HM24] | hm-medium | solved | 5m13s |
| 11 | ▶ [HM29] | hm-hard | - | - |
| 12 | [HM23] | hm-medium | - | - |
| 13 | [HM25] | hm-medium | verified | 1m41s |
| 14 | [M21] | math-medium | - | - |
| 15 | [HM21] | hm-medium | verified | 1m17s |
| 16 | ▶ [HM25] | hm-medium | verified | 4m35s |
| 17 | ▶ [M24] | math-medium | verified | 1m33s |
| 18 | [M24] | math-medium | verified | 4m33s |
| 19 | [**] | verified | 3m03s | |
| 20 | [M20] | math-medium | verified | 3m04s |
| 21 | [HM29] | hm-hard | solved | 4m46s |
| 22 | [HM40] | hm-project | verified | 1m35s |
| 23 | [HM25] | hm-medium | verified | 1m14s |
| 24 | [HM40] | hm-project | - | - |
| 25 | [M35] | math-hard | verified | 1m48s |
| 26 | [M18] | math-medium | verified | 3m28s |
| 27 | [22] | medium | verified | 1m46s |
| 28 | [HM35] | hm-hard | verified | 1m43s |
| 29 | [M20] | math-medium | verified | 1m31s |
| 30 | [M30] | math-hard | solved | 2m12s |
| 31 | [HM39] | hm-project | - | - |
| 32 | [HM30] | hm-hard | - | - |
| 33 | [**] | - | - |
TAOCP 3.4.1 Exercise 1
Let $U$ be a random variable uniformly distributed between 0 and 1.
TAOCP 3.4.1 Exercise 2
Let $U$ be a random variable uniformly distributed on $[0,1)$, and suppose that $mU$ is interpreted as a random integer between $0$ and $m-1$, namely $U_m = \lfloor mU \rfloor.$ Thus $\Pr{U_m = j} = 1...
TAOCP 3.4.1 Exercise 3
Suppose we have a uniform random variable $U$ between 0 and 1, represented in a computer word with $m$ possible discrete values, $0, 1, \ldots, m-1$, as in Section 3.
TAOCP 3.4.1 Exercise 4
The solution does not answer the exercise as stated.
TAOCP 3.4.1 Exercise 5
We are asked to generate a random variable $X$ with distribution function F(x) = p x + q x^2 + r x^3, \qquad 0 \le x \le 1, where $p \ge 0$, $q \ge 0$, $r \ge 0$, and $p + q + r = 1$.
TAOCP 3.4.1 Exercise 6
The algorithm generates two independent uniform deviates $U$ and $V$, each distributed on $[0,1]$, and rejects pairs for which $U^2 + V^2 \ge 1$.
TAOCP 3.4.1 Exercise 7
**Exercise 3.
TAOCP 3.4.1 Exercise 8
We are asked to show that the alias method, as described in equation (3) of Section 3.
TAOCP 3.4.1 Exercise 9
The proposed solution does **not** answer Exercise 3.
TAOCP 3.4.1 Exercise 10
Algorithm M is designed to generate a discrete random variable X \in \{x_0, x_1, \dots, x_{n-1}\}, \quad \Pr\{X = x_j\} = p_j \ge 0, \quad \sum_{j=0}^{n-1} p_j = 1 using a uniform deviate $U \in [0,1)...
TAOCP 3.4.1 Exercise 13
Let $X=(X_1,\ldots,X_n)^T,$ where the $X_i$ are independent normal deviates with mean $0$ and variance $1$.
TAOCP 3.4.1 Exercise 15
Let $S=X_1+X_2.$ Since $X_1$ and $X_2$ are independent, the distribution function of $S$ is Condition on the value of $X_2$.
TAOCP 3.4.1 Exercise 16
Let f(x)=\frac{x^{a-1}e^{-x}}{\Gamma(a)}, \qquad x>0,\qquad 0<a\le1, be the gamma density of order $a$.
TAOCP 3.4.1 Exercise 17
Let $X$ be a random variable representing the number of trials until the first success in a sequence of independent Bernoulli trials with success probability $p$, $0 < p \le 1$.
TAOCP 3.4.1 Exercise 18
We are asked to generate a random integer $N$ such that \Pr\{N=n\} = n p^2 (1-p)^{\,n-1}, \qquad n \ge 0, with particular interest in the case where $p$ is small.
TAOCP 3.4.1 Exercise 19
**Exercise 3.
TAOCP 3.4.1 Exercise 20
Let $N$ be the number of executions of step R1 before the algorithm terminates.
TAOCP 3.4.1 Exercise 21
Let the density to be sampled be proportional to e^{-x^{2}/2}, \qquad x\ge 0.
TAOCP 3.4.1 Exercise 22
Can the exact Poisson distribution for large $\mu$ be obtained by generating an appropriate normal deviate, converting it to an integer in some convenient way, and applying a (possibly complicated) co...
TAOCP 3.4.1 Exercise 23
We are asked to determine whether the two methods described produce a random quantity $X$ with the same distribution.
TAOCP 3.4.1 Exercise 25
Let E_t=X_1\mid\bigl(X_2\mathbin{\&}(X_3\mid(X_4\mathbin{\&}X_5)\cdots)\bigr) denote the nested expression.
TAOCP 3.4.1 Exercise 26
Let $N_1$ and $N_2$ be independent Poisson random variables with means $\mu_1$ and $\mu_2$, respectively, where $\mu_1 > \mu_2 \ge 0$.
TAOCP 3.4.1 Exercise 27
Let a subroutine $\operatorname{Bin}(m,\tfrac12)$ be available; it returns a random variable having the binomial distribution $(m,\tfrac12)$.
TAOCP 3.4.1 Exercise 28
Let \qquad a_1\ge \cdots \ge a_n>0.
TAOCP 3.4.1 Exercise 29
We want $X_1 \le X_2 \le \cdots \le X_n$ such that each $X_i$ lies in $[0,1]$ and the joint distribution is uniform over the simplex $0 \le X_1 \le X_2 \le \cdots \le X_n \le 1.$ Equivalently, we want...