TAOCP 3.4.1 Exercise 8

Exercise 8. [M15] Show that operation (3) could be changed to

$$\text{if } U < P_K \text{ then } X \leftarrow x_{K+1} \quad \text{otherwise} \quad X \leftarrow Y_K$$

(thus using the original value of $U$ instead of $V$) if this were more convenient, by suitably modifying $P_0, P_1, \ldots, P_{k-1}$.

Verified: yes
Solve time: 1m20s

Solution

We are asked to show that the alias method, as described in equation (3) of Section 3.4.1A, could equivalently use the original uniform deviate $U$ rather than the fractional part $V$ in the comparison, provided the $P_j$ table is suitably modified.

Recall that in Walker's method we first compute

$K = \lfloor kU \rfloor, \qquad V = kU - K,$

so that $K$ is an integer between $0$ and $k-1$ and $V$ is uniformly distributed in $[0,1)$. The original comparison is

$\text{if } V < P_K \text{ then } X \leftarrow x_{K+1} \quad \text{otherwise} \quad X \leftarrow Y_K. \eqno(3)$

The idea is to replace $V$ with $U$ in this comparison:

$\text{if } U < P'K \text{ then } X \leftarrow x{K+1} \quad \text{otherwise} \quad X \leftarrow Y_K, \eqno(3')$

for some new table $P'0, \ldots, P'{k-1}$.

We have

$V = kU - K \quad \Longleftrightarrow \quad U = \frac{K + V}{k}.$

Substituting $V = kU - K$ into the original inequality $V < P_K$, we obtain

$kU - K < P_K \quad \Longleftrightarrow \quad U < \frac{K + P_K}{k}.$

Thus, if we define

$P'_K \coloneqq \frac{K + P_K}{k},$

then the condition $U < P'_K$ is equivalent to $V < P_K$. Therefore, the same distribution for $X$ is obtained.

No other modifications to the algorithm are necessary, because $K$ is computed in the same way from $U$, and the alias table $Y_0, \ldots, Y_{k-1}$ is unchanged. This construction guarantees that the probability of choosing $x_{K+1}$ remains exactly $P_K$ as in the original method, while using the original uniform deviate $U$ in place of $V$.

This completes the proof.

∎