Exercises

$\mathbb{E}[X] = 1(0.2) + 2(0.5) + 3(0.3) = 0.2 + 1.0 + 0.9 = 2.1$.

$\mathbb{E}[X^2] = 1^2(0.2) + 2^2(0.5) + 3^2(0.3) = 0.2 + 2.0 + 2.7 = 4.9$.

$\text{Var}(X) = 4.9 - 2.1^2 = 4.9 - 4.41 = 0.49$.

$\mathbb{E}[\mathbf{1}_A] = 1 \cdot \mathbb{P}(\mathbf{1}_A = 1) + 0 \cdot \mathbb{P}(\mathbf{1}_A = 0) = \mathbb{P}(A)$.

$H(X) = -\sum_{k=1}^{6} \frac{1}{6} \log_2 \frac{1}{6} = \log_2 6 \approx 2.585$ bits.

$\mathbb{P}(X > 4 \mid X > 2) = \mathbb{P}(X > 2) = (1 - 0.25)^2 = (0.75)^2 = 0.5625$.

$M_X(t) = \sum_{k=0}^{n} \binom{n}{k} (pe^t)^k (1-p)^{n-k} = [(1-p) + pe^t]^n$$

by the binomial theorem.

$(X - \mu)^2 \geq 0$ for all outcomes, so $\text{Var}(X) = \mathbb{E}[(X - \mu)^2] \geq 0$.

$\text{Var}(X) = 0$ iff $(X - \mu)^2 = 0$ a.s., i.e., $X = \mu$ a.s. $\blacksquare$

$\sum_{k=0}^{\infty} \frac{e^{-\lambda} \lambda^k}{k!} = e^{-\lambda} \sum_{k=0}^{\infty} \frac{\lambda^k}{k!} = e^{-\lambda} \cdot e^{\lambda} = 1. \quad \blacksquare$$

$X \sim \text{Geometric}(0.8)$.

$\mathbb{E}[X] = 1/0.8 = 1.25$ transmissions. $\text{Var}(X) = (1 - 0.8)/0.8^2 = 0.2/0.64 = 0.3125$.

Let $g(n) = \mathbb{P}(X > n)$. The memoryless property gives $g(m+n) = g(m) g(n)$ (since $g(m+n) = g(n) \cdot g(m)$ after conditioning). The only solution with $g(0) = 1$ and $g$ decreasing is $g(n) = q^n$ for $q = g(1) \in (0, 1)$.

$P(k) = g(k-1) - g(k) = q^{k-1} - q^k = q^{k-1}(1-q) = (1-p)^{k-1}p$, which is Geometric($p$) with $p = 1 - q$. $\blacksquare$

Let $q = 1 - p$. $$H(X) = -\sum_{k=1}^{\infty} q^{k-1}p\,[\log_2 p + (k-1)\log_2 q]$$ $$= -p\log_2 p \sum_{k=1}^{\infty} q^{k-1} - p\log_2 q \sum_{k=1}^{\infty}(k-1)q^{k-1}.$$

$\sum_{k=1}^{\infty} q^{k-1} = 1/(1-q) = 1/p$. $\sum_{k=1}^{\infty}(k-1)q^{k-1} = q/(1-q)^2 = q/p^2$.

$H(X) = -\log_2 p - \frac{q}{p}\log_2 q = \frac{-p\log_2 p - q\log_2 q}{p} = \frac{h_b(p)}{p} + \frac{\log_2(1/p) \cdot q}{p}.$$More compactly:$H(X) = \frac{-(1-p)\log_2(1-p) - p\log_2 p}{p}$.

$\mathbb{P}(X_n = k) = \binom{n}{k}\left(\frac{\lambda}{n}\right)^k\left(1 - \frac{\lambda}{n}\right)^{n-k}.$$

$= \frac{\lambda^k}{k!} \cdot \underbrace{\frac{n(n-1)\cdots(n-k+1)}{n^k}}_{\to 1} \cdot \underbrace{\left(1 - \frac{\lambda}{n}\right)^n}_{\to e^{-\lambda}} \cdot \underbrace{\left(1 - \frac{\lambda}{n}\right)^{-k}}_{\to 1}.$$Therefore$\mathbb{P}(X_n = k) \to \frac{e^{-\lambda}\lambda^k}{k!}$.$\blacksquare$

${M_X}_{X+Y}(t) = e^{\lambda(e^t - 1)} \cdot e^{\mu(e^t - 1)} = e^{(\lambda + \mu)(e^t - 1)}$.

This is the MGF of Poisson$(\lambda + \mu)$. Since the MGF uniquely determines the distribution, $X + Y \sim \text{Poisson}(\lambda + \mu)$. $\blacksquare$

The function $\phi(t) = -t\log_2 t$ is concave on $[0,1]$ (since $\phi''(t) = -1/(t\ln 2) < 0$). For each $x \in \mathcal{X}$:

$$\phi(\alpha p(x) + (1-\alpha)q(x)) \geq \alpha\phi(p(x)) + (1-\alpha)\phi(q(x)).$$

Summing over all $x \in \mathcal{X}$:

$$H(\alpha p + (1-\alpha)q) = \sum_x \phi(\alpha p(x) + (1-\alpha)q(x)) \geq \alpha \sum_x \phi(p(x)) + (1-\alpha)\sum_x \phi(q(x)) = \alpha H(p) + (1-\alpha)H(q). \quad \blacksquare$$

$\mathbb{E}[X_i] = n_1/n$ by symmetry (each draw is equally likely to be any item). So $\mathbb{E}[X] = \sum_{i=1}^r \mathbb{E}[X_i] = rn_1/n$.

$\mathbb{E}[X_i X_j] = \mathbb{P}(\text{draws } i,j \text{ both good}) = \frac{n_1(n_1-1)}{n(n-1)}$ for $i \neq j$.

$\text{Cov}(X_i, X_j) = \frac{n_1(n_1-1)}{n(n-1)} - \frac{n_1^2}{n^2} = -\frac{n_1(n - n_1)}{n^2(n-1)}$.

$\text{Var}(X) = r \cdot \text{Var}(X_i) + r(r-1) \cdot \text{Cov}(X_i, X_j)$

$= r \cdot \frac{n_1}{n}\cdot\frac{n-n_1}{n} + r(r-1)\cdot\left(-\frac{n_1(n-n_1)}{n^2(n-1)}\right)$

$= r\frac{n_1(n-n_1)}{n^2}\left(1 - \frac{r-1}{n-1}\right) = r\frac{n_1}{n}\frac{n-n_1}{n}\frac{n-r}{n-1}$. $\blacksquare$

Maximize $-\sum_{k=1}^{\infty} p(k)\log_2 p(k)$ subject to $\sum p(k) = 1$ and $\sum k\,p(k) = \mu$.

$$\mathcal{L} = -\sum p(k)\log_2 p(k) - \alpha\left(\sum p(k) - 1\right) - \beta\left(\sum kp(k) - \mu\right).$$

$\frac{\partial \mathcal{L}}{\partial p(k)} = -\log_2 p(k) - \frac{1}{\ln 2} - \alpha - \beta k = 0$,

so $p(k) = 2^{-(\alpha + \frac{1}{\ln 2} + \beta k)} = C \cdot r^k$ for constants $C, r$.

This is the geometric distribution with parameter $p = 1 - r$, where $r = (\mu - 1)/\mu$ (so that $\mathbb{E}[X] = 1/(1-r) = \mu$). The geometric distribution is the maximum-entropy distribution on the positive integers with a given mean. $\blacksquare$

$\lambda = np = 100 \times 0.02 = 2$. $\mathbb{P}(X \geq 5) = 1 - \sum_{k=0}^{4} \frac{e^{-2} 2^k}{k!}$.

$\sum_{k=0}^{4} e^{-2} 2^k/k! = e^{-2}(1 + 2 + 2 + 4/3 + 2/3) = e^{-2} \cdot 7 \approx 0.1353 \times 7 \approx 0.9473$.

$\mathbb{P}(X \geq 5) \approx 1 - 0.9473 = 0.0527$.

$M_X(t) = e^{-\lambda}\sum_{k=0}^{\infty} \frac{(\lambda e^t)^k}{k!} = e^{-\lambda} e^{\lambda e^t} = e^{\lambda(e^t - 1)}$.

$M_X'(t) = \lambda e^t \cdot e^{\lambda(e^t - 1)}$, so $M_X'(0) = \lambda$.

$M_X''(t) = (\lambda e^t + \lambda^2 e^{2t}) e^{\lambda(e^t - 1)}$, so $M_X''(0) = \lambda + \lambda^2$. Then $\text{Var}(X) = \lambda + \lambda^2 - \lambda^2 = \lambda$. $\blacksquare$

After collecting $i-1$ distinct types, the probability of getting a new type on the next purchase is $(n - i + 1)/n$. So $T_i \sim \text{Geometric}((n-i+1)/n)$.

$T = T_1 + T_2 + \cdots + T_n$, and $\mathbb{E}[T_i] = n/(n - i + 1)$.

$\mathbb{E}[T] = \sum_{i=1}^{n} \frac{n}{n-i+1} = n\sum_{k=1}^{n}\frac{1}{k} = nH_n \approx n\ln n + \gamma n,$$where$\gamma \approx 0.577$is the Euler-Mascheroni constant.$\blacksquare$

$\mathbb{E}[X] = 20 \times 0.3 = 6$. $\text{Var}(X) = 20 \times 0.3 \times 0.7 = 4.2$.

For large $\lambda$, $X \sim \text{Poisson}(\lambda)$ is approximately $\mathcal{N}(\lambda, \lambda)$. The differential entropy of a continuous Gaussian with variance $\sigma^2$ is $\frac{1}{2}\log_2(2\pi e \sigma^2)$.

For a discrete distribution concentrated on integers that approximates a continuous distribution, $H_{\text{discrete}} \approx h_{\text{continuous}} + \frac{1}{2}\log_2(2\pi e)/\ldots$

More precisely, for integer-valued RVs well-approximated by a Gaussian, $H(X) \approx \frac{1}{2}\log_2(2\pi e \lambda)$ for large $\lambda$. A rigorous derivation uses the entropy of a discretized Gaussian. $\blacksquare$