Exercises

$\gamma = 10^{5/10} = 3.162$.

$$C = \log_2(1 + 3.162) = \log_2(4.162) \approx 2.057 \text{ bits/use}.$$

$V = 3.162 \cdot \frac{2 + 3.162}{(1 + 3.162)^2} \cdot (1.4427)^2 = 3.162 \cdot \frac{5.162}{17.31} \cdot 2.082 \approx 3.162 \cdot 0.2982 \cdot 2.082 \approx 1.963 \text{ bits}^2\text{/use}.$$

$R^* \approx 2.057 - \sqrt{\frac{1.963}{200}} \cdot 3.090 = 2.057 - \sqrt{0.009815} \cdot 3.090 = 2.057 - 0.09907 \cdot 3.090 \approx 2.057 - 0.306 = 1.751 \text{ bits/use}.$$

$\frac{R^*}{C} = \frac{1.751}{2.057} \approx 85.1\%.$$At$n = 200$and$\varepsilon = 10^{-3}$, we lose about 15% of capacity.

$N_{\mathrm{sym}} = \left\lfloor \frac{1000}{33.3} \right\rfloor = 30 \text{ OFDM symbols}.$$

Overhead: alignment (2) + gNB processing (3) + UE processing (5) $= 10$ symbols.

$$N_{\mathrm{data}} = 30 - 10 = 20 \text{ OFDM symbols}.$$

$N_{\mathrm{RE}} = 20 \times 1100 = 22{,}000 \text{ resource elements}.$$This gives the maximum blocklength$n = 22{,}000$ channel uses for data, which is actually generous for URLLC. In practice, URLLC uses fewer symbols (mini-slots of 2--7 symbols) to reduce the latency budget consumed by alignment.

Using $\bar{\Delta} = 1/\lambda + 1/(\mu - \lambda)$ with $\mu = 2$:

Among the given values, $\lambda = 1.0$ gives the lowest AoI ($\bar{\Delta} = 2.0$ s). The theoretical optimal is $\lambda^* = 1.061$, giving $\bar{\Delta}^* = 1/1.061 + 1/0.939 \approx 0.943 + 1.065 = 2.008$ s.

Note: $\lambda = 1.0$ and $\lambda = 1.5$ give symmetric AoI values because $1/\lambda + 1/(\mu - \lambda)$ is a convex function with minimum near $\lambda = 1$.

$K_a = 0.02 \times 2000 = 40.$$

$L_p = \Omega\!\left(40 \cdot \log_2\!\left(\frac{2000}{40}\right)\right) = \Omega(40 \cdot \log_2(50)) = \Omega(40 \cdot 5.644) = \Omega(226).$$With a practical constant$C_0 \approx 2$:$L_p \approx 452$.

$\text{Pilot fraction} = \frac{L_p}{T_c} = \frac{452}{300} = 1.51.$$This exceeds the coherence interval. Either we need more receive antennas (massive MIMO) to reduce$L_p$, or we must accept a smaller$C_0$with reduced detection reliability. With$M = 64$antennas and a$\sqrt{M} = 8$effective gain:$L_p \approx 452/8 = 57$symbols, or$57/300 = 19%$ overhead.

For uniform input, the information density $i(X; Y)$ takes value $\log_2(2(1-p)) = 1 + \log_2(1-p)$ when $Y = X$ (probability $1-p$), and $\log_2(2p) = 1 + \log_2 p$ when $Y \neq X$ (probability $p$).

The mean is $C = 1 - H_b(p)$ and the variance is

$$V = (1-p)\bigl(\log_2(2(1-p)) - C\bigr)^2 + p\bigl(\log_2(2p) - C\bigr)^2.$$

Let $a = \log_2(2(1-p))$ and $b = \log_2(2p)$. Then $C = (1-p)a + pb$.

$$V = (1-p)(a - C)^2 + p(b - C)^2 = (1-p)(a - (1-p)a - pb)^2 + p(b - (1-p)a - pb)^2$$ $$= (1-p)\bigl(p(a-b)\bigr)^2 + p\bigl((1-p)(b-a)\bigr)^2 = p(1-p)(a-b)^2\bigl[p + (1-p)\bigr]$$ $$= p(1-p)(a-b)^2 = p(1-p)\left[\log_2\frac{1-p}{p}\right]^2.$$

For $p = 0.11$: $C = 1 - H_b(0.11) \approx 1 - 0.500 = 0.500$ bits (using $H_b(0.11) \approx 0.500$).

$V = 0.11 \times 0.89 \times [\log_2(0.89/0.11)]^2 = 0.0979 \times [\log_2(8.09)]^2 = 0.0979 \times (3.016)^2 = 0.0979 \times 9.096 \approx 0.891$.

With $Q^{-1}(10^{-4}) \approx 3.719$:

$$R^* \approx 0.500 - \sqrt{\frac{0.891}{500}} \cdot 3.719 = 0.500 - 0.04222 \cdot 3.719 \approx 0.500 - 0.157 = 0.343 \text{ bits/use}.$$

$\gamma_{\mathrm{Sh}} = 2^1 - 1 = 1 \quad (0 \text{ dB}).$$

We need $1 = \log_2(1+\gamma) - \sqrt{V(\gamma)/256} \cdot Q^{-1}(10^{-5})$, where $Q^{-1}(10^{-5}) \approx 4.265$.

Trial $\gamma = 2$ (3 dB): $C = \log_2(3) = 1.585$, $V = 2 \cdot 4/(9) \cdot 2.082 = 1.851$. $R^* = 1.585 - \sqrt{1.851/256} \cdot 4.265 = 1.585 - 0.085 \cdot 4.265 = 1.585 - 0.363 = 1.222$. Too high.

Trial $\gamma = 1.5$ (1.76 dB): $C = \log_2(2.5) = 1.322$, $V = 1.5 \cdot 3.5/6.25 \cdot 2.082 = 1.749$. $R^* = 1.322 - \sqrt{1.749/256} \cdot 4.265 = 1.322 - 0.0827 \cdot 4.265 = 1.322 - 0.353 = 0.969$. Slightly low.

Trial $\gamma = 1.55$ (1.90 dB): $C \approx 1.344$, $V \approx 1.765$. $R^* \approx 1.344 - 0.0830 \cdot 4.265 \approx 1.344 - 0.354 = 0.990$. Close.

Trial $\gamma = 1.58$ (1.99 dB): $C \approx 1.367$, $V \approx 1.773$. $R^* \approx 1.367 - 0.0832 \cdot 4.265 \approx 1.012$. Close to 1.

So $\gamma_{\mathrm{min}} \approx 1.57$ or about 1.96 dB.

$\Delta_{\text{SNR}} = 10\log_{10}(1.57) - 10\log_{10}(1.0) \approx 1.96 - 0 = 1.96 \text{ dB}.$$The finite blocklength penalty at$n = 256$and$\varepsilon = 10^{-5}$ is approximately 2 dB of additional SNR compared to Shannon.

$\bar{d} = \Lambda'(1) = 0.5 \cdot 2 + 0.28 \cdot 3 + 0.22 \cdot 8 = 1.0 + 0.84 + 1.76 = 3.6 \text{ replicas/user}.$$

Slotted ALOHA throughput: $S_{\mathrm{ALOHA}} = 1/e \approx 0.368$ packets/slot.

IRSA throughput: $S_{\mathrm{IRSA}} = G^* = 0.938$ packets/slot.

Improvement factor: $0.938 / 0.368 \approx 2.55\times$.

Each successfully decoded user contributes $B = 100$ bits. At load $G^*$, the throughput is $G^*$ users per slot:

$$\eta = G^* \cdot B = 0.938 \times 100 = 93.8 \text{ bits/slot}.$$

However, each user transmits $\bar{d} = 3.6$ replicas, so the total resource consumption is $G^* \cdot \bar{d} = 3.38$ transmissions per slot. The net spectral efficiency per transmission is $100 / 3.6 = 27.8$ bits per replica.

The mean waiting time in M/D/1 is (from Pollaczek-Khinchine with $\mathbb{E}[S^2] = 1/\mu^2$, $\mathbb{E}[S] = 1/\mu$):

$$\mathbb{E}[W] = \frac{\lambda \mathbb{E}[S^2]}{2(1-\rho)} = \frac{\lambda/\mu^2}{2(1-\rho)} = \frac{\rho}{2\mu(1-\rho)}.$$

The system time is $T' = W + D$:

$$\mathbb{E}[T'] = \frac{\rho}{2\mu(1-\rho)} + \frac{1}{\mu}.$$

For Poisson arrivals, inter-arrival times are independent of system times, so $\mathbb{E}[YT'] = \mathbb{E}[Y]\mathbb{E}[T']$.

$$\bar{\Delta} = \frac{\mathbb{E}[Y^2]}{2\mathbb{E}[Y]} + \frac{\mathbb{E}[YT']}{\mathbb{E}[Y]} = \frac{1}{\lambda} + \mathbb{E}[T'] = \frac{1}{\lambda} + \frac{1}{\mu} + \frac{\rho}{2\mu(1-\rho)}.$$

Substituting $\lambda = \mu\rho$:

$$\bar{\Delta} = \frac{1}{\mu\rho} + \frac{1}{\mu} + \frac{\rho}{2\mu(1-\rho)} = \frac{1}{\mu}\left(\frac{1}{\rho} + 1 + \frac{\rho}{2(1-\rho)}\right).$$

M/D/1: $\bar{\Delta} = \frac{1}{\mu}(2 + 1 + 0.5) = 3.5/\mu$.

M/M/1: $\bar{\Delta} = \frac{1}{\mu}(1 + 2 + 0.5) = 3.5/\mu$.

Wait --- let us recheck. M/M/1: $\bar{\Delta} = \frac{1}{\mu}(1 + 1/\rho + \rho^2/(1-\rho)) = \frac{1}{\mu}(1 + 2 + 0.5) = 3.5/\mu$.

M/D/1: $\bar{\Delta} = \frac{1}{\mu}(1 + 2 + 0.25) = 3.25/\mu$.

Actually $\rho/(2(1-\rho)) = 0.5/(2 \cdot 0.5) = 0.5$. And $\rho^2/(1-\rho) = 0.25/0.5 = 0.5$.

Both give $3.5/\mu$? No: M/D/1 coefficient: $\rho/(2(1-\rho)) = 0.5/1 = 0.5$. M/M/1 coefficient: $\rho^2/(1-\rho) = 0.25/0.5 = 0.5$.

Both equal 0.5 at $\rho = 0.5$. Try $\rho = 0.8$: M/D/1: $0.8/(2 \cdot 0.2) = 2.0$. M/M/1: $0.64/0.2 = 3.2$.

At $\rho = 0.8$: M/D/1: $(1 + 1.25 + 2.0)/\mu = 4.25/\mu$. M/M/1: $(1 + 1.25 + 3.2)/\mu = 5.45/\mu$.

The M/D/1 advantage grows with $\rho$, as expected.

The ML detector for device $k$ is the likelihood ratio test:

$$\frac{p(\mathbf{Y} | k \text{ active})}{p(\mathbf{Y} | k \text{ inactive})} \underset{\mathcal{H}_0}{\overset{\mathcal{H}_1}{\gtrless}} \gamma.$$

In the Gaussian model, this reduces to comparing the energy in the projection of $\mathbf{Y}$ onto $\mathbf{a}_k$:

$$\hat{\mathbf{x}}_k = \frac{\mathbf{a}_k^H \mathbf{Y}}{\|\mathbf{a}_k\|^2}.$$

The test becomes $\|\hat{\mathbf{x}}_k\|^2 \gtrless \gamma_{\mathrm{th}}$.

Under $\mathcal{H}_0$ (device $k$ inactive), the contribution of device $k$ to $\mathbf{Y}$ is zero. The projection $\hat{x}_k = \mathbf{a}_k^H \mathbf{w} / \|\mathbf{a}_k\|^2$ is a linear combination of complex Gaussian noise:

$$\hat{x}_k \sim \mathcal{CN}(0, \sigma^2 / \|\mathbf{a}_k\|^2).$$

Thus $|\hat{x}_k|^2 / (\sigma^2/\|\mathbf{a}_k\|^2) \sim \mathrm{Exp}(1)$ (chi-squared with 2 DOF divided by 2).

The false alarm probability is

$$P_{\mathrm{FA}} = \Pr[|\hat{x}_k|^2 > \gamma_{\mathrm{th}}] = \exp\!\left(-\frac{\gamma_{\mathrm{th}} \|\mathbf{a}_k\|^2}{\sigma^2}\right).$$

For normalised pilots ($\|\mathbf{a}_k\|^2 = L_p$): $P_{\mathrm{FA}} = \exp(-\gamma_{\mathrm{th}} L_p / \sigma^2)$.

$\bar{A}^{\mathrm{peak}} = \mathbb{E}[Y + T'] = \mathbb{E}[Y] + \mathbb{E}[T'] = 1/\lambda + 1/(\mu - \lambda)$, using $Y \sim \mathrm{Exp}(\lambda)$ and $T' \sim \mathrm{Exp}(\mu - \lambda)$.

$\frac{d}{d\lambda}\bar{A}^{\mathrm{peak}} = -\frac{1}{\lambda^2} + \frac{1}{(\mu-\lambda)^2} = 0KATEXPLACEHOLDER0END\implies \lambda^2 = (\mu - \lambda)^2 \implies \lambda = \mu - \lambda \implies \lambda^* = \mu/2.$$The minimum PAoI is$\bar{A}^{\mathrm{peak}*} = 2/\mu + 2/\mu = 4/\mu$.

We showed $\bar{\Delta} = 1/\lambda + 1/(\mu-\lambda) = \bar{A}^{\mathrm{peak}}$.

This is a special property of the M/M/1 queue. For M/D/1 or D/M/1, $\bar{A}^{\mathrm{peak}} > \bar{\Delta}$ in general.

Intuition: the memoryless property of the exponential distribution means that the age process has no "memory" of past drops. The average height of the sawtooth at any point equals the average of the peak, because the linear growth between peaks is symmetric in a statistical sense for exponential inter-arrivals.

For the BSC with uniform input, the output distribution is $Y \sim \mathrm{Bernoulli}(1/2)$ (each output bit is equally likely to be 0 or 1, regardless of the input). Since the meta-converse seeks the $Q_{Y^n}$ that maximises the bound, and $P_Y = \mathrm{Bernoulli}(1/2)$ makes the likelihood ratio $P_{Y^n|X^n}/Q_{Y^n}$ depend only on the Hamming distance between $X^n$ and $Y^n$, this is the natural choice.

With $Q_{Y^n}(y^n) = 2^{-n}$ and $P_{Y^n|X^n}(y^n|x^n) = p^{d_H}(1-p)^{n-d_H}$ where $d_H = d_H(x^n, y^n)$:

$$\min(P_{Y^n|X^n}, Q_{Y^n}) = \begin{cases} P_{Y^n|X^n} & \text{if } d_H \leq d^* \\ Q_{Y^n} & \text{if } d_H > d^*\end{cases}$$

where $d^* = \lfloor np \rfloor$ is the threshold where $p^d(1-p)^{n-d} = 2^{-n}$.

The bound becomes $\varepsilon \geq 1 - M^{-1} \cdot 2^n \sum_{d=0}^{d^*} \binom{n}{d} p^d(1-p)^{n-d}$.

For $p = 0.1$, $n = 100$, $R = 0.3$:

Normal approximation: $C = 1 - H_b(0.1) \approx 0.531$, $V = 0.1 \cdot 0.9 \cdot (\log_2 9)^2 = 0.09 \cdot 10.02 = 0.902$. $R^*(100, \varepsilon) = 0.531 - \sqrt{0.902/100} \cdot Q^{-1}(\varepsilon) = 0.3$ $\implies Q^{-1}(\varepsilon) = (0.531 - 0.3)/0.0950 = 2.432$ $\implies \varepsilon \approx Q(2.432) \approx 7.5 \times 10^{-3}$.

The meta-converse gives a similar value, confirming the accuracy of the normal approximation even at $n = 100$.

For a $2 \times 2$ MIMO channel, the mutual information is $C = \log_2\det(\mathbf{I} + \gamma \mathbf{H}\mathbf{H}^{H}) = \sum_{i=1}^2 \log_2(1 + \gamma \lambda_i)$.

Outage at rate $R = r \log_2(1+\gamma)$ occurs when $\sum_i \log_2(1+\gamma\lambda_i) < r\log_2(1+\gamma)$.

At high SNR ($\gamma \to \infty$), this requires both $\gamma\lambda_i$ to be small. Using the DMT framework, write $\lambda_i = \gamma^{-\alpha_i}$ with $\alpha_i \geq 0$. Outage requires $\sum_i (1-\alpha_i)^+ < r$, and $P_{\mathrm{out}} \doteq \gamma^{-\sum_i(2i-1+\alpha_i)}$ minimised over the outage event, giving $d(r) = (2-r)^2$ for $0 \leq r \leq 2$.

At finite $n$, the Q-function $Q((\tilde{C}-R)/\sqrt{\tilde{V}/n})$ has a smooth transition (not a step function) around $\tilde{C} = R$. This means that even realisations with $\tilde{C}$ slightly above $R$ contribute to the error probability. The "outage region" effectively expands, requiring higher $\gamma$ to maintain the same diversity order $d$ at multiplexing gain $r$.

Equivalently, for fixed $\gamma$ and $d$, the maximum $r$ must decrease as $n$ decreases, because the Q-function widening captures more of the probability mass.

At $\gamma = 20$ dB ($\gamma = 100$), $r = 0.5$: $R = 0.5 \times \log_2(101) \approx 3.33$ bits/use.

Asymptotic outage: $P_{\mathrm{out}} \doteq 100^{-(2-0.5)^2} = 100^{-2.25} = 10^{-4.5} \approx 3.16 \times 10^{-5}$.

At $n = 100$, Monte Carlo averaging over channel realisations typically gives $\bar{\varepsilon} \approx 10^{-3}$--$10^{-4}$, significantly higher than the asymptotic outage, confirming the finite blocklength penalty.

The posterior of $X$ given $Z = z$ is a mixture:

$$p(X = 0 | Z = z) = \frac{(1-p_a) \mathcal{CN}(z; 0, \tau)}{(1-p_a)\mathcal{CN}(z; 0, \tau) + p_a \mathcal{CN}(z; 0, \tau + \sigma_x^2)}$$

and the active component has posterior $X | Z, \text{active} \sim \mathcal{CN}(\mu_{\mathrm{post}}, v_{\mathrm{post}})$ with $\mu_{\mathrm{post}} = \sigma_x^2 z / (\tau + \sigma_x^2)$ and $v_{\mathrm{post}} = \sigma_x^2 \tau / (\tau + \sigma_x^2)$.

The MMSE is

$$\mathrm{mmse}(\tau) = p_a \left(\frac{\sigma_x^2 \tau}{\tau + \sigma_x^2}\right) + p_a(1-\pi(\tau))\frac{\sigma_x^4}{(\tau+\sigma_x^2)^2}\mathbb{E}[|Z|^2 | \text{active}] - \text{cross terms},$$

which simplifies (after careful algebra) to

$$\mathrm{mmse}(\tau) = p_a \sigma_x^2 - p_a \frac{\sigma_x^4}{\tau + \sigma_x^2} \cdot \mathbb{E}\!\left[\frac{p_a \mathcal{CN}(Z; 0, \tau+\sigma_x^2)}{(1-p_a)\mathcal{CN}(Z; 0, \tau) + p_a\mathcal{CN}(Z; 0, \tau+\sigma_x^2)}\right].$$

This can be evaluated numerically via 1D integration over $|Z|^2$.

The fixed point equation is $\tau = \sigma^2 + \mathrm{mmse}(\tau)/\delta$.

Since $\mathrm{mmse}(\tau)$ is a decreasing function of $\tau$ (more noise $\to$ higher MMSE) bounded by $p_a \sigma_x^2$, the RHS is a decreasing function of $\tau$. The LHS is the identity. For large enough $\delta$, the term $\mathrm{mmse}(\tau)/\delta$ is small, so there is a unique intersection near $\tau = \sigma^2$.

The critical $\delta^*$ is where the fixed point equation transitions from having one solution (AMP succeeds) to having three solutions (a metastable bad fixed point appears).

For $p_a = 0.05$, $\text{SNR} = 10$ ($\sigma_x^2 = 10\sigma^2$): numerical evaluation of the state evolution shows that $\delta^* \approx 0.15$, meaning $L_p/K \geq 0.15$ is needed.

With $K = 1000$ devices: $L_p \geq 150$ pilots suffice for AMP to converge to the correct solution.

With zero service time and $B_{\max} = 1$, the sensor transmits immediately upon energy arrival (if it has data, which is assumed always available --- "generate at will").

The inter-update time is $Y \sim \mathrm{Exp}(\lambda_h)$: $\mathbb{E}[Y] = 1/\lambda_h$, $\mathbb{E}[Y^2] = 2/\lambda_h^2$.

Since service is instantaneous ($T = 0$), the age drops to 0 upon each update.

$$\bar{\Delta} = \frac{\mathbb{E}[Y^2]}{2\mathbb{E}[Y]} = \frac{2/\lambda_h^2}{2/\lambda_h} = \frac{1}{\lambda_h}.$$

(Simpler than the formula with nonzero service time.)

If the sensor subsamples by independently accepting each energy arrival with probability $p = \lambda_s/\lambda_h$, the inter-update times are geometric sums of exponentials, i.e., $Y \sim \mathrm{Exp}(\lambda_s)$.

$$\bar{\Delta} = \frac{1}{\lambda_s}.$$

Since $\bar{\Delta} = 1/\lambda_s$ is monotonically decreasing in $\lambda_s$, the optimal rate is $\lambda_s^* = \lambda_h$ (maximum possible rate).

Discarding energy is never optimal because with zero service time, there is no queueing penalty. The U-shaped AoI curve of M/M/1 arises only when the server is a bottleneck. Here, instantaneous service means more updates always help.

This changes if the service time is nonzero, in which case the energy harvesting rate must be balanced against queueing.