TAOCP 3.3.2 Exercise 32

Section 3.3.2: Empirical Tests

Exercise 32. [M20] True or false: If $X$ and $Y$ are independent, identically distributed random variables with mean 0, and if they are more likely to be positive than negative, then $X + Y$ is more likely to be positive than negative.

Verified: yes
Solve time: 14m47s

The statement is false.

The assumptions are that (X) and (Y) are independent, identically distributed, that (\mathbb{E}[X]=0), and that [ \mathbb{P}(X>0) > \mathbb{P}(X<0). ] We must decide whether this forces [ \mathbb{P}(X+Y>0) > \mathbb{P}(X+Y<0). ]

The key point is that the sign of (X+Y) depends on a convolution of the distribution of (X), and the condition on (X) only controls probabilities of sign, not magnitudes. This allows a construction where single draws are more often positive, but paired sums are more often negative.

A fully explicit counterexample can be built with a two-point distribution.

Let [ \mathbb{P}(X = 1) = p, \quad \mathbb{P}(X = -a) = 1-p, ] where (0<p<1) and (a>0). The mean-zero condition gives [ p \cdot 1 + (1-p)(-a) = 0, ] so [ p = \frac{a}{1+a}. ]

We want (\mathbb{P}(X>0) > \mathbb{P}(X<0)), which is [ p > 1-p \quad \Longleftrightarrow \quad p > \frac12. ] Using (p = \frac{a}{1+a}), this becomes [ \frac{a}{1+a} > \frac12 \quad \Longleftrightarrow \quad a>1. ]

So choose any (a>1), for example (a=2). Then [ \mathbb{P}(X=1)=\frac{2}{3}, \quad \mathbb{P}(X=-2)=\frac{1}{3}. ] This satisfies all assumptions: [ \mathbb{E}[X]=\frac{2}{3}\cdot 1 + \frac{1}{3}\cdot(-2)=0, \quad \mathbb{P}(X>0)=\frac{2}{3}>\frac{1}{3}. ]

Now compute the distribution of (S=X+Y). The possible sums are [ 2,\quad -1,\quad -4, ] coming from [ (1,1),\ (1,-2),\ (-2,1),\ (-2,-2). ]

Their probabilities are: [ \mathbb{P}(S=2)=\left(\frac{2}{3}\right)^2=\frac{4}{9}, ] [ \mathbb{P}(S=-1)=2\cdot \frac{2}{3}\cdot \frac{1}{3}=\frac{4}{9}, ] [ \mathbb{P}(S=-4)=\left(\frac{1}{3}\right)^2=\frac{1}{9}. ]

Now aggregate signs.

Positive: [ \mathbb{P}(S>0)=\mathbb{P}(S=2)=\frac{4}{9}. ]

Negative: [ \mathbb{P}(S<0)=\mathbb{P}(S=-1)+\mathbb{P}(S=-4)=\frac{4}{9}+\frac{1}{9}=\frac{5}{9}. ]

Thus [ \mathbb{P}(S>0) = \frac{4}{9} < \frac{5}{9} = \mathbb{P}(S<0). ]

This directly contradicts the claimed implication.

The mechanism is structural. The condition (\mathbb{P}(X>0)>\mathbb{P}(X<0)) can hold even when negative values have larger magnitude. When two independent copies are added, the event “both are negative” produces a large negative contribution, while positive outcomes require two positive draws. This imbalance is enough to reverse the sign bias in the sum.

Therefore the original statement does not hold in general, so the answer is false.