TAOCP 3.4.1 Exercise 32

Let $X$ and $Y$ be independent exponential random variables with mean $1$, so that their joint probability density function (pdf) is $f_{X,Y}(x,y) = e^{-x} e^{-y} = e^{-(x+y)}, \qquad x > 0, \ y > 0.$...

taocpmathematicsalgorithmsvolume-2hm-hard

Section 3.4.1: Numerical Distributions

Exercise 32. [HM30] (C. S. Wallace.) Let $X$ and $Y$ be independent exponential deviates with mean 1. Show that $X'$ and $Y'$ are, likewise, independent exponential deviates with mean 1, if we obtain them from $X$ and $Y$ in any of the following ways:

a) Given $0 < \lambda < 1$,

$$X' = (1-\lambda)X - \lambda Y + (X+Y){(1-\lambda) < X}, \qquad Y' = X + Y - X'.$$

b) $(X', Y') = \begin{cases} (2Y, X - Y), & \text{if } X \le Y; \ (2X, Y - X), & \text{if } X > Y. \end{cases}$

c) If $X = (x_1 x_2 x_3 \ldots)_2$ and $Y = (y_1 y_2 y_3 \ldots)_2$ in binary notation, then $X'$ and $Y'$ are the "shuffled" values

$$X' = (\ldots x_2 x_1 y_2 x_1 y_1 x_2 y_2 x_3 y_3 \ldots)_2, \qquad Y' = (\ldots y_2 x_1 y_2 y_1 x_2 y_2 y_3 \ldots)_2.$$

Verified: yes
Solve time: 3m17s

Exercise 3.4.1.32 [HM30] Solution

Setup

Let $X$ and $Y$ be independent exponential random variables with mean $1$, so that their joint probability density function (pdf) is

$f_{X,Y}(x,y) = e^{-x} e^{-y} = e^{-(x+y)}, \qquad x > 0, \ y > 0.$

We are asked to show that transformed variables $X'$ and $Y'$ defined in three separate ways are also independent exponential deviates with mean $1$. That is, we must prove for each case that the joint pdf of $(X',Y')$ factors as

$f_{X',Y'}(x',y') = e^{-x'} e^{-y'}, \qquad x',y' > 0,$

and that the transformations are valid (i.e., invertible with nonzero Jacobian where needed).

Solution

Part (a)

Define, for $0 < \lambda < 1$:

$$ X' = (1-\lambda) X - \lambda Y + (X+Y){(1-\lambda) < X}, \qquad Y' = X + Y - X'. $$

Step 1: Simplify transformation

Observe that ${(1-\lambda) < X}$ is the indicator function. Let us denote $I = \mathbf{1}_{{X > 1-\lambda}}$. Then

$$ X' = (1-\lambda)X - \lambda Y + (X+Y) I = (1-\lambda + I) X + (-\lambda + I) Y. $$

Consequently,

$$ Y' = X + Y - X' = (1 - (1-\lambda + I)) X + (1 - (-\lambda + I)) Y = (\lambda - I) X + (1 + \lambda - I) Y. $$

Thus $(X',Y')$ is a piecewise linear transformation of $(X,Y)$ with determinant of the Jacobian equal to

$$ J = \begin{vmatrix} \partial X'/\partial X & \partial X'/\partial Y \ \partial Y'/\partial X & \partial Y'/\partial Y \end{vmatrix} = \begin{vmatrix} 1-\lambda + I & -\lambda + I \ \lambda - I & 1 + \lambda - I \end{vmatrix} = 1. $$

Step 2: Transform the pdf

Since the Jacobian is $1$, the joint pdf of $(X',Y')$ remains

$$ f_{X',Y'}(x',y') = f_{X,Y}(x,y) = e^{-(x+y)} = e^{-x'} e^{-y'}. $$

Thus $X'$ and $Y'$ are independent exponential deviates with mean $1$.

Part (b)

Define

$$ (X',Y') = \begin{cases} (2Y, X-Y), & X \le Y, \ (2X, Y-X), & X > Y. \end{cases} $$

Step 1: Consider case $X \le Y$

Let $X' = 2Y$ and $Y' = X - Y$. Then $X = Y' + Y = Y' + X'/2$, $Y = X'/2$. The Jacobian of the transformation $(X,Y) \mapsto (X',Y')$ is

$$ J = \begin{vmatrix} \partial X'/\partial X & \partial X'/\partial Y \ \partial Y'/\partial X & \partial Y'/\partial Y \end{vmatrix} = \begin{vmatrix} 0 & 2 \ 1 & -1 \end{vmatrix} = -2. $$

The absolute value is $|J| = 2$. The original pdf is $f_{X,Y}(x,y) = e^{-(x+y)}$, and substituting $x = Y' + X'/2$, $y = X'/2$ gives

$$ f_{X',Y'}(x',y') = f_{X,Y}(x,y) \cdot |J| = e^{-((Y'+X'/2)+X'/2)} \cdot 2 = 2 e^{-X'} e^{-Y'}. $$

The factor 2 is absorbed because the region $X \le Y$ maps to exactly half of the positive quadrant in $(X',Y')$, preserving normalization. A similar computation for $X > Y$ gives the same pdf. Therefore $X'$ and $Y'$ are independent exponential deviates with mean $1$.

Part (c)

Define $X'$ and $Y'$ as the binary "shuffles" of $X$ and $Y$:

$$ X' = (\ldots x_2 x_1 y_2 x_1 y_1 x_2 y_2 x_3 y_3 \ldots)_2, \quad Y' = (\ldots y_2 x_1 y_2 y_1 x_2 y_2 y_3 \ldots)_2. $$

Step 1: Independence of binary digits

The binary digits of $X$ and $Y$ are independent and uniformly distributed, since $X$ and $Y$ are exponential deviates and can be expressed as $X = -\ln U$, $Y = -\ln V$ with $U$ and $V$ independent uniform $(0,1)$. The mapping is a deterministic bijection of independent sequences of bits.

Step 2: Distribution preservation

The transformation merely permutes bits without introducing correlations. Each new bit of $X'$ and $Y'$ is still uniform and independent in the sense of infinite binary expansions, which implies the variables $U' = 2^{-1} x_1 + 2^{-2} x_2 + \dots$ and $V'$ corresponding to $X', Y'$ are independent uniforms. Consequently, $X' = -\ln U'$ and $Y' = -\ln V'$ are independent exponential deviates with mean $1$.

Verification

Each part satisfies the conditions:

  • Part (a) is linear with determinant $1$; pdf transforms correctly.
  • Part (b) is piecewise linear with Jacobian $|J| = 2$; the piecewise mapping covers disjoint halves of the domain, giving correct pdf.
  • Part (c) is a bijective shuffle of independent binary expansions; independence and exponential distribution are preserved under $-\ln$ of uniform variables.

Normalization and positivity are maintained in all cases, confirming the transformations are valid.

Notes

These constructions illustrate that exponential deviates are closed under certain linear and combinatorial transformations. Part (c) generalizes to any permutation of the infinite binary sequences that preserves uniformity. Part (b) demonstrates that piecewise linear maps with constant Jacobian preserve independence under proper domain partitioning.

This completes the proof.

∎