24
$\begingroup$

Taken from Grimmet and Stirzaker:

Show that it cannot be the case that $U=X+Y$ where $U$ is uniformly distributed on $[0,1]$ and $X$ and $Y$ are independent and identically distributed. You should not assume that $X$ and $Y$ are continuous variables.

A simple proof by contradiction suffices for the case where $X$, $Y$ are assumed discrete by arguing that it always possible to find a $u$ and $u'$ such that $P(U\leq u+u') \geq P(U\leq u)$ while $P(X+Y \leq u) = P(X+Y \leq u+u')$.

However this proof does not extend to $X,Y$ being absolutely continuous or singular continuous. Hints/Comments/Critique?

$\endgroup$
3
  • 6
    $\begingroup$ Hint: Characteristic functions are your friends. $\endgroup$
    – cardinal
    Nov 25, 2014 at 1:38
  • 2
    $\begingroup$ X and Y are iid so their characteristic functions must be identical. You need to use the characteristic function not the moment generating function though - the mgf isn't guaranteed to exist for X, so showing the mgf has an impossible property doesn't mean there is no such X. All RVs have a characteristic function, so if you show that has an impossible property then there is no such X. $\endgroup$
    – Silverfish
    Nov 25, 2014 at 8:20
  • 3
    $\begingroup$ If the distributions of $X$ and $Y$ have any atoms, say that $P\{X=a\}=P\{Y=a\} = b > 0$, then $P\{X+Y=2a\} \geq b^2 > 0$ and so $X+Y$ cannot be uniformly distributed on $[0,1]$. Thus, it is unnecessary to consider the case of the distributions of $X$ and $Y$ having atoms. $\endgroup$ Nov 25, 2014 at 17:03

3 Answers 3

17
$\begingroup$

The result can be proven with a picture: the visible gray areas show that a uniform distribution cannot be decomposed as a sum of two independent identically distributed variables.

Notation

Let $X$ and $Y$ be iid such that $X+Y$ has a uniform distribution on $[0,1]$. This means that for all $0\le a \le b \le 1$,

$$\Pr(a < X+Y \le b) = b-a.$$

The essential support of the common distribution of $X$ and $Y$ therefore is $[0,1/2]$ (for otherwise there would be positive probability that $X+Y$ lies outside $[0,1]$).

The Picture

Let $0 \lt \epsilon \lt 1/4$. Contemplate this diagram showing how sums of random variables are computed:

Figure

The underlying probability distribution is the joint one for $(X,Y)$. The probability of any event $a \lt X+Y \le b$ is given by the total probability covered by the diagonal band stretching between the lines $x+y=a$ and $x+y=b$. Three such bands are shown: from $0$ to $\epsilon$, appearing as a small blue triangle in the lower left; from $1/2-\epsilon$ to $1/2+\epsilon$, shown as a gray rectangle capped with two (yellow and green) triangles; and from $1-\epsilon$ to $1$, appearing as a small red triangle in the upper right.

What the Picture Shows

By comparing the lower left triangle in the figure to the lower left square containing it and exploiting the iid assumption for $X$ and $Y$, it is clear that

$$\epsilon = \Pr(X+Y \le \epsilon) \lt \Pr(X \le \epsilon)\Pr(Y \le \epsilon) = \Pr(X \le \epsilon)^2.$$

Note that the inequality is strict: equality is not possible because there is some positive probability that both $X$ and $Y$ are less than $\epsilon$ but nevertheless $X+Y \gt \epsilon$.

Similarly, comparing the red triangle to the square in the upper right corner,

$$\epsilon = \Pr(X+Y \gt 1-\epsilon) \lt \Pr(X \gt 1/2-\epsilon)^2.$$

Finally, comparing the two opposite triangles in the upper left and lower right to the diagonal band containing them gives another strict inequality,

$$2\epsilon \lt 2 \Pr(X\le \epsilon)\Pr(X \gt 1/2-\epsilon) \lt \Pr(1/2-\epsilon \lt X+Y \le 1/2+\epsilon) = 2\epsilon.$$

The first inequality ensues from the previous two (take their square roots and multiply them) while the second one describes the (strict) inclusion of the triangles within the band and the last equality expresses the uniformity of $X+Y$. The conclusion that $2\epsilon \lt 2\epsilon$ is the contradiction proving such $X$ and $Y$ cannot exist, QED.

$\endgroup$
8
  • 4
    $\begingroup$ (+1) I like this approach. Recovering my back-of-an-envelope from the wastepaper basket I can see I drew the same diagram, except that I didn't mark on the yellow and green triangles inside the band. I did obtain the inequalities for the blue and red triangles. I played around with them and a few other probabilities, but never thought to investigate the probability of the strip, which turns out to be the criticial step. I wonder what thought process might have motivated this insight? $\endgroup$
    – Silverfish
    Nov 25, 2014 at 16:32
  • $\begingroup$ In fact, where @whuber has yellow and green triangles, I did draw on squares (I'd effectively decomposed $[0, 0.5]^2$ into a grid). Looking at the step which "describes the (strict) inclusion of the triangles within the band", $2 \Pr(X\le \epsilon)\Pr(X \gt 1/2-\epsilon) \lt \Pr(1/2-\epsilon \lt X+Y \le 1/2+\epsilon)$, I wonder whether this would actually be geometrically more natural with squares capping the band than triangles? $\endgroup$
    – Silverfish
    Nov 25, 2014 at 16:37
  • 1
    $\begingroup$ @Silver I was reminded of an analysis of sums of uniform distributions I posted a couple of years ago. That suggested visualizing the sum $X+Y$ geometrically. It was immediately evident that a lot of probability had to be concentrated near the corners $(0,0)$ and $(1/2,1/2)$ in order for the sum to be uniform and for relatively little probability to be near the center diagonal $X+Y=1/2$. That led to the diagram, which I redrew in Mathematica. At that point the answer wrote itself. Yes, using squares in the center band might be neater. $\endgroup$
    – whuber
    Nov 25, 2014 at 16:41
  • $\begingroup$ Thanks! "Note that the inequality is strict: equality is not possible because there is some positive probability that either of $X$ or $Y$ is less than $\epsilon$ but nevertheless $X+Y \gt \epsilon$." I'm not sure I follow this. It seems to me the aim here is to show $\Pr(X+Y \le \epsilon) \lt \Pr(X \le \epsilon \cap Y \le \epsilon)$, doesn't this require a positive probability for some event $A$ in which both of $X$ and $Y$ are less than or equal to $\epsilon$ and yet $X + Y > \epsilon$? It is the "either of" vs "both of" I'm vacillating over. $\endgroup$
    – Silverfish
    Nov 25, 2014 at 20:04
  • $\begingroup$ @Silverfish Thank you; I did not express that as I had intended. You are correct: the language is intended essentially to describe the portion of a little square not inside the triangle. $\endgroup$
    – whuber
    Nov 25, 2014 at 23:56
12
$\begingroup$

I tried finding a proof without considering characteristic functions. Excess kurtosis does the trick. Here's the two-line answer: $\text{Kurt}(U) = \text{Kurt}(X + Y) = \text{Kurt}(X) / 2$ since $X$ and $Y$ are iid. Then $\text{Kurt}(U) = -1.2$ implies $\text{Kurt}(X) = -2.4$ which is a contradiction as $\text{Kurt}(X) \geq -2$ for any random variable.

Rather more interesting is the line of reasoning that got me to that point. $X$ (and $Y$) must be bounded between 0 and 0.5 - that much is obvious, but helpfully means that its moments and central moments exist. Let's start by considering the mean and variance: $\mathbb{E}(U)=0.5$ and $\text{Var}(U)=\frac{1}{12}$. If $X$ and $Y$ are identically distributed then we have:

$$\mathbb{E}(X + Y) = \mathbb{E}(X) + \mathbb{E}(Y) = 2 \mathbb{E}(X)= 0.5$$

So $\mathbb{E}(X) = 0.25$. For the variance we additionally need to use independence to apply:

$$\text{Var}(X+Y) = \text{Var}(X) + \text{Var}(Y) = 2 \text{Var}(X) = \frac{1}{12}$$

Hence $\text{Var}(X) = \frac{1}{24}$ and $\sigma_X = \frac{1}{2\sqrt{6}} \approx 0.204$. Wow! That is a lot of variation for a random variable whose support ranges from 0 to 0.5. But we should have expected that, since the standard deviation isn't going to scale in the same way that the mean did.

Now, what's the largest standard deviation that a random variable can have if the smallest value it can take is 0, the largest value it can take is 0.5, and the mean is 0.25? Collecting all the probability at two point masses on the extremes, 0.25 away from the mean, would clearly give a standard deviation of 0.25. So our $\sigma_X$ is large but not impossible. (I hoped to show that this implied too much probability lay in the tails for $X + Y$ to be uniform, but I couldn't get anywhere with that on the back of an envelope.)

Second moment considerations almost put an impossible constraint on $X$ so let's consider higher moments. What about Pearson's moment coefficient of skewness, $\gamma_1 = \frac{\mathbb{E}(X - \mu_X)^3}{\sigma_X^3} = \frac{\kappa_3}{\kappa_2^{3/2}}$? This exists since the central moments exist and $\sigma_X \neq 0$. It is helpful to know some properties of the cumulants, in particular applying independence and then identical distribution gives:

$$\kappa_i(U) = \kappa_i(X + Y) = \kappa_i(X) + \kappa_i(Y) = 2\kappa_i(X)$$

This additivity property is precisely the generalisation of how we dealt with the mean and variance above - indeed, the first and second cumulants are just $\kappa_1 = \mu$ and $\kappa_2 = \sigma^2$.

Then $\kappa_3(U) = 2\kappa_3(X)$ and $\big(\kappa_2(U)\big)^{3/2} = \big(2\kappa_2(X)\big)^{3/2} = 2^{3/2} \big(\kappa_2(X)\big)^{3/2}$. The fraction for $\gamma_1$ cancels to yield $\text{Skew}(U) = \text{Skew}(X + Y) = \text{Skew}(X) / \sqrt{2}$. Since the uniform distribution has zero skewness, so does $X$, but I can't see how a contradiction arises from this restriction.

So instead, let's try the excess kurtosis, $\gamma_2 = \frac{\kappa_4}{\kappa_2^2} = \frac{\mathbb{E}(X - \mu_X)^4}{\sigma_X^4} - 3$. By a similar argument (this question is self-study, so try it!), we can show this exists and obeys:

$$\text{Kurt}(U) = \text{Kurt}(X + Y) = \text{Kurt}(X) / 2$$

The uniform distribution has excess kurtosis $-1.2$ so we require $X$ to have excess kurtosis $-2.4$. But the smallest possible excess kurtosis is $-2$, which is achieved by the $\text{Binomial}(1, \frac{1}{2})$ Bernoulli distribution.

$\endgroup$
6
  • 4
    $\begingroup$ (+1) This is a quite clever approach, which was new to me. Thanks. Note that some of your analysis could have been streamlined by considering a uniform centered at zero. (The equivalence of the problem is immediate.) That would have immediately told you that considering skew was a dead-end. $\endgroup$
    – cardinal
    Nov 25, 2014 at 14:18
  • $\begingroup$ @cardinal: I knew the skew was a dead-end before I worked on it. The purpose was expository: it's a self-study question so I didn't want to solve it in full! Rather I wanted to leave a hint on how to deal with the next level up... $\endgroup$
    – Silverfish
    Nov 25, 2014 at 14:23
  • $\begingroup$ @cardinal: I was in two minds whether to center or not. I did back-of-envelope calculations more conveniently, but in the final analysis we just need (1) a simple case of the general result that $Kurt(X_1 + ... + X_n) = \frac{1}{n}Kurt(X)$ for iid $X_i$, (2) that $Kurt(U) = -1.2$ for any uniform distribution, and (3) $Kurt(X)$ exists since $X$ is bounded and $\sigma_X \neq 0$ (which is trivial, else $\sigma_U = 0$). So none of the key results actually required centering, though bits may have looked less ugly! $\endgroup$
    – Silverfish
    Nov 25, 2014 at 14:33
  • $\begingroup$ Yes, the word "streamlined" was carefully chosen. :-) I did not intend my comment to be read as criticism of your exposition. Cheers. $\endgroup$
    – cardinal
    Nov 25, 2014 at 14:41
  • $\begingroup$ @cardinal Incidentally, variance considerations alone almost worked, but the uniform isn't quite spread out enough. With a bit more probability mass nearer the extremes, e.g. $f_T(t)=12t^2$ on [-0.5, 0.5], then $Var(T)=.15$ and if $T = X_1 + X_2$ then $\sigma_X = \sqrt{.15/2} \approx 0.27 > 0.25$ which is impossible as $X$ is bounded by -0.25 and 0.25. Of course, you will see immediately how this relates to the present example! I wonder if the approach generalises, I'm sure other bounded RVs can't be decomposed into sums but require even higher moments investigated to find the contradiction. $\endgroup$
    – Silverfish
    Nov 25, 2014 at 14:48
5
$\begingroup$

Assume $U = X + Y$ for two i.i.d random variables.

First note that since $U$ has support $[0, 1]$, the support of $X$ (and $Y$) must be a subset of $[0, 1/2]$, as a result of \begin{align} & P[X > 1/2]^2 = P[X > 1/2, Y > 1/2] \leq P[X + Y > 1] = P[U > 1] = 0, \\ & P[X < 0]^2 = P[X < 0, Y < 0] \leq P[X + Y < 0] = P[U < 0] = 0. \end{align}

This shows that $E[|X|^k] \leq \frac{1}{2^k} < \infty$ for all $k \in \mathbb{N}$, whence if let $\varphi$ be the characteristic function of $X$, then for every $t \in \mathbb{R}$, $\varphi$ is differentiable at $t$ and $\varphi'(t) = E\left[iXe^{itX}\right]$ (see Probability and Measure (3rd edition) by Patrick Billlingsley, pp. 343-345).

Next, since the characteristic function of $U$ is $\varphi_U(t) = \frac{e^{it} - 1}{it}$ and $\varphi_U(t) = \varphi(t)^2$ by assumption, we have \begin{align} \varphi(t)^2 = \frac{e^{it} - 1}{it}. \tag{1}\label{1} \end{align}

It then follows that (differentiate both sides of $\eqref{1}$) \begin{align} 2\varphi(t)\varphi'(t) = \frac{-te^{it} - ie^{it} + i}{-t^2}. \tag{2}\label{2} \end{align}

By $\eqref{1}$, $\varphi^2(2\pi) = 0$, whence $\varphi(2\pi) = 0$. On the other hand, $\eqref{2}$ implies that \begin{align} 2\varphi(2\pi)\varphi'(2\pi)= -\frac{i}{4\pi^2} \neq 0, \end{align} i.e., $\varphi(2\pi) \neq 0$. This is contradiction.

$\endgroup$
4
  • 2
    $\begingroup$ There is a gap in this proof. When you bound $|\varphi (t)|$ you appear to be using the triangle inequality, but that would expand in powers of $|t|$ not $ t $. This becomes crucial because you later choose a negative $ t $. (cont.) $\endgroup$
    – cardinal
    Nov 25, 2014 at 12:15
  • 2
    $\begingroup$ Indeed, you appear to "prove" that for any distribution supported on $[0, 1/2] $, $|\varphi(t)| \leq e^{t/2}$ for all $ t $, but, of course, this can't be true. (Consider any discrete distribution on a finite number of points in the interval.) $\endgroup$
    – cardinal
    Nov 25, 2014 at 12:19
  • 2
    $\begingroup$ @cardinal Thank you, you are absolutely right, I will try to fix it. $\endgroup$
    – Zhanxiong
    Nov 25, 2014 at 15:14
  • $\begingroup$ I missed out the triangular inequality part. Thanks @cardinal! $\endgroup$ Nov 26, 2014 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.