random-variable

Sat Apr 04 2026

The Problem

Three random variables: $M$ (message), $K$ (key), $C = M \oplus K$ (ciphertext). I know the distributions of $M$ and $K$ individually. How do I find the distribution of $C$?

More generally: when a new random variable is defined as a function of others ($Z = f(X, Y)$), how do I compute its PMF?

Where I Got Stuck

I could reason about $P(\text{event A})$ using Venn diagrams and set operations. But random variables are different. When someone writes $C = K \oplus M$ and asks for $P(C = 1)$, the answer depends on how $K$ and $M$ relate to each other. I didn't have a systematic way to go from "I know $P(K = k)$ and $P(M = m)$" to "here's $P(C = c)$."

The event notation doesn't give you a way to do arithmetic on probabilities. You can intersect events, union them, complement them. But you can't XOR two events or add them. Random variables let you do that because they're functions, not sets.

Random Variables Are Functions

A random variable $X$ is a deterministic function from the sample space to real numbers:

$X: \Omega \to \mathbb{R}$

$P(X = k)$ is shorthand for the probability of the event $\{\omega \in \Omega \mid X(\omega) = k\}$, the inverse image of $k$ under $X$.

Because RVs are functions, we can compose them. $C(\omega) = K(\omega) \oplus M(\omega)$ for every outcome $\omega$. That's what "$C = K \oplus M$" means. The new variable $C$ is just another function on the same sample space, defined pointwise.

The Joint Table Is the Workspace

With two RVs $K$ and $M$, stop listing sample space outcomes. Build the joint PMF:

$P_{K,M}(k, m) = P(K = k \text{ and } M = m)$

For fair independent coins ($K, M \in \{0, 1\}$):

If $K \perp M$: each cell is $P(K{=}k) \cdot P(M{=}m)$.

This table is the object you work with. Everything else follows from it.

Marginalization: $P(K = k)$ = sum of row $k$. You project the 2D table onto one axis.

Conditioning: $P(M = m \mid K = k)$ = take row $k$, divide each cell by the row sum. Same "shrink the universe" idea from conditional-probability, applied to the table instead of Venn diagrams.

Deriving a New Distribution

To find $P(C = c)$ where $C = K \oplus M$: look at every cell $(k, m)$ in the joint table, check whether $k \oplus m = c$, and sum those probabilities.

$P(C = c) = \sum_{\substack{k, m \\ k \oplus m = c}} P(K{=}k, M{=}m)$

For our fair coins: $P(C = 1)$ comes from cells where $k \neq m$, which are $(0, 1)$ and $(1, 0)$. So $P(C = 1) = 0.25 + 0.25 = 0.5$.

The same technique works for any operation. For addition ($Z = X + Y$) with independent RVs, fixing $X = k$ forces $Y = z - k$, giving the convolution formula:

$P(Z = z) = \sum_{k} P(X = k) \cdot P(Y = z - k)$

If $X$ and $Y$ are dependent, replace $P(Y = z - k)$ with $P(Y = z - k \mid X = k)$.

That's the general technique: enumerate all input pairs that produce the target output, sum their joint probabilities.

XOR vs Addition: Why the Outputs Look Different

The operation you apply determines the shape of the resulting distribution.

XOR is a permutation. Fix any row $k$ in the joint table. As $m$ ranges over $\{0, 1\}$, the output $k \oplus m$ hits every value exactly once. Every row is a permutation of the output space. If $K$ is uniform, each output value gets equal total weight.

Addition piles up in the middle. Multiple input pairs can produce the same sum. Middle values have more combinations ($4 = 1{+}3 = 2{+}2 = 3{+}1$) while edge values have fewer ($2 = 1{+}1$). Mass accumulates in the center.

Adding more independent uniform variables keeps smoothing the peak toward a bell curve (Central Limit Theorem).

The Row-Universe Analysis

This is the part that connects to the one-time pad. Split the joint table by rows of $K$. Each row is a separate universe conditioned on a specific key value.

• Row $K = 0$: $C = 0 \oplus M = M$. The ciphertext copies the message.
• Row $K = 1$: $C = 1 \oplus M = \overline{M}$. The ciphertext flips the message.

For $C$ to be independent of $K$, the distribution of $C$ must look the same in every row:

$P(C = 1 \mid K = 0) = P(C = 1 \mid K = 1)$

The left side is $P(M = 1)$. The right side is $P(M = 0)$. These are equal only when $P(M = 1) = P(M = 0) = 1/2$, so $M$ must be uniform.

This is the one-time pad property: Any bias $\oplus$ Uniform $=$ Uniform. Even if $M$ is 90% zeros, a uniform $K$ washes it away completely:

$P(C = c) = \sum_{m} P(M = m) \cdot P(K = c \oplus m) = \sum_{m} P(M = m) \cdot \frac{1}{N} = \frac{1}{N}$

The $1/N$ factors out of the sum, and the remaining $\sum_m P(M = m) = 1$.

See otp-security-proof for how this drives the full security argument.

Independence Matters, Not Just Uniformity

$K$ being uniform isn't enough. $K$ must also be independent of $M$.

Counterexample: let $K = M$ (perfect dependence). $K$ is still uniform since $M$ is fair. But $C = M \oplus K = M \oplus M = 0$ always. The ciphertext is a constant. It leaks everything about $M$ (namely, that $M = K$).

The proof above used $P(K = c \oplus m)$ without conditioning on $M = m$. That step requires $K \perp M$. Without independence, you'd need $P(K = c \oplus m \mid M = m)$, and you can't conclude uniformity.