If the sum of two independent random variables is discrete uniform on $\{a, \dots,a + n\}$, what do we know about $X$ and $Y$?

Question

Basically I want to know whether the sum being discrete uniform effectively forces the two component random variables to also be uniform on their respective domains.

To be a bit more precise:

Suppose we know $X$ and $Y$ are independent and

$$ X+Y \sim UNIF({1, \dots , n})$$

Does this necessarily imply that both $X$ and $Y$ are discrete uniform as well?

Answer 1

1. Proof of the claim

The following lemma shows that $X$ and $Y$ may also be regarded as integer-valued random variables in OP's scenario.

Lemma. Assume that $X$ and $Y$ are independent random variables. Suppose that there exists a finite set $S\subset\mathbb{R}$ satisfying $$ \mathbb{P}(X+Y \in S) = 1 \qquad \text{and} \qquad \mathbb{P}(X+Y = s) > 0, \quad \forall s \in S. $$ Then there exist $x_0, y_0 \in \mathbb{R}$ such that $X' := X + y_0$ and $Y' := Y + x_0$ satisfy $$\mathbb{P}(X' \in S) = 1 \qquad\text{and}\qquad \mathbb{P}(Y' \in S) = 1.$$ Moreover, $\mathbb{P}(X' = \min S) > 0$ and $\mathbb{P}(Y' = \min S) > 0$.

The proof is postponed to the end. Now write $[\![n]\!] := \{0, \cdots, n-1\}$. Then we prove

Proposition.^{(1, Lemma 2.1)} Let $X$ and $Y$ be independent random variables such that $X+Y$ is uniformly distributed over $[\![n]\!]$. Then both $X$ and $Y$ have uniform distribution.

The following proof is based on the reference 1) mentioned in @Mark Wildon's comment.

Proof. In light of the lemma above, we may assume that both $X$ and $Y$ are supported on $[\![n]\!]$ as well as $\mathbb{P}(X=0,Y=0)=1/n$. Using this, set

$$ A(x) := \sum_{k\geq 0} a_k x^k \qquad \text{and} \qquad B(x) := \sum_{k\geq 0} b_k x^k $$

where $a_k := p_X(k)/p_X(0)$ and $b_k := p_Y(k)/p_Y(0)$. Then it follows that $a_k, b_k$ are all non-negative, $a_0 = b_0 = 1$, and

$$ A(x)B(x) = 1 + x + \cdots + x^{n-1}. $$

From this, it is easy to check that both $A(x)$ and $B(x)$ are palindromic, which will be used later.

Now, to establish the desired assertion, it suffices to show that all of the coefficients of $A(x)$ and $B(x)$ lie in $\{0, 1\}$. To this end, assume otherwise. Let $k_0$ be the smallest index such that either $a_{k_0} \notin \{0, 1\}$ or $b_{k_0} \notin \{0, 1\}$. We know that $k_0 \geq 1$. Moreover,

$$ a_{k_0} + \underbrace{ a_{k_0-1}b_{1} + \cdots + a_1 b_{k_0 - 1} }_{\in \mathbb{N}_0} + b_{k_0} = [x^{k_0}]A(x)B(x) \in \{0, 1\}, $$

forces that $a_{k_0} + b_{k_0} = 1$. So both $a_{k_0}$ and $b_{k_0}$ lie in $(0, 1)$. But if we write $d = \deg B(x)$, then we have $b_{d-k_0} = b_{k_0}$ and $b_d = b_0 = 1$, and so,

$$ 1 < a_{k_0}b_{k_0} + 1 \leq a_{d} + \cdots + a_{k_0}b_{d-k_0} + \cdots + b_{d} = [x^{d}]A(x)B(x) \in \{0, 1\}, $$

a contradiction. Therefore no such $k_0$ exists and the desired claim follows. $\square$

References.

_{1) Behrends, E., 1999. Über das Fälschen von Würfeln. Elem. Math. 54, 15–29. https://doi.org/10.1007/s000170050051}

2. Further questions

Based on some simulations as well as actual computation for small $n$, I conjecture that the followings hold:

Conjecture. Let $A(x)$ and $B(x)$ be monic polynomials with coefficients in $[0, \infty)$. Assume that there exists an integer $n \geq 1$ such that $$ A(x)B(x) = 1 + x + \cdots + x^{n-1}. $$ Then there exist positive integers $1 = n_0 \mid n_1 \mid \cdots \mid n_d = n$, not necessarily distinct, such that $$ A(x) = \frac{(x^{n_1} - 1)}{(x^{n_0} - 1)} \frac{(x^{n_3} - 1)}{(x^{n_2} - 1)} \cdots, \qquad B(x) = \frac{(x^{n_2} - 1)}{(x^{n_1} - 1)} \frac{(x^{n_4} - 1)}{(x^{n_3} - 1)} \cdots. $$

This implication of this conjecture is that, up to shift, $X$ is supported on the set of the form

$$ \{ (c_0 + c_2 n_2 + c_4 n_4 + \ldots) : c_k \in [\![n_{k+1}/n_k]\!] \} $$

and likewise $Y$ is supported on

$$ \{ (c_1 n_1 + c_3 n_3 + c_5 n_5 + \ldots) : c_k \in [\![n_{k+1}/n_k]\!] \}. $$

This may be regarded as the converse of the fact that, if $Z$ is sampled uniformly at random from the set $[\![n]\!]$ and $Z = \sum_{k\geq 0} C_k n_k$ with $C_k \in [\![n_{k+1}/n_k]\!]$, then $C_k$'s are independent.

Addendum - Proof of Lemma.

First, we note that both $X$ and $Y$ are bounded. Indeed, choose $x > 0$ so that $\mathbb{P}(|X| \leq x) > 0$ and note that

$$ \mathbb{P}(|Y| \geq y) = \frac{\mathbb{P}(|Y| \geq y, |X| \leq x)}{\mathbb{P}(|X| \leq x)} \leq \frac{\mathbb{P}(|X + Y| \geq y - x)}{\mathbb{P}(|X| \leq x)} $$

can be made to vanish if $y$ is chosen sufficiently large. This shows that $Y$ is bounded. A similar argument shows that $X$ is also bounded.

Next, choose the smallest interval $[x_0, x_1]$ so that $\mathbb{P}(X \in [x_0, x_1]) = 1$, and likewise, choose the smallest interval $[y_0, y_1]$ so that $\mathbb{P}(Y \in [y_0, y_1]) = 1$. Then $x_0 + y_0 = \min S$. Indeed,

• If $x_0 + y_0 < s$, then write $s = x+y$ with $x > x_0$ and $y > y_0$. Then

  $$ 0 < \mathbb{P}(X \leq x, Y \leq y) \leq \mathbb{P}(X + Y \leq s) $$

  shows that $s \geq \min S$. Letting $s \downarrow x_0 + y_0$, this proves $x_0 + y_0 \geq \min S$.

• If $x_0 + y_0 > s$, then $\mathcal{D} := \{(x, y) : x+y \leq s\} \cap ([x_0, x_1]\times[y_0, y_1]) = \varnothing$, and so,

  $$ \mathbb{P}(X+Y \leq s) = \mathbb{P}((X, Y) \in \mathcal{D}) = 0. $$

  This implies that $s < \min S$ and thus $x_0 + y_0 \leq \min S$.

Together with $\mathbb{P}(X+Y = \min S) > 0$, this implies $\mathbb{P}(X = x_0) > 0$ and $\mathbb{P}(Y = x_0) > 0$. From this,

$$ \mathbb{P}(X+y_0 \notin S) = \mathbb{P}(X+Y \notin S \mid Y = y_0) \leq \frac{\mathbb{P}(X+Y \notin S)}{\mathbb{P}(Y = y_0)} = 0 $$

and hence $\mathbb{P}(X+y_0 \in S) = 1$. A similar argument shows that $\mathbb{P}(Y+x_0 \in S) = 1$, and therefore the claim follows by setting $a = y_0$ and $b = x_0$. $\square$

Answer 2

As Lutz Mattner pointed out in his comment to another question, an affirmative answer is given in: Krasner and Ranulac (1937), Sur une propriété des polynomes de la division du cercle, C.R. Acad. Sci. Paris 204, 397–399 (which, unfortunately, does not seem to be available online, except for the Russian version due to D. Raikov). Connection to the other question was observed by @user44191.

Answer 3

(A rather trivial remark, but too long for a comment.)

Phrase it in a different language: two polynomials $P$ and $Q$ with non-negative coefficients have product equal to $$P(x) Q(x) = 1 + x + x^2 + \ldots + x^{n-1} = \frac{1 - x^n}{1 - x} .$$ What does it tell us about $P$ and $Q$?

Write $\sigma = e^{2 \pi i / n}$, so that $$ P(x) Q(x) = \prod_{k = 1}^{n - 1} (x - \sigma^k) .$$ Clearly, for some partition $\{1,2,\ldots,n-1\} = A \cup B$ and appropriate constants $a$ and $b$, we have $$ P(x) = a \prod_{k \in A} (x - \sigma^k) , \qquad b P(x) = \prod_{k \in B} (x - \sigma^k) . $$ For simplicity, let us require that $P(0) = Q(0) = 1$.

Since $P$ and $Q$ are real-valued, if $A$ contains $k$, it also contains $n - k$. Any such partition leads to a factorization $P(x) Q(x)$ where $P$ and $Q$ have real-valued (possibly negative) coefficients.

However, we require the coefficients of $P$ and $Q$ to be non-negative. Does this imply that the coefficients of $P$ and $Q$ are all $0$ and $1$?

Answer 4

Let $Z = X + Y$. I'll assume $n$ is an integer. More generally, I'll allow Z to take values in $S_Z = \{z_1, ..., z_n \}$. As $Z$ is uniform on $S_Z$, we know that

$$P(Z = z) = \frac{1}{n}$$

for any $z \in S_Z$.

Let $S_X, S_Y$ represent the supports of $X, Y$ respectively. Let $p_x = P(X = x)$ and $q_x = P(Y = x)$. As they are independent, we can therefore write $P(Z = z)$ as

$$ P(Z = z) = \sum_{x \in S} p_x q_{z-x} . $$

Therefore, we have the following set of consistency equations

$$ \sum_{x \in S} p_x q_{z-x} = \frac{1}{n} \tag{1}$$

for all $z$. We can solve this iteratively assuming a total order on the supports $S_X$ and $S_Y$. Let $x_{(i)}$ be the $i$th minimal element of $S_X$, $y_{(i)}$ be the $i$th minimal element of $S_Y$, and $z_{(i)}$ be the $i$th minimal element of $S_Z$. We must have that $x_{(1)} + y_{(1)} = z_{(1)}$, as the sum of the minima of both sets $S_X$ and $S_Y$ must map to the minimum of the support of $Z$, so by the consistency equations $(1)$, we obtain

$$p_{x_{(1)}}q_{y_{(1)}} = \frac{1}{n} .$$

If we require that the distributions of $X$ and $Y$ are uniform, i.e., $p_{x_{(1)}} = 1/|S_X|$ and $q_{y{(1)}} = 1/|S_Y|$, then we must have

$$ |S_X||S_Y| = n \tag{2} $$

and therefore uniformity can only hold if both $|S_X|$ and $|S_Y|$ divide $n$. Hence, the distributions of $X$ and $Y$ are not always uniform.

Another way to interpret equation $(2)$ is that the mapping $X + Y$ across the supports of $S_X$, $S_Y$ must map to a unique element in $\{1,...,n\}$. This is shown explicitly in the expanded cases below for $z_{(2)}, z_{(3)}$, and $z_{(4)}$ in equation $(1)$.

In fact, if the mapping does map to unique elements, then the consistency equations become

$$p_{x_{(i)}}q_{y_{(j)}} = \frac{1}{n}, \;\;\; i \in \{1, ..., |S_X|\}, \; j \in \{1, ..., |S_Y|\},$$

Summing over $i$ or $j$ respectively produces

$$p_{x_{(i)}}= \frac{1}{|S_X|} \;\;\; q_{y_{(j)}}= \frac{1}{|S_Y|}$$

where equation $(2)$ emerges from summing over both $i$ and $j$ and is used in the last equation. Therefore, the underlying probability distributions must be uniform in this case.

---

The rest of this answer covers later orders but produces the same result.

For the case $z = z_{(2)}$, we must consider both the minimal elements and the next-to-minimal elements of $S_X$ and $S_Y$. Let $x_{(2)}, y_{(2)}$ be the next-to-minimal elements of $S_X$ and $S_Y$ respectively. There are three possible cases here:

1. $x_{(1)} + y_{(2)} = z_{(2)}$
2. $x_{(2)} + y_{(1)} = z_{(2)}$
3. $x_{(1)} + y_{(2)} = x_{(2)} + y_{(1)} = z_{(2)}$

Hence, for $z = z_{(2)}$ we get (for the 3 cases)

1. $p_{x_{(1)}} q_{y_{(2)}} = \frac{1}{n}$
2. $p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}$
3. $p_{x_{(1)}} q_{y_{(2)}} + p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}$

Let us focus on cases 1 and 2. Consider $z = z_{(3)}$. In these cases, we must have that

1. $x_{(2)} + y_{(1)} = z_{(3)}$
2. $x_{(1)} + y_{(2)} = z_{(3)}$

as we can exclude the other cases by the requirements that $x_{(i)} < x_{(j)}$ if $i < j$ and similarly for $y_{(i)}$. These conditions are identical to the $z = z_{(2)}$ case but with $p$ and $q$ reversed.

For $z = z_{(4)}$, we must have $x_{(2)} + y_{(2)} = z_{(4)}$. We therefore obtain

$$p_{x_{(2)}}q_{y_{(2)}} = \frac{1}{n}$$

In cases 1 and 2, we end up with the same set of equations:

$$ p_{x_{(i)}}q_{y_{(j)}} = \frac{1}{n} $$

for $i,j \in \{1, 2\}$. This gives us the following conditions:

$$ p_{x_{(1)}} = p_{x_{(2)}}, \;\;\; q_{y_{(i)}} = \frac{1}{n p_{x_{(1)}}}, \;\;\; i \in \{1, 2\}$$

Let us now suppose that $X$ and $Y$ are uniformly distributed on their supports, so that $p_x = \frac{1}{|S_X|}$ and $q_y = \frac{1}{|S_Y|}$. These conditions require that

$$ |S_X| |S_Y| = n $$

which means that uniformity depends on whether the cardinality of the supports both divide $n$. Hence, the probability distributions for $X$ and $Y$ aren't necessarily always uniform for cases 1 and 2.

Let us now consider case 3. In case 3, we have $x_{(2)} + y_{(2)} = z_{(3)}$ instead, with the same equation as the $z = z_{(4)}$ for cases 1 and 2. Grouping together the conditions, we have

$$ p_{x_{(1)}}q_{y_{(1)}} = \frac{1}{n}, \;\;\; p_{x_{(1)}} q_{y_{(2)}} + p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}, \;\;\; p_{x_{(2)}}q_{y_{(2)}} = \frac{1}{n} . $$

These have no real solutions. Therefore, the probability distributions cannot exist.